Week02作业补交

bkning · bkning · commit c64291b59302 · 2020-06-29T17:42:59.000+08:00
diff --git a/Week02/AnagramsGroup.java b/Week02/AnagramsGroup.java
@@ -0,0 +1,36 @@
+package week02;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * 字母异位词分组
+ */
+public class AnagramsGroup {
+
+    public static void main(String[] args) {
+        List<List<String>> result = groupAnagrams(new String[] {"ab", "ba"});
+        System.out.println(result);
+    }
+
+    public static List<List<String>> groupAnagrams(String[] strs) {
+        HashMap<String, List<String>> hash = new HashMap<>();
+        for (String str : strs) {
+            char[] s_arr = str.toCharArray();
+            Arrays.sort(s_arr);
+            String key = String.valueOf(s_arr);
+            if (hash.containsKey(key)) {
+                hash.get(key).add(str);
+            } else {
+                List<String> temp = new ArrayList<>();
+                temp.add(str);
+                hash.put(key, temp);
+            }
+
+        }
+        return new ArrayList<>(hash.values());
+    }
+
+}
diff --git a/Week02/BinaryTreeInIteration.java b/Week02/BinaryTreeInIteration.java
@@ -0,0 +1,30 @@
+package week02;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.List;
+
+/**
+ * 二叉树的中序遍历
+ */
+public class BinaryTreeInIteration {
+
+    public List<Integer> inOrderIteration(TreeNode root) {
+        List <Integer> res = new ArrayList<>();
+        Deque <TreeNode> stack = new ArrayDeque<>();
+        TreeNode p = root;
+
+        while (!stack.isEmpty() || p != null) {
+            while (p != null) {
+                stack.push(p);
+                p = p.left;
+            }
+            TreeNode tmp = stack.pop();
+            res.add(tmp.val);
+            p = tmp.right;
+        }
+        return res;
+    }
+
+}
diff --git a/Week02/BinaryTreePreIteration.java b/Week02/BinaryTreePreIteration.java
@@ -0,0 +1,30 @@
+package week02;
+
+import java.util.Stack;
+
+/**
+ * 二叉树的前序遍历
+ */
+public class BinaryTreePreIteration {
+
+    public static void preOrderIteration(TreeNode head) {
+        if (head == null) {
+            return;
+        }
+
+        Stack<TreeNode> stack = new Stack<>();
+        stack.push(head);
+
+        while (!stack.isEmpty()) {
+            TreeNode node = stack.pop();
+            System.out.print(node.val + " ");
+            if (node.right != null) {
+                stack.push(node.right);
+            }
+            if (node.left != null) {
+                stack.push(node.left);
+            }
+        }
+    }
+
+}
diff --git a/Week02/IsAnagram.java b/Week02/IsAnagram.java
@@ -0,0 +1,21 @@
+package week02;
+
+/**
+ * 有效的字母异位词
+ */
+public class IsAnagram {
+
+    public static void main(String[] args) {
+        boolean anagram = isAnagram("ab", "baa");
+        System.out.println(anagram);
+    }
+
+    public static boolean isAnagram(String s, String t) {
+        int[] alphabet = new int[26];
+        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
+        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
+        for (int i : alphabet) if (i != 0) return false;
+        return true;
+    }
+
+}
diff --git a/Week02/NTreeLevelIteration.java b/Week02/NTreeLevelIteration.java
@@ -0,0 +1,36 @@
+package week02;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * N叉树的层序遍历
+ */
+public class NTreeLevelIteration {
+
+    public List<List<Integer>> levelOrder(TreeNode root) {
+        List<List<Integer>> ret = new LinkedList<>();
+
+        if (root == null) return ret;
+
+        Queue<TreeNode> queue = new LinkedList<>();
+
+        queue.offer(root);
+
+        while (!queue.isEmpty()) {
+            List<Integer> curLevel = new LinkedList<>();
+            int len = queue.size();
+            for (int i = 0; i < len; i++) {
+                TreeNode curr = queue.poll();
+                curLevel.add(curr.val);
+                for (TreeNode c : curr.children)
+                    queue.offer(c);
+            }
+            ret.add(curLevel);
+        }
+
+        return ret;
+    }
+
+}
diff --git a/Week02/NTreePreIteration.java b/Week02/NTreePreIteration.java
@@ -0,0 +1,26 @@
+package week02;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * N叉树的前序遍历
+ */
+public class NTreePreIteration {
+
+    public static List<Integer> list = new ArrayList<>();
+
+    public static List<Integer> preorder(TreeNode root) {
+        if (root == null) {
+            return list;
+        }
+
+        list.add(root.val);
+        for(TreeNode node : root.children) {
+            preorder(node);
+        }
+
+        return list;
+    }
+
+}
diff --git a/Week02/TopKFrequent.java b/Week02/TopKFrequent.java
@@ -0,0 +1,44 @@
+package week02;
+
+import java.util.*;
+
+/**
+ * 前K个高频元素
+ */
+public class TopKFrequent {
+
+    public static void main(String[] args) {
+        int[] nums = new int[]{1,1,1,2,2,2,3,3,5,6,7,8,8,9};
+        int k = 2;
+        List<Integer> result = topKFrequent(nums, k);
+        System.out.println(result);
+    }
+
+    public static List<Integer> topKFrequent(int[] nums, int k) {
+        List<Integer> res = new ArrayList<>();
+        HashMap<Integer,Integer> map = new HashMap<>();
+        for(int num : nums){
+            if (map.containsKey(num)) {
+                map.put(num, map.get(num) + 1);
+            } else {
+                map.put(num, 1);
+            }
+        }
+
+        List<Integer>[] list = new List[nums.length+1];
+        for(int key : map.keySet()){
+            int i = map.get(key);
+            if(list[i] == null){
+                list[i] = new ArrayList<>();
+            }
+            list[i].add(key);
+        }
+
+        for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
+            if(list[i] == null) continue;
+            res.addAll(list[i]);
+        }
+        return res;
+    }
+
+}
diff --git a/Week02/TreeNode.java b/Week02/TreeNode.java
@@ -0,0 +1,15 @@
+package week02;
+
+import java.util.List;
+
+public class TreeNode {
+
+    int val;
+    TreeNode left;
+    TreeNode right;
+    List<TreeNode> children;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/Week02/UglyNumber.java b/Week02/UglyNumber.java
@@ -0,0 +1,26 @@
+package week02;
+
+/**
+ * 丑数
+ */
+public class UglyNumber {
+
+    public static void main(String[] args) {
+        System.out.println(getUglyNumberByN(8));
+    }
+
+    public static int getUglyNumberByN(int n) {
+        int a = 0, b = 0, c = 0;
+        int[] dp = new int[n];
+        dp[0] = 1;
+        for(int i = 1; i < n; i++) {
+            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
+            dp[i] = Math.min(Math.min(n2, n3), n5);
+            if(dp[i] == n2) a++;
+            if(dp[i] == n3) b++;
+            if(dp[i] == n5) c++;
+        }
+        return dp[n - 1];
+    }
+
+}
