LeetCode Hot 100 第9天

1. 48 旋转图像（规律）

链接：题目链接
题解：

题解 时间复杂度O(n^2)：

1. (x, y) 元素顺时针旋转90% 第x行转到倒数第len - 1 - x列 第y个元素转到最后一列第y个元素（公式：matrix[x][y] => matrix[y][len - 1 - x]）
2. 第0行第0个元素一直转 (0, 0) -> (0, len -1) -> (len - 1, len - 1) -> (len - 1, 0) -> (0, 0)
3. 所以只需要一个4次循环, 就能把这4个元素的位置纠正 用temp记录 方便swap
4. 哪些数字需要作为起点旋转？如果len为偶数，那么是[0 ~ len / 2, 0 ~ len / 2] 如果len作为奇数 那么是[0 ~ len - 1 / 2, 0 ~ len + 1 / 2]

代码：

class Solution {
    public void rotate(int[][] matrix) {
        // 建立个新二维数组，旧二维数组 起点(0,0) 新二维数组 起点(0, r)，旧二维数组顺指针遍历、填充
        // 找规律
        // 第x行转到倒数第len - 1 - x列 第y个元素转到最后一列第y个元素
        // 公式：matrix[x][y] => matrix[y][len - 1 - x]
        // 第0行第0个元素一直转 (0, 0) -> (0, len -1) -> (len - 1, len - 1) -> (len - 1, 0) -> (0, 0)
        // 所以只需要一个4次循环, 就能把这4个元素的位置纠正 用temp记录 方便swap
        // 哪些数字需要作为起点旋转？如果len为偶数，那么是[0 ~ len / 2, 0 ~ len / 2] 如果len作为奇数 那么是[0 ~ len - 1 / 2, 0 ~ len + 1 / 2]
        int len = matrix.length;
        for (int i = 0; i < len / 2; ++ i) {
            for (int j = 0; j < (len + 1) / 2; ++ j) {
                int temp = matrix[j][len - 1 - i];
                matrix[j][len - 1 - i] = matrix[i][j];
                // (j, len - 1 - i)
                // (len - 1 - i, len - 1 - j)
                // (len - 1 - j, i)
                // (i, j)
                matrix[i][j] = matrix[len - 1 - j][i];
                matrix[len - 1 - j][i] = matrix[len - 1 - i][len - 1 - j];
                matrix[len - 1 - i][len - 1 - j] = temp;
            }
        }
    }
}

2. 240 搜索二维矩阵 II（规律）

链接：题目链接
题解：

题解 时间复杂度O(n + m)：

1. 如果以[x, y]为起点，matrix[x][y] == traget 直接返回，matrix[x][y] > traget 往右或者往下，matrix[x][y] < traget 往左或者或者往上
2. 对于上述情况没办法知道往哪个方向，因为短暂考虑都是对的
3. 换个思路，能不能明确知道往哪个方向呢？比如站在(0, len - 1) 往左下方走，matrix[x][y] > traget 往左，matrix[x][y] < traget 往下
4. 往左 排除掉当前及右边列 往下 排除掉当前及上面行 如果target存在二维数组中，一定可以往左、往下到达
5. 如果下标超出了二维数组范围，那么证明不存在target

代码：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowMax = matrix.length - 1;
        int x = 0, y = matrix[0].length - 1;
        while (x <= rowMax && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y --;
            } else {
                x ++;
            }
        }
        return false;
    }
}

如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！