Array_Leetcode - Hanni Rio’s Blog

704. Binary Search

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;       // create 2 pointers
        while(left <= right){                          // ⬇️⬇️ key point
            int mid = left + (right - left) / 2;      // (left + right) / 2 maybe out of range
            if(nums[mid] == target) return mid;       // find the target
            else if(nums[mid] < target) left = mid + 1;    // target in the right half array
            else right = mid - 1;                     // target in the left half array
        }
        return -1;                       // no target in the array
    }
};

35. Search Insert Position

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;           // create 2 pointers
        while(left <= right){
            int mid = left + (right - left) / 2;    // ‼️ commonly seen in binary search      
            if(nums[mid] == target) return mid;    // find the target
            else if(nums[mid] < target) left = mid + 1;
            else right = mid - 1; 
        }
        return left;                             // no target in the array thus return left index
    }
};

34. Find First and Last Position of Element in Sorted Array

1️⃣最容易想到的方法，但可能有一些时间复杂度错误，因为是O(log N + K)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;           // create 2 pointers
        while(left <= right){
            int mid = left + (right - left) / 2;       // find the area of the target might exist
            if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else {                              // case when target in the area
                while(nums[left] < target) left ++;          // move the pointer to the right place
                while(nums[right] > target) right --;       
                return {left, right};
            }
        }
        return {-1, -1};                      // no target in the array 
    }
};

2️⃣用lower_bound然后类型转换

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto left = lower_bound(nums.begin(), nums.end(), target);    // nums[left] >= target
        auto right = lower_bound(nums.begin(), nums.end(), target + 1);  // nums[right] >= target + 1
        if(left != nums.end() && *left == target){
            return {static_cast<int>(left - nums.begin()), static_cast<int>(right - nums.begin() - 1)};
            // static_cast<int> 是类型转换符， 将迭代器转换为int型
            // conversion operator, convert iterator to integer type
        }
        else return {-1, -1};
    }
};

3️⃣手搓lower_bound:

class Solution {
public:
    int lower_bound(vector<int>& nums, int target){
        int left = 0, right = nums.size() - 1;
        while(left <= right){    // keep moving the pointers until left points the lower_bound
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = lower_bound(nums, target);
        int r = lower_bound(nums, target + 1) - 1;       // r points the upper_bound
        if(l < nums.size() && nums[l] == target) return {l, r};   // check whether target exists
        else return {-1, -1};
    }
};

69. Sqrt(x)

刚拿到题还有点棘手说实话....……一直爆超时，画个图思路清晰多了

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return x;      // specail case
        int left = 1, right = x;
        while(left <= right){     // binary search
            int mid = left + (right - left) / 2;    // avoid overflow
            if(mid <= x / mid && (mid + 1) > x / (mid + 1)) return mid;   // hit the range
            else if(x / mid < mid) right = mid - 1;
            else left = mid + 1;
        }
        return -1;         // impossible case;
    }
};

补充：下面是一个二分答案的板子，突然想起了编程有关数论的题目了.....顺便复习一下好了: 想法是一致的，不过设置了一个精度范围

#include<bits/stdc++.h>
using namespace std;
double sq(double x){          //二分答案
    double left = 0;
    double right = x;
    double eps = 1e-10;       //设置误差，表示10的-10次方
    while(left + eps < right){
        double mid = left + (right - left) / 2;
        if(mid * mid < x) left = mid;    // 浮点数的二分有点不同
        else right = mid;
    }
    return left;
}

int main(){
    double x = 5.0;
    cout << sq(x) << endl;
    return 0;
}
// sqrt(2) ≈ 1.41421

367. Valid Perfect Square

class Solution {
public:
    bool isPerfectSquare(int num) {
        long left = 1, right = num;         // binary search
        while(left <= right){
            long mid = left + (right - left) / 2;
            long q = mid * mid;
            if(q == num) return true;
            else if(q > num) right = mid - 1;
            else left = mid + 1;
        }
        return false;                    // impossible case
    }
};

27. Remove Element

Solution 1 : # Tow pointers && # Brute force

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {     // 2 loops Brute force
        int size = nums.size();
        for(int i = 0; i < size; i++){             // pointer i is to find the val in the array
            if(nums[i] == val){
                for(int j = i + 1; j < size; j++){    // pointer j is to move the remaining array forward
                    nums[j - 1] = nums[j];
                }
                i --;                               // put i into the right location
                size --;                            // remove the val in the array thus size --
            }
        }
        return size;
    }
};

Solution 2 : # Slow & fast pointers

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++){    // fast pointer is to traverse the array
            if(nums[fast] != val){                        
                nums[slow++] = nums[fast];               // slow pointer is to renew the array
            }
        }
        return slow;
    }
};

Feedback : 😠我怎么第三遍刷这道题的时候想不到这个快慢指针呢......Damn🤬

26. Remove Duplicates from Sorted Array

Solution 1 : # Fast & slow pointers, 注意快指针的起始位置

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int slow = 0;                              
        for(int fast = 1; fast < n; fast++){      // fast pointer is always in front of slow pointer
            if(nums[fast] != nums[slow]) nums[++slow] = nums[fast];   // if not the same, slow pointer moves
        }
        slow++;               // resize the nums
        return slow;
    }
};

Solution 2 : # Unique

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto q = unique(nums.begin(), nums.end());
        nums.erase(q, nums.end());
        return nums.size();
    }
};

283. Move Zeroes

Solution 1 : # Tow pointers

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int p1 = 0;                     // p1 points the location for exchanging the non-zero element
        for(int p2 = 0; p2 < n; p2++){      // p2 is to find the non-zero element   
            if(nums[p2] != 0){
                swap(nums[p1], nums[p2]);
                p1++;                   // move p1 afterward if changed
            }
        }
    }
};

Solution 2 : # Brute force

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for(int i = 0; i < n; i++){             // move all non-zero element forward in relative order
            if(nums[i] != 0) nums[j++] = nums[i];
        }
        for(j; j < n; j++) nums[j] = 0;       // repalce the left elements with 0
    } 
};

977. Squares of a Sorted Array

Solution 1 : # Brute force || 直接根据题意的意思暴力一下就可以了，但是时间复杂度是O(log N)级别的

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) nums[i] *= nums[i];
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Solution 2 : # Tow pointers || 绝对值的大小从两端不断向中间递减，根据这个规律优化时间复杂度

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;      // tow pointers
        vector<int> result(n, -1);
        while(left <= right){
            int l = nums[left] * nums[left];
            int r = nums[right] * nums[right];
            int k;
            if(l >= r){
                k = l;
                left++;
            }
            else{
                k = r;
                right--;
            }
            result[--n] = k;      // assign values to the elements from the end to the beginning
        }                         // in this way, we don't have to reverse the array
        return result;
    }
};

209. Minimum Size Subarray Sum

Solution : # Sliding window

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int start = 0;     // the start of the sliding window
        int result = INT_MAX;
        int subL = 0;      // length of the subarray
        for(int end = 0; end < nums.size(); end++){
            sum += nums[end];
            while(sum >= target){       // when it meets the requirement, move the sliding window
                subL = end - start + 1;    // the length of current subarray
                result = min(result, subL);   // refresh the result
                sum -= nums[start++];       // move the start of the sliding window
            }
        }
        return result == INT_MAX ? 0 : result;     // if the result is changed, then the subarray exists
    }
};

904. Fruit Into Baskets

Solution : # Sliding window

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> basket;
        int left = 0, right = 0, ans = 0;
        while(right < fruits.size()){
            basket[fruits[right]]++;     // put the fruit into the basket
            while(basket.size() > 2){     // if there are over 2 kinds of fruits in the basket
                basket[fruits[left]]--;     
                if(basket[fruits[left]] == 0){  
                    basket.erase(fruits[left]);  // put the left kind of fruits is out of basket
                }
                left++;
            }
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

下面是一个暴力的代码，但是O(N^2)的时间复杂度会超时

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int ans = 0;
        unordered_map<int, int> count;
        for(int left = 0; left < fruits.size(); left++){
            count.clear();
            for(int right = left; right < fruits.size(); right++){
                count[fruits[right]]++;
                if(count.size() > 2) break;      //超出两种水果就break
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};
// 70 / 91 testcases passed

59. Spiral Matrix II

Solution: # Simulation

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));  // n*n matrix
        int loop = n / 2;                               
        int sx = 0, sy = 0;    // starting location when each loops begain
        int mid = n / 2;      // when n is odd, we need to fill the mid location in the matrix
        int i , j;            // to record current positon when looping
        int offset = 1;       // when each loop ends, offset + 1
        int count = 1;         // the number to be fiiled in the matrix
        while(loop--){
            i = sx, j = sy;
            for(; j < n - offset; j++) ans[i][j] = count++;     // fill the upmost line
            for(; i < n - offset; i++) ans[i][j] = count++;    // fill the rightmost line
            for(; j > sy; j--) ans[i][j] = count++;            // fill the downmost line
            for(; i > sx; i--) ans[i][j] = count++;            // fill the leftmost line
            sx++;         // when each loop ends, change the starting location & offset
            sy++;
            offset++;
        }
        if(n % 2) ans[mid][mid] = count;    // if n is odd, fill the center location
        return ans;
    }
};

54. Spiral Matrix

Solution: # Simulation

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int m = matrix.size();      // line
        int n = matrix[0].size();   // column
        if(m == 0 || n == 0) return ans;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while(left <= right && top <= bottom){
            for(int j = left; j <= right; j++) ans.push_back(matrix[top][j]);
            for(int i = top + 1; i <= bottom; i++) ans.push_back(matrix[i][right]);
            if(top < bottom && left < right){
                for(int j = right - 1; j > left; j--) ans.push_back(matrix[bottom][j]);
                for(int i = bottom; i > top; i--) ans.push_back(matrix[i][left]);
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        return ans;

    }
};