数组

旋转矩阵

解题思路:
两次翻转轻松搞定。
先对矩阵做沿主对角线的翻转（其实就是矩阵的转置），原地完成；接着再对操作后的矩阵进行根据列序号倒排。
实现:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 沿矩阵中心按列旋转
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n / 2; j++)
            {
                swap(matrix[i][j], matrix[i][n - j -1]);
            }
        }
    }
};

零矩阵

解题思路:
使用标记数组
我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
具体地，我们首先遍历该数组一次，如果某个元素为 00，那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组，用标记数组更新原数组即可。
实现:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> row(rows), col(cols);  // 创建两个标记数组
        // 第一次遍历, 标记为0的位置
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (!matrix[i][j]) row[i] = col[j] = true;
            }
        }
        // 第二次遍历, 处理数组
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
};

对角线遍历

解题思路:

1. 同一对角线上的横列坐标之和是相等的
2. 对角线序号偶数是倒序，奇数是正序

实现:

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> res;
        if (mat.empty() || mat[0].empty()) return res;
        int rows = mat.size(), cols = mat[0].size();
        for (int i = 0; i < rows + cols - 1; i++)
        {
            if (i % 2 == 0)  // 对角线为偶数
            {
                for (int j = min(i, rows - 1); j >= max(0, i - cols + 1); j--)
                {
                    res.push_back(mat[j][i - j]);
                }
            }
            else
            {
                for (int j = max(0, i - cols + 1); j <= min(i, rows - 1); j++)
                {
                    res.push_back(mat[j][i - j]);
                }
            }
        }
        return res;
    }
};

数组拆分

解题思路:
排序后, 每两步, 就是最优的局部最小值
实现:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int res = 0;
        quickSort(nums, 0, nums.size() - 1);
        for (int i = 0; i < nums.size(); i += 2)
        {
            res += nums[i];
        }
        return res;
    }
private:
    void quickSort(vector<int>& nums, int begin, int end)
    {
        if (begin < end)
        {
            int l = begin, r = end, refer = nums[r];
            while (l < r)
            {
                while (nums[l] <= refer && r >l) l++;
                if (l < r) nums[r] = nums[l];
                while (nums[r] >= refer && r > l) r--;
                if (l < r) nums[l] = nums[r];
            }

            nums[l] = refer;
            quickSort(nums, begin, l - 1);
            quickSort(nums, l + 1, end);
        }
    }
};

杨辉三角

杨辉三角性质:

实现:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        for (int i = 0; i < numRows; i++)
        {
            res[i].resize(i + 1);  // 初始化每一列的数量
            res[i][0] = res[i][i] = 1;  // 初始化杨辉三角的外围
            for (int j = 1; j < i; j++)
            {
                res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
            }
        }
        return res;
    }
};