48. 旋转图像

对矩阵的原地旋转操作可通过转置并翻转来实现

本题要求完成90°旋转，可先求转置，再对每一行进行翻转

如果要旋转180°，可以先对列翻转，再对行翻转

如果要逆时针旋转90°，则先求转置，再对列进行翻转

29. 顺时针打印矩阵

1
2
3
4
5
6
处理移动四个移动方向用：
vector<vector<int>> move{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
或者：
static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
标记矩阵的已访问元素和未访问元素用一个相同大小的bool矩阵visit
输入一个空matrix时，如果对其求matrix[0].size()会报错，因为没有matrix[0]
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
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> order;

    if (matrix.size() == 0 || matrix[0].size() == 0) {
        return {};
    }

    int rowRange = matrix.size();
    int colRange = matrix[0].size();
    vector<vector<bool>> visit(rowRange, vector<bool>(colRange));
    int total = rowRange * colRange;
    vector<vector<int>> move{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int row = 0;
    int col = 0;
    int moveIndex = 0;
    int nextRow, nextCol;
    for (int i = 0; i < total; i++)
    {
        order.push_back(matrix[row][col]);
        visit[row][col] = true;
        nextRow = row + move[moveIndex][0];
        nextCol = col + move[moveIndex][1];
        if (nextRow >= rowRange || nextRow < 0 || nextCol >= colRange || nextCol < 0 || visit[nextRow][nextCol])
        {
            moveIndex = (moveIndex + 1) % 4;
        }
        row += move[moveIndex][0];
        col += move[moveIndex][1];
    }
    return order;
}

56. 合并区间

先按区间左边界进行升序排序

每次检查是否能合并时，比较：当前区间的左边界和结果集合中最后一个区间的右边界

1
if(intervals[i][0] <= ret.back()[1])

如果当前区间左边界小于结果集合中最后一个区间的右边界，说明区间重叠，修改当前区间的右边界，选择当前比较的两个区间的右边界中的较大值作为新的右边界

如果不能合并，在结果集合ret中push_back当前检查的区间

62. 不同路径

求只能往右或者往下走的全路径：排列组合中的组合

尽可能的防止溢出，每次循环中更新完分子和分母后，都用分子和分母分别除以公约数

公约数计算方法：

1
2
3
4
int gcd(int a, int b)   
    {
        return b == 0 ? a : gcd(b, a % b);
    }