第九周作业

Simona0769 · Simona0769 · commit 802b489b5380 · 2020-08-09T16:04:38.000+08:00
diff --git a/Week09/NOTE.md b/Week09/NOTE.md
@@ -1 +1,24 @@
-学习笔记
+# 第九周学习笔记
+## 高级动态规划
+### 最长子序列 Longest common sequence
+dp[i][j] = dp[i-1][j-1] (if s1[i-1] == s[j-1])  
+else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
+### 最长子串 Longest common substring
+dp[i][j] = dp[i-1][j-1] + 1 (if s1[si[i-1] == s2[j-1]])  
+else dp[i][j] = 0
+### 编辑距离
+* 如果word1[i]与word2[j]相同，显然dp[i][j] = dp[i-1][j-1]
+* 如果word1[i]与word2[j]不同，那么dp[i][j]可以通过
+    1. 在dp[i-1][j-1]的基础上做replace操作达到目的
+    2. 在dp[i-1][j]的基础上做insert操作达到目的
+    3. 在dp[i][j-1]的基础上做delete操作达到目的
+    取三者最小情况即可
+
+## 字符串匹配算法
+1. 暴力法 brute force
+2. Rabin-Karp算法  
+    1. 假设子串的长度为M(pat), 目标字符串的长度为N(txt)
+    2. 计算子串的hash值hash_pat
+    3. 计算目标字符串txt中每个长度为M的子串的hash值(共需要计算N-M+1次)
+    4. 比较hash值: 如果hash值不同，字符串必然不匹配；如果hash值相同，则还需要通过朴素算法再次判断
+3. KMP算法
diff --git a/Week09/programming/decode-ways.js b/Week09/programming/decode-ways.js
@@ -0,0 +1,25 @@
+/**
+ * @param {string} s
+ * @return {number}
+ */
+var numDecodings = function(s) {
+    if(s.length <= 0 || s[0] === '0') {
+        return 0
+    }
+    let pre = 1, curr = 1
+    for(let i = 1; i < s.length; i++) {
+        const temp = curr
+        if (s[i] === '0') {
+            if (s[i-1] === '1' || s[i-1] === '2') {
+                curr = pre
+            } else {
+                return 0
+            }
+        } else if (s[i-1] === '1' || (s[i-1] === '2' && s[i]>= '1' && s[i] <= '6')) {
+            curr = curr + pre
+        } 
+        pre = temp
+    }
+
+    return curr
+};
diff --git a/Week09/programming/find-all-anagrams-in-a-string.js b/Week09/programming/find-all-anagrams-in-a-string.js
@@ -0,0 +1,33 @@
+/**
+ * 暴力法
+ * @param {string} s
+ * @param {string} p
+ * @return {number[]}
+ */
+var findAnagrams = function(s, p) {
+    const isAnagrams = (word1, word2) => {
+        if (word1.length !== word2.length) {
+            return false
+        }
+        const res = new Array(26).fill(0)
+        const _start = 'a'.charCodeAt(0)
+        for(let i = 0; i < word1.length; i++) {
+            res[word1.charCodeAt(i) - _start]++
+            res[word2.charCodeAt(i) - _start]--
+        }
+        for(let i = 0; i < res.length; i ++) {
+            if(res[i] !== 0) {
+                return false
+            }
+        }
+        return true
+    }
+    const res = []
+    const n = p.length
+    for(let j = 0; j < s.length - n + 1; j++) {
+        if (isAnagrams(s.substring(j, j + n), p)) {
+            res.push(j)
+        }
+    }
+    return res
+};
diff --git a/Week09/programming/longest-increasing-subsequence.js b/Week09/programming/longest-increasing-subsequence.js
@@ -0,0 +1,23 @@
+/**
+ * @param {number[]} nums
+ * @return {number}
+ */
+var lengthOfLIS = function(nums) {
+    if(nums.length <= 0) {
+        return 0
+    }
+    const dp = []
+    dp[0] = 1;
+    let max = 1;
+    for(let i = 1; i < nums.length; i++) {
+        let _max = 0;
+        for(let j = 0; j <= i; j ++) {
+            if (nums[i] > nums[j]) {
+                _max = Math.max(_max, dp[j])
+            }
+        }
+        dp[i] = _max + 1;
+        max = Math.max(max, dp[i])
+    }
+    return max
+};
