120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路: DP的经典题目,用Divide&Conquer的思路来实现,每走一步都有两个选择: 往下走跟往右走. 总体来说走下来时间复杂度有点高为O(2^n). 简单写一下用DFS实现分治的解法

public int miniPath(int[][] triangle) {
    return dfs(triangle, 0, 0);
}

public int dfs(int[][], triangle, int x, int y) {
    if (x == triangle.length - 1) {
        return 0;
    }
    int left = dfs(triangle, x + 1, y);
    int right = dfs(triangle, x + 1, y + 1);
    return Math.min(left, right) + triangle[x][y];
}

同时给下traverse的思路:

//traverse
public void dfs(int[][] triangle, int x, int y, int sum) {
    if (x == triangle.length) {
        if (sum <  miniSum) {
            miniSum = sum;
        }
        return;
    }
    dfs(triangle, x + 1, y, sum + triangle[x][y]);
    dfs(triangle, x + 1, y + 1, sum + triangle[x][y]);
}

DFS过程中, 很多点被重复计算,导致时间复杂度特别高,我们可以加cache来降低时间复杂度.
把时间复杂度降到O(n^2).

class Point {
   int x;
   int y; 
   public Point(int x, int y) {
       this.x = x;
       this.y = y;
   }
}
public int dfs(int[][], triangle, Point point, HashMap<Point, Integer> map) {
    if (point.x == triangle.length - 1) {
        return 0;
    }
    if (map.containsKey(point)) {
        return map.get(point);
    }
    int left = dfs(triangle, point.x + 1, point.y);
    int right = dfs(triangle, point.x + 1, point.y + 1);
    Point newValue =  Math.min(left, right) + triangle[point.x][point.y];
    map.put(point, newValue);
    return map.get(point);
}

我们还可以用循环DP的方式来解决这个问题:
1. Down -> Top approach
2. Top-> Down approach
对于这个题目,如果我们从底部往上开始走,每层取最小值,

1. Down -> Top approach

// 状态定义
f[i][j] 用来表示i,j出发走到最后一层的最小路径长度
n = triangle.length;
// 初始化数组
for (int i = 0; i < n; i++) {
    f[n-1][i] = triangle[n-1][i];
}
// 循环递归求解
for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
    }
}
// 求结果: 起点
f[0][0]

2. Top-> Down approach

对于本题,自顶向下的方法略复杂些,主要是因为要check一些边界条件:

// 状态定义
f[i][j] 用来表示0,0出发,走到i,j的最小路径长度
n = triangle.length;
// 初始化
f[0][0] = triangle[0][0]

// 循环递归求解
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
        f[i][j] = OO
        if(i - 1, j 存在) {
            f[i][j] = Math.min(f[i][j], f[i-1][j]) + triangle[i][j];
        }
        if(i - 1, j - 1存在) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i][j]) + triangle[i][j]
        }
    }
}

// 求结果:
Math.min(f[n-1][0],f[n-1][1],f[n-1][2]…..);

DP的总结:

什么时候用DP来解呢? 一般有以下几个情况可以考虑用DP来做:
1. 求minimum或者maximum的问题
2. 求Yes/No的问题
3. 求个数(Count)的问题
4. 当给的条件不能sort或者swap的时候,可以考虑用DP

DP的四个要素

  1. 状态 State
  2. 转换方程Function
  3. 初始化(起点)
  4. 终点(答案)

大概面试中常见的DP类型

  1. MatrixDP(10%), 二维数组
  2. Sequence(40%), 一维数组
  3. Two Sequences DP(40%)
  4. Backpack(10%)
Advertisements

二维矩阵中Connected Cell问题(DFS)

HackerRank上面对Matrix中Connected Cell的模板, Leetcode中此类问题有island的个数,面积,surrounded regions等

dfs

public class Solution {
    public int getBiggestRegion(int[][] matrix) {
        int maxRegion = 0;
        int row = matrix.length, col = matrix[0].length;
        //boolean[][] visited = new boolean[row][col]; 

        for(int i = 0; i &lt; row; i++) {
            for (int j = 0; j &lt; col; j++) {
                if (matrix[i][j] == 1) { // 找到'1'岛屿
                    int size = getRegionSize(matrix, i, j);
                    maxRegion = Math.max(size, maxRegion);
                }
            }
        }
        return maxRegion;
    }

    public int getRegionSize(int[][] matrix, int row, int col) {
        // 1. boundary checks
        if (row &lt; 0 || col &lt; 0 || row &gt;= matrix.length || col &gt;= matrix.length){
            return 0;
        }
        // 2. check if it is the region
        if (matrix[row][col] == 0) {
            return 0;
        }
        matrix[row][col] = 0; // visited check, 也可以用一个visited数组来实现
        int size = 1; // initialize size is 1
        // explore 4 directions: left, right, up, down
        public int[] rowDir = new int[]{-1, 0, 1, 0};
        public int[] colDir = new int[]{0, -1, 0, 1};
        for (int i = 0; i &lt; 4; i++) {
            int newRow = row + rowDir[i];
            int newCol = col + colDir[i];
            if (newRow == row || newCol == col) continue; // 避免搜索自己
            size += getRegionSize(matrix, newRow, newCol);
        }
        matrix[row][col] = 1; // 搜索完了, 赋原有值
        return size;
    }


}

DFS四个方向搜索的时候,另一种写法

for (int r = row - 1; r &lt;= row + 1; r++) {
    for (int c = col - 1: c &lt;= col + 1; c++) {

    }
}

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

思路: 用的BFS来做的, 先从边界条件寻找’O’, 把边界条件的O用BFS来找到的都不满足被X包围的条件,替换为’Y’,然后剩下图里的O 都满足被X包围的条件,直接替换为X; 最后再把边界的‘Y’替换回‘0’.

public class Solution {
    int[] xDir = new int[]{-1, 0, 1, 0};
    int[] yDir = new int[]{0, 1, 0, -1};
    public void solve(char[][] board) {
        if (board == null || board[0] == null 
         || board.length &lt; 3 || board[0].length &lt; 3 ) return;
        fillBoards(board, 'O', 'Y');
        solve(board, 'O', 'X');
        fillBoards(board, 'Y', 'O');
    }

    public void solve(char[][] board, char target, char c) {
        for (int i = 0; i &lt; board.length; i++) {
            for (int j = 0; j &lt; board[0].length; j++) {
                if (board[i][j] == target) {
                    board[i][j] = c;
                }
            }
        }
    }

    public void fill(char[][] board, int x, int y, char target, char c) {
        if (x &lt; 0 || x &gt;= board.length || y &lt; 0 || y &gt;= board[0].length || board[x][y] != target) return;
        board[x][y] = c;
        for(int i = 0; i &lt; 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            fill(board, newX, newY, target, c);
        }
    }

    public void fillBoards(char[][] board, char target, char c) {
        int row = board.length - 1;
        int col = board[0].length - 1;
        for (int i = 0; i &lt;= row; i++) {
            if (board[i][0] == target) fill(board, i, 0, target, c);
            if (board[i][col] == target) fill(board, i, col, target,c);
        }

        for (int j = 0; j &lt;= row; j++) {
            if (board[0][j] == target) fill(board, 0, j, target, c);
            if (board[row][j] == target) fill(board, row, j, target, c);
        }
    }


}

286.Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

思路: 求矩阵中room到gate的最短距离这个题目用DFS 比较快。
DFS: 找的时候如果当前点的值大于idx的值,就是符合条件的点。
复杂度: 时间 MN4^K, 空间 4^N

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
        for (int i = 0; i &lt; rooms.length; i++) {
            for (int j = 0; j &lt; rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    dfs(rooms, i, j, 0);
                }
            }
        }
    }

    public void dfs(int[][] rooms, int x, int y, int idx) {
        if (x &lt; 0 || x &gt;= rooms.length || y &lt; 0 || y &gt;= rooms[0].length || rooms[x][y] &lt; idx) return;
        rooms[x][y] = idx;
        dfs(rooms, x + 1, y, idx + 1);
        dfs(rooms, x - 1, y, idx + 1);
        dfs(rooms, x, y + 1, idx + 1);
        dfs(rooms, x, y - 1, idx + 1);
    }
}

BFS的解

public class Solution {
    public class Point {
        int x;
        int y;
        int prevPos;
        public Point(int x, int y, int prevPos) {
            this.x = x;
            this.y = y;
            this.prevPos = prevPos;
        }
    }
    public int[] xDir = new int[]{-1, 0 , 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};

    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
        for (int i = 0; i &lt; rooms.length; i++) {
            for (int j = 0; j &lt; rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    bfs(rooms, i, j);
                }
            }
        }
    }

    public void bfs(int[][] rooms, int x, int y) {
        if (x &lt; 0 || x &gt;= rooms.length || y &lt; 0 || y &gt;= rooms[0].length) return;
        ArrayDeque&lt;Point&gt; queue = new ArrayDeque&lt;&gt;();
        queue.offer(new Point(x, y, 0)); // add the start point to the queue
        while(!queue.isEmpty()) {
            Point point = queue.pop(); // dequeue and check 

            // explore 4 directions
            for (int i = 0; i &lt; 4; i++) {
                int newX = point.x + xDir[i];
                int newY = point.y + yDir[i];
                Point newPoint = new Point(newX, newY, point.prevPos);
                if (shouldExplore(newPoint, rooms)) {
                    newPoint.prevPos += 1;
                    rooms[newX][newY] = newPoint.prevPos;
                    queue.offer(newPoint);
                }
            }
        }
    }

    public boolean shouldExplore(Point p, int[][] rooms) {
        if (p.x &lt; 0 || p.x &gt;= rooms.length || p.y &lt; 0 || p.y &gt;= rooms[0].length || rooms[p.x][p.y] &lt; p.prevPos || rooms[p.x][p.y] == -1 ) return false;
        return true;
    }
}