- 博客(31)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 二叉树中序遍历
搜索二叉树转双向链表思路二叉树中序遍历非递归版本的中序遍历用栈来实现。一个元素出现在栈顶一次，这一次会被处理并出栈。trick:用一个指针去记录当前节点cur，如果cur->left左侧还未遍历，就会将cur入栈并访问cur->left。一行很重要的代码是cur = cur->right，这一句之后如果cur == NULL，则说明栈顶元素的左子树访问完了，应该访问当前...
2019-10-15 11:36:17
157
原创 单调栈
应用往往用来遍历数组，找到数组中离某个元素最近的比它小或者比它大的值。O(n)的复杂度，一遍扫描。当然也可以用来找一个元素两侧比它大或者比它小的元素长度（用它将要出栈时的当前元素下标i减去它出栈后栈顶元素的下标j再减1）。方法假如找某个元素左边离它最近的比它小的元素，那么我们要用单调递增的栈。从左到右扫描数组，假如当前元素arr[i]比栈顶元素s.top()小，则s.pop()，直到栈为空...
2019-08-07 21:38:14
131
原创 差分数组和差分矩阵
应用对某一数组或矩阵进行频繁的范围修改后输出操作结果。方法一维差分数组从原数组得到差分数组b的方法为b[i] = a[i] - a[i-1]。所以差分数组b的前缀和数组是原数组a。我们想要修改数组a的一个范围[l,r]的值加c时，只需要b[l] += c，然后b[r+1] -= c，在对b数组求前缀和复原数组时就可以得到修改后的a。tricks零数组的差分数组依旧是零数组。假设零数组...
2019-08-04 20:51:26
4889
2
原创 前缀和
应用快速求某一范围内的数值的和方法一维前缀和S[i]表示前i个数的和，那么用S[r] - S[l-1] 就可以得到第l个数到第r个数的和（若数组下标从1开始则是[l, r]范围内的数值和）。二维前缀和尽量让矩阵横纵坐标从1开始，可以避免很多边界情况。S[i][j] = S[i-1][j] + S[i][j-1] + arr[i][j] - S[i-1][j-1] 就可以得到以(1,1...
2019-08-04 20:02:01
124
原创 快速排序
应用快速排序，适合于可以随机访问的容器（vector, 数组），不适合链表。不稳定排序。最坏情况O(n2)O(n^2)O(n2)，取决于pivot的选择。方法划分过程：选择一个pivot，将数组划分为左右两段，左段小于等于pivot，右段大于等于pivot。将划分过程左右两段进行递归。模版两种模版，只是划分过程不同。交换法void quick_sort(vector<int&...
2019-08-04 15:55:32
112
原创 二分查找
应用一个数组，左右两段有不同的性质，寻找分段的节点。方法两种情况，找左半段的右节点和找右半段的左节点。（如下，分别对应higher_bound和lower_bound）。步骤：首先确定check函数确定找的节点如果是左半段的右节点，则是right = mid-1，这样搜索区间向左移动。同时mid=(left+right)/2+1，而left=mid。如果是右半段的左节点，则是 ...
2019-08-04 15:43:12
119
原创 二分搜索
二分搜索的模版https://www.bilibili.com/video/av59202632?from=search&seid=11859395808577485920 20min左右的讲解模版1:// 闭区间[l, r]，前半段满足性质A，后半段不满足性质A，目标是找到后半段第一个值。int bsearch_1(int l, int r){ while (l <...
2019-07-20 19:07:58
80
原创 机器学习之树模型
决策树模型，树的结构固定，自顶向下分叉。优化方法就是搜索某个特征的取值范围作为分支的界限。所以，各种决策树模型的体现在度量信息增益的方式，Formally讲，就是损失函数。回归树用MSE，分类树用交叉熵。xgboost模型推导第t步的损失函数得到新的目标函数并进一步，将它分解为T个叶子节点上子目标函数之和（方便下边搜索树结构使用）。解这个二次函数的最小值问题得到形式化的解法。贪心...
2019-06-22 19:01:46
428
原创 House Robber LeetCode动态规划
LeetCode上动态规划的一个系列，从多个角度来考虑问题，从而更加熟练动态规划，加深理解和精通应用。House Robber I解法1： 递归解法2： 递归+memorization解法3： 动态规划1：两个动态规划数组dp[i][0]和dp[i][1]分别表示在第i个位置不抢和抢的收益。dp[i][0] = max(dp[i-1][0], dp[i-1][1])dp[i][1] ...
2019-03-20 14:00:43
127
原创 林轩田“机器学习基石”笔记(1) 机器学习理论基础
Feasibility of Learning直观来讲机器学习其实是用采样估计整体。When Can Machines Learn?No Free Lunch (必须有归纳偏好才可以学习)假如没有明确要学习的问题，对于样本，所有的模型假设fff同等重要，那么从D\mathcal{D}D中学习去推断D\mathcal{D}D以外的是注定失败的。在西瓜书中，把NFL定理认为是归纳偏好。也就是...
2019-02-27 21:14:28
272
原创 InvalidArgumentError：You must feed a value for placeholder tensor
InvalidArgumentError：You must feed a value for placeholder tensor ‘Placeholder_2’ with dtype float and shape [128,100,10]在运行sess.run(tf.global_variables_initializers())时因为使用了tf.py_func，它的返回值是shape=&l...
2018-11-02 14:59:28
3871
原创 排序算法比较
排序算法比较排序算法好多种，通过它们之间的比较掌握它们的适用场景，优缺点。时间复杂度参考geeksforgeeks这篇博客会持续更新。选择排序 vs 插入排序大量交换 vs 最少交换插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以通过二分查找改进查找插入位置的效率。插入排序需要反复移动数据，为新插入的数据提供空间。所以它的改进版...
2018-10-14 12:02:57
110
原创 滑动窗口
在一个序列如数组或者字符串上，维护一个滑动的窗口，记录窗口的左右边缘为left和right。经常使用字典map记录窗口内数据的特征。 https://blog.csdn.net/yy254117440/article/details/53025142LC438题目求字符串s内所有可以乱序匹配字符串p的子串下标class Solution {public: vector&amp;lt...
2018-09-16 23:25:59
329
原创 知识碎片C++
面试准备c++记录一些准备面试的c++零碎知识maphttps://www.cnblogs.com/fnlingnzb-learner/p/5833051.html#undefinedmap的键值对构成pair求map的长度用m.size()map没有default value,但是会使用类型的默认值。例如如果value的类型是int，就会默认为0map已经排序，如果修...
2018-09-16 21:43:49
590
原创 numpy和pandas的axis
numpy的axisstackoverflow的回答 简单易懂的例子：x = np.arange(60).reshape(3,4,5)引用x的元素就是形如x[0,1,2]，而axis就指下标所在的维度。x.sum(0) # 表示在第0维上塌缩，最后的结果的shape是(4,5)pandas的axisstackoverflow的回答 axis=0表示沿着纵轴...
2018-04-14 22:13:22
295
原创 【线性代数的本质】笔记
【线性代数的本质】“线性代数的本质”是3blue1brown的视频，看了之后可以对线性代数有更多直观的理解。序言几何上的理解能让你判断出解决特定问题需要用什么样的工具，感受到他们为什么有用，以及如何解读最终结果，数值上的理解则能让你顺利应用这些工具。矩阵与线性变换矩阵的列向量可以看作是原空间的基向量经过变换后的形式。 矩阵的秩表示变换后列空间的维数。 上...
2018-04-04 14:02:22
504
原创 后台进程session关闭后自动关闭
问题描述使用putty连接服务器，运行caddy &开启caddy server后端服务，但是当关闭putty连接后，caddy进程会自动关闭。解决方法使用nohup caddy &让进程在session关闭后继续运行参考博客linux的nohup命令的用法 这篇文章讲了一个错误的做法：运行了nohup caddy &没有退回到shell后就立刻关掉putty，这样会导致n
2018-02-05 16:29:05
2025
原创 编程的奇淫技巧1——尾调用
尾调用尾调用指的是函数func的返回值（或者函数最后一条语句）是对另一个函数func2的调用。如果func2和func相同，就是尾递归咯。尾调用是个更广泛的概念。效率尾调用可以不在调用栈上增加新的栈帧，而是更新它，从而像迭代一样，因此尾递归仅占用常量的栈空间。例子用wikipedia的代码例子来说明什么是尾递归。def recsum(x): if x == 1:
2018-01-30 14:31:06
691
原创 算法题里的坑
算法题踩过的坑WA注意多case一定要每个case都clear或者初始化全局变量注意输出结果的字符串大小写，格式注意审题动态规划注意边界条件搜索注意标记已搜索和检查是否搜索完全TLEcin换成scanf。visual studio里要加上#pragma warning(disable: 4996)检查算法里是否有可以避免重复的地方，如并查集是否路径压缩，是否可以
2018-01-07 21:34:27
220
原创 网络流算法
网络流算法本文对最大流算法做一个总结，不涉及最小费用流等问题的算法。最大流算法Ford-Fulkerson算法：不断使用dfs或者bfs寻找增广路径，直到没有增广路径算法停止。算法的复杂度是O(nm2)O(nm^2)。 常用的Dinic算法：不断用bfs构造层次图，然后使用DFS沿着阻塞流增广。Dinic算法的复杂度是O(n2m)O(n^2m)。实际上Dinic算法比这个理论
2018-01-05 20:54:43
307
原创 STL
STL主要记录一些比较奇怪的，容易忽略导致错误的STL特点。priority_queuepriority_queue默认使用vector作为保存数据的容器，less作为比较数据的方式。可以在functional库中找到less或者greater函数。如果使用less函数，则相当于大根堆。如果使用greater函数，相当于小根堆。less函数相当于正常的operator 参考文
2018-01-04 22:04:24
142
原创 图论算法
图论算法图的数据结构图的存储结构往往跟使用的算法有关，主要有邻接矩阵，邻接表等方式邻接矩阵使用V∗VV*V的二维数组来表示图，g[i][j] 表示顶点i和顶点j的关系。 缺点：一般内存限制在4G以下时，V40000V. 如果V比较大，就很占用空间。不能保存重边优点： - 常数时间内可以查询两点之间的边 - 实现简单邻接表边上有属性的时
2018-01-04 13:26:36
371
原创 算法总结
算法总结大纲贪心动态规划分治并查集图论 宽度优先搜索二部图： 一个图是二部图当且仅当不含奇数边的环强连通：任意点s都可以到达图G所有点，反过来同样。拓扑排序优先队列+堆排序分治网络流STL技巧
2018-01-04 13:20:23
120
原创 Multiplication Puzzle （poj 1651）
poj 1651 Multiplication Puzzle题目大意给出一个整数序列，从中依次删除元素，如果删除元素card[i]，就把card[i]∗card[i−1]∗card[i+1]card[i]*card[i-1]*card[i+1]加到删除的代价里。求最小的删除代价。不允许删除最左和最右的元素。在删除结束后，序列只剩下两个元素。分析动态规划。第一眼就可以看出和矩阵乘法很像。 自顶向上考
2017-11-26 16:20:18
127
原创 信息熵和散度
信息熵和散度信息量首先给出香农信息量的概念：信息量需要具有三个性质事件出现的概率越大，所包含的信息量越小可加性不能为负满足这三个性质的唯一函数h(x)=−log2pxh(x)=-log_2p_x pxp_x是事件xx发生的概率熵熵是所有事件发生的信息量的期望 H(p)=−∑ipi∗log2piH(p)=-\sum_ip_i*log_2p_i 熵也可以看作是最小平均编码长度。参考熵和编码
2017-11-12 12:56:39
614
原创 提升方法
Blending and BaggingUniform BlendingG(x)=1T∑t=1Tgt(x)G(x) = \frac{1}{T}\sum_{t=1}^Tg_t(x)gtg_t 应该是多元化的，才会比单个的假设更好Linear BlendingAny Blending简单模型的组合不一定是线性的，还可能是非线性的。 BAGgingbootstrap aggregation(BAGgin
2017-05-20 17:17:46
240
原创 python正则表达式——re模块的使用
python正则表达式——学习re模块 本文所有的代码使用的python版本为python3.5.1,运行环境为Ubuntu 16.04 LTS, GCC 5.3.1. 本文参考的python文档版本为python3.5.2，强烈建议英语不错的同学直接读文档。这篇博客只是作者阅读文档时的学习笔记，若有纰漏请指出，让我们共同进步。正则表达式基础介绍正则表达式正则表达式re是python自带的模块，
2016-07-10 16:30:42
17075
1
翻译 Python中的yield from语法
这篇文章主要是翻译stackoverflow上的一篇文章，In practice, what are the main uses for the new “yield from” syntax in Python 3.3? 注意yield from 提供了一种透明的双向通道从caller到subgenerator，即可以发送数据到subgenerator或者从subgenerator读取数据
2016-07-09 11:17:53
1539
原创 浅谈Python中的yield表达式
浅谈Python协程中的yield表达式python生成器python中生成器是迭代器的一种，使用yield返回函数值。每次调用yield会暂停，而可以使用next()函数和send()函数可以恢复生成器。 这里可以参考Python函数式编程指南：生成器注意到yield是个表达式而不仅仅是个语句，所以可以使用x = yield r 这样的语法。这个知识点在协程中需要使用。协程的概念指的是在一个线程
2016-06-25 11:26:24
11559
2
原创 264 Ugly Number II
欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
2016-01-19 20:28:30
240
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人