Merge pull request algorithm001#563 from MrMuddle/master

GeekUniversity · web-flow · commit 354d65fc4c91 · 2019-05-06T12:13:28.000+08:00
第三周作业提交-085
diff --git a/Week_03/id_85/LeetCode_200_85.java b/Week_03/id_85/LeetCode_200_85.java
@@ -0,0 +1,73 @@
+public class LeetCode_200_85 {
+}
+
+/**
+ * @Package:
+ * @ClassName: NumberOfIslands
+ * @Description: 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
+ * **************一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
+ * **************你可以假设网格的四个边均被水包围。
+ * @leetcode url:https://leetcode-cn.com/problems/number-of-islands/comments/
+ * @Author: wangzhao
+ * @Date: 2019-05-05 14:02:46
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class NumberOfIslands {
+
+
+    public int numIslands(char[][] grid) {
+
+        if (grid==null||grid.length==0){
+            return 0;
+        }
+        int res =0;
+        int width = grid[0].length;
+        int height = grid.length;
+
+        boolean[][] visited = new boolean[height][width];
+
+        for (int i = 0; i < height; i++) {
+            for (int j = 0; j < width; j++) {
+                if (grid[i][j]=='1'&&!visited[i][j]){
+                    res++;
+                    dfs(grid,width,height,visited,i,j);
+                }
+            }
+        }
+
+        return res;
+    }
+
+    private void dfs(char[][] grid, int width, int height, boolean[][] visited, int i, int j) {
+
+        if (i < 0 || i >= height || j < 0 || j >= width) {
+            return;
+        }
+        if (grid[i][j]=='0'||visited[i][j]){
+            return;
+        }
+
+        visited[i][j]=true;
+        dfs(grid,width,height,visited,i-1,j);
+        dfs(grid,width,height,visited,i+1,j);
+        dfs(grid,width,height,visited,i,j-1);
+        dfs(grid,width,height,visited,i,j+1);
+    }
+
+
+    public static void main(String[] args) {
+
+        char[][] grid ={
+                {'1','1','0','0','0'},
+                {'1','1','0','0','0'},
+                {'0','0','1','0','0'},
+                {'0','0','0','1','1'}
+        };
+
+        int num = new NumberOfIslands().numIslands(grid);
+
+        System.out.println(num);
+    }
+
+}
diff --git a/Week_03/id_85/LeetCode_373_85.java b/Week_03/id_85/LeetCode_373_85.java
@@ -0,0 +1,68 @@
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+public class LeetCode_373_85 {
+}
+
+/**
+ * @Package:
+ * @ClassName: FindKPairsWithSmallestSums
+ * @Description: 给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
+ * **************定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
+ * **************找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
+ * @leetcodeurl: https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
+ * @Author: wangzhao
+ * @Date: 2019-05-05 18:08:49
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class FindKPairsWithSmallestSums{
+    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
+
+        List<int[]> list = new ArrayList<>();
+        if (nums1==null||nums1.length==0||nums2==null||nums2.length==0){
+            return list;
+        }
+
+
+        for (int i = 0; i < nums1.length; i++) {
+            for (int j = 0; j < nums2.length; j++) {
+                int[] arr = new int[2];
+                arr[0]=nums1[i];
+                arr[1]=nums2[j];
+                list.add(arr);
+            }
+        }
+
+        Collections.sort(list, new Comparator<int[]>() {
+            @Override
+            public int compare(int[] o1, int[] o2) {
+                int r1 = o1[0]+o1[1];
+                int r2 = o2[0]+o2[1];
+                return r1-r2;
+            }
+        });
+
+        List<int[]> res = new ArrayList<>();
+        for (int i = 0; i < k; i++) {
+            if (i<list.size())
+            res.add(list.get(i));
+        }
+
+        return res;
+    }
+
+    public static void main(String[] args) {
+
+        int[] num1 = {1,7,11};
+        int[] num2 = {2,4,6};
+        int k =3;
+        List<int[]> res = new FindKPairsWithSmallestSums().kSmallestPairs(num1,num2,k);
+
+        res.stream().forEach(o->{
+            System.out.println("["+o[0]+","+o[1]+"]");
+        });
+    }
+}
diff --git a/Week_03/id_85/LeetCode_997_85.java b/Week_03/id_85/LeetCode_997_85.java
@@ -0,0 +1,98 @@
+import java.util.ArrayList;
+import java.util.HashMap;
+
+public class LeetCode_997_85 {
+}
+
+
+/**
+ * @Package:
+ * @ClassName: FindTownJudge
+ * @Description: 在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
+ * **************如果小镇的法官真的存在，那么：
+ * **************小镇的法官不相信任何人。
+ * ***************每个人（除了小镇法官外）都信任小镇的法官。
+ * ***************只有一个人同时满足属性 1 和属性 2 。
+ * ***************给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。
+ * ***************如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。
+ * @leetcode url:https://leetcode-cn.com/problems/find-the-town-judge/
+ * @Author: wangzhao
+ * @Date: 2019-05-05 10:12:48
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class FindTownJudge {
+
+    public int findJudge(int N, int[][] trust) {
+        if (trust == null) {
+            return -1;
+        }
+        if (N <= 0) {
+            return -1;
+        }
+        if(trust.length==0){
+            return 1;
+        }
+        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
+
+        HashMap<Integer, ArrayList<Integer>> map2 = new HashMap<>();
+
+        for (int i = 0; i < trust.length; i++) {
+            int t0 = trust[i][0];
+            int t1 = trust[i][1];
+
+            ArrayList<Integer> array = map.get(t0);
+            if (array == null) {
+                array = new ArrayList<Integer>();
+            }
+            array.add(t1);
+            map.put(t0, array);
+
+            if (map.get(t1) == null) {
+                map.put(t1, new ArrayList<Integer>());
+            }
+
+            ArrayList<Integer> array2 = map2.get(t1);
+            if (array2 == null) {
+                array2 = new ArrayList<Integer>();
+            }
+            array2.add(t0);
+            map2.put(t1, array2);
+
+            if (map2.get(t0) == null) {
+                map2.put(t0, new ArrayList<Integer>());
+            }
+        }
+
+        int jude = -1;
+        for (Integer integer : map.keySet()) {
+            ArrayList list = map.get(integer);
+            if (list.size() == 0) {
+                jude = integer;
+                break;
+            }
+        }
+
+        if (jude != -1) {
+            ArrayList arr = map2.get(jude);
+            if (arr == null || arr.size() != N - 1) {
+                jude = -1;
+            }
+        }
+
+        return jude;
+    }
+
+    public static void main(String[] args) {
+//        int N = 4;
+//        int[][] trust = {{1, 3}, {1, 4}, {2, 3}, {2, 4}, {4, 3}};
+
+        int N = 3;
+        int[][] trust = {{1, 3}, {2, 3}};
+
+        int res = new FindTownJudge().findJudge(N, trust);
+
+        System.out.println(res);
+    }
+
+}
diff --git a/Week_03/id_85/NOTE.md b/Week_03/id_85/NOTE.md
@@ -1 +1,24 @@
-# 学习笔记
+# 学习笔记
+
+图
+简单：https://leetcode-cn.com/problems/find-the-town-judge/
+中等：https://leetcode-cn.com/problems/course-schedule-ii
+困难：https://leetcode-cn.com/problems/minimize-malware-spread-ii/
+
+堆和排序
+简单：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
+中等：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
+困难：https://leetcode-cn.com/problems/find-median-from-data-stream/
+
+DFS
+简单：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
+中等：https://leetcode-cn.com/problems/number-of-islands/
+中等：https://leetcode-cn.com/problems/find-eventual-safe-states/
+困难：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
+困难：https://leetcode-cn.com/problems/making-a-large-island/
+
+BFS
+简单：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
+中等：https://leetcode-cn.com/problems/minesweeper/
+中等：https://leetcode-cn.com/problems/minimum-height-trees/
+困难：https://leetcode-cn.com/problems/bus-routes/
