finish the 8 week homework

jgan123 · jgan123 · commit 4bef67a5437f · 2020-08-02T15:37:01.000+08:00
diff --git a/Week07/findWords.js b/Week07/findWords.js
@@ -0,0 +1,73 @@
+/**
+ * 单词搜索||
+ * @param {character[][]} board
+ * @param {string[]} words
+ * @return {string[]}
+ */
+var findWords = function(board, words) {
+    let trie = new Trie();
+    for (let word of words) {
+        trie.insert(word);
+    }
+    let res = [];
+    let rows = board.length;
+    if (rows == 0) return res;
+    let cols = board[0].length;
+    for (let i = 0; i < rows; ++i) {
+        for (let j = 0; j < cols; ++j) {
+            dfs(board, i, j, trie.root, res);
+        }
+    }
+    return res;
+    function dfs(board, row, col, node, res) {
+        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) return;
+        let cur = board[row][col];
+        if (cur == '$' || node.children[cur.charCodeAt() - 97] == null) return;
+        node = node.children[cur.charCodeAt() - 97];
+        if (node.word != null) {
+            res.unshift(node.word);
+            node.word = null;
+        }
+        board[row][col] = '$';
+        dfs(board, row, col + 1, node, res);
+        dfs(board, row + 1, col, node, res);
+        dfs(board, row, col - 1, node, res);
+        dfs(board, row - 1, col, node, res);
+        board[row][col] = cur;
+    }
+};
+
+/**
+ * Initialize your data structure here.
+ */
+const TrieNode = function () {
+    this.isEnd = false;
+    this.word = null;
+    this.children = [];
+    for (let i = 0; i < 26; ++i) {
+        this.children[i] = null;
+    }
+} 
+
+var Trie = function() {
+    this.root = new TrieNode();
+};
+
+/**
+ * Inserts a word into the trie. 
+ * @param {string} word
+ * @return {void}
+ */
+Trie.prototype.insert = function(word) {
+    if (!word) return false;
+    let node = this.root;
+    for (let i = 0; i < word.length; ++i) {
+        if (!node.children[word[i].charCodeAt() - 97]) {
+            node.children[word[i].charCodeAt() - 97] = new TrieNode();
+        }
+        node = node.children[word[i].charCodeAt() - 97];
+    }
+    node.isEnd = true;
+    node.word = word;
+    return true;
+};
diff --git a/Week08/NOTE.md b/Week08/NOTE.md
@@ -1 +1,148 @@
-学习笔记
+学习笔记
+
+# 第八周学习笔记
+
+## 常见排序算法
+```javascript
+
+// 冒泡排序
+function bubbleSort(nums) {
+	for (let i = 0; i < nums.length - 1; ++i) {
+		for (let j = i + 1; j < nums.length; ++j) {
+			if (nums[i] > nums[j]) {
+				let temp = nums[i];
+				nums[i] = nums[j];
+				nums[j] = temp;
+			}
+		}
+	}
+}
+
+// 快速排序
+function quickSort(nums, left, right) {
+	if (left < right) {
+		let i = left, j = right, temp = nums[left];
+		while(i < j) {
+			while(i < j && nums[j] > temp) j--;
+			if (i < j) nums[i++] = nums[j];
+			while(i < j && nums[i] < temp) i++;
+			if (i < j) nums[j--] = nums[i];
+		}
+		nums[i] = temp;
+		quickSort(nums, left, i - 1);
+		quickSort(nums, i + 1, right);
+	}
+}
+
+// 归并排序
+const mergeSort = (nums) => {
+  if (nums.length <= 1) return nums
+  let mid = Math.floor(nums.length/2), 
+      left = nums.slice(0, mid), 
+      right = nums.slice(mid)
+  return merge(mergeSort(left), mergeSort(right))
+}
+
+const merge(left, right) => {
+  let result = []
+  while(left.length && right.length) {
+    result.push(left[0] <= right[0] ? left.shift() : right.shift()
+  }
+  while(left.length) result.push(left.shift())
+  while(right.length) result.push(right.shift())
+  return result
+}
+
+```
+
+## LRU缓存算法
+	LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体
+
+```javascript
+/**
+ * 使用 哈希表 + 双端链表 实现
+ */
+class LinkedNode {
+  constructor(key = 0, val = 0) {
+    this.key = key
+    this.val = val
+    this.prev = null
+    this.next = null
+  }
+}
+
+
+class LinkedList {
+  constructor() {
+    this.head = new LinkedNode()
+    this.tail = new LinkedNode()
+    this.head.next = this.tail
+    this.tail.prev = this.head
+  }
+
+
+  insertFirst(node) {
+    node.next = this.head.next
+    node.prev = this.head
+    this.head.next.prev = node
+    this.head.next = node
+  }
+
+
+  remove(node) {
+    node.prev.next = node.next
+    node.next.prev = node.prev
+  }
+
+
+  removeLast() {
+    if (this.tail.prev === this.head) return null
+    let last = this.tail.prev
+    this.remove(last)
+    return last
+  }
+}
+
+
+/**
+ * @param {number} capacity
+ */
+var LRUCache = function(capacity) {
+  this.capacity = capacity
+  this.keyNodeMap = new Map()
+  this.cacheLink = new LinkedList()
+};
+
+
+/** 
+ * @param {number} key
+ * @return {number}
+ */
+LRUCache.prototype.get = function(key) {
+  if (!this.keyNodeMap.has(key)) return -1
+  let val = this.keyNodeMap.get(key).val
+  this.put(key, val)
+  return val
+};
+
+
+/** 
+ * @param {number} key 
+ * @param {number} value
+ * @return {void}
+ */
+LRUCache.prototype.put = function(key, value) {
+  let size = this.keyNodeMap.size
+  if (this.keyNodeMap.has(key)) {
+    this.cacheLink.remove(this.keyNodeMap.get(key)); 
+    --size 
+  }
+  if (size >= this.capacity) {
+    this.keyNodeMap.delete(this.cacheLink.removeLast().key)
+  }
+  let node = new LinkedNode(key, value)
+  this.keyNodeMap.set(key, node)
+  this.cacheLink.insertFirst(node)
+};
+
+```
diff --git a/Week08/hammingWeight.js b/Week08/hammingWeight.js
@@ -0,0 +1,13 @@
+/**
+ * 位1的个数
+ * @param {number} n - a positive integer
+ * @return {number}
+ */
+var hammingWeight = function(n) {
+    let sum = 0;
+    while (n != 0) {
+        sum++;
+        n &= n - 1;
+    }
+    return sum;
+};
diff --git a/Week08/isAnagram.js b/Week08/isAnagram.js
@@ -0,0 +1,18 @@
+/**
+ * 有效的字母异位词
+ * @param {string} s
+ * @param {string} t
+ * @return {boolean}
+ */
+var isAnagram = function(s, t) {
+    if (s.length != t.length) return false;
+    let map = new Array(26).fill(0);
+    for (let i = 0; i < s.length; ++i) {
+        map[s.charCodeAt(i) - 97]++;
+        map[t.charCodeAt(i) - 97]--;
+    }
+    for (let num of map) {
+        if (num != 0) return false;
+    }
+    return true;
+};
diff --git a/Week08/isPowerOfTwo.js b/Week08/isPowerOfTwo.js
@@ -0,0 +1,8 @@
+/**
+ * 2的幂
+ * @param {number} n
+ * @return {boolean}
+ */
+var isPowerOfTwo = function(n) {
+    return n > 0 && (n & (n - 1)) == 0;
+};
diff --git a/Week08/relativeSortArray.js b/Week08/relativeSortArray.js
@@ -0,0 +1,26 @@
+/**
+ * 数组的相对排序
+ * @param {number[]} arr1
+ * @param {number[]} arr2
+ * @return {number[]}
+ */
+var relativeSortArray = function(arr1, arr2) {
+    let count = {};
+    for (let num of arr1) {
+        count[num] = count[num] ? count[num] + 1 : 1;
+    }
+    let index = 0;
+    for (let num of arr2) {
+        while (count[num] > 0) {
+            count[num]--;
+            arr1[index++] = num;
+        }
+    }
+    for (let num in count) {
+        while(count[num] > 0) {
+            arr1[index++] = num;
+            count[num]--;
+        }
+    }
+    return arr1;
+};
diff --git a/Week08/reverseBits.js b/Week08/reverseBits.js
@@ -0,0 +1,13 @@
+/**
+ * 颠倒二进制位
+ * @param {number} n - a positive integer
+ * @return {number} - a positive integer
+ */
+var reverseBits = function(n) {
+    n = (n >>> 16) | (n << 16)
+    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8)
+    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4)
+    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2)
+    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1)
+    return n >>> 0
+};
