总结

  1. 利用题目的数据空间或者返回空间来中间变量，从而节省空间复杂度。

  2. 73. 矩阵置零

    给定一个矩阵，如果某位置为0，要求将同一列同一行的数都改写为0，要求原地改写矩阵。
    暴力法就是用一个一样大的矩阵来标记哪些位置有0，然后在原矩阵进行改写；
    由于同一行中只要有一个0全行都应该是0，因此可以改进为用一个1m和1n的数列分别记录第m行和第n列中是否有0，这样需要O(m+n)空间复杂度；
    进一步改进是不单独创建记录数列，而是在原数组位置进行记录。然而这样会覆盖掉原数组的一行一列的原数据，因此需要创建两个变量记录被覆盖掉的那行与那列是否含有0。

    79. 单词搜索

    给定一个字母矩阵，判断相邻的字母是否能按序组成指定字符串。用过的矩阵块不能再用。
    虽然形式是矩阵，但本质是树（图）的递归与回溯。
    回溯模板：
    1. public boolean dfs(int i, int j, int count){
    2.      if(board[i][j]!=word.charAt(count)) return false;    // 截止条件
    3.      else if(count==word.length()-1) return true;    // 截止条件
    4.      visited[i][j]=true;
    5.      boolean res=false;
    6.      // 循环遍历下一步
    7.      int[][] directions= {{-1,0},{0,-1},{1,0},{0,1}};
    8.      for(int k=0;k<4;k++){
    9.          int[] direction=directions[k];
    10.          int newi=i+direction[0];
    11.          int newj=j+direction[1];
    12.          if(newi>=0 && newi<=board.length-1 && newj>=0 && newj<=board[0].length-1 && !visited[newi][newj]){
    13.              boolean flag=dfs(newi,newj,count+1);
    14.              if(flag){
    15.                  res=true;
    16.                  break;
    17.              }
    18.          }
    19.      }
    20.      // 回溯
    21.      visited[i][j]=false;
    22.      return res;
    23.  }