Merge pull request #1295 from bugyun/master

melody-li · web-flow · commit b8df499d4d83 · 2019-12-12T18:40:06.000+08:00
641-Week 07 08
diff --git a/Week 07/id_641/lesson16/LeetCode_191_641.java b/Week 07/id_641/lesson16/LeetCode_191_641.java
@@ -0,0 +1,30 @@
+package vip.ruoyun.week7.lesson16;
+
+public class LeetCode_191_641 {
+
+
+    //利用 and 操作符
+    public int hammingWeight(int n) {
+        int bits = 0;
+        int mask = 1;
+        for (int i = 0; i < 32; i++) {
+            if ((n & mask) != 0) {
+                bits++;
+            }
+            mask <<= 1;
+        }
+        return bits;
+    }
+
+    //每回都看看是否等于 0 如果不等于 0 那么就 and n-1 位
+    public int hammingWeight2(int n) {
+        int sum = 0;
+        while (n != 0) {
+            sum++;
+            n &= (n - 1);
+        }
+        return sum;
+    }
+
+
+}
diff --git a/Week 07/id_641/lesson16/LeetCode_231_641.java b/Week 07/id_641/lesson16/LeetCode_231_641.java
@@ -0,0 +1,10 @@
+package vip.ruoyun.week7.lesson16;
+
+public class LeetCode_231_641 {
+
+    //2的幂数的数字的二进制有且只有一个1，其余均是0
+    public boolean isPowerOfTwo(int n) {
+        return n > 0 && (n & (n - 1)) == 0;
+    }
+}
+
diff --git a/Week 07/id_641/lesson18/LeetCode_1122_641.java b/Week 07/id_641/lesson18/LeetCode_1122_641.java
@@ -0,0 +1,31 @@
+package vip.ruoyun.week7.lesson18;
+
+public class LeetCode_1122_641 {
+
+
+    public int[] relativeSortArray(int[] arr1, int[] arr2) {
+        int[] nums = new int[1001];
+        int[] res = new int[arr1.length];
+        //遍历arr1,统计每个元素的数量
+        for (int i : arr1) {
+            nums[i]++;
+        }
+        //遍历arr2,处理arr2中出现的元素
+        int index = 0;
+        for (int i : arr2) {
+            while (nums[i] > 0) {
+                res[index++] = i;
+                nums[i]--;
+            }
+        }
+        //遍历nums,处理剩下arr2中未出现的元素
+        for (int i = 0; i < nums.length; i++) {
+            while (nums[i] > 0) {
+                res[index++] = i;
+                nums[i]--;
+            }
+        }
+        return res;
+    }
+
+}
diff --git a/Week 08/id_641/lesson19/LeetCode_300_641.java b/Week 08/id_641/lesson19/LeetCode_300_641.java
@@ -0,0 +1,21 @@
+package vip.ruoyun.week8.lesson19;
+
+public class LeetCode_300_641 {
+
+    //动态规划
+    public int lengthOfLIS(int[] nums) {
+        int[] tails = new int[nums.length];
+        int res = 0;
+        for (int num : nums) {
+            int i = 0, j = res;
+            while (i < j) {
+                int m = (i + j) / 2;
+                if (tails[m] < num) i = m + 1;
+                else j = m;
+            }
+            tails[i] = num;
+            if (res == j) res++;
+        }
+        return res;
+    }
+}
diff --git a/Week 08/id_641/lesson19/LeetCode_91_641.java b/Week 08/id_641/lesson19/LeetCode_91_641.java
@@ -0,0 +1,31 @@
+package vip.ruoyun.week8.lesson19;
+
+public class LeetCode_91_641 {
+
+    public int numDecodings(String s) {
+        return getAns(s, 0);
+    }
+
+    private int getAns(String s, int start) {
+        //划分到了最后返回 1
+        if (start == s.length()) {
+            return 1;
+        }
+        //开头是 0,0 不对应任何字母，直接返回 0
+        if (s.charAt(start) == '0') {
+            return 0;
+        }
+        //得到第一种的划分的解码方式
+        int ans1 = getAns(s, start + 1);
+        int ans2 = 0;
+        //判断前两个数字是不是小于等于 26 的
+        if (start < s.length() - 1) {
+            int ten = (s.charAt(start) - '0') * 10;
+            int one = s.charAt(start + 1) - '0';
+            if (ten + one <= 26) {
+                ans2 = getAns(s, start + 2);
+            }
+        }
+        return ans1 + ans2;
+    }
+}
diff --git a/Week 08/id_641/lesson20/LeetCode_387_641.java b/Week 08/id_641/lesson20/LeetCode_387_641.java
@@ -0,0 +1,22 @@
+package vip.ruoyun.week8.lesson20;
+
+import java.util.HashMap;
+
+public class LeetCode_387_641 {
+    public int firstUniqChar(String s) {
+        HashMap<Character, Integer> count = new HashMap<Character, Integer>();
+        int n = s.length();
+        // build hash map : character and how often it appears
+        for (int i = 0; i < n; i++) {
+            char c = s.charAt(i);
+            count.put(c, count.getOrDefault(c, 0) + 1);
+        }
+
+        // find the index
+        for (int i = 0; i < n; i++) {
+            if (count.get(s.charAt(i)) == 1)
+                return i;
+        }
+        return -1;
+    }
+}
