• 完成一道 mid 数组相关，添加至昨天日报了
• 看了矩阵

矩阵置零

给定一个 _m_ x _n_ 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

思路解析

如果要是遍历到 0 直接将十字交叉线上的所有值全部变为 0 明显是不合适的，在接下来的遍历中就会分不清是原本就存在的 0 还是修改后的 0 ，最终导致整个矩阵都变成 0 为了解决以上问题，我们需要新建一个布尔值记录 是否要将第零行、列全部改为 0 接下来实现第一关 从 1 开始遍历矩阵，如果遇到 0 ，就将他的上方和左方改为 0 继续执行下一步， 再次遍历矩阵，查看上方和左边是否还有 0 ，有的话就将其也修改为 0 最后如果第 0 行、列有 0 直接将其全部修改

代码实现

class Solution {  
    public void setZeroes(int[][] matrix) {  
        int m = matrix.length;  
        int n = matrix[0].length;  
		// 记录第 0 行是否有 0
        boolean firstRowHasZero = false;  
        for (int x : matrix[0]) {  
            if (x == 0) {  
                firstRowHasZero = true;  
                break;  
            }  
        }  
        // 记录第 0 列是否有 0
        boolean firstColHasZero = false;  
        for (int i = 0; i < m; i++) {  
            if (matrix[i][0] == 0) {  
                firstColHasZero = true;  
                break;  
            }  
        }  
        // 跳过 第 0 行，留到最后修改
        for (int i = 1; i < m; i++) {  
            for (int j = 1; j < n; j++) {  
                if (matrix[i][j] == 0) {  
                    matrix[i][0] = 0;  
                    matrix[0][j] = 0;  
                }  
            }  
        }  
  
        for (int i = 1; i < m; i++) {  
            for (int j = 1; j < n; j++) {  
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {  
                    matrix[i][j] = 0;  
                }  
            }  
        }  
		  // 如果包含 0 直接全部修改为 0
        if (firstColHasZero) {  
            for (int[] row : matrix) {  
                row[0] = 0;  
            }  
        }  
        // 如果包含 0 直接全部修改为 0
        if (firstRowHasZero) {  
            Arrays.fill(matrix[0], 0);  
        }  
    }  
}

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

思路解析

观察图片 ，由此的得知，顺时针螺旋顺序其实是依次 “从左向右、从上向下、从右向左、从下向上” 循环

于是我们有以下流程 使用图表来辅助理解

打印方向	1. 根据边界打印	2. 边界向内收缩	3. 是否打印完毕
从左向右	左边界 l，右边界 r	上边界 t 加 1	是否 t > b
从上向下	上边界 t，下边界 b	右边界 r 减 1	是否 l > r
从右向左	右边界 r，左边界 l	下边界 b 减 1	是否 t > b
从下向上	下边界 b，上边界 t	左边界 l 加 1	是否 l > r

代码实现

class Solution {  
    public List<Integer> spiralOrder(int[][] matrix) {  
        if (matrix.length == 0)  
            return new ArrayList<Integer>();  
        int l = 0, r = matrix[0].length - 1;  
        int t = 0, b = matrix.length - 1, x = 0;  
  
        Integer[] res = new Integer[(r + 1) * (b + 1)];  
        while (true) {  
            for (int i = l; i <= r; i++) res[x++] = matrix[t][i];  
            if (++t > b) break;  
            for (int i = t; i <= b; i++) res[x++] = matrix[i][r];  
            if (l > --r) break;  
            for (int i = r; i >= l; i--) res[x++] = matrix[b][i];  
            if (t > --b) break;  
            for (int i = b; i >= t; i--) res[x++] = matrix[i][l];  
            if (++l > r) break;  
        }  
        return Arrays.asList(res);  
  
    }  
}

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像

思路解析

先看图，以此获得映射公式

之后按照公式来进行代码的实现即可

代码实现

class Solution {  
    public void rotate(int[][] matrix) {  
        int n = matrix.length;  
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < i; j++) {  
                int tmp = matrix[i][j];  
                matrix[i][j] = matrix[j][i];  
                matrix[j][i] = tmp;  
            }  
        }  
        for (int[] row : matrix) {  
            for (int j = 0; j < n / 2; j++) {  
                int tmp = row[j];  
                row[j] = row[n - 1 -j];  
                row[n - 1 - j] = tmp;  
            }  
        }  
    }  
}

合并为同一个循环

class Solution {  
    public void rotate(int[][] matrix) {  
        int n = matrix.length;  
        for (int i = 0; i < n; i++) {  
            int[] row = matrix[i];  
            for (int j = i + 1; j < n; j++) {  
                int tmp = row[j];  
                row[j] = matrix[j][i];  
                matrix[j][i] = tmp;  
            }  
            for (int j = 0; j < n / 2; j++) {  
                int tmp = row[j];  
                row[j] = row[n - 1 - j];  
                row[n - 1 - j] = tmp;  
            }  
        }  
    }  
}

搜索二维矩阵 Ⅱ

编写一个高效的算法来搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

思路解析

for for return true（bushi 将矩阵逆时针旋转 45 度，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target

根结点 即为 左下角和右上角的数字，在此用 flag 表示，以左下角元素开始则有：

• 若 flag > target 则证明 target 一定在 flag 所在行的上方，即 flag 所在行可以被消除
• 若 flag < target 则证明 target 一定在 flag 所在列的右方，即 flag 所在列可以被消除

代码实现

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