数组的遍历:414

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<set>
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        //sort(nums.begin(),nums.end(),greater<>());//从大到小排序
        //使用了set就没有必要sort()，排序需要 O(nlog⁡n)的时间
        set<int>s;//set会自动从小到大排序（默认时）,一个元素只能出现一次
        for(int num:nums){
            s.insert(num);//set自动去重
            if(s.size()>3){
                s.erase(s.begin());//注意s.begin()是迭代器类型
            }
        }
        return s.size()==3?*s.begin():*s.rbegin();
    }
};

统计数组中的元素：645(哈希表解法)。关键思想:原地哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <map>
#include <vector>
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int>res(2);
        unordered_map<int,int>mp;
        for(auto& num:nums){    //需要利用迭代器进行遍历
            mp[num]++;
        }
        for(int i=1;i<=nums.size();i++){
            int count=mp[i];
            if(count==2){
                res[0]=i;//重复的数字
            }
            else if(count==0){
                res[1]=i;//缺失的数字
            }
        }
        return res;
    }
};

难题：41

二分搜索：274

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int hIndex(vector<int>& citations) {
        //双指针，二分搜索
        int left = 0, right = citations.size();
        int mid = 0, count = 0;
        while (left < right) {
            mid = (left + right + 1) / 2;//加1防止死循环
            count = 0;
            for (int i = 0; i < citations.size(); i++) {
                if (citations[i] >= mid) {
                    count++;
                }
            }
            if (count >= mid) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

类似min的函数：

1
int minNum = *min_element(nums.begin(),nums.end());

扫描：419

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        int row = board.size(), col = board[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'X') {
                    if ((i >= 1 && board[i - 1][j] == 'X') ||
                        (j >= 1 && board[i][j - 1] == 'X')) {
                        //如果发现其上方或者左边有过X,则继续向右下扫描
                        //此时res不增加，直接continue进入下一次循环
                        //直到确实走到尽头才会结束，然后计数+1
                        continue;
                    }
                    res++;
                }
            }
        }
        return res;
    }
};

迭代：396

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <climits>
#include <numeric>
#include <vector>
class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size(), res = INT_MIN, Fk = 0;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        for (int i = 0; i < n; i++) {
            Fk += i * nums[i];
        }
        res = Fk; //也就是让res=F(0)，避免nums只有一个元素时return INT_MIN
        for (int i = n - 1; i > 0; i--) {
            Fk += sum - n * nums[i];
            res = max(res, Fk);
        }
        return res;
    }
};

模拟：54、59

对角线遍历498：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 0; i < m + n - 1; i++) {
            if (i % 2) {
                int x = (i < n ? 0 : i - n + 1);
                int y = (i < n ? i : n - 1);
                while (x < m && y >= 0) {
                    res.emplace_back(mat[x][y]);
                    x++;
                    y--; 
                }
            } else {
                int x = (i < m ? i : m - 1);
                int y = (i < m ? 0 : i - m + 1);
                while (x >= 0 && y < n) {
                    res.emplace_back(mat[x][y]);
                    x--;
                    y++;
                }
            }
}

在选择使用 emplace_back 还是 push_back 时，通常情况下，emplace_back 更好一些。这是因为 emplace_back 可以避免创建临时对象，从而提高了性能。

另外，emplace_back 也更加灵活，因为它允许你直接传递构造元素所需的参数，而不需要显式地创建对象。

总的来说，如果你需要向 vector 中添加新元素，通常情况下优先考虑使用 emplace_back。

二维数组变换行列长宽：566

1
2
3
4
5
int m = mat.size(), n = mat[0].size();
for (int i = 0; i < m * n; i++) {
     res[i / c][i % c] =mat[i / n][i % n]; 
     //找到第i个数到底分别在数组的哪个位置
}

二维矩阵顺时针旋转（48）=水平翻转(竖直线对称翻转)+(沿)主对角线翻转

矩阵原地置换(73)：用矩阵第一行和第一列代替标记行和列的两个标记数组，使得空间复杂度为$O(1)$，时间复杂度为$O(row*col)$.但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。

在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 0。这样，第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。

矩阵原地置换拓展(289)：创建复合状态2，可以知道修改前是0，而之后变为1.常用于需要同步更新情况。

涉及到类：303

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int>& nums) { //初始化sum数组
        int n = nums.size();
        sum.resize(n + 1); //注意
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        //错误：nums是临时数组，应该用sum
        // return accumulate(nums.begin() + left, nums.begin() + right, 0);
        return sum[right + 1] - sum[left];
    }
};

二维数组resize:

1
sums.resize(m + 1, vector<int>(n + 1));

二维数组定义：(创建n×n的数组，默认初始化所有元素为0)

1
vector<vector<int>> res(n, vector<int>(n));

前缀/后缀之和/之积：238

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size());
        res[0]=1;
        for (int i = 1; i < nums.size(); i++) {
            res[i]=res[i-1]*nums[i-1];//先用res存储前缀之积
        }

        int r=1;
        for(int i=nums.size()-1;i>=0;i--){
            res[i]=res[i]*r;//更新res,res[i]最终应为nums[i]的前缀之积×后缀之积
            r*=nums[i];//用R存储当前对应元素的后缀之积
        }
        return res;
    }
};