每天进步一点点【2019.8.24】

一、有效的数独【leetcode 36】

题目描述：判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效；
要求：

1) 数字 1-9 在每一行只能出现一次。
2）数字 1-9 在每一列只能出现一次。
3）数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

输入：

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

输出：
true
分析：

应用HashSet判断是否出现过：
1）每行；
2）每列；
3）每个小正方形【四层for循环】

代码：

 public static boolean isValidSudoku(char[][] board)  {
         int rows = board.length;
         int cols = board[0].length;
         // 行
         for (int i = 0; i < rows; i++) {
             Set<Character> set = new  HashSet<Character>();
             for (int j = 0; j < cols; j++) {
                 if(set.contains(board[i][j])&&board[i][j]!='.')  return false;
                 else set.add(board[i][j]);
             }
             set.clear();
         }
         // 列
         for (int i = 0; i < cols; i++) {
             Set<Character> set = new  HashSet<Character>();
             for (int j = 0; j < rows; j++) {
                 if(set.contains(board[j][i])  &&board[j][i]!='.') return  false;
                 else set.add(board[j][i]);
             }
             set.clear();
         }
         // 3*3方阵
         for (int i = 0; i <= board.length-3; i=i+3)  {
             for (int j = 0; j <= board.length-3;  j=j+3) {
                 Set<Character> set = new  HashSet<Character>();
                 int curRow = i+2;
                 int curCol = j+2;
                 // 内部小正方形
                 for (int j2 = i; j2 <=curRow;  j2++) {
                      for (int k = j; k <=curCol;  k++) {
                          if(set.contains(board[j2][k])&&board[j2][k]!='.' ){
                               return false;
                          }else {
                               set.add(board[j2][k]);
                          }
                      }
                 }
                 set.clear();
             }
         }
         return true;
    }

存在问题：时间复杂度太大

改进思路：优化空间复杂度：使用一个HashSet，优化时间复杂度：使用i/3,j/3保证一个小正方形在同一区域；
实现：

public static boolean isValidSudoku1(char[][] board)  {
         Set<String> set = new HashSet<String>();
         int rows = board.length;
         int cols = board[0].length;
         for (int i = 0; i < rows; i++) {
             for (int j = 0; j < cols; j++) {
                 if(board[i][j]=='.') continue;
                 String str = "("+board[i][j]+")";
                 String row = i+str,col =  str+j,cell = i/3+str+j/3;
                 if(set.contains(row)||  set.contains(col)||set.contains(cell)) return false;
                 set.add(row);
                 set.add(col);
                 set.add(cell);
             }
         }
         return true;
    }

二、每日一点心理学

巴纳姆效应
典故：1948年由心理学家伯特伦·福勒通过试验证明的一种心理学现象，以杂技师巴纳姆的名字命名，认为每个人都会很容易相信一个笼统的、一般性的人格描述特别适合他。即使这种描述十分空洞，仍然认为反映了自己的人格面貌，哪怕自己根本不是这种人；
启发：
① 要学会面对自己；
② 培养一种收集信息的能力和敏锐的判断力；
③ 以人为镜，通过与自己身边的人在各方面的比较来认识自己；
④ 通过对重大事件，特别是重大的成功和失败认识自己；

三、每日一句
Life starts all over again when it gets crisp in the fall.