这次是返回所有路径,只需要维护一下根节点到当前节点的路径即可(push-> recursive -> pop)
1 | /** |
这次是返回所有路径,只需要维护一下根节点到当前节点的路径即可(push-> recursive -> pop)
1 | /** |
1 | Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. |
如果当前节点为叶节点并且剩余和刚好等于val,则说明存在,否则返回左递归和右递归的或
1 | /** |
1 | Given a binary tree |
使用queue层序遍历1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
queue<TreeLinkNode*> q;
if (!root) return;
q.push(root);
while (!q.empty()) {
size_t sz = q.size();
TreeLinkNode *last = NULL;
for (size_t i = 0; i < sz; i++) {
auto tmp = q.front(); q.pop();
if (last) last->next = tmp;
last = tmp;
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
}
last->next = NULL;
}
}
};
使用O(1)空间,我们维护两层关系,上一层已经被设置好所有next指针,下一层保存开头节点后结尾节点,然后按序尝试更新尾节点,最后到达下一层
1 | /** |
1 | Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. |
1 | Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. |
常规面试题,求最低公共祖先
这里我们用路径交集的方法
首先求出根节点到两个节点的路径,放进stack里面(之前放在了vector里面,其实也ok),然后不断pop两个stack,直到它们顶部不同,那么上一个出栈的节点就是公共祖先
1 | /** |
递归写法1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || p == root || q == root) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
return !l ? r : !r ? l : root;
}
};
1 | Given a complete binary tree, count the number of nodes. |
注意这个树是complete tree,也就是说,除了最后一层,其它层都是满的,且最后一层的所有节点是从左到右连续的
我们逐步从根节点向下试探,考虑根节点的高度和右子树的高度,如果他们高度差1,则说明右子树在整个树的最后一层是有节点的,因此可知左子树是满的,
所以节点数加上1<<根节点树高,然后向右子树走。否则说明最后一层的最右节点存在于左子树中,因此加上1<<(根节点高度-1),因为这一次只知道右子树是满的,且高度少1,这里我们每次都加了子树及根节点,所以是2的幂。并往左子树走。
1 | /** |
1 | Given a binary tree, determine if it is a valid binary search tree (BST). |
判断一个树是否是BST依据是中序遍历是否按序,也等价于对于每个节点,其左子树的所有节点都小于它,右子树的所有节点都大于它。
使用一个指针保存上一次遍历的节点的地址,指针初始为空,表示根节点之前无节点,并且我们使用引用,这样避免使用二级指针,接着按正常中序遍历即可,注意规避根节点的情况(last为null)
1 | /** |
会用goroutine,也要了解其实现原理。这里是对go scheduler的翻译的概要
已经有OS内核中的调度器了,为什么还要自己写一个调度器?
单独开发一个调度器,可以让它知道什么时候内存是一致,在开始GC时,runtime只需要等待当前在CPU上运行的那个程序即可,而不比等所有线程
用户态线程到内核线程有N:1, 1:1, M:N三种关系
多个用户线程跑在一个内核线程上,上下文切换很快,但是无法利用多核
一个用户线程只在一个内核线程上跑,这样可以利用多核,但上下文切换很慢
多个goroutine在多个内核上跑,增加了调度的难度
有三个结构:M P G
M:machine,代表内核线程,真正干活的人
P:调度的上下文,局部的调度器,使goroutine在一个线程上跑,它实现了N:1 -> M:N
G:一个goroutine,它有自己的栈,EIP,其他信息(如陷入等待的channel),用于调度
每个M都有一个P,也有一个正在运行的G。还有一些在runqueue中的goroutine
为何要维护多个上下文?因为当一个OS线程被阻塞时,P可以转投奔另一个M
当阻塞返回时,它会偷一个context,如果没偷到就进入global runqueue
还有一种情况是context很快执行完了,它会去偷任务,要么从global runqueue要么从其他上下文,一般偷一半
上一节我们讲了选主的实现,这一次写的是Lab2的Part B: log replication。在尝试part B的测试样例后,我修改了之前的部分设计和bug,使得更吻合论文所要求的意思
这个操作应该有一个单独的协程,在这里面会类似心跳包的实现,不过不同之处在于,它不会睡眠,而是不断尝试发AE RPC,直到返回success,这个时候Nextindex也到了log末尾。
仍然要注意RPC前后term改变和reply term过大时,我们应该放弃处理这次rpc结果。当返回success时,会更新matchindex 和nextindex,然后让增加commitindex的协程起来更新commitindex
commitindex更新完毕后,会让apply线程开始做事,不断apply到状态机
Start函数应该只append,然后通过条件变量触发这些协程干事情,
在AE handler里面,严格按照论文所述,先舍弃冲突及其之后的log,然后追加,同时更新follower的commitindex,也就是说, commitindex是由leader流向follower
心跳包不要掺和nextindex的事情,不然会发生错误的多次递减,从而越过了共同前缀
在退回到follower时,执行很多相同的代码,抽出来作为一个函数。考虑到candidate会select在两个channel上,因此注意先改变state再传入channel,这样一来,主线程会阻塞在timer的channel里,这个顺序很重要。
抽出来的这个函数,不一定每次都会reset timer,只有在给别人投票时,才会重置
持久化部分应该说是十分简单了,就是encode/decode需要持久化的内容,然后在这些内容被更新时,立即写(这里是写内存)
当leader和follower没找到共享前缀时,leader会逐个entry回退,这十分低效,论文有提到让follower返回一些信息,这样一步回退。这个优化手段,在失败经常发生时,是十分有必要的,而且能显著减少RPC次数,不过我还没有实现,下一篇我会描述一下实现的坑
主线程处于leader状态时,不要睡一会起来看一下,因为会耽误睡眠,应该也等在条件变量,一旦收到消息,立即回到follower状态
lab3会实现一个客户端,初步了解到的内容是需要retry,记录每个command的uuid,避免多次append
各个协程的功能:
sendAE
从Leader同步entry到follower
sendRV
成为candidate之后请求投票
sendPeriodHeartBeat
成为Leader之后发送心跳
applyLoop
在commitindex更新后进行逐个apply
advanceCommitIdx
在更新matchindex之后(sendAE中RPC返回成功时),更新commitindex(超过半数即可更新commitindex)
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true