Skip to content

Commit e974fff

Browse files
LexiXTLexiXT
committed
week
1 parent f113073 commit e974fff

5 files changed

Lines changed: 298 additions & 1 deletion

File tree

‎Week02/144-preorderTraversal.php‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
<?php
2+
/**
3+
* Definition for a binary tree node.
4+
* class TreeNode {
5+
* public $val = null;
6+
* public $left = null;
7+
* public $right = null;
8+
* function __construct($value) { $this->val = $value; }
9+
* }
10+
*/
11+
class Solution {
12+
13+
/**
14+
* @param TreeNode $root
15+
* @return Integer[]
16+
*/
17+
function preorderTraversal($root) {
18+
// 递归
19+
// if (empty($root)) {
20+
// return [];
21+
// }
22+
// $node = [$root->val];
23+
// $nodeleft = $noderight = [];
24+
// if (!is_null($root->left)) {
25+
// $nodeleft = $this->preorderTraversal($root->left);
26+
// }
27+
// if (!is_null($root->right)) {
28+
// $noderight = $this->preorderTraversal($root->right);
29+
// }
30+
// return array_merge($node, $nodeleft, $noderight);
31+
32+
$result = [];
33+
$this->helper($root, $result);
34+
return $result;
35+
}
36+
37+
private function helper($root, &$result){
38+
if ($root == null) {
39+
return [];
40+
}
41+
$result[] = $root->val;
42+
$this->helper($root->left, $result);
43+
$this->helper($root->right, $result);
44+
}
45+
}

‎Week02/242-isAnagram.php‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
<?php
2+
class Solution {
3+
4+
/**
5+
* @param String $s
6+
* @param String $t
7+
* @return Boolean
8+
*/
9+
function isAnagram($s, $t) {
10+
# 暴力排序法，时间复杂度O(Nlog(n)),空间复杂度O(1)
11+
// $s = str_split($s);
12+
// $t = str_split($t);
13+
// sort($s);
14+
// sort($t);
15+
// return $s == $t;
16+
17+
# 使用一个辅助哈希表，PHP中使用数组即可。遍历两个字符串,将每个字母作为键保存，键值保存同一个键名所有出现的键
18+
# 时间复杂度O(n),空间复杂度O(n)
19+
if ($s == $t) {
20+
return true;
21+
}
22+
if (strlen($s) != strlen($t)) {
23+
return false;
24+
}
25+
$sArr = $tArr = [];
26+
for ($i=0; $i<strlen($s); $i++) {
27+
$sArr[$s[$i]][] = $s[$i];
28+
$tArr[$t[$i]][] = $t[$i];
29+
}
30+
return $sArr == $tArr;
31+
32+
# 使用php的内置函数count_chars(string, model)，model=1将返回一个数组，ASCII 值为键名，出现的次数为键值
33+
# 时间复杂度O(N)，空间复杂度O(1)
34+
// return count_chars($s, 1) == count_chars($t, 1);
35+
}
36+
}

‎Week02/589-preorder.php‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
<?php
2+
/**
3+
* Definition for a Node.
4+
* class Node {
5+
* public $val = null;
6+
* public $children = null;
7+
* function __construct($val = 0) {
8+
* $this->val = $val;
9+
* $this->children = array();
10+
* }
11+
* }
12+
*/
13+
14+
class Solution {
15+
/**
16+
* @param Node $root
17+
* @return integer[]
18+
*/
19+
function preorder($root) {
20+
# 借助栈的特性，将二叉树压入栈
21+
# 时间复杂度O(M)，空间复杂度O(M)
22+
$s = new SplStack();
23+
$s->push($root);
24+
25+
$result = [];
26+
while (!$s->isEmpty()) {
27+
$data = $s->pop();
28+
$result[] = $data->val;
29+
for ($i=count($data->children)-1; $i>=0; --$i) {
30+
$s->push($data->children[$i]);
31+
}
32+
}
33+
return $result;
34+
35+
# 前序遍历，根-左-右。使用遍历，
36+
# 时间复杂度O(M)，M是N叉树的节点，空间复杂度O(M)
37+
// $result = [];
38+
// $this->helper($root, $result);
39+
// return $result;
40+
}
41+
42+
# 递归调用的方法
43+
private function helper($root, &$result) {
44+
if ($root->val === null) {
45+
return [];
46+
}
47+
$result[] = $root->val;
48+
foreach ($root->children as $children) {
49+
$this->helper($children, $result);
50+
}
51+
}
52+
}

‎Week02/94-inorderTraversal.php‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
<?php
2+
/**
3+
* Definition for a binary tree node.
4+
* class TreeNode {
5+
* public $val = null;
6+
* public $left = null;
7+
* public $right = null;
8+
* function __construct($value) { $this->val = $value; }
9+
* }
10+
*/
11+
class Solution {
12+
13+
/**
14+
* @param TreeNode $root
15+
* @return Integer[]
16+
*/
17+
function inorderTraversal($root) {
18+
# 递归 时间复杂度O(n),空间复杂度O(n)
19+
if (empty($root)) {
20+
return [];
21+
}
22+
$result = [];
23+
$this->helper($root, $result);
24+
return $result;
25+
}
26+
27+
private function helper($root, &$result){
28+
if ($root == null) {
29+
return [];
30+
}
31+
$this->helper($root->left, $result);
32+
$result[]=$root->val;
33+
$this->helper($root->right, $result);
34+
}
35+
}

‎Week02/NOTE.md‎

Lines changed: 130 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,130 @@
1-
学习笔记
1+
# 算法训练营第二周 学习笔记
2+
##### 问题
3+
## 第2周 第5课 | 哈希表、映射、集合
4+
- 哈希表 Hash table
5+
- 定义：哈希表（Hash table），也叫散列表，是根据关键码值（Key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫作散列函数（Hash Function），存放记录的数组叫作哈希表（或散列表）。
6+
- 工程实践：
7+
- 电话号码簿
8+
- 用户信息表
9+
- 缓存（LRU Cache）
10+
- 键值对存储（Redis）
11+
- 散列函数的特点：
12+
- 确定性
13+
- 散列碰撞（collision）
14+
- 不可逆性
15+
- 混淆特性
16+
- Map: key-value对，key不重复
17+
- Set：不重复元素的集合
18+
## 第2周 第6课 | 树、二叉树、二叉搜索树的实现特性
19+
>链表Linked List是特殊化的Tree，Tree是特殊化的图Graph。
20+
- 树 Tree
21+
- 二叉树 Binary Tree：每个节点最多有两个子树的树结构。
22+
- 二叉树遍历
23+
- 前序（Pre-order）：根-左-右
24+
- 中序（In-order）：左-根-右
25+
- 后序（Post-order）：左-右-根
26+
- 示例代码：
27+
```
28+
Python
29+
class TreeNode:
30+
def __init__(self, val):
31+
self.val = val
32+
self.left, self.right = None, None
33+
34+
def preorder(self, root):
35+
if root:
36+
self.traverse_path.append(root.val)
37+
self.preorder(root.left)
38+
self.preorder(root.right)
39+
40+
def inorder(self, root):
41+
if root:
42+
self.inorder(root.left)
43+
self.traverse_path.append(root.val)
44+
self.inorder(root.right)
45+
46+
def postorder(self, root):
47+
if root:
48+
self.postorder(root.left)
49+
self.postorder(root.right)
50+
self.traverse_path.append(root.val)
51+
```
52+
- 二叉搜索树 Binary Search Tree
53+
- 定义：也称二叉排序树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质的二叉树：
54+
- 左子树上所有节点的值均小于它的根节点的值；
55+
- 右子树上所有节点的值均大于它的根节点的值；
56+
- 以此类推：左、右子树也分别为二叉查找树（重复性）。
57+
- 中序遍历：升序遍历
58+
## 第2周 第6课 | 堆和二叉堆、图
59+
- 堆 Heap
60+
- 定义：可以迅速找到一堆树中的最大或最小值的数据结构。
61+
- 将根节点最大的堆叫作大顶堆或大根堆，根节点最小的堆叫作小顶堆或小根堆。常见的堆有二叉堆、菲波那切堆等。
62+
- 假设是大顶堆，则常见操作（API）：
63+
- find-max: O(1)
64+
- delete-max: O(logN)
65+
- insert(create): O(logN) or O(1)
66+
- [不同实现的比较](https://en.wikipedia.org/wiki/Heap_(data_structure))
67+
- [堆的实现代码](https://shimo.im/docs/Lw86vJzOGOMpWZz2/read)
68+
- 二叉堆 Binary Heap
69+
- 二叉堆性质：通过完全二叉树来实现（注意：不是二叉搜索树）
70+
- 完全二叉树是指根和叶子节点都是满的，除了最下面一级。
71+
- 一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
72+
- 二叉堆（大顶）它满足下列性质：
73+
- 是一棵完全树；
74+
- 树中任意节点的值总是>=其子节点的值。
75+
- 二叉堆实现细节：
76+
- 二叉堆一般都通过“数组”来实现
77+
- 假设“第一个元素”在数组中的索引为0的话，则父节点和子节点的位置关系如下：
78+
- 根节点（顶堆元素）是：a[0] ；
79+
- (01)索引为i的左孩子的索引是(2*i+1)；
80+
- (02)索引为i的右孩子的索引是(2*i+2)；
81+
- (03)索引为i的父节点的索引是floor((i-1)/2)，floor()函数向下取整。
82+
- Insert 插入操作 O(logN)
83+
- 新元素一律先插入到堆的尾部
84+
- HeapifyUp ：依次向上调整整个堆的结构（一直到根即可）
85+
- Delete Max - 删除操作O(logN)
86+
>注意：二叉堆是堆（优先队列Priority_queue）的一种常见且简单的实现；但是并不是最优的实现。
87+
- 图的实现和特性
88+
- 图的属性和分类
89+
- 图的属性
90+
- Graph（V, E）
91+
- V-vertex：点
92+
1. 度 - 入度和出度
93+
2. 点与点之间：连通与否
94+
- E - edge：边
95+
1. 有向和无向（单行线）
96+
2. 权重（边长）
97+
- 基于图相关的算法
98+
- DFS代码 - 递归写法
99+
```
100+
visited = set() # 和树中的DFS最大区别
101+
102+
def dfs(node, visited):
103+
if node in visited: # terminator
104+
# already visited
105+
return
106+
visited.add(node)
107+
# process current node here.
108+
...
109+
for next_node in node.children():
110+
if not next_node in visited:
111+
dfs(next_node, visited)
112+
```
113+
- BFS代码
114+
```
115+
def BFS(graph, start, end)：
116+
queue = []
117+
queue.append([start])
118+
119+
visited = set() # 和树中的BFS的最大区别
120+
121+
while queue:
122+
node = queue.pop()
123+
visited.add(node)
124+
process(node)
125+
nodes = generate_related_nodes(node)
126+
queue.push(nodes)
127+
```
128+
129+
130+

0 commit comments

Comments
 (0)