finish the week 09 homework

jgan123 · jgan123 · commit d899cab940b2 · 2020-08-09T19:01:09.000+08:00
diff --git a/Week09/NOTE.md b/Week09/NOTE.md
@@ -1 +1,10 @@
-学习笔记
+学习笔记
+
+# 第九周学习笔记
+
+## 不同路径II状态转移方程
+1. 状态定义
+	dp[i][j] 表示走到格子(i, j)的方法数
+2. 状态转义
+	(i, j)上有障碍物 dp[i][j] = 0
+	(i, j)上无障碍物 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
diff --git a/Week09/firstUniqChar.js b/Week09/firstUniqChar.js
@@ -0,0 +1,16 @@
+/**
+ * 字符串中的第一个唯一字符
+ * @param {string} s
+ * @return {number}
+ */
+var firstUniqChar = function(s) {
+    let map = new Map();
+    for (let i = 0; i < s.length; ++i) {
+        let c = s.charAt(i);
+        map.has(c) ? map.set(c, map.get(c) + 1) : map.set(c, 1);
+    }
+    for (let i = 0; i < s.length; ++i) {
+        if (map.get(s.charAt(i)) == 1) return i;
+    }
+    return  -1;
+};
diff --git a/Week09/isIsomorphic.js b/Week09/isIsomorphic.js
@@ -0,0 +1,20 @@
+/**
+ * 同构字符串
+ * @param {string} s
+ * @param {string} t
+ * @return {boolean}
+ */
+var isIsomorphic = function(s, t) {
+    let mapS = new Map();
+    let mapT = new Map();
+    for (let i = 0; i < s.length; ++i) {
+        let c1 = s.charAt(i);
+        let c2 = t.charAt(i);
+        if (mapS.get(c1) != mapT.get(c2)) return false;
+        if (!mapS.has(c1)) {
+            mapS.set(c1, i + 1);
+            mapT.set(c2, i + 1);
+        }
+    }
+    return true;
+};
diff --git a/Week09/reverseOnlyLetters.js b/Week09/reverseOnlyLetters.js
@@ -0,0 +1,24 @@
+/**
+ * 仅仅反转字母
+ * @param {string} S
+ * @return {string}
+ */
+var reverseOnlyLetters = function(S) {
+    let left = 0, right = S.length - 1;
+    S = S.split('');
+    while (left < right) {
+        if (!check(S[left])) left++
+        else if (!check(S[right])) right--;
+        else if (check(S[left]) && check(S[left])) {
+            let temp = S[left];
+            S[left] = S[right];
+            S[right] = temp;
+            left++;
+            right--;
+        } 
+    }
+    return S.join('');
+    function check(s) {
+        return /[a-zA-Z]/.test(s);
+    }
+};
diff --git a/Week09/reverseStr.js b/Week09/reverseStr.js
@@ -0,0 +1,24 @@
+/**
+ * 反转字符串||
+ * @param {string} s
+ * @param {number} k
+ * @return {string}
+ */
+var reverseStr = function(s, k) {
+    let i = 0, j = k - 1;
+    s = s.split('');
+    for (let i = 0; i <= s.length; i += 2*k) {
+        reverse(i, i + k - 1);
+    }
+
+    function reverse(left, right) {
+        while (left < right) {
+            let temp = s[left];
+            s[left] = s[right];
+            s[right] = temp;
+            left++;
+            right--;
+        }
+    }
+    return s.join('');
+};
diff --git a/Week09/reverseWords.js b/Week09/reverseWords.js
@@ -0,0 +1,24 @@
+/**
+ * 翻转字符串里头的单词
+ * @param {string} s
+ * @return {string}
+ */
+var reverseWords = function(s) {
+    let left = 0, right = s.length - 1;
+    while (left < right && s.charAt(left) == " ") ++left;
+    while (left < right && s.charAt(right) == " ") --right;
+
+    let deque = [], word = [];
+    while (left <= right) {
+        let c = s.charAt(left);
+        if (word.length != 0 && c == " ") {
+            deque.unshift(word.join(''));
+            word = [];
+        } else if (c != " "){
+            word.push(c);
+        }
+        ++left;
+    }
+    deque.unshift(word.join(''));
+    return deque.join(" ");
+};
diff --git a/Week09/reversewords3.js b/Week09/reversewords3.js
@@ -0,0 +1,25 @@
+/**
+ * 反转字符串中的单词 III
+ * @param {string} s
+ * @return {string}
+ */
+var reverseWords = function(s) {
+    let left = 0, right = s.length - 1;
+    
+    let res = [], word = [];
+    while (left <= right) {
+        if (s.charAt(left) != " ") {
+            word.unshift(s.charAt(left));
+        }
+        if (s.charAt(left) == " " && word.length) {
+            res.push(word.join(''));
+            word = [];
+            res.push (" ");
+        } else if (s.charAt(left) == " ") {
+            res.push(" ");
+        }
+        left++;
+    }
+    res.push(word.join(''));
+    return res.join('');
+};
diff --git a/Week09/validPalindrome.js b/Week09/validPalindrome.js
@@ -0,0 +1,19 @@
+/**
+ * 验证回文字符串II
+ * @param {string} s
+ * @return {boolean}
+ */
+var validPalindrome = function(s) {
+    let left = 0, right = s.length - 1;
+    while (left < right && s.charAt(left) == s.charAt(right)) {
+        left++, right--;
+    }
+    return palindrome(left + 1, right) || palindrome(left, right - 1);
+    
+    function palindrome(left, right) {
+        while (left < right && s.charAt(left) == s.charAt(right)) {
+            left++, right--;
+        }
+        return left >= right;
+    }
+};
