给一个数字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,
越来越体会到编程的好处了，真的能够提高工作效率。
是这样，我女友现在需要统计一个复杂的表， 这个sheet3的公式需要在sheet1传过来，我目前还没有掌握更好的方法，只能使用vba对付一下。
Sub MyCode()
Range("p9") = "=COUNT(输入!C112:C166)"
End Sub
很简单，以Sub开始， End Sub结尾， 上述的语句就是在这个sheet3上面的P9位置，使用execl自带的COUNT函数，执行的结果就是P9的单元格已经是公式化的，推荐使用这种。
上面代码的另一种写法就是
Sub MyCode()
Dim loc As String
loc = "p9"
Range(loc) = "=COUNT(输入!C112:C166)"
End Sub
》Rows(10).Select
Sub MyCode()
Dim loc As String
loc = "p9"
Range(loc) = "=COUNT(输入!C112:C166)"
Dim arr(1 To 9) As String
arr(1) = "b17"
arr(2) = "c17"
arr(3) = "d17"
arr(4) = "e17"
arr(5) = "f17"
arr(6) = "g17"
arr(7) = "h17"
arr(8) = "i17"
arr(9) = "j17"
Debug.Print arr(1)
End Sub
CTRL + G 会打印 “b17”
Please try:
.Range("A:A, C:C, G:G").ColumnWidth = 15
and
.Range("A:C, G:G").Font.Color = vbRed
Public Function StringFormat(ByVal mask As String, ParamArray tokens()) As String
Dim i As Long
For i = LBound(tokens) To UBound(tokens)
mask = Replace(mask, "{" & i & "}", tokens(i))
Next
StringFormat = mask
End Function
Sub MyCode()
Dim row_l As String
row_l = "33" ‘临时存储的位置
Dim arr(1 To 9) As String
arr(1) = "b" + row_l
arr(2) = "c" + row_l
arr(3) = "d" + row_l
arr(4) = "e" + row_l
arr(5) = "f" + row_l
arr(6) = "g" + row_l
arr(7) = "h" + row_l
arr(8) = "i" + row_l
arr(9) = "j" + row_l
Debug.Print arr(1) ' debug
Dim loc_s, loc_e As String
loc_s = "D332" '另一个sheet的域
loc_e = "D378"
Dim fun_total, fun_126, fun_112, fun_98, fun_84, fun_70, fun_56, fun_55, tmp As String
fun_total = "=COUNT(输入!{0}:{1})"
tmp = StringFormat(fun_total, loc_s, loc_e)
Range(arr(1)) = tmp
fun_126 = "=COUNTIF(输入!{0}:{1},"">=126"")"
tmp = StringFormat(fun_126, loc_s, loc_e)
Range(arr(2)) = tmp
fun_112 = "=COUNTIFS(输入!{0}:{1},"">=112"",输入!{2}:{3},""<126"")"
tmp = StringFormat(fun_112, loc_s, loc_e, loc_s, loc_e)
Range(arr(3)) = tmp
fun_98 = "=COUNTIFS(输入!{0}:{1},"">=98"",输入!{2}:{3},""<112"")"
tmp = StringFormat(fun_98, loc_s, loc_e, loc_s, loc_e)
Range(arr(4)) = tmp
fun_84 = "=COUNTIFS(输入!{0}:{1},"">=84"",输入!{2}:{3},""<98"")"
tmp = StringFormat(fun_84, loc_s, loc_e, loc_s, loc_e)
Range(arr(5)) = tmp
fun_70 = "=COUNTIFS(输入!{0}:{1},"">=70"",输入!{2}:{3},""<84"")"
tmp = StringFormat(fun_70, loc_s, loc_e, loc_s, loc_e)
Range(arr(6)) = tmp
fun_56 = "=COUNTIFS(输入!{0}:{1},"">=56"",输入!{2}:{3},""<70"")"
tmp = StringFormat(fun_56, loc_s, loc_e, loc_s, loc_e)
Range(arr(7)) = tmp
fun_55 = "=COUNTIF(输入!{0}:{1},""<56"")"
tmp = StringFormat(fun_55, loc_s, loc_e)
Range(arr(8)) = tmp
End Sub
虽然算出来了各个分段的人数，但是人数比目前还有一点问题， 当前的arr(x)并不能在双引号中使用， 比如这样的:
=SUM(C24:F24)/B24