algorithm007-class02 · qiuxiaoye · Apr 5, 2020 · Apr 19, 2020 · Apr 26, 2020 · May 3, 2020
diff --git a/Week_03/.DS_Store b/Week_03/.DS_Store
diff --git a/Week_04/.DS_Store b/Week_04/.DS_Store
diff --git a/Week_04/G20200447010102/122.买卖股票的最佳时机-ii.java b/Week_04/G20200447010102/122.买卖股票的最佳时机-ii.java
@@ -0,0 +1,20 @@
+/*
+ * @lc app=leetcode.cn id=122 lang=java
+ *
+ * [122] 买卖股票的最佳时机 II
+ */
+
+// @lc code=start
+class Solution {
+    public int maxProfit(int[] prices) {
+        int result = 0;
+        for (int i = 0; i < prices.length - 1; i++) {
+            if (prices[i + 1] > prices[i]) {
+                result += prices[i + 1] - prices[i];
+            }
+        }
+        return result;
+    }
+}
+// @lc code=end
+
diff --git a/Week_04/G20200447010102/200.岛屿数量.java b/Week_04/G20200447010102/200.岛屿数量.java
@@ -0,0 +1,40 @@
+/*
+ * @lc app=leetcode.cn id=200 lang=java
+ *
+ * [200] 岛屿数量
+ */
+
+// @lc code=start
+class Solution {
+
+    private int m;
+    private int n;
+
+    public int numIslands(char[][] grid) {
+        int result = 0;
+        n = grid.length;
+        if (n == 0) return 0;
+        m = grid[0].length;
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++) {
+                if (grid[i][j] == '1') {
+                    islandMarking(grid, i, j);
+                    ++result;
+                }
+            }
+        }
+        return result;
+    }
+
+    private void islandMarking(char[][] gird, int i, int j) {
+        if (i < 0 || j < 0 || i >= n || j >= m || gird[i][j] != '1') return;
+        gird[i][j] = '0';
+        islandMarking(gird, i + 1, j);
+        islandMarking(gird, i - 1, j);
+        islandMarking(gird, i, j + 1);
+        islandMarking(gird, i, j - 1);
+    }
+}
+// @lc code=end
+
diff --git a/Week_04/G20200447010102/33.搜索旋转排序数组.java b/Week_04/G20200447010102/33.搜索旋转排序数组.java
@@ -0,0 +1,32 @@
+/*
+ * @lc app=leetcode.cn id=33 lang=java
+ *
+ * [33] 搜索旋转排序数组
+ */
+
+// @lc code=start
+class Solution {
+    public int search(int[] nums, int target) {
+        int left = 0;
+        int right = nums.length - 1;
+        while (left < right) {
+            int mid = (left + right) / 2;
+            if (nums[mid] > nums[right]) left = mid + 1;
+            else right = mid;
+        }
+
+        int rot = left;
+        left = 0;
+        right =  nums.length - 1;
+        while (left <= right) {
+            int mid = (left + right) / 2;
+            int realMid = (mid + rot) % nums.length;
+            if (nums[realMid] == target) return realMid;
+            if (nums[realMid] < target) left = mid + 1;
+            else right =  mid -1;
+        }
+        return -1;
+    }
+}
+// @lc code=end
+
diff --git a/Week_04/G20200447010102/433.最小基因变化.java b/Week_04/G20200447010102/433.最小基因变化.java
@@ -0,0 +1,14 @@
+/*
+ * @lc app=leetcode.cn id=433 lang=java
+ *
+ * [433] 最小基因变化
+ */
+
+// @lc code=start
+class Solution {
+    public int minMutation(String start, String end, String[] bank) {
+
+    }
+}
+// @lc code=end
+
diff --git a/Week_04/G20200447010102/860.柠檬水找零.java b/Week_04/G20200447010102/860.柠檬水找零.java
@@ -0,0 +1,22 @@
+/*
+ * @lc app=leetcode.cn id=860 lang=java
+ *
+ * [860] 柠檬水找零
+ */
+
+// @lc code=start
+class Solution {
+    public boolean lemonadeChange(int[] bills) {
+        int five = 0, ten = 0;
+        for (int i : bills) {
+            if (i == 5) five++;
+            else if (i == 10) { five--; ten++; }
+            else if (ten > 0) { ten--; five--; }
+            else five -= 3;
+            if (five < 0) return false;
+        }
+        return true;
+    }
+}
+// @lc code=end
+
diff --git a/Week_06/G20200447010102/221.最大正方形.java b/Week_06/G20200447010102/221.最大正方形.java
@@ -0,0 +1,14 @@
+/*
+ * @lc app=leetcode.cn id=221 lang=java
+ *
+ * [221] 最大正方形
+ */
+
+// @lc code=start
+class Solution {
+    public int maximalSquare(char[][] matrix) {
+
+    }
+}
+// @lc code=end
+
diff --git a/Week_06/G20200447010102/621.任务调度器.java b/Week_06/G20200447010102/621.任务调度器.java
@@ -0,0 +1,34 @@
+/*
+ * @lc app=leetcode.cn id=621 lang=java
+ *
+ * [621] 任务调度器
+ */
+
+// @lc code=start
+class Solution {
+    public int leastInterval(char[] tasks, int n) {
+        int[] counter = new int[26];
+        int max = 0;
+        int maxCount = 0;
+        for(char task : tasks) {
+            counter[task - 'A']++;
+            if(max == counter[task - 'A']) {
+                maxCount++;
+            }
+            else if(max < counter[task - 'A']) {
+                max = counter[task - 'A'];
+                maxCount = 1;
+            }
+        }
+
+        int partCount = max - 1;
+        int partLength = n - (maxCount - 1);
+        int emptySlots = partCount * partLength;
+        int availableTasks = tasks.length - max * maxCount;
+        int idles = Math.max(0, emptySlots - availableTasks);
+
+        return tasks.length + idles;
+    }
+}
+// @lc code=end
+
diff --git a/Week_06/G20200447010102/64.最小路径和.java b/Week_06/G20200447010102/64.最小路径和.java
@@ -0,0 +1,34 @@
+/*
+ * @lc app=leetcode.cn id=64 lang=java
+ *
+ * [64] 最小路径和
+ */
+
+// @lc code=start
+class Solution {
+    public int minPathSum(int[][] grid) {
+        if (grid == null || grid.length == 0) return 0;
+
+        int m = grid[0].length;
+        int n = grid.length;
+        int[][] dp = new int[n][m];
+        for (int i = n - 1; i >= 0; i--) {
+            for (int j = m -1; j >= 0; j--) {
+                if (i == n - 1 && j != m - 1) {
+                    dp[i][j] = grid[i][j] + dp[i][j + 1];
+                }
+                else if (i != n - 1 && j == m - 1) {
+                    dp[i][j] = grid[i][j] + dp[i + 1][j];
+                }
+                else if (i != n - 1 && j != m - 1) {
+                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
+                } else {
+                    dp[i][j] = grid[i][j];
+                }
+            }
+        }
+        return dp[0][0];
+    }
+}
+// @lc code=end
+
diff --git a/Week_06/G20200447010102/91.解码方法.java b/Week_06/G20200447010102/91.解码方法.java
@@ -0,0 +1,28 @@
+/*
+ * @lc app=leetcode.cn id=91 lang=java
+ *
+ * [91] 解码方法
+ */
+
+// @lc code=start
+class Solution {
+    public int numDecodings(String s) {
+        if (s == null || s.length() == 0) return 0;
+        int n = s.length();
+        int[] dp = new int[n];
+        dp[0] = s.charAt(0) != '0' ? 1 : 0;
+        for (int i = 1; i < n; i++) {
+            int first = Integer.valueOf(s.substring(i, i + 1));
+            int second = Integer.valueOf(s.substring(i - 1, i + 1));
+            if (first >= 1 && first <= 9) {
+                dp[i] += dp[i - 1];
+            }
+            if (second >= 10 && second <= 26) {
+                dp[i] += i >= 2 ? dp[i - 2] : 1;
+            }
+        }
+        return dp[n - 1];
+    }
+}
+// @lc code=end
+
diff --git a/Week_07/G20200343040102/127.单词接龙.java b/Week_07/G20200343040102/127.单词接龙.java
@@ -0,0 +1,50 @@
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/*
+ * @lc app=leetcode.cn id=127 lang=java
+ *
+ * [127] 单词接龙
+ */
+
+// @lc code=start
+class Solution {
+    public int ladderLength(String beginWord, String endWord, List<String> wordAsList) {
+        if(!wordAsList.contains(endWord)) return 0;
+
+        Set<String> wordList = new HashSet<String>(wordAsList);
+        Set<String> start = new HashSet<String>();
+        Set<String> end = new HashSet<String>();
+        int length = 1;
+        start.add(beginWord); end.add(endWord);
+        wordList.remove(beginWord); wordList.remove(endWord);
+
+        while(!start.isEmpty()){
+            Set<String> next = new HashSet<String>();
+            for(String word: start){
+                char[] wordArray = word.toCharArray();
+                for(int i=0; i<word.length(); i++){
+                    char old = wordArray[i];
+                    for(char c='a'; c<='z'; c++){
+                        wordArray[i] = c;
+                        String str = String.valueOf(wordArray);
+                        if(end.contains(str))
+                            return length+1;
+                        if(wordList.contains(str)){
+                            next.add(str);
+                            wordList.remove(str);
+                        }
+                    }
+                    wordArray[i] = old;
+                }
+            }
+            start = next.size() < end.size() ? next: end;
+            end = start.size() < end.size() ? end : next;
+            length++;
+        }
+        return 0;
+    }
+}
+// @lc code=end
+
diff --git a/Week_07/G20200343040102/547.朋友圈.java b/Week_07/G20200343040102/547.朋友圈.java
@@ -0,0 +1,29 @@
+/*
+ * @lc app=leetcode.cn id=547 lang=java
+ *
+ * [547] 朋友圈
+ */
+
+// @lc code=start
+class Solution {
+    public void dfs(int[][] M, int i) {
+        for (int j = 0; j < M.length; j++) {
+            if (M[i][j] == 1) {
+                M[i][j] = M[j][i] = 0;
+                dfs(M, j);
+            }
+        }
+    }
+    public int findCircleNum(int[][] M) {
+        int count = 0;
+        for (int i = 0; i < M.length; i++) {
+            if (M[i][i] == 1) {
+                dfs(M, i);
+                count++;
+            }
+        }
+        return count;
+    }
+}
+// @lc code=end
+
diff --git a/Week_07/G20200343040102/70.爬楼梯.java b/Week_07/G20200343040102/70.爬楼梯.java
@@ -0,0 +1,59 @@
+/*
+ * @lc app=leetcode.cn id=70 lang=java
+ *
+ * [70] 爬楼梯
+ *
+ * https://leetcode-cn.com/problems/climbing-stairs/description/
+ *
+ * algorithms
+ * Easy (48.03%)
+ * Likes:    869
+ * Dislikes: 0
+ * Total Accepted:    147.3K
+ * Total Submissions: 306.6K
+ * Testcase Example:  '2'
+ *
+ * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
+ * 
+ * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
+ * 
+ * 注意：给定 n 是一个正整数。
+ * 
+ * 示例 1：
+ * 
+ * 输入： 2
+ * 输出： 2
+ * 解释： 有两种方法可以爬到楼顶。
+ * 1.  1 阶 + 1 阶
+ * 2.  2 阶
+ * 
+ * 示例 2：
+ * 
+ * 输入： 3
+ * 输出： 3
+ * 解释： 有三种方法可以爬到楼顶。
+ * 1.  1 阶 + 1 阶 + 1 阶
+ * 2.  1 阶 + 2 阶
+ * 3.  2 阶 + 1 阶
+ * 
+ * 
+ */
+
+// @lc code=start
+class Solution {
+    public int climbStairs(int n) {
+        if (n < 2) {
+            return n;
+        } 
+        int first = 1;
+        int second = 2;
+        for (int i = 3; i <= n; i++) {
+            int third = first + second;
+            first = second;
+            second = third;
+        }
+        return second;
+    }
+}
+// @lc code=end
+