Merge pull request algorithm001#709 from yanlingli3799/master

GeekUniversity · web-flow · commit 4b09f64262ff · 2019-05-13T17:20:51.000+08:00
第四周作业，李颜翎
diff --git a/Week_03/id_118/NOTE.md b/Week_03/id_118/NOTE.md
@@ -1 +1,30 @@
-# 学习笔记
+# 学习笔记
+
+这周的学习分两部分：
+- 专栏，集中在单模式字符串匹配算法。
+- 算法，集中做了几道“图”相关的题。
+
+还是用 xmind 结合手绘图来做学习总结的，不过又有了些新的感受。
+
+---
+
+在看字符串匹配算法的时候，有一些点不太想的明白，以BM算法为例：
+- 为什么坏字符位移数可能为负？
+- 好后缀与模式串的多个子串匹配时，选哪一个？
+- 为什么必须是完整子串匹配，或模式串的前缀子串与好后缀的后缀子串匹配，其他子串不行吗？
+
+遇到这些问题的时候，可以通过举例子的方式辅助思考。
+
+附上我在学习过程中画的图例，和整理的总结：
+- 图例：https://github.com/yanlingli3799/algorithm/blob/master/Week_03/id_118/src/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D-%E5%9B%BE%E4%BE%8B.pdf
+- 小结：https://github.com/yanlingli3799/algorithm/blob/master/Week_03/id_118/src/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D-%E6%80%9D%E7%BB%B4%E5%AF%BC%E5%9B%BE.pdf
+
+
+----
+
+做题的时候，挑的几个图做的，其他的难度都不大，稍微转化一下就好。
+928比较麻烦，费了好大力气才理解和 924 啥区别。
+整理思路的时候，还是画了一些图例，个人感觉还是比较有用的。目前使用bfs暴力搜索算出来的，时间复杂度比较高，提交有的时候甚至会报超时。
+
+附928图例草稿：https://github.com/yanlingli3799/algorithm/blob/master/Week_03/id_118/src/928%E8%8D%89%E7%A8%BF.pdf
+
diff --git a/Week_04/id_118/leetcode_121_118.java b/Week_04/id_118/leetcode_121_118.java
@@ -0,0 +1,27 @@
+// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
+// 121.买卖股票的最佳时机
+// 思路：其实就是求某个时间点左边的最小值和右边的最大值之差的最大值。
+class Solution {
+    public int maxProfit(int[] prices) {
+        if(prices.length <=0){
+            return 0;
+        }
+        
+        int minPrice = prices[0];
+        int maxProfit = 0;
+        
+        for(int i=1;i<prices.length;i++){
+            // 若今天价格高于前面几天的最低价格，则可以卖出。
+            // 此时，计算今天卖出利润多少，是否比已计算的利润更高
+            if(prices[i]>minPrice && maxProfit<(prices[i]-minPrice)){
+                maxProfit = prices[i]-minPrice;
+            }
+            
+            // 若今天价格低于前几天的最低价格，则更新最低价格
+            if(prices[i]<minPrice){
+                minPrice = prices[i];
+            }
+        }
+        return maxProfit;
+    }
+}
diff --git a/Week_04/id_118/leetcode_122_118.java b/Week_04/id_118/leetcode_122_118.java
@@ -0,0 +1,38 @@
+// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
+// 122.买卖股票的最佳时机2
+// 和 121 不一样的是，121 要求买买一次获得最大利润，122 要求多次买卖，获得最大利润，且不可以同时参与多笔交易
+// 这样问题可以拆解为多个区间找最大差值的问题
+// 由于可以多次买卖，所以我们只需要找到所有的独立的“单调递增区间”，然后计算其差值之和即可。
+class Solution {
+    public int maxProfit(int[] prices) {
+        
+        int totalProfit = 0;
+        
+        // 1. 数组为空，或只有一个元素，则最大利润为0
+        if(prices.length<=1){
+            return 0;
+        }
+        
+        int partLeft = prices[0];
+        int partRight = prices[0];
+        
+        // 2. 从1开始，寻找并累加单调区间左右差值
+        for(int i=1;i<prices.length;i++){
+            if(prices[i]>partRight){
+                partRight = prices[i];
+            }
+            if(prices[i]<partRight){
+                totalProfit += (partRight-partLeft);
+                partLeft = prices[i];
+                partRight = prices[i];
+            }
+        }
+        
+        // 3. 最后一个小区间
+        if(partLeft!=partRight){
+            totalProfit += (partRight-partLeft);
+        }
+        
+        return totalProfit;
+    }
+}
diff --git a/Week_04/id_118/leetcode_123_118.java b/Week_04/id_118/leetcode_123_118.java
@@ -0,0 +1,57 @@
+// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
+// 123.买卖股票的最佳时机3
+// 是在 122 的基础上，加了限制条件，不能对所有值做累加，只能取最大的两个求和
+class Solution {
+    public int maxProfit(int[] prices) {
+        
+        ArrayList<Integer> profit = new ArrayList();
+        
+        // 1. 数组为空，或只有一个元素，则最大利润为0
+        if(prices.length<=1){
+            return 0;
+        }
+        
+        int totalMaxProfit = 0;
+        
+        // 
+        for(int i=1;i<prices.length;i++){
+            // 左侧闭区间：[0,i]
+            // 右侧闭区间：[i+1,length-1]
+            int leftMaxProfit = maxProfit(prices,0,i);
+            int rightMaxProfit = maxProfit(prices,i+1,prices.length-1);
+            if(leftMaxProfit+rightMaxProfit >totalProfit){
+                totalProfit = leftMaxProfit+rightMaxProfit;
+            }
+        }
+        
+        return totalProfit;
+    }
+    
+    
+    // 求闭区间 [from,to] 做一笔交易的最大值。
+    int maxProfit(int[] prices,int from,int to){
+        if(from>=to){
+            return 0;
+        }
+        if(from+1==to){
+            return prices[to]-prices[from]>0?prices[to]-prices[from]:0;
+        }
+        
+        int minPrice = prices[from];
+        int maxProfit = 0;
+        for(int i=from+1;i<prices.length && i<=to;i++){
+            // 若今天价格高于前面几天的最低价格，则可以卖出。
+            // 此时，计算今天卖出利润多少，是否比已计算的利润更高
+            if(prices[i]>minPrice && maxProfit<(prices[i]-minPrice)){
+                maxProfit = prices[i]-minPrice;
+            }
+            
+            // 若今天价格低于前几天的最低价格，则更新最低价格
+            if(prices[i]<minPrice){
+                minPrice = prices[i];
+            }
+        }
+        
+        return maxProfit;
+    }
+}
diff --git a/Week_04/id_118/leetcode_455_118.java b/Week_04/id_118/leetcode_455_118.java
@@ -0,0 +1,33 @@
+// https://leetcode-cn.com/problems/assign-cookies/
+// 455.分发饼干
+// 解法：每次选一个胃口最小的孩子，给尺寸最小的饼干
+class Solution {
+    public int findContentChildren(int[] g, int[] s) {
+       
+        // 分别排序
+        Arrays.sort(g);
+        Arrays.sort(s);
+        
+        int i=0;
+        int lastMatchIndex = -1;
+    
+        // 对每一个孩子 i ，从 s 里找第一个比它大的 j，能满足 s[j]>=g[i]（尺寸>=胃口）。
+        // 若某个孩子 i 找不到比它大的 j，则终止，后面的孩子也一定得不到满足
+        for(i=0;i<g.length;i++){
+            boolean found = false;
+            for(int j=lastMatchIndex+1;j<s.length;j++){
+                if(s[j]>=g[i]){
+                    lastMatchIndex = j;
+                    found=true;
+                    break;
+                }
+            }
+            if(found==false){
+                break;
+            }
+        }
+        
+        return i;
+    }
+    
+}
diff --git a/Week_04/id_118/leetcode_720_118.java b/Week_04/id_118/leetcode_720_118.java
@@ -0,0 +1,85 @@
+// https://leetcode-cn.com/problems/longest-word-in-dictionary/
+// 720.词典中最长的单词
+// 解题思路：构建Trie树，对每个单词的末尾做标记；然后扫描Trie树，找出最长单词
+// - 为了快速计算单词，对Trie树做个小小的变形，每个节点存储的不是一个字符，而是到当前节点为止的字串
+// - 这样，可以使用层次遍历，找出最长单词
+// - 若出现多个最长单词，第一个遇到的就是字典序最前的
+
+class Solution {
+    
+    // 定义一个内部类
+    class TrieNode{
+        String data;// 以当前字符结尾的字符串
+        boolean isEndingChar;// 用来标识当前节点是否为某个单词的终点。
+        TrieNode[] children;
+        TrieNode(String data){
+            this.data = data;
+            this.children = new TrieNode[26];
+        }
+    }
+    
+    // 向Trie树中插入一个单词
+    void insertToTrie(TrieNode root,String word){
+        TrieNode tmp = root;
+        
+        // 遍历单词的每一个字符
+        for(int i=0;i<word.length();i++){
+            // 取字符，并计算索引
+            char c = word.charAt(i);
+            int index = c-'a';
+            String data = word.substring(0,i+1);
+            // 查看当前根节点对应索引位置是否为null，若为null，则new 一个新节点，插入
+            if(tmp.children[index] == null){
+                TrieNode newNode = new TrieNode(data);
+                tmp.children[index] = newNode;
+            }
+            tmp = tmp.children[index];
+        }
+        // 最后一个单词，标记
+        tmp.isEndingChar = true;        
+    }
+    
+    // 构建 Trie 树
+    void buildTrie(TrieNode root,String[] words){
+        for(int i=0;i<words.length;i++){
+            insertToTrie(root,words[i]);
+        }
+    }
+    
+    
+  
+    
+    public String longestWord(String[] words) {
+        TrieNode root = new TrieNode("");
+        buildTrie(root,words);
+        
+        String longestWord = "";
+        Queue<TrieNode> queue = new LinkedList<TrieNode>();
+        
+        // 先遍历第一层子节点，初始化Queue。
+        for(int i=0;i<26;i++){
+            if(root.children[i]!=null && root.children[i].isEndingChar==true){
+                queue.offer(root.children[i]);
+                if(longestWord.length() < root.children[i].data.length()){
+                    longestWord = root.children[i].data;
+                }
+            }
+        }
+        
+        // 层次遍历，每次从队列中取出一个节点来，向下遍历
+        while(queue.size()!=0){
+            TrieNode node = queue.poll();
+            for(int i=0;i<26;i++){
+                if(node.children[i]!=null && node.children[i].isEndingChar==true){
+                    queue.offer(node.children[i]);
+                    if(longestWord.length() < node.children[i].data.length()){
+                        longestWord = node.children[i].data;
+                    }
+                }
+            }
+        }
+        
+        return longestWord;
+    }
+
+}
diff --git a/Week_04/id_118/src/leetcode-买卖股票问题.pdf b/Week_04/id_118/src/leetcode-买卖股票问题.pdf
diff --git a/Week_04/id_118/src/四大算法思想.pdf b/Week_04/id_118/src/四大算法思想.pdf
