今天面腾讯, 这道题没想出来 题目要求基本如题, 然后只有一个元素的时候 (最右末尾元素) 对应值为空 当时面试官要求时间复杂度为 O(n), 想了半天也没想出来 提示了使用栈和栈顶指针做, 过了一会时间不够了就问下面的题了, 现在回过头来看一下这道题 这道题我一开始想的是栈中存储对应元素, 但是怎么推都达不到 O(n) 的复杂度, 后来百度了一下, 看到一篇博客, 原来栈中可以存储数组的索引... 作者:weixin_36888577 发表于 2019/03/21 20:22:38 原文链接 https://blog.csdn.net/weixin_36888577/article/details/88724916 阅读:34 继续阅读 >>


吕子健 19/03/21 20:22:38
文章目录@[toc]基本思想时间复杂度代码实现 基本思想 堆是一种完全二叉树, 分为大顶堆和小顶堆. 本篇博客我们默认要进行一个升序排序, 那么我们要构建一个大顶堆 堆排序的算法思想就是先构建一个大顶堆之后, 堆顶元素就是该数列最大值, 然后我们将其(即array[0])和数组末尾元素(即array[i])交换, 然后将剩下的元素(即array[0] 到 array[i - 1])重新进行调整... 作者:weixin_36888577 发表于 2019/03/11 15:39:33 原文链接 https://blog.csdn.net/weixin_36888577/article/details/88395215 阅读:27 继续阅读 >>


吕子健 19/03/11 15:39:33
文章目录问题描述解题思路状态转移方程不将第 i 种物品放进背包将第 i 种物品放进背包优化空间复杂度代码实现 问题描述 给定一组物品, 每种物品都有自己的重量和价格, 在限定的总重量内, 我们如何选择, 才能使得物品的总价格最高 每种物品只有一件, 要么放进背包, 要么不放, 即只能选择 0 / 1个, 该问题称为0-1背包 解题思路 设 F(i, j)表示放进前 i 种物品, 总容量不超过 j... 作者:weixin_36888577 发表于 2019/03/10 16:58:18 原文链接 https://blog.csdn.net/weixin_36888577/article/details/88380574 阅读:23 继续阅读 >>


吕子健 19/03/10 16:58:18
文章目录求解思路代码实现 这篇博客是听完郭炜老师的课之后的总结 求解思路 现在假设求两个字符串s1, s2的最长公共子序列 s1长度为len1, s2长度为len2, 我们设MaxLen(i, j)表示: s1左边 i 个字符形成的子串, 与s2左边 j 个字符形成的子串的最长公共子序列长度 i, j 从 0 开始 那么我们最终求解的是 MaxLen( len1, len2 )的值 那... 作者:weixin_36888577 发表于 2019/03/08 22:26:47 原文链接 https://blog.csdn.net/weixin_36888577/article/details/88360043 阅读:20 继续阅读 >>


吕子健 19/03/08 22:26:47
文章目录问题描述时间复杂度为O(n2)时间复杂度为O(n logn) 问题描述 对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度, 这里的子序列定义为这样一个序列U1,U2…,其中Ui < Ui+1,且A[Ui] < A[Ui+1]。 给定一个数字序列A及序列的长度n,请返回最长上升子序列的长度。 测试样例: [2 ,1, 5, 3... 作者:weixin_36888577 发表于 2019/03/07 15:51:42 原文链接 https://blog.csdn.net/weixin_36888577/article/details/88311002 阅读:26 继续阅读 >>


吕子健 19/03/07 15:51:42
文章目录红黑树的定义红黑树的插入操作红黑树的自平衡case 1case 2case 3case 4case 5总结红黑树与平衡二叉树 红黑树的定义 红黑树是特殊的二叉搜索树, 拥有自平衡的能力, 解决了BST树有可能退化成单链表的情况, 效率良好, 可以在O(log N)时间内完成查找, 删除, 添加. 红黑树应用很广泛, 主要用来存储有序的数据, STL 中的 set, map 等的内部实... 作者:weixin_36888577 发表于 2019/02/18 21:13:06 原文链接 https://blog.csdn.net/weixin_36888577/article/details/87646572 阅读:51 继续阅读 >>


吕子健 19/02/18 21:13:06
文章目录AVL树的定义AVL树不平衡的情况左子树的左子树插入结点 (左左)右子树的右子树插入节点左子树的右子树插入节点右子树的左子树插入节点删除结点插入节点更复杂的情况所有代码测试结果 AVL树的定义 平衡因子 : 树中某结点其左子树的高度和右子树的高度之差 AVL树中的任意一个结点, 其平衡因子的绝对值小于2 AVL树是一种特殊的二叉搜索树 (BST树), 相对于数据极端情况下, 二叉搜索树会... 作者:weixin_36888577 发表于 2019/02/13 21:59:47 原文链接 https://blog.csdn.net/weixin_36888577/article/details/87211314 阅读:68 评论:1 查看评论 继续阅读 >>


吕子健 19/02/13 21:59:47
example 如下例: class Test { public: Test(int v) : val(v) {} Test(const Test& t) { val = 100; cout << t.val << endl; } void show(Test a) { cout << a.val <& 作者:weixin_36888577 发表于 2019/01/29 20:38:25 原文链接 https://blog.csdn.net/weixin_36888577/article/details/86695218 继续阅读 >>


吕子健 19/01/29 20:38:25
文章目录二叉搜索树 (BST) 的定义BST 的构建BST 的插入BST 的查询BST 的删除BST 的检验 二叉搜索树 (BST) 的定义 二叉搜索树 (Binary Search Tree)的结点定义一般如下 typedef struct Node { int key; //节点关键值 Node* left; //左子树指针 Node* right; //右子树指针 } ... 作者:weixin_36888577 发表于 2019/01/27 20:50:41 原文链接 https://blog.csdn.net/weixin_36888577/article/details/86669496 阅读:62 继续阅读 >>


吕子健 19/01/27 20:50:41
/* 钢条切割 不同长度的钢条对应不同的价格 给定一定长度的钢条,怎样切割利益最大 注意: 最优解可能是完全不需要切割 */ #include <vector> #include <iostream> using namespace std; //给定长度从1到10对应的不同价格 vector<int> price{0, 1, 5, 8, 9, 10, 1... 作者:weixin_36888577 发表于 2019/01/24 17:52:16 原文链接 https://blog.csdn.net/weixin_36888577/article/details/86630966 继续阅读 >>


吕子健 19/01/24 17:52:16