Skip to content

Commit f787d54

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#501 from Zachy-lee/master
361-Week 02
2 parents a27de14 + a1ba3dc commit f787d54

File tree

9 files changed

+358
-13
lines changed

9 files changed

+358
-13
lines changed

‎.idea/algorithm004-01.iml‎

Lines changed: 12 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/misc.xml‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/modules.xml‎

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/vcs.xml‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/workspace.xml‎

Lines changed: 94 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Week 01/id_361/NOTE.md‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,18 @@
1-
# 第一周心得：
2-
3-
经过听课及作业练习,发现比较适合个人的解题和学习思路：
4-
5-
- 第一步，拆题，看清题目及要求，运用“切题四件套”。
6-
7-
- 第二步，确定方法，通常情况下由易到难、自顶向下来做。首先的想到通用的如中间变量交换的方法（move zeros）,或者暴力法（container-with-most-water）。
8-
另外空间想象力也很重要，需要通过图形变幻来解题，比如move zeros中的滚雪球法，container-with-most-water中的暴力法。可以自己提前画画变化的步骤和逻辑有助于解题。
9-
10-
- 第三步，在前面的基础之上 能解出题目进行，时间和空间复杂的分析，以及如何进行空间和时间的转换，分析各种解题方法的优劣目前来说达不到老师的熟练程度，后期我想熟练之后可以把这个步骤提升到第一步来做，。
11-
12-
- 第四步，刚开始感觉各种不熟练，一些细节点会卡住，因为基础不扎实。查漏补缺，刻意练习，深化理解。“五毒神掌”贯穿。
1+
# 第一周心得：
2+
3+
经过听课及作业练习,发现比较适合个人的解题和学习思路：
4+
5+
- 第一步，拆题，看清题目及要求，运用“切题四件套”。
6+
7+
- 第二步，确定方法，通常情况下由易到难、自顶向下来做。首先想到的直观的暴力法（container-with-most-water），一些基本会用到的小技巧，如中间变量交换的方法（move zeros），另外空间想象力也很重要，需要通过图形变幻来解题，比如move zeros中的滚雪球法，container-with-most-water中的暴力法。可以自己画图(理清变化的步骤和思路)来辅助解题。
8+
9+
- 第三步，在前面的基础之上。进行时间和空间复杂的分析，以及如何进行空间和时间的转换，分析各种解题方法的优劣目前来说达不到老师的熟练程度，后期熟练之后可以把这个步骤提升到第一步来做，。
10+
11+
- 第四步，刚开始感觉各种不熟练，一些细节点会卡住，因为基础不扎实。所以查漏补缺，刻意练习，深化理解，用“五毒神掌”贯穿。
12+
13+
14+
做一个一名前端，虽然很少写后端代码，但是通过学习数据结构和算法，也可以同时学习java甚至其他语言，因为都是相通的，学习语言的核心就在于数据结构和算法。希望通过持之以恒的学习打通全栈能力。
15+
16+
不足：对知识的提炼和总结不够。后面需要加强对不同语言和前端的对比分析，前端很多算法和数据结构(比如ES6 中 map set、TypeScript 中class等等)也是借鉴了其他语言的特性。
1317

1418

‎Week 02/id_361/NOTE.md‎

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,85 @@
1-
# NOTE
1+
## 第二周学习总结
22

3+
### 1.Hash Table
4+
#### 1.1 哈希碰撞解决
5+
- 拉链式解决冲突 => 链表(或退化为O(n)的时间复杂度)
36

47

8+
> 应用：ST BOOST 区块链
9+
10+
> 平均查询O(1)
11+
12+
#### 1.2 JavaScript中的Hash Map
13+
> JavaScript 的对象（Object），本质上是键值对的集合（Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。
14+
>为了解决这个问题，ES6 提供了 Map 数据结构。
15+
- [es6中Set 和 Map的使用](http://es6.ruanyifeng.com/#docs/set-map)
16+
- javascript中hashMap应用，以two sum题为例
17+
```
18+
var twoSum = function(nums, target) {
19+
let map = new Map();
20+
for (let i = 0; i < nums.length; i++) {
21+
let complement = target - nums[i];
22+
if (map.has(complement)) {
23+
return [map.get(complement), i];
24+
}
25+
map.set(nums[i], i);
26+
}
27+
throw new Error("No two sum solution");
28+
};
29+
```
30+
---
31+
32+
### 2.树
33+
#### 2.1树 是没有环的图
34+
链表->树->图
35+
- 生活中的树：
36+
- alpha go
37+
- 下棋
38+
- 人生状态
39+
- 游戏发展 科技树
40+
41+
#### 2.2 树的面试题解法一般都是递归，为什么？
42+
43+
- [递归的概念-知乎](https://www.zhihu.com/question/20507130)
44+
45+
![Image text](https://pic3.zhimg.com/80/1f818b686dc5482cbb8343d8caf65dac_hd.jpg)
46+
- 树本身是没有后继，本身的数据结构决定
47+
- 注意：递归不一定会影响效率
48+
49+
#### 2.3 树的常见操作
50+
- 查询
51+
log2n 类似于二分查找
52+
- 删除
53+
在叶子上直接删除 在其他位置的必须找到替换节点
54+
55+
- 遍历
56+
57+
- preorder traversal 先序遍历
58+
根左右
59+
60+
- inorder traversal 中序遍历
61+
左根右
62+
63+
- postorder traversal 后续遍历
64+
左右根
65+
66+
67+
68+
### 3 递归
69+
#### 3.1 范型递归 树的递归
70+
- 不要人肉递归
71+
- 找到最近最简单方法，将其拆解成可重复解决的问题（重复子问题）
72+
- 数学归纳法思维
73+
74+
[递归代码模板](https://shimo.im/docs/DjqqGCT3xqDYwPyY/read)
75+
76+
#### 3.2 复杂递归： 分治 回溯
77+
-重复性：
78+
- 最近重复性（分治、回溯）
79+
- 最优重复性 （动态规划）
80+
81+
[分治代码模板](https://shimo.im/docs/3xvghYh3JJPKwdvt/read)
82+
83+
[括号生成问题](https://leetcode-cn.com/problems/generate-parentheses/)
84+
85+

‎Week 02/id_361/leetCode_1_361.js‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
//1. Two Sum
2+
3+
/**
4+
* javascript
5+
* 1.暴力法
6+
* 时间复杂度：O(n^2)
7+
* 空间复杂度：O(1)
8+
* @param {number[]} nums
9+
* @param {number} target
10+
* @return {number[]}
11+
*/
12+
var twoSum = function(nums, target) {
13+
var arr=[]
14+
for(let i=0;i<nums.length;i++){
15+
for(let j=i+1;j<nums.length;j++){
16+
if(target - nums[i]=== nums[j]){
17+
arr.push(i)
18+
arr.push(j)
19+
}
20+
}
21+
}
22+
return arr
23+
};
24+
25+
/**
26+
* javascript
27+
* 2.两遍哈希表
28+
* 时间复杂度：O(n)
29+
* 空间复杂度：O(n)
30+
* @param {number[]} nums
31+
* @param {number} target
32+
* @return {number[]}
33+
*/
34+
var twoSum = function(nums, target) {
35+
let map = new Map()
36+
for (let i = 0; i < nums.length; i++) {
37+
map.set(nums[i], i);
38+
}
39+
for (let i = 0; i < nums.length; i++) {
40+
let complement = target - nums[i];
41+
if (map.has(complement) && map.get(complement) != i) {
42+
return [ i, map.get(complement) ];
43+
}
44+
}
45+
throw new Error("No two sum solution");
46+
};
47+
48+
/**
49+
* javascript
50+
* 2.一遍哈希表
51+
* 时间复杂度：O(n)
52+
* 空间复杂度：O(n)
53+
* @param {number[]} nums
54+
* @param {number} target
55+
* @return {number[]}
56+
*/
57+
var twoSum = function(nums, target) {
58+
let map = new Map();
59+
for (let i = 0; i < nums.length; i++) {
60+
let complement = target - nums[i];
61+
if (map.has(complement)) {
62+
return [map.get(complement), i];
63+
}
64+
map.set(nums[i], i);
65+
}
66+
throw new Error("No two sum solution");
67+
};

‎Week 02/id_361/leetCode_94_361.js‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
//94. Binary Tree Inorder Traversal
2+
3+
4+
/**
5+
* * javascript
6+
* 1.递归
7+
* 时间复杂度：O(n)
8+
* 空间复杂度：最坏情况下需要空间O(n)O(n)，平均情况为O(\log n)O(logn)。
9+
* Definition for a binary tree node.
10+
* function TreeNode(val) {
11+
* this.val = val;
12+
* this.left = this.right = null;
13+
* }
14+
*/
15+
/**
16+
* @param {TreeNode} root
17+
* @return {number[]}
18+
*/
19+
var inorderTraversal = function(root) {
20+
var res=[]
21+
helper(root,res)
22+
return res
23+
};
24+
25+
function helper(root,res){
26+
if (root != null) {
27+
if (root.left != null) {
28+
helper(root.left, res);
29+
}
30+
res.push(root.val);
31+
if (root.right != null) {
32+
helper(root.right, res);
33+
}
34+
}
35+
}
36+
37+
/**
38+
* javascript
39+
* 2.基于栈的遍历
40+
* Definition for a binary tree node.
41+
* function TreeNode(val) {
42+
* this.val = val;
43+
* this.left = this.right = null;
44+
* }
45+
*/
46+
/**
47+
* @param {TreeNode} root
48+
* @return {number[]}
49+
*/
50+
var inorderTraversal = function(root) {
51+
let res = []
52+
let stack = []
53+
let curr=root
54+
while (curr != null || stack.length>0) {
55+
while (curr != null) {
56+
stack.push(curr);
57+
curr = curr.left;
58+
}
59+
curr = stack.pop();
60+
res.push(curr.val);
61+
curr = curr.right;
62+
}
63+
return res;
64+
};
65+
66+
67+

0 commit comments

Comments
 (0)