每天进步一点点【2019.8.27】

一、矩阵清零leetcode 73】

题目描述：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法；
输入：

[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

输出：

[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

分析：

1）找出0的位置
2）按行和列，将矩阵元素清零

代码：

public void setZeroes(int[][] matrix) {
        // 检索0的位置
        int rows = matrix.length;
        int cols = matrix[0].length;
        HashSet<Integer> rowSet = new HashSet<Integer>();
        HashSet<Integer> colSet = new HashSet<Integer>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(matrix[i][j]==0){
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        // 将位置清零
        // 行清零
        for (int i = 0; i < cols; i++) {
            for(int item:rowSet){
                matrix[item][i] = 0;
            }
        }
        // 列清零
        for (int i = 0; i < rows; i++) {
            for(int item:colSet){
                matrix[i][item] = 0;
            }
        }
    }

存在问题：空间复杂度太高
优化方案：空间复杂度【从 O(m+n)降到O(1)】，第一列作为标记位，不断更新矩阵中的第一行和第一列的元素，然后根据第一行和第一列的值更新当前行和当前列；
代码：

 public static void setZeroes(int[][] matrix) {
        // 用第一列作为标志列
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean colFlag = false;
        for (int i = 0; i < rows; i++) {
            // 标记第0列
            if(matrix[i][0]==0) colFlag = true;
            // 根据i的0对第0行和第0列处理
            for (int j = 1; j < cols; j++) {
                if(matrix[i][j]==0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        //根据第0列、第0行更新当前行和当前列
        for (int i = rows-1; i >=0; i--) {
            for (int j = cols-1; j >=1; j--) {
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
            if(colFlag) matrix[i][0] = 0;
        }
    }

二、每日一点心理学

贝勃定律:
原理：当人经历强烈的刺激后，再施予的刺激对他（她）来说也就变得微不足道；
表现：
比如，原本一元钱的报纸变成了十元一份，你定会感到无法接受；而原本10000元的电脑涨了100元，你一定不会有什么大的反应；
应用：
1） 有的商家起初一直把价位抬得很高，某天突然大幅减价，虽远远高于成本，却也会起到招引顾客的效果；
2） 一般有经验的谈判专家都是在谈判临近结束时才提出一些棘手的条件，而对方被一开始的优厚条件所诱惑，也就不怎么在意后来才知道的那些缺点了；

三、每日一句
I fell in love with him the way you fall asleep: slowly, and then all at once.