Guide to series of articles
Open source project
All articles in this series will be included in GitHub for unified collection and management. Welcome ISSUE and Star.
GitHub portal: Kiner algorithm
69. Square root of X
Problem solving ideas
We can use dichotomy to solve this problem. Because we know: parseInt (x / 2) ^ 2 < = (√ x)^2, we can know that the range of the square root of X we want to find is within the range of 0~x/2. We only need to set two pointers and calculate mid by taking the middle value through the head and tail pointers, and then compare mid^2 with X.
Code demonstration
/*
* @lc app=leetcode.cn id=69 lang=typescript
*
* [69] x Square root of
*
* https://leetcode-cn.com/problems/sqrtx/description/
*
* algorithms
* Easy (39.21%)
* Likes: 688
* Dislikes: 0
* Total Accepted: 319.1K
* Total Submissions: 812.5K
* Testcase Example: '4'
*
* Implement the int sqrt(int x) function.
*
* Calculates and returns the square root of X, where x is a nonnegative integer.
*
* Since the return type is an integer, only the integer part of the result will be retained, and the decimal part will be rounded off.
*
* Example 1:
*
* Input: 4
* Output: 2
*
*
* Example 2:
*
* Input: 8
* Output: 2
* Note: the square root of 8 is 2.82842,
* Since the return type is an integer, the decimal part will be rounded off.
*
*
*/
// @lc code=start
function mySqrt(x: number): number {
// Special judgment: when x is 0, the square root is 0, and when x is 1, the square root is 1
if(x <= 1) {
return x;
}
// Left cursor is 0
let left = 0;
// The right cursor is parseInt(x/2)
// Why is the right cursor not x but parseInt(x/2)
// Because: parseInt (x / 2) ^ 2 < = (√ x)^2
// Therefore, we can know that the maximum of √ x is x/2, that is, just parseInt(x/2) = √ X
let right = x >> 1;
// Enter the cycle when the left and right pointers do not meet
while(left <= right) {
// Calculate the intermediate value according to the left and right cursors
let mid = (left + right) >> 1;
// Calculate parseInt(x/2)^2
let pow = mid * mid;
// If pow is exactly equal to x, then mid is the square root we are looking for
if(pow === x) return mid;
// If pow is smaller than the target value, adjust the left pointer to mid+1
else if(pow < x) left = mid + 1;
// Adjust right pointer
else right = mid - 1;
}
// Since the title asks us to discard the decimal part, we want to ask for an integer closest to the square root of x
// So when you jump out of the loop, because the left and right pointers meet, the value they point to is the integer closest to the answer
return right;
};
// @lc code=end
The above is a more conventional binary decomposition method, and the following is a more coquettish binary writing method, which can run successfully through all cases. Do you know the principle of this writing method?
/*
* @lc app=leetcode.cn id=69 lang=typescript
*
* [69] x Square root of
*
* https://leetcode-cn.com/problems/sqrtx/description/
*
* algorithms
* Easy (39.21%)
* Likes: 688
* Dislikes: 0
* Total Accepted: 319.1K
* Total Submissions: 812.5K
* Testcase Example: '4'
*
* Implement the int sqrt(int x) function.
*
* Calculates and returns the square root of X, where x is a nonnegative integer.
*
* Since the return type is an integer, only the integer part of the result will be retained, and the decimal part will be rounded off.
*
* Example 1:
*
* Input: 4
* Output: 2
*
*
* Example 2:
*
* Input: 8
* Output: 2
* Note: the square root of 8 is 2.82842,
* Since the return type is an integer, the decimal part will be rounded off.
*
*
*/
// @lc code=start
function mySqrt(x: number): number {
let head = 0, tail = x, mid;
tail+=1;
for(let i=0;i<32;i++) {
mid = head + ((tail - head) >> 1);
if(mid*mid <= x) head = mid;
else tail = mid;
}
return Math.abs(Math.floor(head));
};
// @lc code=end
In fact, the above solution also makes use of the problem. We don't need to find the absolute accurate square root solution, but the integer closest to the square root of the root. We know that using the dichotomy, the interval will be divided into the original 1 / 2 each time. Then when we run it for 32 times, we have reduced the interval to 1 / (2 ^ 32), It is already a fairly small interval. We can think that the value of the midpoint in this interval is the nearest integer of the square root of x. then, how do we determine that the number of fixed cycles is 32? Because our integer range is - 2 ^ 32 ~ 2 ^ 32, we can cycle 32 times. Well, isn't this solution coquettish.
35. Search insertion position
Problem solving ideas
This problem needs as like as two peas 0-1 models we have talked about before. In addition to the meaning of the problem, we need to find the location where the value is inserted when the target value is not in our search interval, and the other operations are exactly the same as the 0-1 models. Two.
Code demonstration
/*
* @lc app=leetcode.cn id=35 lang=typescript
*
* [35] Search insertion location
*
* https://leetcode-cn.com/problems/search-insert-position/description/
*
* algorithms
* Easy (47.00%)
* Likes: 930
* Dislikes: 0
* Total Accepted: 390.1K
* Total Submissions: 829.4K
* Testcase Example: '[1,3,5,6]\n5'
*
* 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, return the position where it will be inserted in order.
*
* You can assume that there are no duplicate elements in the array.
*
* Example 1:
*
* Input: [1,3,5,6], 5
* Output: 2
*
*
* Example 2:
*
* Input: [1,3,5,6], 2
* Output: 1
*
*
* Example 3:
*
* Input: [1,3,5,6], 7
* Output: 4
*
*
* Example 4:
*
* Input: [1,3,5,6], 0
* Output: 0
*
*
*/
// @lc code=start
function searchInsert(nums: number[], target: number): number {
let min = 0, max = nums.length - 1;
while(max - min > 3) {
let mid = (min + max) >> 1;
if(nums[mid]<target) min = mid + 1;
else max = mid;
}
for(let i=min;i<=max;i++) {
if(nums[i] >= target) return i;
}
// Note that when we go through the above binary search process, we find that the target value is not what we are looking for at all
// When it is within the range, the insertion position of the value should be returned according to the meaning of the question. We should let it be inserted into the last element
// Next in line
return nums.length;
};
// @lc code=end
1. Sum of two numbers
Problem solving ideas
We have previously realized this problem by using space for time with the help of hash table. Have you ever thought that we can use binary search to solve this problem? First of all, because our original array is out of order, we need to sort the array to solve it by dichotomy. Here, we use a new programming technique, which is to use an additional subscript array. We directly sort the subscripts according to the value of the original array from small to large, which will affect our original array. Then, we just need to cycle through the subscript array, and then get the corresponding value according to the subscript (at this time, the value we get each time intersects the previous value must be incremented). We only need to find out whether the target value we want to recruit exists in the array after the current position through bisection. If so, it will be returned.
Code demonstration
/*
* @lc app=leetcode.cn id=1 lang=typescript
*
* [1] Sum of two numbers
*
* https://leetcode-cn.com/problems/two-sum/description/
*
* algorithms
* Easy (51.07%)
* Likes: 11273
* Dislikes: 0
* Total Accepted: 2.1M
* Total Submissions: 4.1M
* Testcase Example: '[2,7,11,15]\n9'
*
* Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.
*
* You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.
*
* You can return answers in any order.
*
*
*
* Example 1:
*
*
* Input: num = [2,7,11,15], target = 9
* Output: [0,1]
* Explanation: because num [0] + num [1] = = 9, return [0, 1].
*
*
* Example 2:
*
*
* Input: num = [3,2,4], target = 6
* Output: [1,2]
*
*
* Example 3:
*
*
* Input: num = [3,3], target = 6
* Output: [0,1]
*
*
*
*
* Tips:
*
*
* 2
* -10^9
* -10^9
* There will only be one valid answer
*
*
* Advanced: can you think of an algorithm with less time complexity than O(n^2)?
*
*/
// @lc code=start
function findX(arr:number[], idxs: number[], head: number, x: number): number {
let tail = idxs.length - 1, mid;
while(head <= tail) {
mid = (head + tail) >> 1;
if(arr[idxs[mid]]===x) return mid;
else if(arr[idxs[mid]]>x) tail = mid - 1;
else head = mid + 1;
}
return -1;
}
function twoSum(nums: number[], target: number): number[] {
// Define a subscript array
const idxs: number[] = [];
for(let i=0;i<nums.length;i++) idxs[i] = i;
// And sort the subscript array from small to large according to the original array value
idxs.sort((a, b) => nums[a] - nums[b]);
// Circular subscript array
for(let i=0;i<idxs.length;i++) {
// The value of the original array is obtained according to the ordered subscript array, so we take it out every time
// The value of must be increasing
const val = nums[idxs[i]];
// Find target Val in the following ordered array through binary search
const idx1 = findX(nums, idxs, i + 1, target - val);
// If the returned index is not - 1, the answer is found and returned directly
if(idx1!==-1) {
return [idxs[i], idxs[idx1]];
}
}
return [];
};
// @lc code=end
34. Find the first and last position of an element in a sorted array
Problem solving ideas
It's very simple to find the first position in this problem. We can easily do it by using the 0-1 model of binary search. I won't repeat it here. How do we find the last position? In fact, we can change our way of thinking. Why should we find the last position of an element? Can't we find the position of the first element larger than this element? As long as we find the first position larger than the target element, we only need to subtract one to find the last position of the target element. Therefore, to find the last position of the element, you only need to use the 0-1 model of binary search to find the first position larger than the target element, and then subtract one
Code demonstration
/*
* @lc app=leetcode.cn id=34 lang=typescript
*
* [34] Finds the first and last positions of an element in a sorted array
*
* https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
*
* algorithms
* Medium (42.41%)
* Likes: 1041
* Dislikes: 0
* Total Accepted: 263.3K
* Total Submissions: 619.8K
* Testcase Example: '[5,7,7,8,8,10]\n8'
*
* Given an integer array nums arranged in ascending order and a target value target. Find the start and end positions of the given target value in the array.
*
* If the target value target does not exist in the array, return [- 1, - 1].
*
* Advanced:
*
*
* Can you design and implement an algorithm with time complexity of O(log n) to solve this problem?
*
*
*
*
* Example 1:
*
*
* Input: num = [5,7,7,8,8,10], target = 8
* Output: [3,4]
*
* Example 2:
*
*
* Input: num = [5,7,7,8,8,10], target = 6
* Output: [- 1, - 1]
*
* Example 3:
*
*
* Input: num = [], target = 0
* Output: [- 1, - 1]
*
*
*
* Tips:
*
*
* 0
* -10^9
* nums Is a non decreasing group
* -10^9
*
*
*/
// @lc code=start
function binarySearch(nums: number[], target: number): number {
let min = 0, max = nums.length-1,mid;
while(max - min > 3) {
mid = (min + max) >> 1;
if(nums[mid] >= target) max = mid;
else min = mid + 1;
}
for(let i=min;i<=max;i++) {
if(nums[i]>=target) return i;
}
return nums.length;
}
function searchRange(nums: number[], target: number): number[] {
let res = [-1,-1];
// Firstly, the 0-1 model of dichotomy algorithm is used to find the first location
res[0] = binarySearch(nums, target);
// If the first position of the finally found element is equal to the next bit of the last bit of the array, or the value found from the original array according to the index is not equal to the target element
// If not found
if(res[0] === nums.length || nums[res[0]] !== target) {
return [-1,-1];
}
// If the first element is found, the position of the last element can be found by finding the position of the first element larger than this element, and then subtracting one
res[1] = binarySearch(nums, target+1) - 1;
return res;
};
// @lc code=end
1658. Minimum operand to reduce x to 0
Problem solving ideas
According to the meaning of the question, there is no negative number in our operand array. According to this condition, we can change the problem to add the sum sumL of some elements of the array from left to right and the sum sumR of some elements of the array from right to left, which is equal to our target number, that is, target = sumL(i) + sumR(j). So, our problem now is how to find the sumL and sumR. We have talked about the concept of prefix sum more than once to calculate the interval sum, that is, the element corresponding to the array subscript i corresponds to the sum of the elements from the array 0 to I. We can calculate the prefix sum of the left and right sides respectively. Since there is no negative number in the element group, the prefix and array must be monotonically increasing ordered arrays, so we use each prefix and number on the left to use the 0-1 model of binary search to find the number of target - sumL(i) in the prefix and array on the right. After finding it, We only need to accumulate the indexes of the left and right elements to get the minimum operand.
Code demonstration
/*
* @lc app=leetcode.cn id=1658 lang=typescript
*
* [1658] Minimum operand to reduce x to 0
*
* https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/description/
*
* algorithms
* Medium (28.04%)
* Likes: 63
* Dislikes: 0
* Total Accepted: 7K
* Total Submissions: 24.5K
* Testcase Example: '[1,1,4,2,3]\n5'
*
* Give you an integer array nums and an integer x. In each operation, you should remove the leftmost or rightmost element of array num, and then subtract the value of that element from x. Please note that
* Modify the array for subsequent operations.
*
* If x can be exactly reduced to 0, the minimum operand is returned; Otherwise, - 1 is returned.
*
*
*
* Example 1:
*
*
* Input: num = [1,1,4,2,3], x = 5
* Output: 2
* Explanation: the best solution is to remove the last two elements and reduce x to 0.
*
*
* Example 2:
*
*
* Input: nums = [5,6,7,8,9], x = 4
* Output: - 1
*
*
* Example 3:
*
*
* Input: num = [3,2,20,1,1,3], x = 10
* Output: 5
* Explanation: the best solution is to remove the last three elements and the first two elements (a total of 5 operations) and reduce x to 0.
*
*
*
*
* Tips:
*
*
* 1
* 1
* 1
*
*
*/
// @lc code=start
function binarySearch(arr: number[], x: number): number {
let min = 0,max = arr.length-1,mid;
while(max - min > 3) {
mid = (min + max) >> 1;
if(arr[mid]>=x) max = mid;
else min = mid + 1;
}
for(let i=min;i<=max;i++) {
if(arr[i] === x) return i;
}
return -1;
}
function minOperations(nums: number[], x: number): number {
// First find the element prefix sum from left to right and from right to left
let sumL: number[] = [], sumR: number[] = [];
sumL[0] = sumR[0] = 0;
for(let i=0;i<nums.length;i++) sumL[i+1] = sumL[i] + nums[i];
for(let i=nums.length-1;i>=0;--i) sumR[nums.length - i] = sumR[nums.length - i - 1] + nums[i];
let res = Number.MAX_SAFE_INTEGER;
// Loop the prefix and array from left to right, and take each number to the prefix and array from right to left to find the corresponding solution
for(let i=0;i<sumL.length;i++) {
// Take each prefix on the left and find the index of the target solution in the prefix and array from right to left
const j = binarySearch(sumR, x - sumL[i]);
// Handle the boundary conditions. If the target solution cannot be found or the two indexes are added, that is, the number of operands has exceeded the number of the original array, indicating that i and j overlap,
// Both cases are illegal, so skip them directly
if(j===-1 || i + j > nums.length) continue;
// If the above situation does not occur, it means that a group of solutions have been found. We compare the found solutions with the previous group and take the minimum value
res = Math.min(res, i+j);
}
// If the loop ends and res is still the initial value, it indicates that it is not found and returns - 1
if(res===Number.MAX_SAFE_INTEGER) res = -1;
return res;
};
// @lc code=end
81. Search rotation sort array II
Problem solving ideas
Code demonstration
/*
* @lc app=leetcode.cn id=81 lang=typescript
*
* [81] Search rotation sort array II
*
* https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/description/
*
* algorithms
* Medium (41.54%)
* Likes: 441
* Dislikes: 0
* Total Accepted: 107.7K
* Total Submissions: 258.9K
* Testcase Example: '[2,5,6,0,0,1,2]\n0'
*
* It is known that there is an integer array nums arranged in non descending order, and the values in the array do not have to be different from each other.
*
* Before passing to the function, Num rotates on a previously unknown subscript k (0), making the array [num [k], Num [K + 1],
* nums[n-1], nums[0], nums[1], ..., nums[k-1]](Subscripts count from 0). For example,
* [0,1,2,4,4,4,5,6,6,7] After rotation at subscript 5, it may become [4,5,6,6,7,0,1,2,4,4].
*
* Give you the rotated array num and an integer target. Please write a function to judge whether the given target value exists in the array. If this target value exists in nums
* target ，Returns true, otherwise false.
*
*
*
* Example 1:
*
*
* Input: num = [2,5,6,0,0,1,2], target = 0
* Output: true
*
*
* Example 2:
*
*
* Input: num = [2,5,6,0,0,1,2], target = 3
* Output: false
*
*
*
* Tips:
*
*
* 1
* -10^4
* The title data ensures that nums rotates on a subscript unknown in advance
* -10^4
*
*
*
*
* Advanced:
*
*
* This is an extension of the search rotation sorting array. The nums in this question may contain duplicate elements.
* Does this affect the time complexity of the program? What impact will it have and why?
*
*
*/
// @lc code=start
function search(nums: number[], target: number): boolean {
// If an element equal to target is found at both ends of the array, it will directly return true
if(nums[0] === target || nums[nums.length-1] === target) return true;
let l = 0, r = nums.length - 1, mid, head, tail;
// You need to exclude elements with the same ends
while(l < nums.length && nums[l] === nums[0]) ++l;
while(r >= 0 && nums[r] === nums[0]) --r;
head = l, tail = r;
// The following is a schematic diagram of the monotonicity of the array before rotation
// y-axis
// | /|
// | / |
// | / |
// | / |
// | /| |
// | / | |
// |/____|_______|________________________________ x-axis
// a b c
// The following is a schematic diagram of the monotonicity of the array after rotation
// y-axis
// | /|
// | / |
// | / |
// |/ |
// | | /|
// | | / |
// |_______|/____|_______________________________ x-axis
// b c b
// a'
// According to the monotonicity diagram of the array after on-line rotation, we need to divide the whole array into two parts
// First, we need to calculate the value num [mid] in the middle of the array to see whether the mid falls on the bc end or the cb end
// After determining that the mid falls behind that segment, because both bc and cb are monotonically increasing, you can directly use the binary search method to search
while(l <= r) {
mid = (l + r) >> 1;
// If the value pointed to by mid is just equal to target, return true to indicate that it has been found
if(nums[mid] === target) return true;
// If the value corresponding to the middle value is less than or equal to the value corresponding to the end of the array (excluding the array with the same elements at the beginning and end), it indicates our
// mid fell to the second half of the interval
if(nums[mid] <= nums[tail]) {
// If the target is before num [mid] and num [tail], it indicates that it is too small. Move the left pointer to mid+1
if(target <= nums[tail] && target > nums[mid]) l = mid + 1;
// Otherwise, the description is too large, move the right pointer to mid-1
else r = mid - 1;
} else {// Otherwise, our mid falls into the first half of the interval
// If the target is between num [head] and num [mid], it indicates that it is too large, and the right pointer moves to mid-1
if(target >= nums[head] && target < nums[mid]) r = mid - 1;
// Otherwise, the left pointer moves to mid+1
else l = mid + 1;
}
}
return false;
};
// @lc code=end