我太菜了

喜欢写Hello World的未来程序员.

二叉搜索树的后序序列

你快乐吗？

二叉搜索树的后序序列 C++，后序序列的规律。 后序序列的组成一定是[左子树，右子树，根结点]，再根据BST的规律，左 < 根 < 右， 就可以先找出左子树序列，右子树序列，根结点其实就是最后的结点。如果是合法的后序序列的话，必然满足所有左子树序列都小于根结点，所有右子树序列都大于根结点。 根据如上规律，可以递归每棵子树的序列，然后检查子树是否符合后序序列规律。 所以代...

Posted by bbkgl on September 26, 2019

二叉搜索树与双向链表

你快乐吗？

二叉搜索树与双向链表 C++，中序遍历构造链表，类似于线索二叉树。 既然要生成一个有序的链表，那就应该很快想到中序遍历。 方法如下： 首先中序遍历整棵树，可以得到key小的结点一定比key大的结点先访问； 需要同时能操作第k个被访问的结点和第k+1个被访问的结点，这样才能在前后两个结点之间建立关系； 也就是让第k个结点的right指向第k+1个结点，让第k+1个结点的l...

Posted by bbkgl on September 26, 2019

两个链表的第一个公共节点

你快乐吗？

两个链表的第一个公共结点 C++，链表。 首先分别遍历链表1和2，记录下二者长度差为k，然后利用两个指针遍历两个链表，先遍历长链表，当长链表指针走了k步时，短链表指针才开始走，碰到第一个相等的公共结点就是解。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next...

Posted by bbkgl on September 26, 2019

丑数

你快乐吗？

丑数 C++，丑数，质因数。 网上很多代码讲了怎么获得下一个最小的丑数，就是利用前面的每一个丑数分别*2，*3，*5，然后选出最小的那个。按照这个描述，只能每次将之前所有的丑数都和2、3、5乘一遍，那复杂度就是O(n)，可网上写出来的代码都是O(n)的，你说气人不气人？？？ 看了一会自己看懂了，把思路讲一下： 首先每个丑数都是由之前的丑数乘(*2，*3，*5)出来的； 为了...

Posted by bbkgl on September 26, 2019

不用加减乘除做加法

你快乐吗？

不用加减乘除做加法 C++，位运算。 不能用四则运算实现加法，就只能用位运算来实现了。 在十进制中，加法的过程如下，例如a + b = 134 + 267： 加法包括按位相加以及进位 按位相加就是[1 + 2 = 3， 3 + 6 = 9， 4 + 7 = 1]， 即a = [0, 3, 9, 1]； 进位就是把和当成四位数来看[0, 1 + 2 = 0, 3 + 6 ...

Posted by bbkgl on September 26, 2019

cmake中add_library、target_link_libraries、include_directories的使用

add_library、target_link_libraries、include_directories

这里没有细说每个函数的功能，因为这个百度都有的，我只说在我这里起到的作用。当然其实理解了这个项目的cmake，其他的也问题不大，大部分情况下的都是类似的。 栗子 其实这个东西最好就是举个例子了，首先可以看到整个项目的层级如下图，我们只需要一个CMakeLists.txt就好了。 然后看下cmake怎么写： project(fist-week) cmake_minimum_requ...

Posted by bbkgl on September 26, 2019

C和C++中引用的底层原理

关于引用是否占用内存，和指针的区别

菜菜菜菜菜。 给点希望行不行。 求包养。 其实我们见到的大部分解释都是这么说的： 引用就是变量的别名 引用不占用空间 引用和指针的区别，blablabla… 引用到底占用空间没，占用的话存的是什么？ 首先我们来看看对引用取地址会发生什么？ #include <cstdio> int main() { int a = 10; ...

Posted by bbkgl on September 26, 2019

98.ValidateBinarySearchTree

你快乐吗？

98. Validate Binary Search Tree 98. Validate Binary Search Tree 推荐办法 只需要明白一个结论：BST树的中序遍历一定是严格递增的 参考：二叉排序树（BST）/二叉查找树的建立(BST是笔试面试的常客)； 中序走一遍，生成中序序列； 判断中序序列是否递...

Posted by bbkgl on September 26, 2019

96.UniqueBinarySearchTrees

你快乐吗？

96. Unique Binary Search Trees 96. Unique Binary Search Trees C++，讲一下思路。 设n个结点的树能组成bst个数为dp(n)，以点i为根结点构成的BST数目为f(i)； 根据以上假设，我们可以先得出dp(0) = 0，dp(1) = 1，这是边界条件； 因为bst的个数应该为以每个结点作为根结点能构...

Posted by bbkgl on September 26, 2019

95.UniqueBinarySearchTreesII

你快乐吗？

95. Unique Binary Search Trees II C++。思路如下： 对于连续整数序列[left, right]中的一点i，若要生成以i为根节点的BST，则有如下规律： i左边的序列可以作为左子树结点，且左儿子可能有多个，所以有vector<TreeNode *> left_nodes = generate(left, i - 1)...

Posted by bbkgl on September 26, 2019

FEATURED TAGS
Blog leetcode C++ 剑指offer http Raft Linux Hadoop 设计模式 CV 链表 动态规划 图 拓扑排序 快排 二叉树 leveldb 数学 数组 二分 dfs profile hash表 字符串 贪心 01背包 最小堆 单调栈 luajit 计算机网络 操作系统 共享内存 linux 原地哈希 双指针 滑动窗口 UE4 编译原理
ABOUT ME

写过Hello World, 下过矿。

✉️ zoujiakun@zju.edu.cn

FRIENDS