{"action":"created","issue":{"url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/1235","repository_url":"https://api.github.com/repos/algorithm004-05/algorithm004-05","labels_url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/1235/labels{/name}","comments_url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/1235/comments","events_url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/1235/events","html_url":"https://github.com/algorithm004-05/algorithm004-05/issues/1235","id":534427746,"node_id":"MDU6SXNzdWU1MzQ0Mjc3NDY=","number":1235,"title":"【280-Week 08】学习总结","user":{"login":"TanChungui","id":9277956,"node_id":"MDQ6VXNlcjkyNzc5NTY=","avatar_url":"https://avatars3.githubusercontent.com/u/9277956?v=4","gravatar_id":"","url":"https://api.github.com/users/TanChungui","html_url":"https://github.com/TanChungui","followers_url":"https://api.github.com/users/TanChungui/followers","following_url":"https://api.github.com/users/TanChungui/following{/other_user}","gists_url":"https://api.github.com/users/TanChungui/gists{/gist_id}","starred_url":"https://api.github.com/users/TanChungui/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/TanChungui/subscriptions","organizations_url":"https://api.github.com/users/TanChungui/orgs","repos_url":"https://api.github.com/users/TanChungui/repos","events_url":"https://api.github.com/users/TanChungui/events{/privacy}","received_events_url":"https://api.github.com/users/TanChungui/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2019-12-07T17:20:01Z","updated_at":"2019-12-08T07:35:18Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"**递归**\r\n\r\n> 1. 人肉递归低效、很累\r\n> 2. 找到最近最简方法，将其拆解成可重复解决的问题 3. 数学归纳法思维\r\n> 本质:寻找重复性 —> 计算机指令集\r\n\r\n![image](https://user-images.githubusercontent.com/9277956/70378135-f450b300-1957-11ea-8f20-508d11ecbfe6.png)\r\n![image](https://user-images.githubusercontent.com/9277956/70378139-ffa3de80-1957-11ea-9ed2-1516baf40140.png)\r\n **关键点**\r\n\r\n> 动态规划 和 递归或者分治 没有根本上的区别(关键看有无最优的子结构) 拥有共性:找到重复子问题\r\n> 差异性:最优子结构、中途可以淘汰次优解\r\n\r\n **高阶DP复杂度来源**\r\n\r\n> 1. 状态拥有更多维度(二维、三维、或者更多、甚至需要压缩) \r\n> 2. 状态方程更加复杂\r\n> 本质:内功、逻辑思维、数学\r\n\r\n 字符串匹配算法\r\n1. 暴力法(brute force) - O(mn)\r\n```\r\npublic static int forceSearch(String txt, String pat) { int M = txt.length();\r\nint N = pat.length();\r\nfor (int i = 0; i <= M - N; i++) { int j;\r\nfor (j = 0; j < N; j++) {\r\nif (txt.charAt(i + j) != pat.charAt(j))\r\nbreak;\r\n}\r\nif (j == N) {\r\nreturn i; }\r\n// 更加聪明?\r\n// 1. 预先判断– hash(txt.substring(i, M)) == hash(pat)\r\n// 2. KMP\r\n}\r\nreturn -1; }\r\n```\r\n2. Rabin-Karp 算法\r\n\r\n> 在朴素算法中，我们需要挨个比较所有字符，才知道目标字符串中是否包含 子串。那么， 是否有别的方法可以用来判断目标字符串是否包含子串呢?\r\n> 答案是肯定的，确实存在一种更快的方法。为了避免挨个字符对目标字符串 和子串进行比较， 我们可以尝试一次性判断两者是否相等。因此，我们需 要一个好的哈希函数(hash function)。 通过哈希函数，我们可以算出子 串的哈希值，然后将它和目标字符串中的子串的哈希值进行比较。 这个新 方法在速度上比暴力法有显著提升。\r\n> Rabin-Karp 算法的思想:\r\n> 1. 假设子串的长度为 M (pat)，目标字符串的长度为 N (txt)\r\n> 2. 计算子串的 hash 值 hash_pat\r\n> 3. 计算目标字符串txt中每个长度为 M 的子串的 hash 值(共需要计算 N-M+1 次)\r\n> 4. 比较 hash 值:如果 hash 值不同，字符串必然不匹配; 如果 hash 值相同， 还需要使用朴素算法再次判断\r\n\r\n3. KMP 算法\r\n\r\n> KMP算法(Knuth-Morris-Pratt)的思想就是，当子串与目标字符串不匹配时， 其实你已经知道了前面已经匹配成功那 一部分的字符(包括子串与目标字符 串)。以阮一峰的文章为例，当空格与 D 不匹配时，你其实 知道前面六个字符是 “ABCDAB”。KMP 算法的想法是，设法利用这个已知信息，不要把“搜索位\r\n> 置” 移回已经比较过的位置，继续把它向后移，这样就提高了效率。\r\n\r\n\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/comments/562920789","html_url":"https://github.com/algorithm004-05/algorithm004-05/issues/1235#issuecomment-562920789","issue_url":"https://api.github.com/repos/algorithm004-05/algorithm004-05/issues/1235","id":562920789,"node_id":"MDEyOklzc3VlQ29tbWVudDU2MjkyMDc4OQ==","user":{"login":"fforange","id":55771390,"node_id":"MDQ6VXNlcjU1NzcxMzkw","avatar_url":"https://avatars1.githubusercontent.com/u/55771390?v=4","gravatar_id":"","url":"https://api.github.com/users/fforange","html_url":"https://github.com/fforange","followers_url":"https://api.github.com/users/fforange/followers","following_url":"https://api.github.com/users/fforange/following{/other_user}","gists_url":"https://api.github.com/users/fforange/gists{/gist_id}","starred_url":"https://api.github.com/users/fforange/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fforange/subscriptions","organizations_url":"https://api.github.com/users/fforange/orgs","repos_url":"https://api.github.com/users/fforange/repos","events_url":"https://api.github.com/users/fforange/events{/privacy}","received_events_url":"https://api.github.com/users/fforange/received_events","type":"User","site_admin":false},"created_at":"2019-12-08T07:35:18Z","updated_at":"2019-12-08T07:35:18Z","author_association":"CONTRIBUTOR","body":"总结的很好"}}
{"actor":{"display_login":"fforange"}}