- 博客(130)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 已知二叉树的前序和中序序列，不建立二叉树来输出后序序列
关于不建立这棵二叉树来求解这棵树的后序序列，可以这么考虑：其实求解一棵二叉树的后序序列等价于求解左子树的后序序列+右子树的后序序列+根节点，这是一个递归的考虑过程。
2015-10-03 23:09:37
593
原创 关于指针的见解
最近在看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
646
原创 棋盘覆盖问题
在一个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
1120
原创 九度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
1039
原创 使用递归的方法生成一个序列的所有排列
#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
1368
原创 两数之和等于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
1111
原创 个人体会：编写自己的头文件
最近在看C++的一本入门参考书，C++ primer。其中有涉及到自己编写一个头文件，并在头文件中定义一个Sales_item的类。经过查看有关内容后，发现编写这么一个文件关键就是格式，也就是所谓的语法了。格式如下，编写了一个sale.h的头文件。#ifndef sale_h#define sale_h把类的定义写在此处#endif然后在自己所写的.cpp中只要包含了这个头文件
2015-02-20 14:48:47
857
原创 九度OJ 1463 招聘会
这个题目是典型的贪心问题。贪心策略如下：按照结束时间进行从小到大排序，从第一个开始遍历排序后的招聘会一遍得出结果，每次设置一个temp进行记录当前所在招聘会，下一个招聘会向后找到第一个不冲突的，然后修改temp，当然此时能参加的招聘会要+1。贪心策略简单证明：假设有两个招聘会A和B，且A的结束时间要早于B的结束时间，那么显然我们选择B的时候B的所有后续安排全部不会和A冲突，而选择A的时候A的后
2015-01-12 23:03:06
710
原创 算法导论 计数排序
计数排序的关键就在于如何处理每个元素的最终位置。在计数排序中，我们可以通过维护一个数组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
779
原创 堆排序------最大堆进行排序为例
#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
559
原创 将一棵二叉树的全部节点的左右子树交换顺序
模拟了层次遍历的算法。#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
6573
1
原创 构建一棵二叉树并按照层次遍历输出
这个算法中的构建一棵二叉树用的是前序和中序来构建二叉树的。层次遍历当然要用到队列了。#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
5151
原创 二叉树的层次遍历的算法
二叉树的层次遍历指的是从二叉树的根节点，按照从上到下从左向右依次遍历。首先要访问头结点，然后将其压入队列中，然后取出该元素，访问之并且将该元素的孩子（为空时不加入，也不访问）按照先左后右的顺序压入队列......依次进行，知道访问完所有的元素，也就是队列为空了。伪代码如下void trave(Betree *p){ if(p==NULL) return;//空树没有访问的必要
2014-02-27 15:30:53
1832
原创 求解二叉树高度的递归算法
二叉树的高度就是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
4354
原创 二叉树前序遍历的非递归算法
二叉树的前序遍历是先根节点，然后如果有左子树则再先序遍历左子树，然后如果有右子树则再先序遍历其又子树。递归算法如下 void preorder(Betree *t){ if(t==null) return;visit(t);//访问该节点preorder(t->lchild);preorder(t->rchild); }当然递归算法是隐式使用了栈。我们仔细分析这个过程，先是
2014-02-26 22:42:08
1736
原创 由前序和中序遍历构建一颗二叉树
这个算法本身是存在问题的，不细究。等大四我再写一个完善的算法。考试的时候可以写这个算法，思路没错，但是有种特殊情况这个算法没考虑。#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
1064
原创 首尾相连数组的最大子数组和 淘宝面试题
题目描述：给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。
2014-02-22 17:04:22
1292
原创 哦，是约数定理
题目描述：输入n个整数,依次输出每个数的约数的个数输入：输入的第一行为N，即数组的个数(N接下来的1行包括N个整数，其中每个数的范围为(1当N=0时输入结束。输出：可能有多组输入数据，对于每组输入数据，输出N行，其中每一行对应上面的一个数的约数的个数。样例输入：51 3 4 6 12样例输出：1
2014-02-20 22:17:24
801
原创 稀疏矩阵的乘法
#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
1534
原创 这就是传说中的复试上机题
一个整数总可以拆分为2的幂的和，例如：7=1+2+47=1+2+2+27=1+1+1+47=1+1+1+2+27=1+1+1+1+1+27=1+1+1+1+1+1+1总共有六种不同的拆分方式。再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。用f(n)表示n的不同拆分的种数，例如f(7)=6.要求编写程
2014-02-08 19:37:05
1056
原创 用两个栈模拟一个队列
题目要求：请利用两个栈来模拟一个队列，利用栈的操作来实现队列的三个运算1.enqueue插入一个元素入队列；2.dequeue删除一个元素出队列；3.queue_empty判断队列为空#includeusing namespace std;#define maxsize 100struct que{ int top1,top2; int s1[maxsize],s2[m
2014-02-03 18:38:11
1256
转载 如何将中缀式转化成前缀式和后缀式
35,15,+,80,70,-,*,20,/ //后缀表达方式(((35+15)*(80-70))/20）=25 //中缀表达方式/,*,+,35,15,-,80,70, 20 //前缀表达方式人的思维方式很容易固定~~！正如习惯拉10进制。就对2，3，4，8，16等进制不知所措一样~~！人们习惯的运算方式是中缀表达式。而碰到前缀，后缀方式。。迷茫其实仅仅是
2014-01-26 18:39:34
2041
2
原创 链表合并
清华大学1995。已知三个带头结点的线性链表A,B,C中的结点均依照自小到大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅存留三个表中均包含的元素的结点，且没有值相等的结点，并释放所有无用的结点。限定算法的时间复杂度为O(m+n+p),其中m,n,p分别为三个单链表的长度。#includeusing namespace std;stru
2014-01-26 16:53:15
720
原创 分解链表
写算法将单链表L1分解为两个链表，其中以L1为头的链表保持原来向后的链接，另一个链表的头为L2，将其链接方向和L1的方向相反，其中L1包含原链表的奇数序号的结点，L2包含原链表中偶数序号的结点。#includeusing namespace std;struct node{ int data; node* next;};node *build(node* p){
2014-01-26 16:03:22
1955
原创 链表的集合操作Av（B^C）
#includeusing namespace std;struct node{ int data; node* next;};node *build(node* p){ int n; cout<<"请输入链表长度"<<endl; cin>>n; p=(node*)malloc(sizeof(node)); node *r,*q; r=p;
2014-01-25 20:30:24
1008
原创 链表合并 求两个递增链表的并
#include#includeusing namespace std;struct node{ int data; node* next;};node* build(node* x){ x=(node*)malloc(sizeof(node)); node *y,*z; y=x; y->next=NULL; int n; cin>>n;
2014-01-23 19:58:56
1055
原创 单链表的归并1
要求：创建两个无头结点的单链表，头指针分别为ha,hb，链中有数据data和指针域next，两个链表的数据都按照不递减存放，现在要求将hb归并到ha表中，归并后要求ha依然递增有效，归并中的ha表中的元素如果hb表中也有，则该元素不再重复归并到ha中，hb在算法中不能被破坏。#includeusing namespace std;struct node{ int data;
2014-01-23 17:50:54
1142
原创 对一个不带头结点的单链表进行逆置
#include#includeusing namespace std;struct node{ int data; node* next;};node *L;node* reverse(node *h){ node *p,*q; p=NULL; q=h; while(q!=NULL) { h=h->next; q->next
2014-01-22 22:10:04
8116
原创 一个有关于static的小程序
#include#include#includeusing namespace std;class Account{public: void applyint() { amount=amount+amount*interestrate; } double charge(double a) { amount=a; return amount; } double c
2013-11-20 22:29:23
1235
原创 浅析将一个类作为另一个类的友元
友元出现的的意义就在于它可以让一个类得到访问这个类的私有成员的权限。下面的程序主要讲解的是如何将一个类作为另一个类的友元。友元的声明可以放在public或者是private，这两个都是可以的。也就是说友元的声明只要出现在类的定义的内部就可以了。#includeusing namespace std;class screen{public: friend class windowmg
2013-11-11 22:33:12
2296
原创 指向字符串的指针
刚才不小心发现了一个自己以前从没注意的问题。下面的程序输出的结果很有意思的。注意num到底是什么。#include#include#include#includeusing namespace std;int main(){ char *p; char *num[]={"basic","fortan","c++","java"}; cout<<*num<<endl;
2013-11-10 12:25:22
854
原创 第一个类的程序
#includeusing namespace std;class sstring{ int length; char *contents;public: void set_contents(char *p); int get_length(); char *get_contents();};void sstring::set_contents(char *p){ int
2013-10-10 21:33:59
552
原创 hdu 4740 The Donkey of Gui Zhou
让这个题坑坏了，不过没报这个赛区。不过貌似比成都的题目出的简单。成都竟然还有签到题。这个题目就是说现在有个人将一只驴和一只老虎放入了一个矩阵中，然后老虎和驴都是直线跑但是他们不走自己走过的路，并且当无路可走的时候就要转弯，驴每次转弯都是朝右转，老虎正好朝左转。问这两个动物能不能相遇，如果能输出第一次坐标，不能输出-1。首先声明这个题目中的两个cheat，第一个转向的时候要忽略时间，第二个可能数据中
2013-09-15 22:51:24
632
原创 poj 2912 rochambeau
这个题目并查集的意味还是比较浓厚的，刚开始纠结于里面的数是不是全是正的，其实不是是全体整数。思路就是枚举谁是judge，然后有judge的当然不能用并查集找矛盾了。除了有judge的边不添加，当添加其他边出现矛盾时，这个假定的judge必然不是真正的judge。这个题目还要记录有几组可能的judge，并且如果只有一个可能还要输出最少多少行后能知道答案。后一个问题要求出所有的其他情况最少出错的行
2013-08-29 17:01:44
653
原创 hdu 4632 Palindrome subsequence
这个题目让你求一个字符串中所有的回文串的个数。这个题目对于什么样的算不重复有这要求，仔细阅读。dp(i,j)表示从第i个字符到第j个字符回文串的个数，dp(i,j)=dp(i+1,j)+dp(i,j-1)-dp(i+1,j-1)，这个是因为两端是新更新的，所以首先可有以前求解出来的来表示i或者j至少有一个不算在内有多少个回文串，当然要去掉重复的。然后如果s[i-1]==s[j-1]那么也就是说，两
2013-08-29 16:55:19
647
原创 hdu 4681 string
这个题目就是说现在给你三个字符串a,b,c，要求求出一个字符串d要求长度最大，并且要求d是a,b的子串（注意这个子串没要求字符是连续的），然后c必然是d的连续子串。现在求这个长度。注意到无论如何d串中必然有连续子串c，现在只需要知道c在a，b中的开始位置和结束位置（注意，一旦开始位置选定，结束位置的下标要最小），然后枚举这些位置，分别求出最长公共子序列就好了。附带一组数据，abcddc,bcdd,
2013-08-29 10:12:37
650
原创 hdu 1198 Farm Irrigation
简单并查集。这个题目就是找最少挖多少口井。让数据坑了一次，本来说是两个最大都是50，真坑啊，改成550就过了。#includeusing namespace std;char map[550][550];int father[150000];int find_ant(int x){ if(x!=father[x]) father[x]=find_ant(father[x]);
2013-08-27 22:13:30
504
原创 hdu 1913 computers
关键是理解意思。要点一，这个题目要在所有的n年都有电脑，也就是说第一年的时候必定先买电脑；要点二，到第i年的最少花费，必然是不知道从第几年买电脑，并且一直使用到了第i年；要点三，矩阵中的信息是从第i年买电脑，到第j年总的维修费，只是维修费，买电脑的钱没在里面。题目很黑啊，没给数据范围，我的程序到1000就过了。#include#includeusing namespace std;int
2013-08-27 16:11:20
992
原创 poj 1390 blocks
刘汝佳黑书上的题目。书上解释的很详细了，不说了。#include#includeusing namespace std;int dp[205][205][205];int color[205],len[205];int maxi(int a,int b){ if(a>b) return a; return b;}int dfs(int start,int end,int
2013-08-27 14:48:09
773
空空如也
vs2013 文件操作为什么fstream没有绑定这个文件
2016-02-02
TA创建的收藏夹 TA关注的收藏夹
TA关注的人