二叉树的遍历是二叉树的众多算法的基础。主要有，前序，中序与后序。对于以下二叉树：前序：12354中序：21543后序：24531笔者实现了三种遍历方式:1 前序：递归版本比较简单，只需要改变push_back操作的位置即可。vector<int> PreOrderTraverse2(TreeNode *root) {vector<int> nodes;vector<int> temp;if(root == NULL) return nodes;nodes.push_back(root->val);temp = PreOrderTraverse2(root->left);for(vector<int>::size_type...
Description由n个1组成的整数能被K（K<10000)整除，n至少为多少？Input多组测试数据，第一行输入整数T,表示组数 然后是T行，每行输入1个整数代表KOutput对于每组测试数据输出1行，值为nSample Input1 11Sample Output2#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]){int t;while(scanf("%d",&t)!=EOF){ while(t--){int k;scanf("%d",&k);if(k==1){printf("1\n");continue;}unsigned long n=1;int c=1;i...
1 #include<stdio.h>2 #include <stdlib.h>3 #include <string.h>4 #include <ctype.h>5 #include <math.h>6 7char *Mystrstr(constchar *string, constchar *strCharSet)8{9if (NULL == string)10 {11return (char *)string;12 }13if (NULL == strCharSet)14 {15return NULL;16 }17int nLen1 = strlen(string);18int nLen2 = strlen(strCharSet);19 20for (int i = 0; i < nLen2; i++)21 {22for (int j = 0; j <n...
第一题: 给出{1, 2, 3,…, n}的入栈顺序, 输出所有可能的出栈顺序#include "stdafx.h" #include <stack> #include <queue> #include <iostream> #include <cstdio> #include <cstdlib> usingnamespace std; int n = 0; typedef stack<int> Stack; typedef queue<int> Queue;void dfs(int level,Stack s, Queue buf, constint LEVEL);/** 每一次递归都只有一个元素(level)入栈, 但是可能有0个元素出栈, 也可能有至少一个元素出栈* @...
我们在一个母字符串中查找一个子字符串有很多方法。KMP是一种最常见的改进算法，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。当然我们可以看到这个算法针对的是子串有对称属性，如果有对称属性，那么就需要向前查找是否有可以再次匹配的内容。 在KMP算法中有个数组，叫做前缀数组，也有的叫next数组，每一个子串有一个固定的next数组，它记录着字符串匹配过程中失配情况下可以向前多跳几个字符，当然...
SVM上：这个算法应该是机器学习这门课里最重要的部分了。 首先是SVM的思想：找到超平面，将两类中距离最近的点分的越开越好（直至二者相等）。 然后是函数间隔和几何间隔的定义，二者之间的区别。 接着是超平面模型的建立，看看它是如何将问题转化为凸优化问题的。 SVM第一个难点：拉格朗日对偶。由KKT条件可知，起作用的约束都在边界上，这个会用来解释支持向量。 由KKT条件知，在S...
许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。在本节中，我们将学习三种这样的数据类型，分别是背包(Bag)、队列(Queue)、和栈(Stack). 他们的不同之处在于删除或者访问对象的顺序不同。一、背包API:publicclass Bag<Item> implements Iterable<Item> Bag() 创建一个空背包 void add(Item item) 添加一个元...
不懂优化的人希望能有通用的方法来解决他手头的问题。但不幸的事没有这样的方法存在。高速的方法都须要某些条件，比方常见的有强凸。线性，可分解啥的。眼下研究的比較成熟的就是强凸光源可分解 非凸没有特别有效的方法来解。假设是强凸的，何必用那么复杂的方法求最优解？正是由于不是强凸的，才用到优化方法。就算是凸的。也分好几种不同的情况。仅仅用一阶梯度，达到牛顿梯度法的收敛速度。在convex问题中，还有non-smooth的函数...
给定一个无序整型数组arr，找到数组中未出现的最小正整数 解题思路非常好，需要好好学习一下，很逻辑 如果arr长度为N， 最优解可以做到时间复杂度O（N） 额外空间复杂度O(1) 1、遍历arr之前生成两个变量， l r 初始值 l=0 r=N 2、从左到右遍历arr，arr[l] 3、如果arr[l]=l+1 没有遍历arr[l]之前，arr已经包含的正整数范围是[1,l]，此时出现了arr[l]=l+1的情况，所以arr包含的正整数范围可以扩展到[1,l+1] 即令 l++ 4、...
mro即 method resolution order (方法解释顺序)，主要用于在多继承时判断属性的路径(来自于哪个类)。在python2.2版本中，算法基本思想是根据每个祖先类的继承结构，编译出一张列表，包括搜索到的类，按策略删除重复的。但是，在维护单调性方面失败过（顺序保存），所以从2.3版本，采用了新算法C3。为什么采用C3算法C3算法最早被提出是用于Lisp的，应用在Python中是为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性的问...
给定一个有向图 G = (V, E) ，对于任意一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的，则说明该图 G 是强连通的（Strongly Connected）。如下图中，任意两个顶点都是互相可达的。对于无向图，判断图是否是强连通的，可以直接使用深度优先搜索（DFS）或广度优先搜索（BFS），从任意一个顶点出发，如果遍历的结果包含所有的顶点，则说明图是强连通的。而对于有向图，则不能使用 DFS 或 BFS 进行直接遍历来...
题意：给定一个数，判断是不是素数。析：由于数太多，并且太大了，所以以前的方法都不适合，要用米勒拉宾算法。代码如下：#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <cstring> #include <map> #include <cctype>using namespace std; typedef long long LL; const int maxn = 1000 + 5;LL qpow(int a, int b, int r){LL ans = 1;LL k = a % r;while(b){if(b & 1) ...
基本思想希尔排序是基于插入排序的，又叫缩小增量排序。在插入排序中。标记符左边的元素是有序的，右边的是没有排过序的，这个算法取出标记符所指向的数据，存入一个暂时变量，接着，在左边有序的数组中找到暂时变量应该插入的位置，然后将插入位置之后的元素依次后移一位，最后插入暂时变量中的数据。试想。假如有一个非常小的数据项在靠近右端的位置上。把这个数据项插入到有序数组中时，将会有大量的中间数据项须要右移一位。这...
transform函数原型1.template<class _InIt,class _OutIt,class _Fn1> inline_OutIt transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func){ // transform [_First, _Last) with _Func_DEPRECATE_UNCHECKED(transform, _Dest);return (_Transform_no_deprecate(_First, _Last, _Dest, _Func));} 2.template<class _InIt1,class _InIt2,class _OutIt,class _Fn2> inline_OutIt transform(_InIt1 _First1, _InIt1 _Last1,_I...
算法第三章布隆过滤器海量数据管理，在哈希表上再压缩数据，但会存在较低的失误率 失误类型：宁可错杀三千不可错放一个，非存储数据小概率判断为存储数据bit位数组存储：eg. int数组每位存储0~31位bit数组思想：准备k个哈希函数，哈希值取模bit数组大小m，每个键经过记录得到k个哈希值范围[0,m-1]，将bit数组k个哈希值的对应位置1。查表时，若是查询键中非全部哈希置位为1，则未被记录。 若是k个值有重复，则仍然置1，多余的不变所...