Merge pull request algorithm001#674 from bugcodes/master

GeekUniversity · web-flow · commit 414e4bb11e56 · 2019-05-13T17:27:48.000+08:00
049_week04_homework
diff --git a/Week_04/id_49/LeetCode_169_49.java b/Week_04/id_49/LeetCode_169_49.java
@@ -0,0 +1,46 @@
+package com.v0ex.leetcode;
+
+import java.util.Arrays;
+
+/**
+ * @author bugcoder
+ */
+public class LeetCode_169_49 {
+
+    public int majorityElement(int[] nums) {
+        if(nums.length==1||nums.length==2){
+            return nums[0];
+        }
+        Arrays.sort(nums);
+        int length = nums.length;
+        int start = 0;
+        int end = length-1;
+        int mid = start + (end-start)/2;
+        if (nums[start] == nums[mid] && nums[mid] == nums[mid+1]){
+            mid = start;
+        }
+        if (nums[end] == nums[mid] && nums[mid] == nums[mid-1]){
+            mid = end;
+        }
+        return nums[mid];
+    }
+
+    /**
+     * 很有意思的Boyer-Moore投票算法
+     * @param nums
+     * @return
+     */
+    public int majorityElementBmVoting(int[] nums) {
+        int count = 0;
+        int candidate = 0;
+
+        for (int num : nums) {
+            if (count == 0) {
+                candidate = num;
+            }
+            count += (num == candidate) ? 1 : -1;
+        }
+
+        return candidate;
+    }
+}
diff --git a/Week_04/id_49/LeetCode_720_49.java b/Week_04/id_49/LeetCode_720_49.java
@@ -0,0 +1,42 @@
+package com.v0ex.leetcode;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * @author bugcoder
+ */
+public class LeetCode_720_49 {
+
+    /**
+     * brute force + 剪枝法
+     * @param words
+     * @return
+     */
+    public String longestWord(String[] words){
+        String result = "";
+        Set<String> set = new HashSet<>();
+        for(String word : words){
+            set.add(word);
+        }
+        for(String word: words){
+            //凡是小于目标字符串长度的字符串都不符合要求
+            if(word.length() < result.length() ||
+                    //长度相等，但是按照字典顺序大于目标字符串长度的也不符合要求
+                    word.length()== result.length()&&word.compareTo(result)>0){
+                continue;
+            }
+            boolean flag = true;
+            for(int i = 1;i < word.length();i++){
+                if(!set.contains(word.substring(0,i))){
+                    flag = false;
+                    break;
+                }
+            }
+            if(flag){
+                result = word;
+            }
+        }
+        return result;
+    }
+}
diff --git a/Week_04/id_49/NOTE.md b/Week_04/id_49/NOTE.md
@@ -1 +1,57 @@
-# 学习笔记
+# 学习笔记
+## 分治法
+
+分治法的基本步骤：
+
+step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
+
+step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
+
+step3 合并：将各个子问题的解合并为原问题的解。
+
+它的一般的算法设计模式如下：
+
+    Divide-and-Conquer(P)
+    
+    1. if |P|≤n0
+    
+    2. then return(ADHOC(P))
+    
+    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
+    
+    4. for i←1 to k
+    
+    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
+    
+    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
+    
+    7. return(T)
+
+其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
+
+可使用分治法求解的一些经典问题
+
+1. 二分搜索
+2. 大整数乘法
+3. Strassen矩阵乘法
+4. 棋盘覆盖
+5. 合并排序
+6. 快速排序
+7. 线性时间选择
+8. 最接近点对问题
+9. 循环赛日程表
+10. 汉诺塔
+
+##贪心算法
+
+贪心算法的基本步骤：
+
+1. 建立数学模型来描述问题。
+
+1. 把求解的问题分成若干个子问题。
+
+1. 对每一子问题求解，得到子问题的局部最优解。
+
+1. 把子问题的解局部最优解合成原来解问题的一个解。
+
+贪心策略适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
