catalogue
1. Binary search (loop invariant principle)
Example 1: leetcode 704 binary search
Example 2: leetcode 34. Find the first and last positions of elements in the sorted array
Example 3: leetcode 69 Square root of x, using binary search
Example 1: leetcode 27. Remove element
Example 2: leetcode 26. Delete duplicates in the ordered array
Example 3: leetcode 977. Square of ordered array
Example 1: leetcode 209. Minimum length subarray
Example 2: leetcode 904. Fruit baskets
Knowledge points:
- An array is a collection of data of the same type stored in a continuous memory space.
- The array subscript starts from 0;
- The addresses of array memory space are continuous. When deleting or adding elements, the addresses of other elements should be moved.
- The elements of the array cannot be deleted, but can only be overwritten.
- The difference between vector and array: the underlying implementation of vector is array, and vector is a container, not an array.
Algorithm:
1. Binary search (loop invariant principle)
Key: handle the boundary according to the definition of search interval.
Preconditions for binary search: an ordered array and no duplicate elements in the array.
There are generally two types of interval definitions: left closed right open, left closed right closed.
Example 1: leetcode 704 binary search
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.
#include<iostream>
using namespace std;
#include<vector>
int search(vector<int>&nums, int target) {
int left = 0;
int right = nums.size() - 1;//Define the target in the [left,right] left closed right closed interval
while (left <= right) {
int middle = left + (right - left) / 2;//Prevent overflow, = = (right - left) / 2
if (nums[middle] < target) {
left = middle + 1;
}
else if (nums[middle] > target) {
right = middle - 1;
}
else {
return middle;
}
}
return -1;
}
int main() {
cout << "Please enter the number of elements of the array: ";
int n;
while (cin >> n) {
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
cout << "Please enter the target value (integer): " ;
int target;
cin >> target;
if (search(nums, target) == -1) {
cout << "There are no elements in the array equal to the target value." << endl;
}
else {
cout << "The subscripts of the elements in the array equal to the target value are: " ;
cout<<search(nums, target)<<endl;
}
}
system("pause");
return 0;
}Supplement: < < 1, shifting left by 1 bit is equivalent to multiplying by 2; > > 1. Shifting 1 bit to the right is equivalent to dividing by 2;
Example 2: leetcode 34. Find the first and last positions of elements in the sorted array
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].
Idea:
First position: the first position in the array equal to target
Last position: the last position in the array greater than the target element minus 1;
int search4(vector<int>&nums, int target,bool lf) {//bool lf is used to determine whether the calculation is a left pointer or a right pointer
int left = 0;
int right = nums.size() - 1;//Define the target in the [left,right) left closed right open interval
int result = nums.size();//For example, the array is [7,7,8,8], and the target value is 8. In fact, it cannot enter the if statement, that is, the result value will not change, so it is set as the array length at the beginning, and the subscript value obtained at the end is reduced by 1
while (left <= right) {
int middle = left + (right - left) / 2;//Prevent overflow, = = (right - left) / 2
if ((nums[middle] >= target && lf) || nums[middle]>target) {
right = middle - 1; //target is in the right interval, [middle+1, right)
result = middle;
}
else{
left = middle + 1;//target is in the left interval, [left,middle)
}
}
return result;
}
vector<int> serchFirstAndLast(vector<int>&nums, int target) {
int leftptr = search4(nums, target, true);
int rightptr = search4(nums, target, false)-1;
if (leftptr <= rightptr && rightptr <nums.size() && nums[leftptr]==target && nums[rightptr] == target) {
return vector<int> { leftptr, rightptr };
}
return vector<int> { -1, -1 };
}Example 3: leetcode 69 Square root of x, using binary search
int mySqrt(int x) {
int l = 1, r = x, result = x;
while (l <= r) {
int mid = l + (r - l) / 2;
if ( mid*mid <= x) {
l = mid + 1;
result = mid;
}
else {
r = mid - 1;
}
}
return result;
}2. Double pointer
Double finger needle method: complete the work of two for loops under one for loop through a fast pointer and a slow pointer.
Example 1: leetcode 27. Remove element
Give you an array nums And a value Val, you need to remove all values in place equal to val And returns the new length of the array after removal.
Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.
The order of elements can be changed. You don't need to consider the elements in the array beyond the new length.
#include<iostream>
using namespace std;
#include<vector>
int removeElement2(vector<int>& nums, int val) {
int slow = 0;//Slow pointer
for (int i = 0; i < nums.size(); i++) {
//If it is equal to the target value, the fast pointer moves forward. If it is not equal, the slow pointer and the fast pointer move at the same time
if (nums[i] != val) {
nums[slow++] = nums[i];
}
}
return slow;
}
int main() {
cout << "Please enter the number of elements of the array: ";
int n;
while (cin >> n) {
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
cout << "Please enter the target value (integer): ";
int target;
cin >> target;
//Removing Elements
int len = removeElement2(nums, target);
cout << "The array length after removing elements is:"<< len <<endl;
for (int i = 0; i < len; i++) {
cout<< nums[i] <<" ";
}
system("pause");
return 0;
}Example 2: leetcode 26. Delete duplicates in the ordered array
The core code is as follows:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int slow = 0;
for (int i = 0; i < n; i++) {
if (nums[slow] != nums[i]) {
nums[++slow] = nums[i];
}
}
return slow + 1;
}Example 3: leetcode 977. Square of ordered array
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.
vector<int> sortedSquares(vector<int>& nums) {
int first = 0, last = nums.size() - 1;
vector<int> v(last+1,0);
for(int i=last;i>=0;i--) {
if (nums[first] * nums[first] > nums[last] * nums[last]) {
v[i] = nums[first] * nums[first];
first++;
}
else {
v[i] = nums[last] * nums[last];
last--;
}
}
return v;
}3. Sliding window
Constantly adjust the start position and end position of the subsequence, so as to get the desired results.
Sliding window is mainly used on arrays and strings.
Example 1: leetcode 209. Minimum length subarray
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int first = 0;//Start position of sliding window
int subLength = 0;//Subarray length
int sum = 0;//Sum of subarrays
int result = INT32_MAX;//The default is the maximum value at the beginning
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= target) {
//When the sum of subarrays is greater than or equal to the target value, the starting position of the sliding window needs to move forward
subLength = i - first + 1;
result = result < subLength ? result : subLength;
sum -= nums[first];
first++; //Continuously change the starting position of the subsequence
}
}
// If the result is not assigned, it returns 0, indicating that there are no qualified subsequences
return result==INT32_MAX ? 0 : result;
}Example 2: leetcode 904. Fruit baskets
First of all, we have to find out the requirements of this problem: find the longest subarray with only two types, and return its length
int totalFruit(vector<int>& fruits) {
int first = 0, second = 0;
int len = 0;
int subLen = 0;
int temp = 0;//You need a variable to record which subscript should start when the third element appears.
for (int i = 0; i < fruits.size(); i++) {
if (fruits[first] != fruits[i] && fruits[second] != fruits[i])
{
if (fruits[first] != fruits[second]) {
first = temp;
}
second = i;
}
if (fruits[temp] != fruits[i]) {
temp = i;
}
subLen = i - first + 1;
len = len < subLen ? subLen : len;
}
return len;
}