week02 second commit

herost789 · herost789 · commit 55b8a790b62d · 2020-06-21T15:15:45.000+08:00
diff --git a/Week02/com/mypractice/Anagram.java b/Week02/com/mypractice/Anagram.java
@@ -0,0 +1,46 @@
+package com.mypractice;
+
+import java.util.Arrays;
+
+public class Anagram {
+    public boolean isAnagram1(String s, String t) {
+
+        if (s.length() != t.length()) {
+            return false;
+        }
+        //使用暴力解法，将得到的两个字符串进行排序后比较是否相同
+        char[] str1 = s.toCharArray();
+        char[] str2 = t.toCharArray();
+        Arrays.sort(str1);
+        Arrays.sort(str2);
+        return Arrays.equals(str1, str2);
+    }
+
+    public boolean isAnagram2(String s, String t) {
+        if (s.length() != t.length()) {
+            return false;
+        }
+        //使用数组缓存字母元素，在s中出现时给元素+1，在t中出现时给元素-1
+        //最后检查数组元素是否均为0
+        int[] counter = new int[26];
+        for (int i = 0; i < s.length(); i++) {
+            counter[s.toLowerCase().charAt(i)-'a']++;
+            counter[t.toLowerCase().charAt(i)-'a']--;
+        }
+        for (int count : counter) {
+            if (count != 0) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    public static void main(String[] args) {
+        String s="Aa";
+        System.out.println((s.charAt(0)-'a'));
+        System.out.println((s.charAt(1)-'a'));
+
+    }
+
+}
diff --git a/Week02/com/mypractice/BinaryTreeInorder.java b/Week02/com/mypractice/BinaryTreeInorder.java
@@ -0,0 +1,26 @@
+package com.mypractice;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class BinaryTreeInorder {
+    public List<Integer> inorderTraversal(TreeNode root) {
+        List<Integer> result=new ArrayList<>();
+        helper(root, result);
+        return result;
+
+    }
+
+    public void helper(TreeNode root, List<Integer> result) {
+        if (root != null) {
+            if (root.left != null) {
+                helper(root.left,result);
+            }
+            result.add(root.val);
+            if (root.right != null) {
+                helper(root.right,result);
+            }
+        }
+    }
+
+}
diff --git a/Week02/com/mypractice/TreeNode.java b/Week02/com/mypractice/TreeNode.java
@@ -0,0 +1,12 @@
+package com.mypractice;
+
+
+public class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/Week02/com/mypractice/UglyNumber.java b/Week02/com/mypractice/UglyNumber.java
@@ -0,0 +1,17 @@
+package com.mypractice;
+
+public class UglyNumber {
+    public int nthUglyNumber(int n) {
+        //我们将前面求得的丑数记录下来，后面的丑数就是前面的丑数*2，*3，*5
+        int p2=0,p3=0,p5=0;
+        int[] dp=new int[n];
+        dp[0]=1;
+        for(int i=1;i<n;i++){
+            dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5));
+            if(dp[i]==dp[p2]*2) p2++;
+            if(dp[i]==dp[p3]*3) p3++;
+            if(dp[i]==dp[p5]*5) p5++;
+        }
+        return dp[n-1];
+    }
+}
