Lexi's Leetcode solutions

Posts Tagged ‘matrix

遇见这种matrix题就腿发软,bf给讲了个四条边bound的方法,立刻15分钟bug free了。高兴够呛。

public int[][] generateMatrix(int n) {
    int[][] res = new int[n][n];
    int k = 1;
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    while (left < right && top < bottom) {
        for (int j = left; j < right; j++) {
            res[top][j] = k++;
        }
        for (int i = top; i < bottom; i++) {
            res[i][right] = k++;
        }
        for (int j = right; j > left; j--) {
            res[bottom][j] = k++;
        }
        for (int i = bottom; i > top; i--) {
            res[i][left] = k++;
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    if (n % 2 != 0)
        res[n / 2][n / 2] = k;
    return res;
}
Advertisements
Tags:

这个题挺吓人的,后来bf给讲明白了然后记得葫芦半片的,今天自己重新想了想,还是做出来了也通过了。不过是O(M * M * N的速度,没有网上说的O(M*N),忍了,反正也能pass oj.

算法:

  1. 先用dp求一个新矩阵,d[i][j]表示以(i, j)结尾有几个连续1(在当前row)。
  2. 然后遍历这个新矩阵,在每个cell,都看看“宽度是d[i][j]的矩阵最多能有多高?“,也就是往上expand到宽度变窄为止,往下expand到宽度变窄为止,然后总高度×当前宽度就是d[i][j]所属于的矩阵的最大面积。这就是个O(M * N) * O(M)。

当时给讲的时候觉得这怎么是人类能想出来的呢?然后bf说你把二维降成一维怎么做,不也是找以当前结束的1有多长吗。然后恍然大悟,这题还是有救的。题目本身写起来细节不多,不容易出bug,两遍就过了很开心~

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0)
        return 0;
    int res = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = matrix[i][0] - '0';
        for (int j = 1; j < n; j++) {
            d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = Math.max(res, expand(d, i, j));
        }
    }
    return res;
}
private int expand(int[][] d, int I, int J) {
    int height = 0;
    int width = d[I][J];
    //go up
    for (int i = I - 1; i >= 0; i--) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    //go down
    for (int i = I; i < d.length; i++) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    return width * height;
}

这个好像两年前在纽约就做过,到今天才好好分析了一遍。Leetcode上面的这篇分析特别特别好,看过一遍顺便还练习算时间复杂度了。总之两个比较好的解法:

1. O(n)的linear解法:

因为二维矩阵是行列都sort好的,所以最上面一行和最右边一列正好形成了一个sort好的递增数列。取右上角这个A[i][j],它左边的全<x, 它下边的全>x,所以每次可以删掉一行/列。这样每次往下/往左走一步,最后要是走到左下角了还没找到,那走的最多步数是m + n步。所以时间是O(m + n)。

public boolean searchMatrixLinear(int[][] matrix, int target) {
  int i = 0, j = matrix[0].length - 1;
  while (i < matrix.length && j >= 0) {
    if (matrix[i][j] == target)
      return true;
    else if (matrix[i][j] > target) // eliminate col, go left
      j--;
    else
      i++; // eliminate row, go down
  }
  return false;
}

2. O(logm * logn)的更快的解法:

每次取中间一列,然后在这一列里面binary search,要是没找到,最后会找到(j1, j2)这样的两个位置,A[i][j1] < x && A[i][j2]。说明(i, j1)左上的全<x,(i, j 2)右下的全>x,说明x肯定不在这两块里面,就可以eliminate掉了。在剩下的两块里面各自找x,然后返回||。

这个时间复杂度为什么是O(logm * logn)?每次删掉行数的一半,是logm,在每个check的row里面做一次binary search是logn。

public boolean searchMatrixFastest(int[][] matrix, int target) {
  return searchBinary(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
}
private boolean searchBinary(int[][] matrix, int i1, int i2, int j1, int j2, int x) {
  if (i1 > i2 || j1 > j2)
    return false;
  int midRow = (i1 + i2) / 2; 
  int midCol = searchInRow(matrix, midRow, j1, j2, x); 
  if (midCol == -10) //用-10不用-1因为可能没找到但是q=-1
    return true;
  return searchBinary(matrix, i1, midRow - 1, midCol + 1, j2, x) || searchBinary(matrix, midRow + 1, i2, j1, midCol, x);
}
private int searchInRow(int[][] matrix, int i, int p, int q, int x) {
  while (p <= q) {
    int mid = (p + q) / 2;
    if (matrix[i][mid] == x)
      return -10;
    else if (matrix[i][mid] > x) // go up
      q = mid - 1;
    else
      p = mid + 1;
  }
  return q;
}

 

 

没啥可说的,对于每个cell,如过和word的开头字母一致,就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。

要点:之前做的是直接

  // left, right, up, down
  return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
  || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);

这样就挂了!因为往左走的一路已经Update visited[][]了,然后没人去undo它,往右走的一支就直接拿来用了,不就乱套了么!所以在mark true的时候,函数结尾给undo一下,就可以保证一对儿出现,路径在反上来的被清理。

public boolean exist(char[][] board, String word) {
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
      if (board[i][j] == word.charAt(0)) {
        boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
        if (found)
          return true;
      }
    }
  }
  return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
  if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
    return false;
  if (board[i][j] != word.charAt(index) || visited[i][j])
    return false;
  visited[i][j] = true;
  if (index == word.length() - 1)
    return true;
  // left, right, up, down
  boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
                || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
  visited[i][j] = false;//这样就能保证每次true的能给false回来
  return found;
}

这个题好像就没一次做对过。实在是,太绕了太绕了太绕了。二维数组的上下左右index能把人活活烦死。出现的多次失误:

  1. 只转了四个角(主要在于i的物理意义没弄清)
  2. 每个边转了整个长度而不是长度-1(这样四角就会一直转来转去)
  3. 没搞清left, right, up, bottom怎么用layer和index表示。一个检查写的对不对的方法:记住
    1. upper说明i不变(depend on constant layer), j在从小到大变动(从左往右)
    2. left说明j不变(一直是最小值,因为靠左),i在从大到小的变动(从下往上)
    3. bottom说明i不变(一直是最大的),j在从大到小变动(从右往左)
    4. right说明j不变(一直是最大的),i在从大到小变动(从上往下)
public void rotate(int[][] matrix) {
  int len = matrix[0].length;
  for (int layer = 0; layer < len / 2; layer++) {
    for (int i = layer; i < len - 1 - layer; i++) {
      // save upper
      int temp = matrix[layer][i];
      // upper = left
      matrix[layer][i] = matrix[len - 1 - i][layer];
      // left = bottom
      matrix[len - 1 - i][layer] = matrix[len - 1 - layer][len - 1 - i];
      // bottom = right
      matrix[len - 1 - layer][len - 1 - i] = matrix[i][len - 1 - layer];
      // right = up
      matrix[i][len - 1 - layer] = temp;
    }
  }
}

十月份重做,还是没做出来。不知道为什么大家都觉得这个题简单,我个人认为这是CC150最难的3道题之一。别的难题都是理解了下次就做出来了,这题是理解了再做5遍还是做不出来。
和spiral matrix的区别:那道题是大大卷那种,spiral的,这个是一层一层的,上一层和这一层没关系。

这题做了好几遍了,(尽管每次都有进步)但是因为一直用的二维数组char[][] board,到leetcode上跑才发现超时。问题出现在算“对角能不能放”的时候,因为char[][]要遍历才能知道之前都在哪些位置放了皇后,所以多花了遍历的时间。书上的算法是用int[] queenColAtRow,这样queenColAtRow[i]就表示“在第i行,把queen放在了result位置上“。这样可以直接O(1)的知道每行queen都放在哪列了,少遍历一维,大的就过了。

public int totalNQueens(int n) {
  ArrayList<String[]> solveNQueens = solveNQueens(n);
  return solveNQueens.size();
}
public ArrayList<String[]> solveNQueens(int n) {
  //生成全是.的board,因为要返回board本身,所以现在先填好了。
  char[][] board = new char[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      board[i][j] = '.';
    }
  }
  ArrayList<String[]> result = new ArrayList<String[]>();
  placeQueen(board, 0, n, result);
  return result;
}
private void placeQueen(char[][] board, int row, int n, ArrayList<String[]> result) {
  if (row == n) {
    result.add(copyBoard(board));
    return;
  }
  for (int col = 0; col < n; col++) {
    if (canPlace(board, row, col)) {
      board[row][col] = 'Q';
      placeQueen(board, row + 1, n, result);
      board[row][col] = '.';
    }
  }
}
private boolean canPlace(char[][] board, int row, int col) {
  // row is definitely fine
  for (int i = 0; i <= row; i++) {
    if (board[i][col] == 'Q')
      return false;
  }
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < board.length; j++) {
      if (board[i][j] == 'Q' && Math.abs(i - row) == Math.abs(j - col))
      return false;
    }
  }
  return true;
}
Tags: , ,