leetcode数据结构__代码随想录打卡：数组篇

【声明：本文为的学习笔记，很多代码示例直接从中摘录(毕竟鄙人水平太菜代码太烂注释不清...)】

【我想对自己说：动手！在纸上画一画、算一算，把模糊的地方落到实处；把思维呈现出来，理清楚；还有，要负责：对自己，对大家——不必急，但必须认真】

Tips

1.（真诚.jpg）大家如果想找一份的刷题参考的话，我真的觉得卡哥的（）很合适！它按照数据结构的类型划分章节，每个章节都有更细致的划分，相关的题目类型集合在一起，每题每种算法都附有文字、动图和视频讲解！刷得很酸爽！很适合系统刷题！小白爆哭......

2.本篇博客是基于随想录的刷题笔记，鄙菜鸡接下来对每种结构都会整理刷题笔记的💪；（惶恐）所以大家没必要看我写的这些啊，直接饮源头活水（指随想录）多好啊😭；不过很推荐大家把自己学习的东西整成博客进行记录，这个过程是内化并输出的过程，还能留下自己的思考痕迹、成长历程，相当好~（但本菜鸡还是有点羞耻感......）

3.(不知道为啥博客中的动图不动了......)个人感觉，把一些数据结构啊程序运行步骤啊可视化一下，还是对理解很有帮助的！推荐一个相关的网站：（小东西长得挺别致！）

⭐二分查找

704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target
 = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

关键

• 对区间的定义：左闭右闭or左闭右开
• 在循环中坚持根据查找区间的定义来做边界处理。
• 区间的定义就是不变量，那么在循环中坚持根据查找区间的定义来做边界处理，就是循环不变量规则。
• 循环条件反映查找区间的边界：决定了每次if条件判断后，更新边界取值是middle 还是 middle+1/-1。

题解【力扣默认给main类了...】

//查询区间为左闭右闭
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

class Solution {
public:
    int search(vector<int>& num, int target) {
        int left = 0;
        int right = num.size() - 1;
        
        while(left <= right) {
        int middle = left + ((right - left) >> 1);
       //每次循环middle的值都要更新！该句要放在循环里面.
        if(num[middle] < target) {
            left = middle + 1;
        }
         else if(num[middle] > target) {
            right = middle - 1;
         }
        else return middle;
    }
    return -1;
    }
};

int main() {
    Solution solution;

    string input;
//声明一个 string 类型的变量 input，用于存储用户输入的整行字符串。
    getline(cin,input);
//调用 getline 函数，从标准输入流 cin 中读取一整行文本，并将其存储在 input 变量中。这里，getline 会读取直到遇到换行符为止的所有字符，包括空格。
    stringstream ss(input);
//创建一个 stringstream 对象 ss，并用 input 初始化它。
//这使得我们可以像处理流一样处理字符串 input，允许我们从中提取数据。
    vector<int> nums;
    int n;

    while(ss >> n) {
        nums.push_back(n);
    }
//这是一个循环，尝试从 stringstream 对象 ss 中提取整数并赋值给 n。
//如果提取成功，循环继续；如果没有更多的整数可读（例如到达字符串的末尾），则循环结束。
    
    int target;
    cin >> target;

    int result = solution.search(nums,target);

    cout << result;

    return 0;
}

//区间为左闭右开
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

35

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 为 无重复元素 的 升序 排列数组
• -10^4 <= target <= 10^4

题解

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出

            if (nums[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标值在右侧
            } else {
                right = mid - 1; // 目标值在左侧
            }
        }

        return left; // 返回插入位置
    }
};

移除元素27

给你一个数组 nums 和一个值 val，你需要  移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

关键

多动手，画一下图示会明了一些。

暴力解法

两个for循环，一个for循环遍历数组元素，第二个for循环更新数组（“平移”）。

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

⭐双指针法

• 抓住核心思想：遍历数据过程中遇到等于目标值就直接跳过，不等于目标值就赋值，这样就能 过滤掉（也就是覆盖掉）目标值
• 对比“单指针”：遇非目标值，两指针共同移动，而不用等着整个数组后面的元素“挨个移动”，提高了效率。嘿嘿。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
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;
    }
};

【24.9.22 自己画图过程还是有点不清楚】

【双指针法应用】有序数组的平方977

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

暴力解法

直接：所有元素平方后再排序

#include <iostream>
#include <vector>
#include <algorithm>  // sort 函数需要这个头文件

using namespace std;

class Solution {
public:
    vector<int> sortedSquares0(vector<int>& A) {
        // 将每个元素平方
        for(int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        // 对数组进行排序
        sort(A.begin(), A.end());
        return A;
    }
};

int main() {
    Solution sol;
    int n;
    // 输入数组的长度
    cin >> n;

    vector<int> A(n);
    //C++ 标准库的 std::vector 的声明方式！ 

    // 输入数组的元素
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    // 调用函数处理
    vector<int> result = sol.sortedSquares0(A);

    // 输出结果
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

⭐双指针法

• 数组是有序的：数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
• 此时考虑双指针法，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { 
        // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

【24.9.22 循环条件没有理解透】

【双指针法应用】移动零283

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

【24.9.22 先把答案抄上（回头重做）】

⭐双指针法（一次遍历）

这里参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点 x，然后把所有小于等于 x 的元素放到 x 的左边，大于 x 的元素放到其右边。
这里我们可以用 0 当做这个中间点，把不等于 0(注意题目没说不能有负数)的放到中间点的左边，等于 0 的放到其右边。
这的中间点就是 0 本身，所以实现起来比快速排序简单很多，我们使用两个指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]
请对照动态图来理解：

作者：王尼玛
链接：https://leetcode.cn/problems/move-zeroes/solutions/90229/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
来源：力扣（LeetCode）

【代码掌控能力】螺旋矩阵59

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3

输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

关键

• 搞清楚所需要的数据结构（数组），正确初始化（特别是基础薄弱情况下...）
• 遵循循环不变量原则，按照相同的规律处理每一条边界（左开右闭）
• 可以画一下图，取几个小一点的值模拟一下过程；把大体的循环逻辑确定了，再考虑细节处理或者优化的办法
• （我出现的问题：左和下两条边循环条件无脑照抄了前两条边...debug半小时，遂更正...)

直白的解法

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)

简洁版

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > generateMatrix(int n) {
    vector<vector<int> > matrix(n, vector<int> (n));
    int num = 1, layers = (n + 1) / 2;

    for (int layer = 0; layer < layers; ++layer) {
        int end = n - layer - 1;

        // 从左到右
        for (int i = layer; i <= end; ++i) matrix[layer][i] = num++;
        
        // 从上到下
        for (int i = layer + 1; i <= end; ++i) matrix[i][end] = num++;
        
        // 从右到左
        if (layer < end) {
            for (int i = end - 1; i >= layer; --i) matrix[end][i] = num++;
        }

        // 从下到上
        if (layer < end) {
            for (int i = end - 1; i > layer; --i) matrix[i][layer] = num++;
        }
    }

    return matrix;
}

int main() {
    int n = 3; // 示例输入
    vector<vector<int> > result = generateMatrix(n);

    // 输出结果
    for (const auto& row : result) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

【24.9.26 好玩耶！减少了变量，实现了同样的功能！隔段时间再来研究一下】

⭐Skill：前缀和

区间和58【熟悉ACM输出模式】

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

数据范围：

0 < n <= 100000

（直接想法：累加；结果：超时......弃之)

• 前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
• 前缀和 在涉及计算区间和的问题时非常有用！

摘抄随想录：

• 例如，我们要统计 vec[i] 这个数组上的区间和。

  我们先做累加，即 p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和。

如果，我们想统计，在vec数组上 下标 2 到下标 5 之间的累加和，用 p[5] - p[1] 就可以了。

p[1] = vec[0] + vec[1];

p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] 就是 红色部分的区间和。

而 p 数组是我们之前就计算好的累加和，所以后面每次求区间和的之后 我们只需要 O(1) 的操作。

• 特别注意： 在使用前缀和求解的时候，要特别注意 求解区间。

如上图，如果我们要求 区间下标 [2, 5] 的区间和，那么应该是 p[5] - p[1]，而不是 p[5] - p[2]。

很多录友在使用前缀和的时候，分不清前缀和的区间，建议画一画图，模拟一下 思路会更清晰。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
        presum += vec[i];
        p[i] = presum;
    }

    while (cin >> a >> b) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        cout << sum << endl;
    }
}

C++ 代码 面对大量数据 读取 输出操作，最好用scanf 和 printf，耗时会小很多：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &vec[i]);
        presum += vec[i];
        p[i] = presum;
    }

    while (~scanf("%d%d", &a, &b)) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        printf("%d\n", sum);
    }
}

【后续会补充题目、重做巩固的！】