deqiangjie8094-CSDN博客

转载字符串的组合

引用剑指offer 1 //组合，从字符串str中取m个字符的所有组合,结果保存在vector中 2 void combination(char* str,int m,vector<char>& result){ 3 //有两个停止条件：m==0或者*str=='\0' 4 //先判断m 5 if(m==0){ 6 ...

2014-09-20 11:26:00 138

转载字符串全排列

引用剑指offer 1 //字符串全排列,begin始终指向当前要置换的字符串 2 void permutation(char* str,char* begin){ 3 if(!str || !begin) 4 return; 5 if(*begin=='\0'){ 6 cout<<str<&l...

2014-09-20 10:50:00 153

转载树的子结构

引用剑指offer 1 //判断以root1为根的树是否和树2有相同的结构(如果为真，必须从root1节点就相同） 2 bool doesRoot1HaveAllNodesOfRoot2(treeNode* root1,treeNode* root2){ 3 if(root2==NULL) 4 return true; 5 if(r...

2014-09-20 10:30:00 129

转载判断二叉树是否平衡

应用剑指offer 1 //判断二叉树是否平衡，后序遍历 2 bool isBalanced(treeNode* root,int& deep){ 3 if(root==NULL){ 4 deep=0; 5 return true; 6 } 7 //左右子树平衡时，根据高度差判断当前是否平衡 ...

2014-09-20 09:38:00 133

转载二叉树中和为某一值的所有路径

引用编程之美，百度笔试题 1 //二叉树中和为某一值的所有路径 2 void findPath(treeNode* root,vector<treeNode*>& path, int& curSum,int expSum){ 3 if(root==NULL) 4 return; 5 //将当前节点的值放入...

2014-09-20 09:18:00 141

转载二叉树中两个节点的最低公共祖先

引用编程之美，引用网址：http://zhedahht.blog.163.com/blog/static/25411174201081263815813/ 情况一：二叉树为搜索二叉树情况二：如果存在指向父节点的指针，则转换为求两个链表的第一个公共节点情况三：为一般的二叉树针对情况三： 1 //判断一棵树是否含有某个节点 2 //利用递归方式的前序优先遍历，时间复...

2014-09-18 09:44:00 134

转载判断两个链表是否相交；查找两个链表的第一个公共节点；头插法建链表（补充）...

问题一：（引用编程之美）如果两个链表相交，则尾节点一定是公共的问题二：头插法建链表（补充，头指针而非投节点） 1 node* createList(int array[],int n){ 2 node* head=NULL; 3 node* temp=NULL; 4 for(int i=n-1;i>=0;i--){ 5 ...

2014-09-16 15:15:00 98

转载最长递增子序列-动态规划（引用编程之美）

测试用例：输入：1,-1,2,-3,4,-5,6,-7 输出：4 1 int lis(int array[]){ 2 int n=sizeof(array); 3 //定义lisMax存放当前的最长递增序列 4 int nMax=1; 5 //list[i]中放着从array[0]到array[i]找到的最长递增序列的长度,初...

2014-09-15 21:23:00 109

转载将字符串转化为整形数

1 int toInteger(char* str){ 2 //检查空串 3 if(str==NULL) {cout<<"string is NULL"; return -1;} 4 //跳过空格 5 while(isspace(*str)) 6 str++; 7 //读取符号位 ...

2014-09-15 19:34:00 337

转载观察者模式（Observer）

引用：http://blog.csdn.net/zhangerqing/article/details/8243942 当一个对象发生变化时，其他依赖该对象的对象会受到通知，并随着变化，是一对多的关系。如关系图，Mysubject类是我们的主对象，Observer1和Observer2是依赖Mysuject的对象，当Mysubject变化时，Observer1和Observer2随着变...

2014-09-10 23:33:00 99

转载最长回文子串，及回文分割分析（leetcode）

最长回文串：引用地址：http://www.ituring.com.cn/article/57155 分析建一个二维表，设定P[i][j]： 1. 为true时，表示str[i..j]为回文 2. 为false时，表示str[i..j]不是回文则，当： 1. i==j时，P[i][j]=true 2. j==i+1时，P[i][j]=str[i]==str[j]...

2014-09-10 20:41:00 126

转载最少插入的字符个数，使原字符串变成回文串（leetcode）

引用网址：http://www.ituring.com.cn/article/60247 例如： 1. ab最少插入1个字符，变为*b*ab 2. aa最少插入0个字符 3. abcd最少插入3个字符，*dcb*abcd 分析： 1. 如果str[0]==str[n-1]，则问题转变为求str[1,n-2]，插入最少字符，得到回文 2. 如果str[0]!=str...

2014-09-10 17:24:00 1018

转载计数排序

1 //一直待排序列的范围是0~bound-1，所以辅助数组C的大小为bound；时间复杂度O(n) 2 int* countSort(int A[],int n,int bound){ 3 int* B=new int[n]; 4 int* C=new int[bound]; 5 for(int i=0;i<bound;i++)...

2014-09-10 16:18:00 101

转载堆排序

1 //大顶堆调整O(log n) 2 void maxHeapify(int A[],int heapSize,int i){ 3 int lChild=2*i; 4 int rChild=2*i+1; 5 int largest=i; 6 if(lChild<=heapSize&&A[lChild]...

2014-09-10 15:41:00 132

转载归并排序，统计逆序对的个数

归并排序O(n log n) 1 void merge(int A[],int p,int r,int q){ 2 int n1=r-p+1; 3 int n2=q-r; 4 int* L=new int[n1]; 5 int* R=new int[n2]; 6 for(int i=0;i<n1;i++) 7 ...

2014-09-10 15:05:00 265

转载快排，查找第K大的数

快排 1 int partition(int A[],int n,int p,int q){ 2 int i=p; 3 for(int j=p+1;j<=q;j++){ 4 if(A[j]<=A[p]){ 5 i++; 6 swap(A[i],A[j]); 7 ...

2014-09-10 11:55:00 250

转载输入两个整数m和n，输出0~n-1范围内m个随机整数的有序列表，不允许重复

方法一:Knuth 时间复杂度O(n) 1 void genknuth(int m,int n){ 2 for(int i=0;i<n;i++){ 3 if(bigrand()%(n-i)<m){ 4 cout<<i<<endl; 5 m--; 6 ...

2014-09-09 20:36:00 747

转载单例模式Singleton

单例模式Singleton：确保系统中一个类只有一个实例（1）对于频繁使用的对象，可省略创建对象所花费的时间（2）new次数减少，降低GC压力 1 public class Singleton{ 2 /*构造私有方法，防止实例化*/ 3 private Singleton(){ 4 } 5 /*此处使用一个内部类来维护单例*...

2014-09-07 17:49:00 109

转载重写Java String类的equals()方法

1 /*重写Java String类的equals()方法*/ 2 public boolean equals(Object anObject){ 3 if(this==anObject){ 4 return true; 5 } 6 if(anObject instanceof String){ 7 S...

2014-09-07 17:08:00 208

deqiangjie8094的博客