【代码随想录】二刷-数组

数组

• 《代码随想录》

二分查找

704. 二分查找

方法1

• 注意:
  • 边界控制。
  • 前提是有序数组。
  • 循环控制
• 解释: 这里使用我最好理解的一种方式。
  • 使用mid控制下标访问，nums[mid]大于target，+1更新左边界，反之，-1更新右边界。相等即找到目标数。
  • while循环条件left<=right,left=right仍有需要判断的数。即目标数的索引在数组的
    边界。
  • 防止left+right过大会溢出，所以写成(right-left)/2，等同于(right+left)/2

// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
    int search(vector& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        
        while(left <= right){
            int mid = left+((right-left)/2);
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法2

• 与上一种方法的区别在于区间的控制不同，方法1为[left,right]，方法2为[left,right)。

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size();

        while(left < right){// 等于时无意义
            int mid = left + (right-left)/2;
            if(nums[mid] > target){
                right = mid;
            }else if(nums[mid] < target){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 感悟:
  • 算是比较基础的算法了，前两天给群友回答问题的时候，也重新复习了一下，这次顺利AC。
  • 这两天可能也是没啥状态，被KMP困住了好久，希望数组可以给我找回点自信。
  • 不过这题上来我写了个for循环，md，还是错了下。

---

35. 搜索插入位置

• 同上一题，不过需要多想一下插入的位置。
  • 分析每种情况:
    • 目标值在数组所有元素之前
    • 目标等于数组中的某一个元素
    • 目标值插入到数组中
    • 目标值在所有元素之后

// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        while(left <= right){
            int mid = left + ((right-left)/2);
            if(nums[mid] > target){
                right = mid-1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;// 等于数组中某个存在元素
            }
        }
        return right+1;// 其它三种情况
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

34. 在排序数组中查找元素的第一个和最后一个位置

• 分析每一种情况
  • target在数组的范围内，但是不存在于数组中。
  • target在数组范围内，存在于数组中。
  • target不在数组范围内。同样也不存在与数组中。
• 在最基础的二分查找上减少了判断，不断收缩边界。结合示例带入进行运算下。

class Solution {
public:
/*
nums:    5 7 7 8 8 10
index:   0 1 2 3 4 5
*/
    int getLeftBorder(vector& nums,int target){
        int left = 0;
        int right = nums.size()-1;
        int ret = -2;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] >= target){
                right = mid - 1;
                ret = right;
            }else{
                left = mid + 1;
            }
        }
        return ret;
    }
    int getRightBorder(vector& nums,int target){
         int left = 0;
        int right = nums.size()-1;
        int ret = -2;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
                ret = left;
            }
        }
        return ret;       
    }
    vector searchRange(vector& nums, int target) {
        int leftBorder = getLeftBorder(nums,target);
        int rightBorder = getRightBorder(nums,target);
        if(leftBorder == -2 || rightBorder == -2){// 情况三
            return {-1,-1};
        }
        if(rightBorder - leftBorder > 1){
            return {leftBorder+1,rightBorder-1};// 情况二
        }
        return {-1,-1};// 情况一
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

---

69. x 的平方根

// 时间复杂度 O(logn)
// 空间复杂度 o(1)
class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ret = -1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if((long long)mid * mid <= x){
                ret = mid;
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

367. 有效的完全平方数

• 二分法的使用，注意根据题意进行判断。
• 个人感觉比上面那两道题要好理解

// 时间复杂度 O(logn)
// 空间复杂度 O(1)
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        while(left <= right){
            int mid = left + (right-left)/2;
            if((long long)mid*mid < num){
                left = mid + 1;
            }else if((long long)mid* mid > num){
                right = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

双指针

27. 移除元素

• 暴力

// 时间复杂度O(n²)
// 空间复杂度O(1)
class Solution {
public:
    int removeElement(vector& nums, int val) {
        /*3 3 2 2 3 3
          3 3 2 3 3
        */
        int n = nums.size();
        for(int i = 0 ; i < n ;i++){
            if(nums[i] == val){
                for(int j = i+1;j < n;j++){
                    nums[j-1] = nums[j];
                }
                i--;// 后面整体前移，i也前移
                n--;
            }      
        }
        return n;
    }
};   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 双指针
  • 快指针负责搜寻目标值，当找到目标，慢指针停住，将后面的非目标值换上来。

// 时间复杂度O(n)  
// 空间复杂度O(1)
class Solution {
public:
    int removeElement(vector& nums, int val) {
        int n =  nums.size();
        int slowIndex = 0;
        for(int fastIndex = 0;fastIndex < n;fastIndex++){
            if(nums[fastIndex] != val){// 找到目标值了，慢指针就不动了
                nums[slowIndex++] = nums[fastIndex];// 把后面不是目标值的替换上来
            }
        }
        return slowIndex;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

26. 删除有序数组中的重复项

• 双指针，快指针带路，将挑选出来的数，传递给慢指针。完成去重效果。

// 时间复杂度 O(n)
// 空间复杂度 O(1)
class Solution {
public:
    int removeDuplicates(vector& nums) {
        int slow = 1;
        int fast = 1;
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        while( fast < n){
            if(nums[fast] != nums[fast-1]){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        // 从题目中可以看出，根据新的长度来遍历数组进行判断
        return slow;
        
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

283.移动零

• 双指针

// 时间复杂度O(N)
// 空间复杂度O(1)
class Solution {
public:
    void moveZeroes(vector& nums) {
        // 在不赋值数组的情况下原地对数组进行操作
        int n = nums.size();
        if(n == 0)return ;
        int fast = 0;
        int slow =0;
        while(fast < n){
            if(nums[fast] != 0){
                swap(nums[slow++],nums[fast]);
            }
            fast++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

844.比较含退格的字符串

• 双指针: 遇到‘#’t将，#后面的数与#前面的交换，最后根据slow指针截取长度。

// 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
    string build(string s){
        int n = s.size();
        int slow = 0;
        for(int fast = 0;fast < n;fast++){
            if(s[fast] != '#'){
                s[slow] = s[fast];
                slow++;
            }else if(slow > 0){
                slow--;
            }
        }
        return s.substr(0,slow);
    }
    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 用栈很简单,主要还是掌握双指针。

// 时间复杂度 O(m+n) 即O(n)
// 空间复杂度 O(m+n)
class Solution {
public:
    string build(string s){
        stackst;
        for(char c:s){
            if(c != '#'){// 刚开始这里多了个条件，st.empty()然后把我坑了。
                st.push(c);
            }else if(c == '#' && !st.empty()){
                st.pop();
            }
        }
        string ret = "";
        while(!st.empty()){
            ret += st.top();
            st.pop();
        }
        return ret;
    }
    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

977.有序数组的平方

• 双指针: 默认是从升序，但是负数平方后不一定比右边大的整数平方小，i指针从前遍历，j指针从后遍历，取出较大的放入结果集，并移动指针。

// 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
    vector sortedSquares(vector& nums) {
        int i = 0;
        int j = nums.size() - 1;
        int k = nums.size() - 1;
        vectorret(nums.size());
        while(i <= j){
            if(nums[j]*nums[j] > nums[i]*nums[i]){
                ret[k--] = nums[j]*nums[j];
                j--;
            }else{
                ret[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 暴力

// 时间复杂度 O(n+nlogn)
// 空间复杂度 O(n)
class Solution {
public:
    vector sortedSquares(vector& nums) {
        int n = nums.size();
        for(int i = 0; i < n;i++){
            nums[i] *= nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

滑动窗口

• 所谓滑动窗口，就是不断的调节子序列和起始位置和终止位置，从而得出我们想要的结果。
• 滑动窗口三部曲
  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

209. 长度最小的子数组

• 本题中:
  • 窗口: 为满足和 >= s的长度最小的连续子数组
  • 窗口的起始位置如何移动: 如果当前窗口的值大于s了，窗口就要向前移动了(即，该缩小了)。
  • 窗口的结束位置如何移动: 窗口结束位置就是遍历数组的指针，也就是for循环里的索引。
• 解题的关键在于窗口的其实位置如何移动。
• j负责便利数组，即j为窗口右侧，i为窗口左侧，当窗口内的值sum大于targat了。
• 就开始计算长度，保存结果，并使窗口的左侧右移。更新窗口内数字和。
• 这是个循环的过程，因为可能去掉左侧的一个值，当前和扔大于target。

// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int n = nums.size();
        int ret = INT_MAX;// 结果
        int sum = 0;// 窗口内元素之和
        int i = 0;// 窗口的左侧
        int subLength = 0;// 窗口的长度
        for(int j = 0; j < n ; j++){
            sum += nums[j];
            while(sum >= target){// 维护窗口
                subLength = j - i + 1;
                ret = ret > subLength?subLength:ret;
                sum -= nums[i++];
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

904. 水果成篮

• 本题中的滑动窗口为一个只能装两种水果的水果篮。
• 使用一个哈希表来记录窗口中的元素数量，当窗口中的种类>2(即==3了)，就开始判断上一次的窗口长度(即水果数量)。

// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    int totalFruit(vector& fruits) {
        unordered_mapmp;
        int n = fruits.size();
        int ret = 0;// 保存结果，摘取的水果数量
        for(int i = 0,j = 0;i < n; i++){
            mp[fruits[i]]++;// 摘取水果
            while(mp.size() > 2){// 维护滑动窗口
                int cur = fruits[j++];
                if(--mp[cur] == 0)mp.erase(cur);// 将水果篮中的一种水果拿光了，这时栏中又只剩两种水果了
            }
            ret = max(ret,i-j+1);// 求长度，即数量
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

76. 最小覆盖子串

• 相关题解-最小覆盖子串 | 图解滑动窗口 | 最通俗易懂的讲解【c++/java版本】
• 大致步骤:
  • 本题中维护的滑动窗口为使用哈希表保存遍历s每一个的字符，j为窗口左边界，i为窗口右边界，同时负责向后遍历。
  • 如果在我们当前遍历过的s中，其中的某一个字符出现的次数大于在t中出现的次数，此时我们可以尝试收缩边界，即j++。
  • 使用一个变量cnt来记录当前遍历过的s中，包含在t中的字符个数，当t==t.size()时，说明我们要找的字符都已经找到了，然后开始获取结果，
• 详细流程详见代码中的注释。

// 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
    string minWindow(string s, string t) {
        //ts为统计我们需要的字符与其对应的数量，ss为我们维护的滑动窗口
        unordered_mapts,ss;
        // 先统计要查找字符串中各个字符的数量
        for(char& c:t)ts[c]++;
        int n = s.size();
        string ret;
        int cnt = 0;// 统计当前应该收集元素的个数
        for(int i = 0,j=0;its[s[j]])ss[s[j++]]--;
            if(cnt == t.size()){// 每种元素都收集到了，开始计算长度
                if(ret.empty() || i-j+1 < ret.size()){// 减少计算次数，如果没计算过或找到更小的连续子数组，才计算，收集结果。
                    ret = s.substr(j,i-j+1);
                }
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

模拟行为

59. 螺旋矩阵 II

• 顺时针转，注意控制边界和起始位置。左闭右开。

class Solution {
public:
    vector> generateMatrix(int n) {
        vector>ret(n,vector(n,0));
        int starX = 0;// 每圈开头
 `       int starY = 0;
        int loop = n / 2;// 转几圈
        int mid = n / 2;// 矩阵中间的位置
        int count = 1;// 每个元素值
        int offset = 1;// 收缩个数
        // 顺时针转
        int i = 0,j =0;
        while(loop--){
            i = starX;
            j = starY;
            // 左闭右开
            for(j = starY;j < n-offset;j++){
                ret[starX][j] = count++;
            }
            for(i = starX;i < n-offset;i++){
                ret[i][j] = count++;
            }
            for(;j > starY;j--){
                ret[i][j] = count++;
            }
            for(;i > starX;i--){
                ret[i][j] = count++;
            }
            offset++;
            starX++;
            starY++;
        }
        if(n % 2){// 给中间位置单独赋值
            ret[mid][mid] = count;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

54. 螺旋矩阵

• 同上，不过这题是获取元素，注意本体的获取元素以及控制边界的方法，还是与上一题有所不同的。
• 可以理解≈左开右闭。

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        int rc = matrix.size()-1;// 行数-下边界
        int cc = matrix[0].size()-1;// 列数-右边界
        int row = 0;// 标记当前行-上边界
        int col = 0;// 标记当前列-左边界
        vectorret;
        while(true){
            for(int i = col;i <= cc;i++){
                ret.push_back(matrix[row][i]);
            }
            if(++row > rc)break;// 收缩上边界
            for(int i = row;i <= rc;i++){
                ret.push_back(matrix[i][cc]);
            }
            if(--cc < col)break;// 收缩右边界
            for(int i = cc;i >= col;i--){
                ret.push_back(matrix[rc][i]);
            }
            if(--rc < row)break;// 收缩下边界
            for(int i = rc;i>= row;i--){
                ret.push_back(matrix[i][col]);
            }
            if(++col > cc)break;// 收缩左边界
        }
        return ret;
    }
};    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

剑指 Offer 29. 顺时针打印矩阵

• 与上一题完全相同，但是要加入矩阵是否为空的判断，因为这题给的数据可以为空。

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vectorret;
        if(matrix.empty())return ret;
        int rc = matrix.size()-1;// 下
        int cc = matrix[0].size()-1;// 右
        int row = 0;//上
        int col = 0;// 左      
        while(true){
            for(int i = col;i <=cc;i++){
                ret.push_back(matrix[row][i]);
            }
            if(++row > rc)break;
            for(int i = row;i <= rc;i++){
                ret.push_back(matrix[i][cc]);
            }
            if(--cc < col)break;
            for(int i = cc; i >= col;i--){
                ret.push_back(matrix[rc][i]);
            }
            if(--rc < row)break;
            for(int i = rc; i >= row;i--){
                ret.push_back(matrix[i][col]);
            }
            if(++col > cc)break;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---