algorithm004-02 · wangmy · Nov 4, 2019 · Nov 4, 2019 · Nov 4, 2019 · Nov 17, 2019
diff --git a/Week 01/id_502/LeetCode_1_502.java b/Week 01/id_502/LeetCode_1_502.java
@@ -0,0 +1,13 @@
+class Solution {
+    public int[] twoSum(int[] nums, int target) {
+        for (int i = 0; i < nums.length; i++) {
+            int other = target - nums[i];
+            for (int j=i+1;j<nums.length;j++) {
+                if(other == nums[j]) {
+                    return new int[]{i,j};
+                }
+            }
+        }
+        return new int[]{};
+    }
+}
diff --git a/Week 01/id_502/LeetCode_283_502.java b/Week 01/id_502/LeetCode_283_502.java
@@ -0,0 +1,16 @@
+class Solution {
+    public void moveZeroes(int[] nums) {
+
+        int j = -1;
+
+        for(int i = 0; i < nums.length; i++){
+            if(nums[i] != 0){
+                j++;
+                int temp = nums[i];
+                nums[i] = nums[j];
+                nums[j] = temp;
+
+            }
+        }
+    }
+}
diff --git a/Week 01/id_502/NOTE.md b/Week 01/id_502/NOTE.md
@@ -1,4 +1,11 @@
 # NOTE
+**Array**：连续空间，访问很快，但是删除和插入比较慢
 
+于是就有了**LinkedList**，删除和插入很快
+Insert：两次操作，但都是O(1)
 
-
+**跳表**
+由于链表访问时间复杂度O(n)
+加速中心思想：**升维、空间换时间** 
+多增加一些指针。
+**添加索引**
diff --git a/Week 02/id_502/LeetCode_429_502.java b/Week 02/id_502/LeetCode_429_502.java
@@ -0,0 +1,23 @@
+class Solution {
+    public List<List<Integer>> levelOrder(Node root) {
+        List<List<Integer>> res = new ArrayList<>();
+        if (root == null) return res;
+        Queue<Node> queue = new LinkedList<>();
+        queue.add(root);
+        while (!queue.isEmpty()) {
+            int count = queue.size();
+            List<Integer> list = new ArrayList<>();
+            while (count-- > 0) {
+                Node cur = queue.poll();
+                list.add(cur.val);
+                for (Node node : cur.children) {
+                    if (node != null) {
+                        queue.add(node);
+                    }
+                }
+            }
+            res.add(list);
+        }
+        return res;
+    }
+}
diff --git a/Week 02/id_502/LeetCode_77_502.java b/Week 02/id_502/LeetCode_77_502.java
@@ -0,0 +1,30 @@
+class Solution {
+
+    private ArrayList<List<Integer>> res;
+    private void generateCombinations(int n, int k, int start, List<Integer> list) {
+        if (list.size() == k) {
+            res.add(new ArrayList<>(list));
+            return;
+        }
+
+        for (int i = start; i <= n - (k - list.size()) + 1; i++) {
+            list.add(i);
+            generateCombinations(n, k, i + 1, list);
+            list.remove(list.size() - 1);
+
+        }
+    }
+
+    public List<List<Integer>> combine(int n, int k) {
+
+        res = new ArrayList<>();
+        if (n <= 0 || k <= 0 || k > n) {
+            return res;
+        }
+        List<Integer> list = new ArrayList<>();
+        generateCombinations(n, k, 1, list);
+
+        return res;
+
+    }
+}
diff --git a/Week 02/id_502/NOTE.md b/Week 02/id_502/NOTE.md
@@ -1,4 +1,6 @@
 # NOTE
-
+树的面试题解法一般都是递归，为什么？
+1. 树节点的定义
+2. 树结构的限制，并且每个子树都具有重复性
 
 
diff --git a/Week 03/id_502/LeetCode_153_502.java b/Week 03/id_502/LeetCode_153_502.java
@@ -0,0 +1,12 @@
+class Solution {
+    public int findMin(int[] nums) {
+        int left = 0;
+        int right = nums.length - 1;
+        while (left < right) {
+            int mid = left + (right - left) / 2;
+            if (nums[mid] > nums[right]) left = mid + 1;
+            else right = mid;
+        }
+        return nums[left];
+    }
+}
diff --git a/Week 03/id_502/LeetCode_200_502.java b/Week 03/id_502/LeetCode_200_502.java
@@ -0,0 +1,86 @@
+//DFS
+class Solution1 {
+    int[] dx = {0, 0, -1, 1}; // 上下左右
+    int[] dy = {-1, 1, 0, 0}; // 上下左右
+    public int numIslands(char[][] grid) {
+        if (grid.length == 0) {
+            return 0;
+        }
+        boolean[][] visit = new boolean[grid.length][grid[0].length];
+        int ret = 0;
+        for (int i = 0; i < grid.length; i++) {
+            for (int j = 0; j < grid[0].length; j++) {
+                if (!visit[i][j] && grid[i][j] == '1') {
+                    dfs(grid, visit, i, j);
+                    ret += 1;
+                }
+            }
+        }
+        return ret;
+    }
+
+    // 深度优先搜索
+    public void dfs(char[][] grid, boolean[][] visit, int x, int y) {
+        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
+            return;
+        }
+        if (!visit[x][y] && grid[x][y] == '1') {
+            visit[x][y] = true;
+            for (int i = 0; i < 4; i++) {
+                dfs(grid, visit, x + dx[i], y + dy[i]);
+            }
+        }
+    }
+}
+
+//BFS
+class Solution2 {
+    int[] dx = {0, 0, -1, 1}; // 上下左右
+    int[] dy = {-1, 1, 0, 0}; // 上下左右<
2AFE
/span>
+    public int numIslands(char[][] grid) {
+        if (grid.length == 0) {
+            return 0;
+        }
+        boolean[][] visit = new boolean[grid.length][grid[0].length];
+        int ret = 0;
+        for (int i = 0; i < grid.length; i++) {
+            for (int j = 0; j < grid[0].length; j++) {
+                if (!visit[i][j] && grid[i][j] == '1') {
+                    bfs(grid, visit, i, j);
+                    ret += 1;
+                }
+            }
+        }
+        return ret;
+    }
+
+    // 广度优先搜索
+    public void bfs(char[][] grid, boolean[][] visit, int x, int y) {
+   
E0C2
     Queue<Pair> queue = new LinkedList<>();
+        queue.offer(new Pair(x, y));
+        visit[x][y] = true;
+        while (!queue.isEmpty()) {
+            Pair top = queue.poll();
+            for (int i = 0; i < 4; i++) {
+                int newX = top.x + dx[i];
+                int newY = top.y + dy[i];
+                if (newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length) {
+                    continue;
+                }
+                if (!visit[newX][newY] && grid[newX][newY] == '1') {
+                    queue.offer(new Pair(newX, newY));
+                    visit[newX][newY] = true;
+                }
+            }
+        }
+    }
+
+    static class Pair {
+        int x;
+        int y;
+        Pair(int x, int y) {
+            this.x = x;
+            this.y = y;
+        }
+    }
+}
diff --git a/Week 03/id_502/NOTE.md b/Week 03/id_502/NOTE.md
@@ -1,4 +1,11 @@
 # NOTE
 
-
+* 树的深度优先，一个个子树遍历
+* 树的广度优先，一层层扩散，像水波、地震波
 
+**什么时候可以用贪心？**
+* 问题可以分解成子问题
+* 子问题最优解能递推到最终问题的最优解
+
+贪心对每个子问题的解决方案都做出选择，不能回退。
+动态规划会保存以前的运算结果，并根据当前结果对当前进行选择，支持回退。
diff --git a/Week 05/id_502/LeetCode_32_502.py b/Week 05/id_502/LeetCode_32_502.py
@@ -0,0 +1,45 @@
+
+#最长有效括号
+# 暴力解决：每次取偶数个，时间复杂度：n^2
+
+def isValidParentheses(s: str) -> bool:
+    stack = []
+    for i in range(len(s)):
+        if s[i] == "(":
+            stack.append("(")
+        elif len(stack) > 0:
+            stack.pop()
+        else:
+            return False
+    return (len(stack) == 0)
+
+def longestValidParentheses_recursion(s: str) -> int:
+        if not s or len(s) <= 0:
+            return 0
+        res = 0
+
+        for i in range(len(s)):
+            for j in range(i+2,len(s)+1, 2):
+                if (isValidParentheses(s[i:j])):
+                    res = max(res, j-i)
+
+        return res
+
+
+#DP 解决
+def longestValidParentheses_dp(s: str) -> int:
+        n = len(s)
+        if n <= 1: return 0
+        dp = [0] * n
+        res = 0
+        for i in range(n):
+            if i>0 and s[i] == ")":
+                if  s[i - 1] == "(":
+                    dp[i] = dp[i - 2] + 2
+                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
+                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
+            res = max(res,dp[i])
+        return res
+
+print("recursion:"+str(longestValidParentheses_recursion("(())()")))
+print("dp:"+str(longestValidParentheses_dp("(())()")))
diff --git a/Week 05/id_502/LeetCode_403_502.java b/Week 05/id_502/LeetCode_403_502.java
@@ -0,0 +1,32 @@
+public class Solution {
+    public boolean canCross(int[] stones) {
+        int[][] memo = new int[stones.length][stones.length];
+        for (int[] row : memo) {
+            Arrays.fill(row, -1);
+        }
+        return can_Cross(stones, 0, 0, memo) == 1;
+    }
+    public int can_Cross(int[] stones, int ind, int jumpsize, int[][] memo) {
+        if (memo[ind][jumpsize] >= 0) {
+            return memo[ind][jumpsize];
+        }
+
+        int ind1 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize);
+        if (ind1 >= 0 && can_Cross(stones, ind1, jumpsize, memo) == 1) {
+            memo[ind][jumpsize] = 1;
+            return 1;
+        }
+        int ind2 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize - 1);
+        if (ind2 >= 0 && can_Cross(stones, ind2, jumpsize - 1, memo) == 1) {
+            memo[ind][jumpsize - 1] = 1;
+            return 1;
+        }
+        int ind3 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize + 1);
+        if (ind3 >= 0 && can_Cross(stones, ind3, jumpsize + 1, memo) == 1) {
+            memo[ind][jumpsize + 1] = 1;
+            return 1;
+        }
+        memo[ind][jumpsize] = ((ind == stones.length - 1) ? 1 : 0);
+        return memo[ind][jumpsize];
+    }
+}
diff --git a/Week 05/id_502/NOTE.md b/Week 05/id_502/NOTE.md
@@ -1,4 +1,9 @@
 # NOTE
+DP 问题的思路：
+1. 寻找子问题，要多尝试自底向上分解问题
+2. 状态定义
+    这里的状态定义即是定义初始值
+3. DP 方程
 
 
 
diff --git a/Week 06/id_502/LeetCode_127_502.java b/Week 06/id_502/LeetCode_127_502.java
@@ -0,0 +1,37 @@
+class Solution {
+    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
+        Set<String> wordSet = new HashSet<>(wordList.size());
+        wordSet.addAll(wordList);
+        if (!wordSet.contains(endWord)) return 0;
+        Set<String> s1 = new H
8020
ashSet<>();
+        Set<String> s2 = new HashSet<>();
+        s1.add(beginWord);
+        s2.add(endWord);
+        int n = beginWord.length();
+        int step = 0;
+        while (!s1.isEmpty() && !s2.isEmpty()) {
+            step++;
+            if (s1.size() > s2.size()) {
+                Set<String> tmp = s1;
+                s1 = s2;
+                s2 = tmp;
+            }
+            Set<String> s = new HashSet<>();
+            for (String word : s1) {
+                for (int i = 0; i < n; i++) {
+                    char[] chars = word.toCharArray();
+                    for (char ch = 'a'; ch <= 'z'; ch++) {
+                        chars[i] = ch;
+                        String tmp = new String(chars);
+                        if (s2.contains(tmp)) return step + 1;
+                        if (!wordSet.contains(tmp)) continue;
+                        wordSet.remove(tmp);
+                        s.add(tmp);
+                    }
+                }
+            }
+            s1 = s;
+        }
+        return 0;        
+    }
+}
diff --git a/Week 06/id_502/LeetCode_36_502.java b/Week 06/id_502/LeetCode_36_502.java
@@ -0,0 +1,32 @@
+class Solution {
+    public boolean isValidSudoku(char[][] board) {
+        for(int i = 0; i < 9; i ++){
+            // hori, veti, sqre分别表示行、列、小宫
+            int hori = 0, veti = 0, sqre = 0;
+            for(int j = 0; j < 9; j ++){
+                // 由于传入为char，需要转换为int，减48
+                int h = board[i][j] - 48;
+                int v = board[j][i] - 48;
+                int s = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3] - 48;
+                // "."的ASCII码为46，故小于0代表着当前符号位"."，不用讨论
+                if(h > 0){
+                    hori = sodokuer(h, hori);
+                }
+                if(v > 0){
+                    veti = sodokuer(v, veti);
+                }
+                if(s > 0){
+                    sqre = sodokuer(s, sqre);
+                }
+                if(hori == -1 || veti == -1 || sqre == -1){
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    private int sodokuer(int n, int val){
+        return ((val >> n) & 1) == 1 ? -1 : val ^ (1 << n);
+    }
+}