8 弱者

尚未进行身份认证

我要认证

爱猫忍者

等级
TA的排名 4w+

已知二叉树的前序和中序序列,不建立二叉树来输出后序序列

关于不建立这棵二叉树来求解这棵树的后序序列,可以这么考虑:其实求解一棵二叉树的后序序列等价于求解左子树的后序序列+右子树的后序序列+根节点,这是一个递归的考虑过程。

2015-10-03 23:09:37

关于指针的见解

最近在看c++ primer第13章复制控制。习题13.4中有个指针成员pstring,当时写构造函数初始化一个对象的时候想当然的写成了NoName(string a,int b,double c){ pstring=&a;i=b;d=c;} 写完后发现不对,因为在这个构造函数中a是一个临时的对象,当NoName这个构造函数结束后,该变量自行销毁,直接导致了指针悬空。改正办法是将a写成一个stri

2015-08-15 10:02:27

棋盘覆盖问题

在一个2^k×2^k (k≥0)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中可能出现的位置有4^k种,因而有4^k种不同的棋盘,图4.10(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题(chess cover problem)要求用图4.10(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

2015-03-02 18:21:37

九度OJ 1035找出直系亲属

题目描述:    如果A,B是C的父母亲,则A,B是C的parent,C是A,B的child,如果A,B是C的(外)祖父,祖母,则A,B是C的grandparent,C是A,B的grandchild,如果A,B是C的(外)曾祖父,曾祖母,则A,B是C的great-grandparent,C是A,B的great-grandchild,之后再多一辈,则在关系上加一个great-。输入:

2015-03-01 16:38:10

使用递归的方法生成一个序列的所有排列

#includeusing namespace std;int a[100];int count;void swap(int A[],int i,int j){int temp=A[i];A[i]=A[j];A[j]=temp;}void arrange(int A[],int i,int n){if(i>n){count=count+1;

2015-03-01 11:13:50

两数之和等于x

算法导论第2.3-7的习题中要求给出一个运行时间为O(nlgn)的算法,这个算法的功能是能在给定一个由n个整数构成的集合S和另一个整数x时,判断出S中是否存在两个其和等于x的元素。方法一:都知道在一个有序的序列中使用二分查找的时间复杂度是O(lgn)。首先排序,那么我们可以枚举集合S中的每一个元素,然后使用二分查找算法查找x-y(y是S中的一个元素),那么这个算法的时间复杂度是O(nlgn)。

2015-02-21 17:48:22

个人体会:编写自己的头文件

最近在看C++的一本入门参考书,C++ primer。其中有涉及到自己编写一个头文件,并在头文件中定义一个Sales_item的类。经过查看有关内容后,发现编写这么一个文件关键就是格式,也就是所谓的语法了。格式如下,编写了一个sale.h的头文件。#ifndef sale_h#define sale_h把类的定义写在此处#endif然后在自己所写的.cpp中只要包含了这个头文件

2015-02-20 14:48:47

九度OJ 1463 招聘会

这个题目是典型的贪心问题。贪心策略如下:按照结束时间进行从小到大排序,从第一个开始遍历排序后的招聘会一遍得出结果,每次设置一个temp进行记录当前所在招聘会,下一个招聘会向后找到第一个不冲突的,然后修改temp,当然此时能参加的招聘会要+1。贪心策略简单证明:假设有两个招聘会A和B,且A的结束时间要早于B的结束时间,那么显然我们选择B的时候B的所有后续安排全部不会和A冲突,而选择A的时候A的后

2015-01-12 23:03:06

算法导论 计数排序

计数排序的关键就在于如何处理每个元素的最终位置。在计数排序中,我们可以通过维护一个数组C[i]来记录键值为i的元素所属的位置。每次输入一个A[i],首先记录每个A[i]出现的次数C[i],然后从前向后C[i]=C[i-1]+C[i],这样可以得出值为i所在排序后新数组中的最后一个重复数的位置。计数排序的一个显然问题就是C[]数组的大小确定的问题。下面贴上我自己理解写出的代码。#include

2015-01-12 22:52:34

堆排序------最大堆进行排序为例

#includeusing namespace std;void maxheapify(int A[],int i,int length){ int left,right,largest; bool flag=true; while(flag&&i<=length) { left=i*2; right=left+1; largest=i; flag=false;

2015-01-06 19:59:34

二叉树常见非递归操作

层次遍历函数中的count是用来计数这一层多少个节点的

2014-10-11 19:11:02

将一棵二叉树的全部节点的左右子树交换顺序

模拟了层次遍历的算法。#include#include#include#includeusing namespace std;struct node{ char c; node *lchild,*rchild;};char pre[100];char mid[100];void build(node* &t,int start1,int end1,int start2,

2014-04-06 23:42:11

构建一棵二叉树并按照层次遍历输出

这个算法中的构建一棵二叉树用的是前序和中序来构建二叉树的。层次遍历当然要用到队列了。#include#include#include#includeusing namespace std;struct node{ char c; node *lchild,*rchild;};char pre[100],mid[100];void build(node* &t,int

2014-04-06 21:25:03

二叉树的层次遍历的算法

二叉树的层次遍历指的是从二叉树的根节点,按照从上到下从左向右依次遍历。首先要访问头结点,然后将其压入队列中,然后取出该元素,访问之并且将该元素的孩子(为空时不加入,也不访问)按照先左后右的顺序压入队列......依次进行,知道访问完所有的元素,也就是队列为空了。伪代码如下void trave(Betree *p){  if(p==NULL) return;//空树没有访问的必要 

2014-02-27 15:30:53

求解二叉树高度的递归算法

二叉树的高度就是1+max{height(root->light),height(root->right)},从而有了递归算法的求解思路。int height(Betree *p){    if(p==NULL) hi=0;     else { if(p->lchild==NULL) lh=0; else lh=height(p->lchild);//递归求解左子树的高度   

2014-02-27 15:08:43

二叉树前序遍历的非递归算法

二叉树的前序遍历是先根节点,然后如果有左子树则再先序遍历左子树,然后如果有右子树则再先序遍历其又子树。递归算法如下 void   preorder(Betree *t){   if(t==null) return;visit(t);//访问该节点preorder(t->lchild);preorder(t->rchild); }当然递归算法是隐式使用了栈。我们仔细分析这个过程,先是

2014-02-26 22:42:08

由前序和中序遍历构建一颗二叉树

这个算法本身是存在问题的,不细究。等大四我再写一个完善的算法。考试的时候可以写这个算法,思路没错,但是有种特殊情况这个算法没考虑。#include#includeusing namespace std;struct Betree{ char c; Betree *lchild,*rchild;};char fore[100],mid[100];void preorder(Betre

2014-02-25 16:34:52

首尾相连数组的最大子数组和 淘宝面试题

题目描述:给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。

2014-02-22 17:04:22

哦,是约数定理

题目描述:输入n个整数,依次输出每个数的约数的个数输入:输入的第一行为N,即数组的个数(N接下来的1行包括N个整数,其中每个数的范围为(1当N=0时输入结束。输出:可能有多组输入数据,对于每组输入数据,输出N行,其中每一行对应上面的一个数的约数的个数。样例输入:51 3 4 6 12样例输出:1

2014-02-20 22:17:24

稀疏矩阵的乘法

#includeusing namespace std;struct triple{ int r;//hang int c;//lie int data;};struct matrix{ triple ko[300]; int rpos[15];//各行第一个非0原在ko中的位置 int num[15];//各行非0元的个数 int mu;//矩阵的行数 int nu;//

2014-02-11 21:25:17

查看更多

勋章 我的勋章
    暂无奖章