Merge pull request algorithm001#645 from tidelgl/week-4

GeekUniversity · web-flow · commit 7799074f82c8 · 2019-05-13T17:31:06.000+08:00
【064-week4】作业（JavaScript）
diff --git a/Week_04/id_64/LeetCode_279_64.js b/Week_04/id_64/LeetCode_279_64.js
@@ -0,0 +1,32 @@
+/**
+ * 使用图论，求最短路径，通过队列使用BFS广度优先遍历
+ * @param {number} n
+ * @return {number}
+ */
+var numSquares = function(n) {
+    if (n < 1) { return; }
+    const queue = [[n, 0]]; // [[完全平方差, 步数]]
+    const set = new Set(); // 保存访问过的节点
+    set.add(n);
+    while(queue.length != 0) {
+      const el = queue.shift();
+      const num = el[0];
+      const step = el[1];
+          
+      if (num == 0) { // 找到最短路径
+        return step;
+      }
+      
+      for (let i = 1; ; i++) {
+        const nn = num - i*i;
+        if (nn < 0) { // num - i*i >= 0
+          break;
+        }
+        if (!set.has(nn)) {
+          queue.push([nn, step + 1]); // 保存节点和步数，节点是完全平方差
+          set.add(nn);
+        }
+      }
+    }
+    return;
+  };
diff --git a/Week_04/id_64/LeetCode_455_64.js b/Week_04/id_64/LeetCode_455_64.js
@@ -0,0 +1,26 @@
+/**
+ * 455. 分发饼干
+ * https://leetcode-cn.com/problems/assign-cookies/
+ * 贪心算法，greedy
+ * T(n) = O(nlogn)
+ * @param {number[]} g
+ * @param {number[]} s
+ * @return {number}
+ */
+var findContentChildren = function(g, s) {
+  // 将小孩的饼干从大到小排序
+  g = g.sort((a, b) => b - a);
+  s = s.sort((a, b) => b - a);
+  
+  let si = 0, gi = 0, res = 0;
+  while(gi < g.length && si < s.length) {
+    if (s[si] >= g[gi]) {
+      res++;
+      si++;
+      gi++;
+    } else {
+      gi++;
+    }
+  }
+  return res;
+};
diff --git a/Week_04/id_64/LeetCode_51_64.js b/Week_04/id_64/LeetCode_51_64.js
@@ -0,0 +1,55 @@
+/**
+ * 51. N皇后
+ * https://leetcode-cn.com/problems/n-queens/
+ * 递归，回溯
+ * @param {number} n
+ * @return {string[][]}
+ */
+var solveNQueens = function(n) {
+    const col = new Array(n).fill(false); 
+    const dia1 = new Array(2*n - 1).fill(false); 
+    const dia2 = new Array(2*n - 1).fill(false); 
+    
+    // 尝试在一个 n 皇后问题中，摆放第 index 行的皇后位置
+    function putQueen(n, index, row) {
+      if (index == n) {
+        res.push(generateBoard(n, row));
+      }
+      
+      for (let i = 0; i < n; i++) {
+        // 尝试将第index行的皇后放到第i列
+        if (!col[i] && !dia1[index + 1] && !dia2[index - n - 1]) {
+          // 开始递归
+          row.push(i);
+          col[i] = true;
+          dia1[index + i] = true;
+          dia2[index - i + n - 1] = true;
+          putQueen(n, index + 1, row);
+          
+          // 开始回溯
+          col[i] = false;
+          dia1[index + i] = false;
+          dia2[index - i + n - 1] = false;
+          row.pop();
+        }
+      }
+      return;
+    }
+    
+    function generateBoard(n, row) {
+      // 初始化 n 个 string 每个 string n 个 '.'
+      const board = new Array(n).fill(new Array(n).fill('.').join(''));
+      for (let i = 0; i < n; i++) {
+        const s = board[i].split('');
+        s[row[i]] =  'Q';
+        board[i] = s.join('');
+      }
+      return board;
+    }
+    
+    const res = [];
+    const row = [];
+    putQueen(n, 0, row);
+    
+    return res;
+  };
diff --git a/Week_04/id_64/LeetCode_784_64.js b/Week_04/id_64/LeetCode_784_64.js
@@ -0,0 +1,41 @@
+/**
+ * 784. 字母大小写全排列
+ * https://leetcode-cn.com/problems/letter-case-permutation/
+ * 深度优先DFS 递归 https://user-images.githubusercontent.com/49065208/56465164-f0a10800-642a-11e9-81a0-5894bb030e6f.png
+ * dfs(arr, i):
+ *   if i == str.length: res.push(str.json(''))
+ *   dfs(arr, i + 1)
+ *   if arr[i] is letter:
+ *      toggleCase(arr[i])
+ *      dfs(arr, i + 1)
+ *      toggleCase(arr[i]) // toggle back case
+ * 
+ * @param {string} S
+ * @return {string[]}
+ */
+var letterCasePermutation = function(S) {
+  const result = [];
+  function toggleCase(s) {
+      if (/[A-Z]/.test(s)) {
+          return s.toLowerCase();
+      } else {
+          return s.toUpperCase();
+      }
+  }
+  
+  function dfs(arr, i, res) {
+      if (i == arr.length) {
+          res.push(arr.join(''));
+          return;
+      }
+      dfs(arr, i + 1, res);
+      if(/\d/.test(arr[i])) { return; } // is number
+      arr[i] = toggleCase(arr[i]); // transform to upper/lower case
+      dfs(arr, i + 1, res);
+      arr[i] = toggleCase(arr[i]);// transform back to upper/lower case
+  }
+  
+  dfs(S.split(''), 0, result);
+  
+  return result;
+};
diff --git a/Week_04/id_64/NOTE.md b/Week_04/id_64/NOTE.md
@@ -1 +1,24 @@
-# 学习笔记
+# 学习笔记
+
+- 动态规划
+  - 自底向上
+  - 通过求子问题的最优解， 可以获得原问题的最优解
+  - 有重叠子问题 + 最优子结构，还必须记忆搜索，即可用动态规划
+
+## 常用数据结构的小结及 ADT API
+- Trie 字典树, 每个节点都是 map, 根节点为空
+  - add(val)
+  - isWord(val)
+  - contains(val)
+  - isPrefix(val)
+
+## 其他
+- JS 初始化二维数组 `Array(m).fill().map(() => Array(n).fill(-1))`
+
+# 书本笔记
+
+![14](https://user-images.githubusercontent.com/49065208/57494782-8084f400-72fd-11e9-8ad1-49d08aef2b01.png)
+
+![12](https://user-images.githubusercontent.com/49065208/57494772-719e4180-72fd-11e9-818a-7c07fb45df5e.jpg)
+
+![13](https://user-images.githubusercontent.com/49065208/57494774-7236d800-72fd-11e9-9084-8133a8f807f4.jpg)
