代码随想录1刷—数组篇

数组理论基础

• 数组是存放在连续内存空间上的相同类型数据的集合。
• 数组下标都是从0开始的。数组内存空间的地址是连续的。
• 数组的元素是不能删的，只能覆盖。
• C++中要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
  • array 定义的时候必须定义数组的元素个数，且只能包含整型字面值常量，枚举常量或者用常量表达式初始化的整型const对象，非const变量以及需要到运行阶段才知道其值的const变量都不能用来定义数组的维度；而vector 不需要；
  • array 定义后的空间是固定的了，不能改变；而vector 要灵活得多，可再加或减
  • vector有一系列的函数操作，非常方便使用；和vector不同，array数组不提供 push_back或者其他的操作在数组中添加新元素，array数组一经定义就不允许添加新元素，若需要则要充许分配新的内存空间，再将原数组的元素赋值到新的内存空间。
  • array数组和vector不同，一个数组不能用另一个数组初始化，也不能将一个数组赋值给另一个数组。

二分法

力扣相关题目

使用前提条件

• 数组为有序数组

• 数组中无重复元素（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的）

  如果题目描述满足如上条件，可想一想是不是可以用二分法了。

704.二分查找

//注意边界条件

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，在数组和链表的操作中是非常常见的。此外还有双向指针法：两个指针分别从前后开始进行遍历并进行操作。

力扣相关题目

27.移除元素

//快慢双指针
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0;fastIndex <nums.size();fastIndex++){
            if(val!=nums[fastIndex]){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

//相向双指针
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size()-1;
        while(leftIndex <= rightIndex){
            while(leftIndex <= rightIndex && nums[leftIndex]!=val){
                leftIndex++;
            }
            while(leftIndex <= rightIndex && nums[rightIndex]==val){
                rightIndex--;
            }
            if(leftIndex < rightIndex){
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

滑动窗口（参考labuladong算法小抄）

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

套用模板

先思考如下问题：

• 1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

  2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？

  3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

  4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    //unordered_map 容器和 map 容器仅有一点不同：
    //即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
    for (char c : t) need[c]++;
    //这里的for(char c:chars)就是定义一个遍历字符c，让它分别等于字符串数组chars里面的各个字符，然后执行下面的语句，当c被赋值为chars里面所有字符各一次后，就会退出这个循环.
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
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

力扣相关题目

76.最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> need,window;
        for (char c : t)	need[c]++;
        int left = 0;
        int right = 0;
        int count = 0;
        int start = 0;
        int len = INT_MAX;
        while(right<s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    count++;
                }
            }
            while(count == need.size()){
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s[left];
                left++;
                if (need.count(d)) {
                    if (window[d] == need[d])
                        count--;
                        window[d]--;
                }  
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
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

螺旋矩阵（模拟行为）

54/offer29.螺旋矩阵（二维变一维）

示例 ：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
1
2

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty()) {
            return ans;
        }	
        //一定要先做判空，若这段代码放到int定义结束之后，则如果matrix为空，那么在matrix[0].size()时会报错。
        int up = 0;
        int down = matrix.size() - 1;
        int left = 0;
        int right = matrix[0].size() - 1;
        while(1){
            for(int j = left;j<=right;j++){
                ans.push_back(matrix[up][j]);
            }
            if(++up>down){
                break;
            }
            for(int i = up;i<=down;i++){
                ans.push_back(matrix[i][right]);
            }
            if(--right<left){
                break;
            }
            for(int j = right;j>=left;j--){
                ans.push_back(matrix[down][j]);
            }
            if(--down<up){
                break;
            }
            for(int i = down;i>=up;i--){
                ans.push_back(matrix[i][left]);
            }
            if(++left>right){
                break;
            }
        }
        return ans;
    }
};
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

59.螺旋矩阵（一维变二维）

示例 ：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
1
2

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));    //二维数组
        int i = 0;
        int j = 0;
        res[i][j] = 1;
        while(res[i][j]!=n*n){
            while(j+1<n && 0 == res[i][j+1]){
                res[i][j+1]=res[i][j]+1;
                j++;
            }
            while(i+1<n && 0 == res[i+1][j]){
                res[i+1][j]=res[i][j]+1;
                i++;
            }
            while(j>0 && 0 == res[i][j-1]){
                res[i][j-1]=res[i][j]+1;
                j--;
            }
            while(i>0 && 0 == res[i-1][j]){
                res[i-1][j]=res[i][j]+1;
                i--;
            }
        }
        return res;
    }
};
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