Sword finger Offer22. The penultimate node in the lin k ed list
OJ link: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
Title: enter a linked list and output the penultimate node in the linked list. In order to conform to the habit of most people, this question starts from 1, that is, the tail node of the linked list is the penultimate node.
For example, a linked list has six nodes. Starting from the beginning, their values are 1, 2, 3, 4, 5 and 6. The penultimate node of the linked list is a node with a value of 4.
Given a linked list:
1 - > 2 - > 3 - > 4 - > 5, and k = 2
Return to linked list 4 - > 5
code:
Idea: Let's go first p Pointer walk k Step; Then let p Pointer and head The pointer advances together When p When you come to the end, return head
// An highlighted block
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
struct ListNode* p = head;
while(k--){
p = p->next;
}
while(p){
p = p->next;
head = head->next;
}
return head;
}
Fast and slow pointer method: Construct fast and slow pointers, which are separated from each other K Then the fast pointer comes to the end, and the slow pointer is just counting down K Location of
// An highlighted block
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
if(head==NULL)return head;
struct ListNode* p=head;
struct ListNode* q=head;
for(int i=0;i<k;i++){
p=p->next;//Construct two pointers separated by K
}
while(p!=NULL){
p=p->next;//The pointer is coming to the end
q=q->next; // The slow pointer is exactly at the countdown K
}
return q;
}
165. Compare version number
OJ link: https://leetcode-cn.com/problems/compare-version-numbers/
Title: give you two version numbers, version 1 and version 2. Please compare them.
The version number consists of one or more revision numbers, and each revision number is connected by a '.'. Each revision number consists of multiple digits and may contain leading zeros. Each version number contains at least one character. The revision number is numbered from left to right, the subscript starts from 0, the leftmost revision number subscript is 0, the next revision number subscript is 1, and so on. For example, both 2.5.33 and 0.1 are valid version numbers.
When comparing version numbers, compare their revision numbers from left to right. When comparing revision numbers, you only need to compare integer values that ignore any leading zeros. That is, revision 1 and revision 001 are equal. If the revision number at a subscript is not specified in the version number, the revision number is regarded as 0. For example, version 1.0 is smaller than version 1.1 because they have the same revision number with subscript 0, while the revision numbers with subscript 1 are 0 and 1 respectively, 0 < 1.
The return rules are as follows:
If Version1 > version2 returns 1,
If Version1 < version2 returns - 1,
In addition, 0 is returned.
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: ignoring leading zeros, "01" and "001" both represent the same integer "1"
Example 2:
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify a revision number with subscript 2, which is regarded as "0"
Example 3:
Input: version1 = "0.1", version2 = "1.1"
Output: - 1
Explanation: the revision number with subscript 0 in version1 is "0", and the revision number with subscript 0 in version2 is "1". 0 < 1, so version1 < version2
Example 4:
Input: version1 = "1.0.1", version2 = "1"
Output: 1
Example 5:
Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: - 1
code:
Idea: Encounter'.'At the end of and string, compare the size of the next version; If the program does not return, it will return 0;
// An highlighted block
int compareVersion(char * version1, char * version2)
{
int len1 = strlen(version1);
int len2 = strlen(version2);
int i = 0;
int j = 0;
while (i < len1 || j < len2)
{
int num1 = 0;
int num2 = 0;
while (i < len1 && version1[i] != '.')
{
num1 = num1 * 10 + (version1[i++] - '0');
}
while (j < len2 && version2[j] != '.')
{
num2 = num2 * 10 + (version2[j++] - '0');
}
if (num1 < num2)
{
return -1;
} else if (num1 > num2)
{
return 1;
}
i++;
j++;
}
return 0;
}
Interview question 17.14. Minimum number of K
OJ link: https://leetcode-cn.com/problems/smallest-k-lcci/
Title: design an algorithm to find the minimum k number in the array. These k numbers can be returned in any order.
Example:
Input: arr = [1,3,5,7,2,4,6,8], k = 4
Output: [1,2,3,4]
code:
Basic idea: maximum heap maintenance arr Before array k For each of the remaining elements, if it is larger than the largest element in the heap, use this element Replace the largest element so that the smallest element is always in the heap k Elements
// An highlighted block
void SiftDown(int a[], int i, int n)
{
//In the maximum heap formed by data[0,n), execute the sink operation for the element with index i, that is, maintain the maximum heap
while( (2*i+1) < n )
{
//Node i is not a leaf node, that is, there are at least left children
//Find out the maximum value of i for children around
int j = 2*i+1;
if((2*i+2) < n && a[2*i+1] < a[2*i+2]) //Right child exists
j = 2*i + 2;
if(a[i] >= a[j]) //If the maximum value of the child node is greater than this node, exchange
break;
int t = a[i];
a[i] = a[j];
a[j] = t;
i = j;
}
}
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
if(k<=0)
{
*returnSize = 0;
return NULL;
}
//Copy the first k elements to the st array
int *sk = (int*)malloc(sizeof(int)*k);
for(int i=0; i<k; i++)
sk[i] = arr[i];
//Arrange the sk array elements according to the maximum heap, heapify
for(int i=k/2-1; i>=0; i--)
SiftDown(sk,i,k);
//Compare the largest element in the heap with the remaining elements one by one
for(int i=k; i<arrSize; i++)
{
if(sk[0] > arr[i])
{
sk[0] = arr[i]; //If it is greater than, the maximum heap is replaced, and the smallest k elements in the first i elements are saved in sk
SiftDown(sk,0,k);
}
}
//Return sk array
*returnSize = k;
return sk;
}
704. Binary search
OJ link: https://leetcode-cn.com/problems/binary-search/
Title: given an n-element ordered (ascending) integer array nums and a target value target, write a function to search the target in nums. If the target value exists, return the subscript, otherwise return - 1.
Example 1:
Input: num = [- 1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 appears in nums and the subscript is 4
Example 2:
Input: num = [- 1,0,3,5,9,12], target = 2
Output: - 1
Explanation: 2 does not exist in nums, so - 1 is returned
code:
Binary search is a textbook algorithm based on comparing the target value with the middle element of the array. If the target value is equal to the intermediate element, the target value is found. If the target value is small, continue to search on the left. If the target value is large, continue searching on the right.
// An highlighted block
int search(int* nums, int numsSize, int target)
{
int left = 0;
int right = numsSize;
while (left < right)
{
int index = left + (right - left) / 2;
if (nums[index] == target)
{
return index;
}
else if (nums[index] > target )
{
right = index;
}
else
{
left = index + 1;
}
}
return -1;
}
278. First wrong version
OJ link: https://leetcode-cn.com/problems/first-bad-version/
Title: you are a product manager and are leading a team to develop new products. Unfortunately, the latest version of your product has not passed the quality test. Since each version is developed based on the previous version, all versions after the wrong version are wrong.
Suppose you have n versions [1, 2,..., n], you want to find the first wrong version that causes errors in all subsequent versions.
You can call the bool isBadVersion(version) interface to determine whether the version number is wrong in the unit test. Implement a function to find the first wrong version. You should minimize the number of calls to the API.
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
Call isbadversion (3) - > false
Call isbadversion (5) - > true
Call isbadversion (4) - > true
So, 4 is the first wrong version.
Example 2:
Input: n = 1, bad = 1
Output: 1
code:
It is similar to the dichotomy thought in the above question
// An highlighted block
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
int firstBadVersion(int n)
{
int left = 1, right = n;
while (left < right) { // Cycle until the left and right end points of the interval are the same
int mid = left + (right - left) / 2; // Prevent overflow during calculation
if (isBadVersion(mid))
{
right = mid; // The answer is in the interval [left, mid]
}
else
{
left = mid + 1; // The answer is in the interval [mid+1, right]
}
}
// At this time, there is left == right, and the interval is reduced to a point, which is the answer
return left;
}
35. Search insertion position
OJ link: https://leetcode-cn.com/problems/search-insert-position/
Title: given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, returns the position where it will be inserted in order.
You must use an algorithm with a time complexity of O(log n).
Example 1:
Input: num = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: num = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: num = [1,3,5,6], target = 7
Output: 4
Example 4:
Input: num = [1,3,5,6], target = 0
Output: 0
Example 5:
Input: num = [1], target = 0
Output: 0
code:
Set the left subscript first left And right subscript right，Recalculate intermediate subscript mid -Every time according to nums[mid]and target Judge the size between. If it is equal, the subscript will be returned directly, nums[mid]< target be left Shift right, nums[mid] > target be right Shift left -End of search, return if there is no equal value left，This value is the insertion position
// An highlighted block
int searchInsert(int* nums, int numsSize, int target)
{
int left = 0, right = numsSize - 1, ans = numsSize;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (target <= nums[mid])
{
ans = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return ans;
}
Sword finger Offer 10- I. Fibonacci sequence
OJ link: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
Title: write a function, enter n, and find the nth term of Fibonacci sequence (i.e. F(N)). Fibonacci sequence is defined as follows:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), where n > 1
The Fibonacci sequence starts with 0 and 1, and the subsequent Fibonacci numbers are obtained by adding the previous two numbers.
The answer needs to take the module 1e9+7 (100000007). If the initial result is 100000008, please return 1.
Example 1:
Input: n = 2
Output: 1
Example 2:
Input: n = 5
Output: 5
code:
// A code block var foo = 'bar';
// An highlighted block
int fib(int n)
{
long *dp = (long *)malloc(101*sizeof(long));
dp[0] = 0;
dp[1] = 1;
for (int i=2;i<=n;i++)
{
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
return dp[n];
}
977. Square of ordered array
OJ link: https://leetcode-cn.com/problems/squares-of-a-sorted-array/
Title: give you an integer array nums sorted in non decreasing order, and return a new array composed of the square of each number. It is also required to sort in non decreasing order.
Example 1:
Input: num = [- 4, - 1,0,3,10]
Output: [0,1,9,16100]
Explanation: after squaring, the array becomes [16,1,0,9100]
After sorting, the array becomes [0,1,9,16100]
Example 2:
Input: num = [- 7, - 3,2,3,11]
Output: [4,9,9,49121]
code:
Double finger needling We can use two pointers to point to positions 00 and 00, respectively n-1n−1，Compare the numbers corresponding to two pointers each time and select the larger one in reverse order Put in the answer and move the pointer. This method does not need to deal with the case where a pointer moves to the boundary.
// An highlighted block
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int* ans = malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
for (int i = 0, j = numsSize - 1, pos = numsSize - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
} else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
189. Rotate array
OJ link: https://leetcode-cn.com/problems/rotate-array/
Title: given an array, move the elements in the array K positions to the right, where k is a non negative number.
Advanced:
Think of as many solutions as possible. There are at least three different ways to solve this problem.
Can you use the in-situ algorithm with spatial complexity O(1) to solve this problem?
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate one step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: num = [- 1, - 100,3,99], k = 2
Output: [3,99, - 1, - 100]
Explanation:
Rotate 1 step to the right: [99, - 1, - 100,3]
Rotate 2 steps to the right: [3,99, - 1, - 100]
code:
We can use additional arrays to put each element in the right place. use nn Represents the length of the array. We traverse the original array and Subscript is ii Put the element of into the new array with the subscript (i+k)\bmod n(i+k)modn Finally, copy the new array to the original array.
// An highlighted block
void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize];
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];
}
}
283. Move zero
OJ link: https://leetcode-cn.com/problems/move-zeroes/
Title: given an array num, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
code:
Double finger acupuncture: Double pointers are used. The left pointer points to the tail of the currently processed sequence and the right pointer points to the head of the sequence to be processed. The right pointer keeps moving to the right, Each time the right pointer points to a non-zero number, the number corresponding to the left and right pointers will be exchanged, and the left pointer will move to the right at the same time. Noting the following nature: **The left pointer is a non-zero number** **It is zero from the left of the right pointer to the left pointer** Therefore, each exchange is to exchange the zero of the left pointer with the non-zero number of the right pointer, and the relative order of the non-zero numbers does not change.
// An highlighted block
void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void moveZeroes(int *nums, int numsSize) {
int left = 0, right = 0;
while (right < numsSize) {
if (nums[right]) {
swap(nums + left, nums + right);
left++;
}
right++;
}
}
The following is a common method, which is easier to understand
// An highlighted block
void moveZeroes(int *nums, int numsSize)
{
int i=0,place=0;
while(i<numsSize)
{
if(nums[i]!=0)
nums[place++]=nums[i];
i++;
}
for(int i=place;i<numsSize;i++)
nums[i]=0;
}
1221. Split balanced string
OJ link: https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/
Title: in a balanced string, the number of 'L' and 'R' characters is the same. Give you a balanced string s, please divide it into as many balanced strings as possible.
Note: each split string must be a balanced string.
Returns the maximum number of balanced strings that can be split.
Example 1:
Input: s = "rlrrllrll"
Output: 4
Explanation: s can be divided into "RL", "RRLL", "RL" and "RL". Each substring contains the same number of 'L' and 'R'.
Example 2:
Input: s = "rlllrrrlr"
Output: 3
Explanation: s can be divided into "RL", "LLLRRR" and "LR". Each substring contains the same number of 'L' and 'R'.
Example 3:
Enter: s = "llrrrr"
Output: 1
Explanation: s can only keep the original "llrrrr"
Example 4:
Input: s = "rlrrllrll"
Output: 2
Explanation: s can be divided into "RL" and "rrrlllrll". Each substring contains the same number of 'L' and 'R'.
code:
Here are some inline snippets.
Use and understand s[i] == 'L' ? ++d : --d operation
// An highlighted block
int balancedStringSplit(char * s)
{
int ans = 0, d = 0;
for (int i = 0; s[i]; i++)
{
s[i] == 'L' ? ++d : --d;//If the position indicated by the pointer string is L, d increases, otherwise d decreases
if (d == 0)
{
++ans;
}
}
return ans;
}
1167. Sum of two numbers II - input ordered array
OJ link: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
Title: given an integer array numbers that has been arranged in non decreasing order, please find out that the sum of the two numbers in the array is equal to the target number target.
The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts counting from 1, so the answer array should meet 1 < = answer [0] < answer [1] < = numbers.length.
You can assume that each input only corresponds to a unique answer, and you can't reuse the same elements.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: the sum of 2 and 7 is equal to the target number 9. So index1 = 1, index2 = 2.
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
code:
Method 1: binary search Find two numbers in the array so that their sum is equal to the target value. First fix the first number, and then find the second number. The second number is equal to The difference between the target value minus the first number. Using the ordered nature of the array, the second number can be found by binary search method. In order to avoid repeated search, When looking for the second number, look only to the right of the first number.
// An highlighted block
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
for (int i = 0; i < numbersSize; ++i)
{
int low = i + 1, high = numbersSize - 1;
while (low <= high)
{
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i])
{
ret[0] = i + 1, ret[1] = mid + 1;
return ret;
}
else if (numbers[mid] > target - numbers[i])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
}
ret[0] = -1, ret[1] = -1;
return ret;
}
Method 2: double pointer Initially, the two pointers point to the position of the first element and the position of the last element respectively. Calculate the sum of two elements pointed to by two pointers at a time, and Target value comparison. If the sum of the two elements is equal to the target value, a unique solution is found. If the sum of the two elements is less than the target value, the left pointer is to the right Move one position. If the sum of the two elements is greater than the target value, the right pointer is moved one bit to the left. After moving the pointer, repeat until you find the answer.
// An highlighted block
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
int low = 0, high = numbersSize - 1;
while (low < high)
{
int sum = numbers[low] + numbers[high];
if (sum == target)
{
ret[0] = low + 1, ret[1] = high + 1;
return ret;
}
else if (sum < target)
{
++low;
}
else
{
--high;
}
}
ret[0] = -1, ret[1] = -1;
return ret;
}