XIAOLONG LI - Leetcode

Leetcode

Leetcode Questions patterns

clarification -> brute force + Big O -> optimal solution + Big O -> manual test in (45 minutes)

Pattern 0: Array & Hashing

Pure Array problems... the most fundamentals

217. Contains Duplicate

242. Valid Anagram

Pattern 1: Two pointers

1) left = 0, right = len(list) - 1

2) left = 0, right = 0

125. Valid Palindrome

Pattern 2: Sliding windows

Window size keep adding on the right,(right += 1) until we face a blocker,

then we remove the left edge of the window, and left += 1

Pattern 3: Next Greater Element

Here：

总结：

机器人从左上角走到最右下角，一共多少走法。

解法一递归

（0，0） ->（m-1，n-1）= （1，0） ->（m-1，n-1）+ （0，1）->（m-1，n-1）（1，0） ->（m-1，n-1） = （1，1）->（m-1，n-1） + （2，0）->（m-1，n-1（0，1）->（m-1，n-1）= （1，1）->（m-1，n-1）+ （0，2）->（m-1，n-1）。。。等等递归下去一直到（m-1，n-1）返回 1。
class Solution { int count; public int uniquePaths(int m, int n) { count = 0; DFS(0, 0, m, n); return count; } private void DFS(int i, int j, int m, int n) { if(i >= m || j >= n ) return; if(i == m - 1 && j == n - 1) { count++; } DFS(i + 1, j, m, n); DFS(i, j + 1, m, n); }}

解法二 DP (bottomUP)

如果只有一行，那就一个路径如果只有一列，那就只有一个路径所以首先填满最后一列和最后一行全是1
现在从m-2 和 n-2开始填满grid 从那里有可以向右，向下走，可以到终点
for(int i = m - 2; i >= 0; i--) for(int j = n - 2; j >= 0; j--) dp[i][j] = dp[i + 1][j] + dp[i][j + 1]; // how many ways got herereturn dp[0][0];

解法三 DP (bottomDown)

如果只有一行，那就一个路径如果只有一列，那就只有一个路径所以首先填满第一列和第一行全是1到 1 行 1列开始有多少路径
for(int i = 1;i < m; i++) for(int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // how many ways got herereturn dp[m - 1][n - 1];

思路：跟上题解法类似，算出第一行和第一列的值，然后加上以后的值（找出小的）

int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; for(int i = 1; i < m; i++) { grid[i][0] = grid[i - 1][0] + grid[i][0]; }
for(int i = 1; i < n; i++) { grid[0][i] = grid[0][i - 1] + grid[0][i]; }
for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m-1][n-1]; }

思路：其实很简单。iterate 2d Array 的每个element，当遇到1的时候，用DFS把周围的1都变成 '#' 或者 0，这样我们就不会在碰到它一会儿另个途径来run 的时候.然后每次数多少个dfs过了，那就是几个岛

public class solution { public int numIsland(char[][] grid) { int island = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length;j++) { if(grid[i][j] == '1') { DFS(grid, i, j); island++; } } } return island; } private static void DFS(char[][] grid, int row, int col) { if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != 1) { return; } grid[row][col] == '#'; DFS(grid, i + 1, j); DFS(grid, i, j + 1); DFS(grid, i - 1, j); DFS(grid, i, j - 1); }}

BFS: 主要思路是用一个queue 存储，然后用一个flag （visited）来表明是否去过这点

public class solution { public int numIsland(char[][] grid) { int island = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length;j++) { if(grid[i][j] == '1') { BFS(grid, i, j); island++; } } } } private static void BFS(char[][]grid, int i, int j) { if(i < 0 || i > grid.length || j < 0 || j > grid[0].length || grid[i][j] != '1') { return; } grid[i][j] = '#'; Queue<Integer> row = new LinkedList<>(); Queue<Integer> col = new LinkedList<>(); row.offer(i); col.offer(j); while(!row.isEmpty()) { int a = row.poll(); int b = col.poll(); BFS(grid, a + 1, b); BFS(grid, a, b + 1); BFS(grid, a - 1, b); BFS(grid, a, b - 1); } }}