Week04 Home Work

MrFreezing · MrFreezing · commit 00b78b17d0f5 · 2020-07-04T02:34:02.000+08:00
diff --git a/Week04/LeetCodes/122_Best_Time_to_Buy_and_Sell_Stock_II.cpp b/Week04/LeetCodes/122_Best_Time_to_Buy_and_Sell_Stock_II.cpp
@@ -0,0 +1,10 @@
+class Solution {
+public:
+    int maxProfit(vector<int>& prices) {
+        int max = 0;
+        for (int i = 1; i < prices.size(); i++) 
+            if (prices[i] > prices[i-1]) 
+                max += prices[i] - prices[i-1];
+        return max;
+    }
+};
diff --git a/Week04/LeetCodes/127_Word_Ladder.cpp b/Week04/LeetCodes/127_Word_Ladder.cpp
@@ -0,0 +1,37 @@
+class Solution {
+public:
+    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
+        if (beginWord.empty() || endWord.empty() || wordList.size() == 0) return 0;
+        if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
+
+        vector<int> visited(wordList.size(), 0);
+        queue<string> q;
+        q.push(beginWord);
+        int step = 1;
+
+        while(q.size()) {
+            step++;
+            int len = q.size();
+            for (int k = 0; k < len; k++) {
+                string tmp = q.front();
+                q.pop();
+
+                for (int i = 0; i < wordList.size(); i++) {
+                    if (visited[i] == 0) {
+                        int diff = 0;
+                        for (int j = 0; j < tmp.length(); j++) 
+                            if (tmp[j] != wordList[i][j]) diff++;
+                        
+                        if (diff == 1) {
+                            if (wordList[i] == endWord) return step;
+                            visited[i] = 1;
+                            q.push(wordList[i]);
+                        }
+                    }
+                }
+            }
+        }
+
+        return 0;
+    }
+};
diff --git a/Week04/LeetCodes/153_Find_Minimum_in_Rotated_Sorted_Array.cpp b/Week04/LeetCodes/153_Find_Minimum_in_Rotated_Sorted_Array.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+    int findMin(vector<int>& nums) {
+        if (!nums.size()) return 0;
+        if (nums.size() == 1) return nums[0];
+        if (nums[0] < nums[nums.size() - 1] ) return nums[0];
+
+        int left = 0, right = nums.size() - 1;
+        while(left < right) {
+            if (left + 1 == right) return nums[right];
+            int mid = (left + right) / 2;
+            if (nums[mid - 1] > nums[mid]) return nums[mid];
+            else if (nums[mid] > nums[mid + 1]) return nums[mid + 1];
+            else if (nums[mid] < nums[right]) {//右侧有序
+                right = mid - 1;
+            } else {//左侧有序
+                left = mid + 1;
+            }
+        }
+
+        return 0;
+        
+    }
+};
diff --git a/Week04/LeetCodes/200_Number_of_Islands.cpp b/Week04/LeetCodes/200_Number_of_Islands.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+    int numIslands(vector<vector<char>>& grid) {
+        if (!grid.size() || !grid[0].size()) return 0; 
+        int lands = 0;
+        for (int i = 0; i < grid.size(); i++) 
+            for (int j = 0; j < grid[0].size(); j++) 
+                if (grid[i][j] == '1') {
+                    lands++;
+                    clear(i, j, grid);
+                }
+        return lands;
+    }
+    void clear(int row, int col, vector<vector<char>>& grid) {
+        if (grid[row][col] == '0') return;
+        grid[row][col] = '0';
+        if (col < grid[0].size() - 1) clear(row, col + 1, grid); //清理右边
+        if (row < grid.size() - 1) clear(row + 1, col, grid); //清理下边
+        if (col > 0) clear(row, col - 1, grid); //清理左边，有必要
+        if (row > 0) clear(row - 1, col, grid);//清理上边，好像没必要，因为调用是从上至下的，被一个S型用例整服了
+    }
+};
diff --git a/Week04/LeetCodes/33_Search_in_Rotated_Sorted_Array.cpp b/Week04/LeetCodes/33_Search_in_Rotated_Sorted_Array.cpp
@@ -0,0 +1,28 @@
+class Solution {
+public:
+    int search(vector<int>& nums, int target) {
+        if (nums.empty()) return -1;
+
+        int left = 0, right = nums.size() - 1;
+        while (left <= right) {
+            int pivot = (left + right) / 2;
+
+            if (target == nums[pivot]) return pivot;
+            else if (nums[pivot] < nums[right]) { //右侧有序
+                if (target > nums[pivot] && target <= nums[right]) {//在有序区
+                    left = pivot + 1;
+                } else {
+                    right = pivot - 1;
+                }
+            } else { //左侧有序
+                if (target >= nums[left] && target < nums[pivot]) {
+                    right = pivot - 1;
+                } else {
+                    left = pivot + 1;
+                }
+            }
+
+        }
+        return  -1;
+    }
+};
diff --git a/Week04/LeetCodes/433_Minimum_Genetic_Mutation.cpp b/Week04/LeetCodes/433_Minimum_Genetic_Mutation.cpp
@@ -0,0 +1,39 @@
+class Solution {
+public:
+    int minMutation(string start, string end, vector<string>& bank) {
+        if (start.empty() || end.empty() || bank.size() == 0) return -1;
+        if (find(bank.begin(), bank.end(), end) == bank.end()) return -1;
+
+
+        vector<int> visited(bank.size(), 0);
+        queue<string> q;
+        q.push(start);
+        int step = 0;
+
+        while(q.size()) {
+            step++;
+            int len = q.size();
+
+            for (int k = 0; k < len; k++) {
+                string tmp = q.front();
+                q.pop();
+
+                for (int i = 0; i < bank.size(); i++) {
+                    if (visited[i] == 0) {
+                        int diff = 0;
+                        for (int j = 0; j < tmp.length(); j++){
+                            if (tmp[j] != bank[i][j]) diff++;
+                        }
+
+                        if (diff == 1) {
+                            if (bank[i] == end) return step;
+                            visited[i] = 1;
+                            q.push(bank[i]);
+                        }
+                    }
+                }
+            }
+        }
+        return -1;
+    }
+};
diff --git a/Week04/LeetCodes/455_Assign_Cookies.cpp b/Week04/LeetCodes/455_Assign_Cookies.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+    int findContentChildren(vector<int>& g, vector<int>& s) {
+        sort(g.begin(), g.end());
+        sort(s.begin(), s.end());
+
+        int num = 0, i = 0, j = 0;
+        while(i < g.size() && j < s.size()) {
+            if (s[j] >= g[i]) {
+                j++;
+                i++;
+                num++;
+            } else {
+                j++;
+            }
+        }
+
+        return num;
+    }
+};
diff --git a/Week04/LeetCodes/45_Jump_Game_II.cpp b/Week04/LeetCodes/45_Jump_Game_II.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+    int jump(vector<int>& nums) {
+        int maxpos = 0, end = 0, step = 0; 
+        for (int i = 0; i < nums.size() - 1; i++) {
+            if (maxpos >= i) {
+                maxpos = max(maxpos, i + nums[i]);
+                if ( end == i) {
+                    end = maxpos;
+                    step++;
+                }
+            }
+        }
+
+        return step;
+    }
+};
+
+
diff --git a/Week04/LeetCodes/529_Minesweeper.cpp b/Week04/LeetCodes/529_Minesweeper.cpp
@@ -0,0 +1,43 @@
+class Solution {
+public:
+    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
+        if (!board.size() || !board[0].size()) return board;
+
+        char c =  board[click[0]][click[1]];
+        if (c == 'M') board[click[0]][click[1]] = 'X';
+        else if (c == 'E') {
+            calcBlock(click[0], click[1], board);    
+        } else {
+            ;
+        }
+        return board;
+    }
+
+    void calcBlock(int row, int col, vector<vector<char>>& board) {
+        int rows = board.size();
+        int cols = board[0].size();
+        if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != 'E') 
+            return;
+        
+        int Ms = 0;
+        int begin_row = row ? row - 1 : row;
+        int begin_col = col ? col - 1 : col;
+        int end_row = row == rows - 1 ? row : row + 1;
+        int end_col = col == cols - 1 ? col : col + 1;
+
+        for (int i = begin_row; i <= end_row; i++) 
+            for (int j = begin_col; j <= end_col; j++) {
+                if (board[i][j] == 'M') Ms++;
+            }
+        
+        if (Ms) {
+            board[row][col] = '0' + Ms;
+        } else {
+            board[row][col] = 'B';
+            for (int i = begin_row; i <= end_row; i++) 
+                for (int j = begin_col; j <= end_col; j++) {
+                    calcBlock(i, j, board);
+                }
+        }
+    }
+};
diff --git a/Week04/LeetCodes/55_Jump_Game.cpp b/Week04/LeetCodes/55_Jump_Game.cpp
@@ -0,0 +1,26 @@
+// class Solution {
+// public:
+//     bool canJump(vector<int>& nums) {
+//         int k = 0;
+//         for (int i = 0; i < nums.size() && k < nums.size(); i++) {
+//             if (i > k) return false;
+//             k = max(k, i + nums[i]);
+//         }
+
+//         return true;
+//     }
+// };
+
+class Solution {
+public:
+    bool canJump(vector<int>& nums) {
+        int last = nums.size() - 1;
+        for (int i = last - 1; i >= 0; i--) {
+            if (nums[i] + i >= last) {
+                last = i;
+            }
+        }
+
+        return last <= 0;
+    }
+};
diff --git a/Week04/LeetCodes/74_Search_a_2D_Matrix.cpp b/Week04/LeetCodes/74_Search_a_2D_Matrix.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    bool searchMatrix(vector<vector<int>>& matrix, int target) {
+        int rows = matrix.size();
+        if (!rows) return false;
+        int cols = matrix[0].size();
+        if (!cols) return false;
+
+        int left = 0, right = rows * cols - 1;
+        while (left <= right) {
+            int pivot = (left + right) / 2;
+            if (matrix[pivot/cols][pivot%cols] == target)
+                return true;
+            else if (matrix[pivot/cols][pivot%cols] > target) {
+                right = pivot - 1;
+            } else {
+                left = pivot + 1;
+            }
+        }
+        
+        return false;
+    }
+};
diff --git a/Week04/LeetCodes/860_Lemonade_Change.cpp b/Week04/LeetCodes/860_Lemonade_Change.cpp
@@ -0,0 +1,16 @@
+class Solution {
+public:
+    bool lemonadeChange(vector<int>& bills) {
+        int five = 0, ten = 0;
+
+        for (int bill : bills) {
+            if (bill == 5) five++;
+            else if (bill == 10) five--, ten++;
+            else if (bill == 20) ten ? ten--, five-- : five -=3;
+            else return false;
+
+            if (five < 0) return false;
+        }
+        return true;
+    }
+};
diff --git a/Week04/LeetCodes/874_Walking_Robot_Simulation.cpp b/Week04/LeetCodes/874_Walking_Robot_Simulation.cpp
diff --git a/Week04/NOTE.md b/Week04/NOTE.md
