[Function add]

Seanforfun · Seanforfun · commit 03a2113ff3d8 · 2019-06-05T17:04:07.000-04:00
1. Add leetcode solutions with amazon tag.
diff --git a/leetcode/1000. Minimum Cost to Merge Stones.md b/leetcode/1000. Minimum Cost to Merge Stones.md
@@ -0,0 +1,76 @@
+## 1000. Minimum Cost to Merge Stones
+
+### Question
+There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.
+
+A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
+
+Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.
+
+```
+Example 1:
+
+Input: stones = [3,2,4,1], K = 2
+Output: 20
+Explanation: 
+We start with [3, 2, 4, 1].
+We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
+We merge [4, 1] for a cost of 5, and we are left with [5, 5].
+We merge [5, 5] for a cost of 10, and we are left with [10].
+The total cost was 20, and this is the minimum possible.
+
+Example 2:
+
+Input: stones = [3,2,4,1], K = 3
+Output: -1
+Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.
+
+Example 3:
+
+Input: stones = [3,5,1,2,6], K = 3
+Output: 25
+Explanation: 
+We start with [3, 5, 1, 2, 6].
+We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
+We merge [3, 8, 6] for a cost of 17, and we are left with [17].
+The total cost was 25, and this is the minimum possible.
+```
+ 
+Note:
+1. 1 <= stones.length <= 30
+2. 2 <= K <= 30
+3. 1 <= stones[i] <= 100
+
+### Thinking:
+* Method: dp
+    ```Java
+   class Solution {
+        public int mergeStones(int[] stones, int K) {
+            int n = stones.length;
+            if((n - 1) % (K - 1) != 0) return -1;
+            int[][][] dp = new int[n][n][K + 1];
+            int[] sum = new int[n + 1];
+            for(int i = 0; i < n; i++) 
+                sum[i + 1] = sum[i] + stones[i];
+            for(int[][] dd: dp)
+                for(int[] d: dd)
+                    Arrays.fill(d, Integer.MAX_VALUE);
+            for(int i = 0; i < n; i++)
+                dp[i][i][1] = 0;
+            for(int l = 2; l <= n; l++){
+                for(int start = 0; start <= n - l; start++){
+                    int end = start + l - 1;
+                    for(int k = 2; k <= K; k++){
+                        for(int mid = start; mid < end; mid += K - 1)
+                            dp[start][end][k] = Math.min(dp[start][end][k], dp[start][mid][1] + dp[mid + 1][end][k - 1]);
+                        dp[start][end][1] = dp[start][end][K] + sum[end + 1] - sum[start];
+                    }
+                }
+            }
+            return dp[0][n - 1][1];
+        }
+    }
+    ```
+
+### Reference
+1. [花花酱 LeetCode 1000. Minimum Cost to Merge Stones](https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1000-minimum-cost-to-merge-stones/)
diff --git a/leetcode/207. Course Schedule.md b/leetcode/207. Course Schedule.md
@@ -176,5 +176,39 @@ class Solution {
 	}
 	```
 
+### Amazon session
+* Method 1: Topological sort
+	```Java
+	class Solution {
+		public boolean canFinish(int numCourses, int[][] prerequisites) {
+			Map<Integer, Set<Integer>> map = new HashMap<>();   //key: current course, value: courses that cur is pre 
+			int[] indegree = new int[numCourses];   // indegree of course
+			for(int[] requests : prerequisites){
+				indegree[requests[0]]++;
+				Set<Integer> req = map.getOrDefault(requests[1], new HashSet<>());
+				req.add(requests[0]);
+				map.put(requests[1], req);
+			}
+			Queue<Integer> q = new LinkedList<>();
+			int finished = 0;
+			for(int i = 0; i < numCourses; i++){
+				if(indegree[i] == 0){
+					q.offer(i);
+				}
+			}
+			while(!q.isEmpty()){
+				int c = q.poll();
+				finished++;
+				if(!map.containsKey(c)) continue;   // current course is not any pre-request for any course.
+				for(int course : map.get(c)){
+					if(--indegree[course] == 0)
+						q.offer(course);
+				}
+			}
+			return finished == numCourses;
+		}
+	}
+	```
+
 ### Reference
 1. [【图论】有向无环图的拓扑排序](https://www.cnblogs.com/en-heng/p/5085690.html)
diff --git a/leetcode/733. Flood Fill.md b/leetcode/733. Flood Fill.md
@@ -83,3 +83,36 @@ Note:
       }
   }
   ```
+
+### Amazon session
+* Method 1: dfs
+	```Java
+	class Solution {
+		private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
+		private int cur;
+		private int[][] image;
+		private int newColor;
+		private int height, width;
+		public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
+			this.cur = image[sr][sc];
+			if(this.cur == newColor) return image;
+			this.image = image;
+			this.newColor = newColor;
+			this.height = image.length;
+			this.width = image[0].length;
+			dfs(sr, sc);
+			return this.image;
+		}
+		private void dfs(int x, int y){
+			int tx = 0, ty = 0;
+			image[x][y] = newColor;
+			for(int d = 0; d < 4; d++){
+				tx = x + dir[d][0];
+				ty = y + dir[d][1];
+				if(tx >= 0 && tx < height && ty >= 0 && ty < width && image[tx][ty] == cur){
+					dfs(tx, ty);
+				}
+			}
+		}
+	}
+	```
