又解鎖了git新技能， 开心。
事情的缘由是这样的， 目前我们的gerrit是允许别人cherry-pick下来后把自己的改动推送到gerrit上去，这样的一个潜在风险是: 我们需要的gerrit链接(或者说基于的)也会再次被update， 很无语, 下面是复现这个场景:
54ce0be59cb98c3a304e37d300bbcdbce3da54d9 (HEAD -> test) [Do not merge] Test cases for HNewInstance
44cc0c7487b2c5a16ac963ea4e50b8a8eef161c2 Add xx1 support Add xx2 support
3e82976b5856b2617c374e7663cfe40941f42918 Add yyz function
........................................(master, HEAD)
也就是说， 我的commit(54ce0b)是基于别人的commit ID(44cc0c和3e8297), 再往下就是已经merge的commit id， 可以不用管了。 我现在的问题是， 比如我的代码在test分支上无问题的，现在呢准备提交，ok，看着一切很简单的样子， git add, commit, push 一气呵成，但是， sorry， 我在gerrit服务器上一看， 别人的gerrit也有update， 最可气的是居然把别人的文件给删除了。
先不说我这种git 操作流程是否不正确，仅就目前的事情来说，必须想出一种方案，解决目前棘手的问题。那么， 我现在能想到的一个方案就是， 我保证代码在 test 分支上没有问题， 然后 移动 到一个刚从master分支上拉出来的新分支，然后在push， 这样子肯定不会影响别人， 关键是怎么做呢？ google了一番， 我的出发点是rebase或者merge啥的， 直到here 才算解决问题。
针对以上的问题分析， 我们可以得出一个问题抽象模型: 如何将一个分支上的git commit移动到另一个分支上， 从我上面的问题中， 具体一点就是如何将一个分支上的HEAD移动到另一个分支上， 再一般化， 就是如何将一个分支上的任何commit移动到另一个分支上。
一般我们都是基于master分支去检出一个新分支， 这样就可以最大程度的较少冲突的可能性。
git checkout master
git checkout -b test_tmp
然后把你想 移动的 commit的hash值放后面就可以。
git cherry-pick 54ce0b
该commit就会移动到你的分支上了， 对的， 被移动的commit可以位于分支上的任何位置。 我也很纳闷 git cherry-pick是如何知道 local branch的commit信息的。
通过以上的问题可以发现， cherry-pick很有用， 尤其作为负责人的时候， 比如说， 一个 git pull请求， 如果有bad commit，你 不得不cherry-pick 下， 这也是文中参考资料的使用场景。
这个时候再回味一下我之前的fool
给一个数字n,试着计算以这个[1,n]为root的bst有多少独一无二的。
这是一个数学题目，其中和catalan数密切相关。catalan数有很多种应用场景，值得总结一把。
f(0) = 0;
令f(0) = 1
f(1) = f(0)*f(0)
f(2) = f(1)*f(0) + f(0)*f(1)
f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2)
……
f(n) = f(n-1)*f(0) + f(n-2)*f(1) +……f(0)*f(n-1)
由此得出规律，
对于任意以i为根节点的二叉树，
其左子树的值一定小于i，也就是[0, i - 1]区间，
而右子树的值一定大于i，也就是[i + 1, n]区间。
假设左子树有m种排列方式，而右子树有n种，则对于i为根节点的二叉树总的排列方式就是m x n
参考资料: https://www.cnblogs.com/liuliu5151/p/9108838.html
则代码如下:
class Solution {
public:
int numTrees(int n) {
int a[n + 1];
a[0] = a[1] = 1;
for(int i = 2; i <=n; i++){
a[i] = 0;
for (int j = 0; j < i; j++)
a[i] += a[j] * a[i-j-1]; // 这一步尤其精妙
}
return a[n];
}
};
这道题目是给你一个BST，然后另外给定一个值，判断这个值是否在BST中，如果在的话，返回以这个值为root的子树， 否则返回null。 期初吧，我想的是应该可能需要栈什么的操作，憋了半天，实在没什么好的办法，参考下其他人的答案吧，不丢人的。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while(root != nullptr && root->val != val){
root = (root->val > val) ? (root->left) : (root->right);
}
return root;
}
};
要么就说，好的程序员价值连城呢，如果放到古代，这种人都得是杨过 郭靖这类的大侠，像我这种，都得是不配给台词的 小罗罗。
这道题目还是比较有意思的，原因在于使用另一个数据结构保存树中的某一节点，我当时想到过这个问题就是不知道运用什么方法解决妥当：考虑过 BST,让root值不停的与k（或者差进行比较），但是呢，这样很大的问题就是你不确定怎么不遗漏。原来，你像使用下面的set容器，就可以解决这个问题 还可以确定一点的是： set就是一个hashtable.
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> set;
return dfs(root, set, k);
}
bool dfs(TreeNode* root, unordered_set<int>& set, int k){
if(root == NULL) return false;
if(set.count(k - root->val)) return true;
set.insert(root->val);
return dfs(root->left, set, k) || dfs(root->right, set, k);
}
};
使用 ffmpeg 的入门 ：
最简单的命令:
ffmpeg -i buka.flv -c copy -ss 00:00:00 -t 00:10:03.446 edu17-264.mp4
其中，这个-c可以指定编码格式(包括解码器)。
-i 设定输入流
-f 设定输出格式
-ss 开始时间
-c 指定编解码器
ffmpeg -i buka.flv -vcodec h264 -ss 00:00:00 -t 00:10:03.446 edu17-2-264.mp4
指定video的编码格式为h264.
ffmpeg -i buka.flv -vcodec h264 -ss 00:00:00 -t 00:10:03.446 -s 960X540 edu18-960-540-264.mp4
今天开始解锁leetcode tree medium的题目,首先你得感觉有意思。
建议阅读这篇csdn
递归和非递归。前者 使用一个void型的函数，判断左子树， 打印root的值，判断右子树。
中序遍历,递归版:
class Solution {
public:
void displayInorder(vector<int> &arr, TreeNode *root){
if (root->left) displayInorder(arr, root->left);
arr.push_back(root->val);
if (root->right) displayInorder(arr, root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (root)
displayInorder(res, root);
return res;
}
};
非递归版:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
if (!root) return res;
TreeNode* p = root;
while(p || !s.empty()){
while(p){
s.push(p);
p = p->left;
}
if(!s.empty()){
p = s.top(); s.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
};
前序遍历非递归版:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
TreeNode *p = root;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
res.push_back(p->val);
p = p->left;
}
if(!s.empty()){
p = s.top(); s.pop();
p = p->right;
}
}
return res;
}
};
使用双栈:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
TreeNode *cur;
stack<TreeNode*> s1;
stack<TreeNode*> s2;
s1.push(root);
while(!s1.empty()){
cur = s1.top(); s1.pop();
if(cur->left) s1.push(cur->left);
if(cur->right) s1.push(cur->right);
s2.push(cur);
}
while(!s2.empty()){
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}
};
这是解决二叉树的层次遍历题目，下面使用了两个队列，关键在于题目返回的类型是 vector<vector
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
vector<int> level; // 存储每一层的元素
if (!root) return ans;
std::queue<TreeNode*> s; // save output to val array
std::queue<TreeNode*> nodes; // save left & right of root
s.push(root); // root val in queue
while(!s.empty()){
TreeNode *cur = s.front(); s.pop();//得到队首元素, 并且出队
level.push_back(cur->val);
if (cur->left) nodes.push(cur->left); // 注意，是保存在nodes queue 中
if (cur->right) nodes.push(cur->right);
if(s.empty()){
s.swap(nodes); // 这是关键，把存储叶子节点的队列中的内容交换到s queue中
ans.push_back(level);
level.clear(); // 清0每一行的输出结果
}
}
return ans;
}
};
尤其使用了 std::queue.swap() 的api，感觉拖慢了运行速度。试着一个队列怎么样？使用一个null marker。
还有一种使用一个队列的方式，如下代码:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == nullptr) return {}; // 尤其注意"{}"在赋值时的应用
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int count = q.size();
vector<int> temp;
while(count--)
{
TreeNode* curr = q.front();
q.pop();
temp.push_back(curr->val);
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
}
res.push_back(temp);
}
return res;
}
};
这个题目还可以使用dfs的思路，利用递归完成这一要求。但是有人据说，这种方法只是一个形似，然而实质上不是level遍历。 效率呢，肯定赶不上非递归的。
class Solution {
public:
vector<vector<int>> res; // 其实，也许这也就是成员变量的作用吧，但是这样监控起来太难了
vector<vector<int>> levelOrder(TreeNode* root) {
levelOrderHelper(root, 0);
return res;
}
void levelOrderHelper(TreeNode* root, int level){
if (!root) return;
if (level == res.size()) res.push_back(vector<int>()); // 按行申请空间
res[level].push_back({root->val}); // res[level].push_back({val}) 是经典
if (root->left) levelOrderHelper(root->left, level+1);
if(root->right) levelOrderHelper(root->right, level+1);
}
};
下面使用一个null marker，我真不明白为啥这样做;
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
q.push(NULL);
vector<int> cur_vec;
while(!q.empty()) {
TreeNode* t = q.front();
q.pop();
if (t==NULL) {
result.push_back(cur_vec);
cur_vec.resize(0);
if (q.size() > 0) {
q.push(NULL);
}
} else {
cur_vec.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return result;
}
};
这个题目的意思是就是在前面题目的基础上（层次遍历），把每个数累加然后取double，注意int溢出的问题。
#include <iomanip>
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
if (!root) return res;
queue<TreeNode*> q;
TreeNode* cur = NULL;
q.push(root);
while(!q.empty()){
double sum = 0.0, anv = 0.0;
int count = q.size();
for(int i = 0; i < count; i++){
cur = q.front(); q.pop();
sum +=(double)(cur->val); // 避免 int overflow
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
anv = sum/count;
res.push_back(anv);
}
return res;
}
};
就是给你一个数字和一个二叉树，然后判断从root到leaf的和是不是等于这个数字，递归的算法如下:
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root->left && !root->right && root->val == sum)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
使用stack实现这个算法:
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
stack<TreeNode*> s;
TreeNode* cur = NULL, *tmp = NULL;
stack<int> sum_stack;
if (!root) return false;
s.push(root);
while(!s.empty()){
cur = s.top(); s.pop();
if(cur->left == cur->right)
if (cur->val == sum)
return true;
if (cur->left) {
cur->left->val += cur->val;
s.push(cur->left);
}
if(cur->right) {
cur->right->val += cur->val;
s.push(cur->right);
}
}
return false;
}
};
题目很简单就是给你一个sum，让你保存从root到leaf的一个路径。这里利用了回溯的思想，请参考本blog的算法系列。
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> path;
findPaths(res, path, root, sum);
return res;
}
private:
void findPaths(vector<vector<int>> &paths, vector<int> &path, TreeNode *cur, int sum){
if(!cur) return ;
path.push_back(cur->val);
if(!(cur->left) && !(cur->right) && (cur->val == sum))
paths.push_back(path);
if(cur->left) findPaths(paths, path, cur->left, sum - cur->val);
if (cur->right) findPaths(paths, path, cur->right, sum - cur->val);
path.pop_back();
}
};
原本这是一个技术笔记，我不想把个人的情感如此的向其他人倾诉，但是，我找不到一个发泄的窗口， 就一句话： 中国足协，去你妈的！
啥也不说， 你们高兴就好！
无论以后鲁能还在不在联赛， 我会永远支持你们， 尽管是一家国企，我自己承认，山东沾了国网的光。国企和民企， 就不应该在竞技层面上一起搞。 但是，鲁能是我在有足球记忆就存在的一个符号，怕是一辈子也找不到另一支令我牵挂的 球队了。
从此以后，中国足球再也不看，自己娱乐健身就OK， 不浪费时间与感情去让自己体会屎一样的憋屈。
中国足协， 中国足球上不去， 你们绝对负有不可推卸的责任。你们让中国社会目前在经济发展过程中存在的种种弊端 在足球场上得到了展示。 中国足球让人寒了心！
再见！我爱中国，但是我希望中国足协消失！
超级指令与user 指令之间的转换，在riscv中是依赖ecall指令完成的
宏内核简单理解就是所有的功能在内核中实现(与内核相关的)， 而微内核就是 ， 比如， 文件系统的一个使用， shell打开文件不是直接使用open或者read 而是使用ipc进行交互
一个进程拥有自己的地址空间， 这个特性是由页表实现的。
xv6 riscv 页表只能38 bits, 大小就是 2^38-1=0x3fffffffff,