Skip to content

Commit 4abf199

Browse files
SpongeMaSpongeMa
committed
week04 assignment-1
1 parent 10a43c2 commit 4abf199

5 files changed

Lines changed: 501 additions & 2 deletions

File tree

‎Week03/NOTE.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,10 +38,10 @@ def recursion(level,param1,param2,...):
3838

3939
实际上是一种特殊的递归，本质就是要找重复性。
4040

41-
不断在每一层去试，每一层有不同的方法，典型问题：八皇后、数独
41+
回溯就是不断在每一层去试，每一层有不同的方法，典型问题：八皇后、数独
4242

4343
- 找到一个可能存在的正确的答案
44-
- 在尝试了所有可能的分步方法后宣告该问题没有答案，就取消上一步或者上几步的计算
44+
- 在尝试了所有可能的分步方法后如果该问题没有答案，就取消上一步或者上几步的计算
4545
- 再通过其他可能的分步方式
4646

4747
worst：O(2^n)

‎Week04/102.levelOrder.js‎

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
/*
2+
* @lc app=leetcode.cn id=102 lang=javascript
3+
*
4+
* [102] 二叉树的层序遍历
5+
*
6+
* https://leetcode-cn.com/problems/binary-tree-level-order-traversal/description/
7+
*
8+
* algorithms
9+
* Medium (62.88%)
10+
* Likes: 555
11+
* Dislikes: 0
12+
* Total Accepted: 153.7K
13+
* Total Submissions: 243.9K
14+
* Testcase Example: '[3,9,20,null,null,15,7]'
15+
*
16+
* 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
17+
*
18+
*
19+
*
20+
* 示例：
21+
* 二叉树：[3,9,20,null,null,15,7],
22+
*
23+
* ⁠ 3
24+
* ⁠ / \
25+
* ⁠ 9 20
26+
* ⁠ / \
27+
* ⁠ 15 7
28+
*
29+
*
30+
* 返回其层次遍历结果：
31+
*
32+
* [
33+
* ⁠ [3],
34+
* ⁠ [9,20],
35+
* ⁠ [15,7]
36+
* ]
37+
*
38+
*
39+
*/
40+
41+
// @lc code=start
42+
/**
43+
* Definition for a binary tree node.
44+
* function TreeNode(val) {
45+
* this.val = val;
46+
* this.left = this.right = null;
47+
* }
48+
*/
49+
/**
50+
* @param {TreeNode} root
51+
* @return {number[][]}
52+
*/
53+
/**@other
54+
* 解法一：BFS(层序遍历)
55+
* time:O(n),每个点进队出队各一次
56+
* space:O(n),队列中元素的个数不超过n个
57+
* runtime:64ms 93.82%
58+
* memory usage:37.2MB 8.33%
59+
*/
60+
var levelOrder = function (root) {
61+
if (!root) return [];
62+
63+
let queue = [];
64+
let result = [];
65+
queue.push(root); //将根节点放如队列中
66+
67+
while (queue.length) {
68+
let size = queue.length; //获取当前队列的长度，即这一层的节点个数
69+
let level = []; //存放每一层的所有结点
70+
71+
//循环每一层的结点
72+
for (let i = 0; i < size; i++) {
73+
let node = queue.shift();
74+
level.push(node.val); //将队列中的元素都取出来(即获取这一层的节点)，放到当前层level中
75+
//如果节点的左右子树不为空，则放如队列中
76+
node.left && queue.push(node.left);
77+
node.right && queue.push(node.right);
78+
}
79+
result.push(level); //将leve当前层的所有结点加入结果数组中
80+
}
81+
return result;
82+
};
83+
84+
/**@other
85+
* 解法二：DFS(递归)
86+
* 由于DFS不是按层访问,所以要加个level记录当前层数
87+
* 当递归到新节点要把该节点放如level对应的列表的末尾
88+
* 当遍历到新的一层level,而最终结果 result 中还没有创建 level 对应的列表时,
89+
* 则在 result 中新建一个列表用来保存该 level 的所有节点.
90+
*
91+
* time:O(n),每个点进队出队各一次
92+
* space:O(h),h是树的高度
93+
* runtime:84ms 18.9%
94+
* memory usage:37.4MB 8.33%
95+
*/
96+
var levelOrder = function(root) {
97+
let result = [];
98+
if(!root) return result;
99+
100+
function dfs(level,root){
101+
if(result.length < level) result.push([]);
102+
//将当前节点的值加入result中，level表示当前层
103+
result[level-1].push(root.val);
104+
//递归的处理左子树，右子树，同时将层数level+1
105+
root.left && dfs(level+1,root.left);
106+
root.right && dfs(level+1,root.right);
107+
}
108+
109+
dfs(1,root);
110+
return result;
111+
};
112+
// @lc code=end

‎Week04/127.ladderLength.js‎

Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,186 @@
1+
/*
2+
* @lc app=leetcode.cn id=127 lang=javascript
3+
*
4+
* [127] 单词接龙
5+
*
6+
* https://leetcode-cn.com/problems/word-ladder/description/
7+
*
8+
* algorithms
9+
* Medium (41.81%)
10+
* Likes: 364
11+
* Dislikes: 0
12+
* Total Accepted: 47.5K
13+
* Total Submissions: 111.4K
14+
* Testcase Example: '"hit"\n"cog"\n["hot","dot","dog","lot","log","cog"]'
15+
*
16+
* 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord
17+
* 的最短转换序列的长度。转换需遵循如下规则：
18+
*
19+
*
20+
* 每次转换只能改变一个字母。
21+
* 转换过程中的中间单词必须是字典中的单词。
22+
*
23+
*
24+
* 说明:
25+
*
26+
*
27+
* 如果不存在这样的转换序列，返回 0。
28+
* 所有单词具有相同的长度。
29+
* 所有单词只由小写字母组成。
30+
* 字典中不存在重复的单词。
31+
* 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
32+
*
33+
*
34+
* 示例 1:
35+
*
36+
* 输入:
37+
* beginWord = "hit",
38+
* endWord = "cog",
39+
* wordList = ["hot","dot","dog","lot","log","cog"]
40+
*
41+
* 输出: 5
42+
*
43+
* 解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
44+
* ⁠ 返回它的长度 5。
45+
*
46+
*
47+
* 示例 2:
48+
*
49+
* 输入:
50+
* beginWord = "hit"
51+
* endWord = "cog"
52+
* wordList = ["hot","dot","dog","lot","log"]
53+
*
54+
* 输出: 0
55+
*
56+
* 解释: endWord "cog" 不在字典中，所以无法进行转换。
57+
*
58+
*/
59+
60+
// @lc code=start
61+
/**
62+
* @param {string} beginWord
63+
* @param {string} endWord
64+
* @param {string[]} wordList
65+
* @return {number}
66+
*/
67+
68+
/**@other
69+
* 解法一：BFS
70+
* time:O(n*m),n是wordList.length,m是beginword.length
71+
* space:O(n*m),要在allComboMap记录每个单词的m个通用状态，访问数组的大小是n
72+
* runtime:136ms 76.83%
73+
* memory usage:50.9MB 50%
74+
*/
75+
var ladderLength = function(beginWord, endWord, wordList) {
76+
if(!wordList.includes(endWord)) return 0; //如果wordList不存在endWord，返回0
77+
78+
let allComboMap = {}; //所有组合map
79+
let len = beginWord.length;
80+
81+
// 对 wordList 做预处理，找出所有的通用状态
82+
for (let i = 0;i<wordList.length;i++) {
83+
for(let j = 0;j<len;j++){
84+
let tmp = wordList[i].slice(0,j)+'*'+wordList[i].slice(j+1);
85+
//将通用状态记录在字典中，键是通用状态，值是所有具有通用状态的单词。
86+
if(allComboMap[tmp])
87+
allComboMap[tmp].push(wordList[i]);
88+
else
89+
allComboMap[tmp] = [wordList[i]]
90+
}
91+
}
92+
93+
let queue = [[beginWord,1]]; //将包含 beginWord 和 1 的元组放入队列中，1 代表节点的层次。我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。
94+
let visited = new Set(); //为了防止出现环，使用访问数组记录。
95+
visited.add(beginWord);
96+
97+
while (queue.length) {
98+
let [word,level] = queue.shift();
99+
//找到 word 的所有通用状态
100+
for (let i=0;i<len;i++) {
101+
let newWord = word.slice(0,i)+'*'+word.slice(i+1);
102+
if(!allComboMap[newWord]) continue; //如果word的当前通用状态不存在，则跳过
103+
104+
//检查这些通用状态是否存在其它单词的映射
105+
for (let adjacentWord of allComboMap[newWord]) {
106+
// 找到endWord返回其最短长度
107+
if(adjacentWord == endWord)
108+
return level + 1;
109+
110+
//如果adjacentWord没有被访问过，将其加入队列并加入已访问列表
111+
if (!visited.has(adjacentWord)) {
112+
queue.push([adjacentWord,level+1])
113+
visited.add(adjacentWord);
114+
}
115+
}
116+
}
117+
}
118+
return 0; //没有找到
119+
};
120+
121+
/**@other
122+
* 解法二：双向BFS
123+
* 与解法一类似，但是是从头尾两个部分一起搜索遍历，当一个节点被头尾都搜索到就终止
124+
* time:O(n*m),n是wordList.length,m是beginword.length
125+
* space:O(n*m),要在allComboMap记录每个单词的m个通用状态，访问数组的大小是n
126+
* runtime:176ms 63.64%
127+
* memory usage:52.2MB 50%
128+
*/
129+
var ladderLength = function(beginWord, endWord, wordList) {
130+
if(!wordList.includes(endWord)) return 0;
131+
let allComboMap = {};
132+
let len = beginWord.length;
133+
134+
for (let word of wordList) {
135+
for (let i = 0;i<len;i++) {
136+
let genericForms = word.slice(0,i) + '*' +word.slice(i+1);
137+
if(allComboMap[genericForms])
138+
allComboMap[genericForms].push(word);
139+
else
140+
allComboMap[genericForms] = [word];
141+
}
142+
}
143+
let queueBegin = [[beginWord,1]];
144+
let queueEnd = [[endWord,1]];
145+
let visitedBegin = new Map();
146+
let visitedEnd = new Map();
147+
visitedBegin.set(beginWord,1);
148+
visitedEnd.set(endWord,1);
149+
while (queueBegin.length && queueEnd.length) {
150+
//from Begin
151+
let ans = visitWordNode(queueBegin,visitedBegin,visitedEnd);
152+
if (ans>-1) return ans;
153+
//from End
154+
ans = visitWordNode(queueEnd,visitedEnd,visitedBegin);
155+
if (ans>-1) return ans;
156+
}
157+
158+
function visitWordNode(queue,visited,otherVisited){
159+
let [word,level] = queue.shift();
160+
for (let i = 0;i<len;i++){
161+
let newWord = word.slice(0,i) + '*' + word.slice(i+1);
162+
163+
if(!allComboMap[newWord]) continue;
164+
for (let adjacentWord of allComboMap[newWord]) {
165+
if (otherVisited.has(adjacentWord))
166+
return level + otherVisited.get(adjacentWord);
167+
168+
if (!visited.has(adjacentWord)) {
169+
visited.set(adjacentWord,level+1);
170+
queue.push([adjacentWord,level+1]);
171+
}
172+
}
173+
}
174+
return -1;
175+
}
176+
return 0;
177+
}
178+
179+
/**@other
180+
* 解法三：
181+
*/
182+
var ladderLength = function(beginWord, endWord, wordList) {
183+
let wordSet =
184+
}
185+
// @lc code=end
186+

0 commit comments

Comments
 (0)