二叉树的层序遍历概述

2016年07月27日 39 阅读

二叉树的层序遍历概述2015-09-04前面有篇博客详细分析了二叉树三种遍历（前序、中序、后序）方式的递归与非递归实现，参见：http://blog.csdn.net/ns_code/article/details/12977901，但把二叉树的层序遍历算法给漏掉了，实际上也不能说漏掉了，毕竟层序遍历的实现方法与这三种遍历的实现方法有所不同，因此单独拿出来分析比较合适。二叉树的层序遍历的实现还是比较简单的，由于其层级的关系，很明显要用到队列来辅助实现，主要...

二叉树递归和非递归遍历

2016年07月27日 38 阅读

二叉树递归和非递归遍历2015-09-04二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现。一、三种遍历方式的递归实现（比较简单，这里不详细讲解）...

求一天中时针和分针会相遇多少次

2016年07月27日 40 阅读

求一天中时针和分针会相遇多少次2015-09-04如标题题目：数学分析请看：http://www.planetseed.com/node/18560程序：#include <iostream>#include <vector>#include <string>#include <algorithm>#include <map>#include <math.h>using namespa...

如何求两个数组的交集

2016年07月27日 39 阅读

如何求两个数组的交集2015-09-04题目意思大概是这样的：给定两个大数组（1w以上1亿以下），用最有效的方法找出来两个数组的交集。对于这道题，我有一个思路就是，先对数组进行排序，然后用两个指针在已排序的数组上轮流指向头结点，进行比较。比较亮的地方，就是在于这个比较的方式了。首先，比较的时候，要先确定两个指针指向的内用是否一致。如果一致，那么这个点，就是交集的一个元素，没问题吧？这里有一个问题就是，接下来如何比较？步骤是这样的：先比较两个指针指向内容的大...

产生下一个排列数的算法

2016年07月27日 41 阅读

产生下一个排列数的算法2015-09-06全排序：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。例如n=3，全排序为：123、132、213、231、312、321共6种。字典序法：对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是：从左到右逐个比较对应的字符大小。字符集{1,2,3}，较小的数字较先，这样按字典序生成的全排列即：1...

可持久化的数据结构

2016年07月27日 40 阅读

可持久化的数据结构2015-09-06 cnblogs BLADEVIL可持久数据结构主要指的是我们可以查询历史版本的情况并支持插入，利用使用之前历史版本的数据结构来减少对空间的消耗（能够对历史进行修改的是函数式）。在这里只讲下比较常用的可持久化线段树和trie。对于线段树我们记录每个节点的左右儿子，如果空间允许的话我们也可以记录每个数代表的区间，对于打标签操作我们则需要新建两个节点表示新的历史，比较常用的是用可持久化线段树来维护权值，然后维护不同区间的权...

二叉排序树的C语言实现

2016年07月27日 44 阅读

二叉排序树的C语言实现2015-09-06二叉排序树简介二叉排序树（Binary Sort Tree，简称BST），又称二叉查找树，是红黑树、AVL树等的基础。它或是一棵空树，或者是具有下列性质的一棵二叉树：1、若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2、若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；3、它的左右子树也分别为二叉排序树。下面的一棵树即为二叉排序树：很明显，对二叉排序树进行中序遍历，便可得到一个有序序列，...

编程算法之合并有序链表

2016年07月27日 40 阅读

编程算法之合并有序链表2015-09-06题目:合并有序链表, 给定两个升序的链表, 返回一个合并之后的升序链表.节点结构:struct Node{int val;Node *next;};要求实现的函数:Node* mergeList（Node *list_a, Node* list_b）代码:/** test.cpp**Created on: 2014.04.24*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#in...

如何把数组排成最小的数

2016年07月27日 37 阅读

如何把数组排成最小的数2015-09-08题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个整数m （1<=m <=100）代表输入的正整数的个数。输入的第二行包括m个正整数，其中每个正整数不超过10000000。输出：对应每个测试案例，输出m...

求树中两个结点的最近公共祖先

2016年07月27日 37 阅读

求树中两个结点的最近公共祖先2015-09-08剑指offer上的最后一题了，一个递归函数调了一下午，才得到正确的结果。题目描述：给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个数n（0<n<1000），代表测试样例的个数。其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num<10000。...

哈夫曼树以及哈夫曼编码

2016年07月27日 37 阅读

哈夫曼树以及哈夫曼编码2015-09-08哈夫曼树简介哈夫曼树（哈夫曼树），又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,...,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为哈夫曼树。这里补充下树的带权路径长度的概念。树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，如果在一棵二叉树中共有n个叶子节点，用...

排序算法之快速排序

2016年07月27日 38 阅读

排序算法之快速排序2015-09-08快速排序算法，以升序为例操作系统：ubuntu编译软件：gcc结果截图：源代码：#include<stdio.h>void quickSort（int *,int,int）;int findPoss（int *,int,int）;int main（）{int i;int arry[] = {8,9,0,-3,6,7,-11};quickSort（arry,0,6）;printf（"After so...

输出斐波那契数列的算法

2016年07月27日 41 阅读

输出斐波那契数列的算法2015-09-10斐波那契数列（Fibonacci polynomial），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……要求编程输出这样的一组数，比如输出10个数的序列/*** @param i 第n个数* @param j 第n+1个数* @param n 输出个数*/public static void ff（ int i,int j,int n）{int m=1...

如何递归处理多层嵌套列表

2016年07月27日 40 阅读

如何递归处理多层嵌套列表2015-09-10建立一个多层列表（即列表中存储列表）并输出列表项如下图：可以看出输出的只是输出了外列表当然也可以多次循环输出每一个子项：如下图所示注：isinstance（object, classinfo）为python的内置函数，用来判断对象的类型这是三层循环，如果是很多次循环再用for循环输出就太麻烦了，对于这种情况需要建立一个函数，递归循环输出子项如下图所示：只需建立函数print_lol（），如果内置函数isinsta...

字典树概述

2016年07月27日 35 阅读

字典树概述2015-09-10字典树简介字典树（Trie Tree），又称单词查找树，是键树的一种，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。字典树有3个基本性质：1、根节点不包含字符，其余的每个节点都包含一个字符；2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；3、每个节点的所有子节点包含的字符都不相同。字典树的结构一般如下图所示：以字符串为例，我们可以将其存储结构写成...

内部排序算法的总结

2016年07月27日 38 阅读

内部排序算法的总结2015-09-10内部排序总结这篇博文我们简要地总结下各种内部排序方法。这10种排序算法中，前面7种属于建立在“比较”基础上的排序算法，通过决策树已经证明，任何基于比较进行的排序算法的时 间复杂度不可能再优于O（n*logn）。后面3种不是建立在比较的基础上的，因此，可以达到线性运行时间。下面我们给出各种排序方法的时空复杂度的表格（属于自己总结，有不对的地方，希望大家指正或补充）。关于各种排序，给出如下几点总结：...

关于数组中的逆序对

2016年07月27日 35 阅读

关于数组中的逆序对2015-09-12题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。输入：每个测试案例包括两行：第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。第二行包含n个整数，每个数组均为int类型。输出：对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。样例输入：47 5 6 4样例输出：5思路：最简单的方法是顺序...

求按从小到大的顺序的第N个丑数

2016年07月27日 42 阅读

求按从小到大的顺序的第N个丑数2015-09-12题目描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。输入：输入包括一个整数N（1<=N<=1500）。输出：可能有多组测试数据，对于每组数据，输出第N个丑数。样例输入：3样例输出：3思路：最简单的方法就是先通过将一个数不断除以2，3，5来判定该数是不是丑数，而后在...

求整数中1出现的次数

2016年07月27日 38 阅读

求整数中1出现的次数2015-09-12题目描述：亲们！！我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的...

异或去重的例子

2016年07月27日 38 阅读

异或去重的例子2015-09-12这篇文章没有代码，介绍的是纯理论的思路。异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。异或的性质：1、交换律：a^b = b^a；2、结合律：（a^b）^c = a^（b^c）；3、对于任意的a：a^a=0，a^0=a，a^（-1）=~a。了解了上面这些，来看看这...