- 消除字符串中的重复字符
题目:不使用额外缓冲。注意:一两个变量使用OK的,但是复制整个数组就不行。
分析:如果不使用额外缓冲,则对每个字符串判断是否为重复字符,如果是重复字符跳过,非重复字符记录。O(n^2).
三个指针,tail指向未含重复字符的字符串的下一位,i做全遍历,j只遍历0-tail指向的已有统计字符。void removeDuplicates(char* str,int n) { if(str == NULL) return; if(n < 2) return; int tail = 1;//未含重复字符的string的下一位 for(int i=1;i<n;++i) { int j; for(j = 0;j<tail;++j) { if(str[j] == str[i]) break; } if(j == tail) { str[tail] = str[i]; ++tail; } } str[tail] = '\0'; }
如果可以使用额外缓冲(与题2相似)
void removeDuplicates(char* str,int n) { if(str == NULL) return; if(n < 2) return; bool* set = new bool[256]; for(int i=0;i<256;++i) set[i] = false; set[str[0]]=true; int tail=1; for(int i=1;i<n;++i) { if(!set[str[i]]) { str[tail]=str[i]; ++tail; set[str[i]]=true; } } str[tail]=0; }
- 判断字符串中的字符唯一
题目:判断字符串中的子否都是唯一的。
分析:
1). 可以检查每一个字符在字符串中的出现次数,这样的方法时间复杂度为O(n^2),但是空间复杂度为0。
2). 如果字符串中的内容可以破坏的话。我们可以将字符串中的字符排序(时间复杂度为O(nlogn)),然后遍历字符串中的某个字符相邻的字符时候相同。但是要注意有些排序算法是需要额外的存储空间的。
3). 先假设字符串中的字符均为ASCII码(如果不是的可以增大存储空间,而算法的逻辑是相同的)。bool isUnique(string str) { bool* charset = new bool[256]; for(int i=0;i<256;++i) charset[i] = 0; for(int i=0;i<str.length();++i) { int val = str[i]; if(charset[val]) return false; charset[val] = true; } return true; }
4). 采用bit序列来代替数组可以为我们进一步节省空间。这里我们需要假设字符串中的字符为’a’-‘z’。这样只要用一个int型的变量就能记录字符是否出现了。
- 最小的k个数
题目:输入n个整数,找出其中最小的k个数。例如输入{4,5,1,6,2,7,3,8},则最小的4个数字是1,2,3,4。
更多细节分析—http://blog.csdn.net/v_JULY_v/article/details/6370650
解法一:O(n)的算法,需要修改数组
分析:利用排序时间复杂度O(nlogn),其实O(n)就行,同样基于Partition函数,如果基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组左边,比第k个数字大的都位于数组的右边,那么位于数组中左边的k个数就是最小的k个数字。
void GetMin(int* input,int n,int* output,int k) { if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0) return; int start = 0; int end = n - 1; int index = Partition(input,n,start,end); while(index != k-1) { if(index > k-1) { end = index-1; index = Partition(input,n,start,end); } else { start = index+1; index = Partition(input,n,start,end); } } for(int i = 0;i < k;++ i) output[i] = input[i]; }
解法二:利用k大小的容器来存储最小的k个数,若填满,则每次选择是否替换其中最大的数。容器满 了之后,需要做三件事,一是在k个数中找出最大的数,二是删除最大数,三是插入一个新的数。由一很容易想到使用大顶堆,所以可以在O(1)时间内找到k中 的最大数,但需要O(logk)删和插。偷懒的办法是直接使用STL中的容器,采用红黑树来实现我们的容器,其中查找、删除和插入都只需要 O(logk),STL中的set和multiset都是基于红黑树实现的。
STL multiset实现
typedef multiset<int,greater<int>> intset; typedef multiset<int,greater<int>>::iterator setIterator; void GetMin(const vector<int>& data,intset& minNumbers,int k) { minNumbers.clear(); if(k<1 || data.size()<k) return; vector<int>::const_iterator iter = data.begin(); for(;iter != data.end();++iter) { if(minNumbers.size()<k) minNumbers.insert(*iter); else { setIterator iter2 = minNumbers.begin(); for(*iter <*(minNumbers.begin())) { minNumbers.erase(iter2); minNumbers.insert(*iter); } } } }
大顶堆实现
void HeapAdjust(int array[], int i, int Length) { int child,temp; for(temp=array[i];2*i+1<Length;i=child) { child = 2*i+1; if(child<Length-1 && array[child+1]<array[child]) child++; if (temp>array[child]) array[i]=array[child]; else break; array[child]=temp; } } void Swap(int* a,int* b) { *a=*a^*b; *b=*a^*b; *a=*a^*b; } int GetMin(int array[], int Length,int k) { int min=array[0]; Swap(&array[0],&array[Length-1]); int child,temp; int i=0,j=k-1; for (temp=array[0]; j>0 && 2*i+1<Length; --j,i=child) { child = 2*i+1; if(child<Length-1 && array[child+1]<array[child]) child++; if (temp>array[child]) array[i]=array[child]; else break; array[child]=temp; } return min; } void Kmin(int array[] , int Length , int k) { for(int i=Length/2-1;i>=0;--i) //初始建堆,时间复杂度为O(n) HeapAdjust(array,i,Length); int j=Length; for(i=k;i>0;--i,--j) //k次循环,每次循环的复杂度最多为k次交换,复杂度为o(k^2) { int min=GetMin(array,j,i); printf("%d,", min); } } int main() { int array[MAXLEN]; for(int i=MAXLEN;i>0;--i) array[MAXLEN-i] = i; Kmin(array,MAXLEN,K); return 0; }
- 连续子数组的最大和
题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间 复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
分析:加上一个正数,和会增加,想法加上负数和减少。所以若当前得到的和是一个负数,那应该直接舍弃。int maxsum(int a[n]) { int max=a[0]; //全负情况,返回最大数 int sum=0; for(int j=0;j<n;j++) { if(sum>=0) //如果加上某个元素,sum>=0的话,就加 sum+=a[j]; else sum=a[j]; //如果加上某个元素,sum<0了,就不加 if(sum>max) max=sum; } return max; } int main() { int a[]={-1,-2,-3,-4}; cout<<maxsum(a)<<endl; return 0; }
传送门http://blog.csdn.net/v_JULY_v/article/details/6444021
- 从1到n整数中1出现的次数
题目:输入一个正数n,求从1到n这n个数中十进制表示中1出现的次数,例如输入12,则1,10,11和12,1出现了5次。
分析:每次去掉最高位做递归,递归的次数和位数相同。
- 数组中只出现一次的数字
题目:一个整型数组里除了两个数字外,其他的数字都出现了两次,请写出程序找出这两个只出现一次的数字,要求时间复杂度为O(n),空间复杂度为O(1)。
分析:只出现一次的情况可以使用异或操作,任意一个数字异或自己都为0,成对的数字全部在异或中抵消。想办法把数组拆成两个子数组,使每个子数组只包含一 个只出现一次的数字。首先从头至尾进行一次异或,我们在结果中找到第一个为1的位置,记为第n位。然后以第n位是不是1为标准把原数组分为两个子数组,第 一个子数组中每个数字的第n位都是1,第二个子数组中第n位都是0.这样出现两次的数字肯定被分到同一个子数组,而出现一次的被分开了。 - 和为s的两个数字 v.s.和为s的连续整数序列
题目1:输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得他们的和正好为s。如果有多对,输出任意一对即可。例如,{1,2,4,7,11,15}和15,输出4和11.
分析:两个指针指头指尾,大了,尾指针前移,小了,头指针后移。时间复杂度O(n)。bool sum2(int *data,int len,int sum,int* num1,int* num2) { bool find=false; if(len<1||data==NULL||num1==NULL||num2==NULL) return find; int begin = 0; int end = len-1; while(begin < end) { int curSum = data[begin]+data[end]; if(curSum == sum) { *num1 = data[begin]; *num2 = data[end]; find = true; break; } else if(curSum > sum) end --; else begin++; } return find; }
题目2:输入一个正数s,打印出所有和为s的连续正数序列(至少2个数)。例如,输入15,由于1+2+3+4+5=4+5+6=7+8=15,输出1-5,4-6和7-8.
分 析:也考虑两个指针small和big,small初始化1,big初始化2,如果small到big的序列和小于s,增大big,序列包含更多的数字; 如果和大于s,就从序列中去掉较小的值,即增大small。因为至少要包含两个数字,所以small增加到(1+s)/2为止。等于的时候打印,并增加 big。void sumSeq(int sum) { if(sum < 3) return; int small = 1; int big = 2; int mid = (1+sum)/2; int cur = small+big; while (small<mid) { if(cur == sum) PrintSeq(small,big); while(cur > sum && small < mid) { cur -= small; small++; if(cur == sum) PrintSeq(small,big); } big ++; cur += big; } }
- 翻转单词顺序和左旋字符串
题目1:输入一个英文句子,翻转句子中单词的顺序,但单词内字符顺序不变。”I am a student.”->”student. a am I”.
子函数Reverse实现C语言风格的字符串反转的算法。void Reverse(char *pBegin, char *pEnd) { if(pBegin == NULL || pEnd == NULL) return; while(pBegin < pEnd) { char temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin ++, pEnd --; } } char* ReverseSentence(char *pData) { if(pData == NULL) return NULL; char *pBegin = pData;//指向单词的起始位置 char *pEnd = pData;//指向单词的终止位置 while(*pEnd != '\0') pEnd ++; pEnd--; // Reverse the whole sentence Reverse(pBegin, pEnd); // Reverse every word in the sentence pBegin = pEnd = pData; while(*pBegin != '\0') { if(*pBegin == ' ') { pBegin ++; pEnd ++; continue; } // A word is between with pBegin and pEnd, reverse it else if(*pEnd == ' ' || *pEnd == '\0') { Reverse(pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd ++; } } return pData; }
题目2:字符串左旋转操作是把字符串前面若干个字符转移到字符串的尾部,比如“abcdefg”和2,则“cdefgab”.
分析:先翻转两个子部分得“bagfedc”,再翻转整个字符串。调用题目1中的Reverse函数3次即可。char* LeftRotate(char* pStr,int n) { if(pStr!=NULL) { int len = strlen(pStr); if(len > 0 && n > 0 && n < len) { char* p1Begin = pStr; char* p1End = pStr+n-1; char* p2Begin = pStr+n; char* p2End = pStr+len-1; //翻转前n个字符 Reverse(p1Begin,p1End); //翻转后半部分 Reverse(p2Begin,p2End); //翻转整个字符串 Reverse(p1Begin,p2End); } } return pStr; }
- 判断两个string是否互为换位词
/*******************************************/ /*decide if two strings are anagrams or not*/ /*******************************************/ /*sort the string*/ bool anagram(string s,string t) { sort(s.begin(),s.end()); sort(t.begin(),t.end()); return (s == t); } /*Check if the two strings have identical counts for each unique char*/ static bool anagram2(string s,string t) { if(s.length()!=t.length()) return false; int *letters=new int[256](); //()!初始化为0 int num_unique_chars=0; int num_completed_t=0; const char *s_array=s.c_str(); for(int i=0;i<strlen(s_array);++i) { if(letters[s_array[i]] == 0) ++num_unique_chars; ++letters[s_array[i]]; } for(int i=0;i<t.length();++i) { int c=(int)t[i]; if(letters[c]==0) { return false;//t中有非s中的新字符 } --letters[c]; if(letters[c]==0) { ++num_completed_t;//比较完一个字符 if(num_completed_t==num_unique_chars) { return i==t.length()-1;//比较完所有字符,t正好处理完 } } } return false; }
- 将所有空格转换为‘%20’
题目:将字符串中出现的空格全都替换为‘%20’。
分析:首先遍历字符串,记录下有多少个空格,再从字符串尾部重新构造:
(1) 如果当前字符为空格,在写入字符串’%20′
(2) 非空格则直接记录void Replace(char* str,int len) { int count = 0; for(int i=0;i<len;++i) { if(str[i] == ' ') count++; } int newlen = len+count*2; str[newlen]='\0'; //backward for(int i=len-1;i>=0;--i) { if(str[i] == ' ') { str[newlen-1] = '0'; str[newlen-2] = '2'; str[newlen-3] = '%'; newlen -= 3; } else str[--newlen]=str[i]; } }
- Given an image represented by an N*N matrix,where each pixel in the image is 4 bytes,write a method to rotate the image by 90 degrees.Can you do this in place?
Analysis: The rotation can be performed in layers,where you perform a cyclic swap on the edges on each layer.In the first for loop,we rotate the first layer(outermost edges).We rotate the edges by doing a four-way swap first on the corners,then on the element clockwise from the edges,then on the element three steps away.
void rotate(int** matrix,int n) { for(int layer = 0;layer < n/2;++layer) { int first = layer; int last = n-1-layer; for(int i=first;i<last;++i) { int offset = i-first; int top = matrix[first][i]; //save top matrix[first][i] = matrix[last-offset][first];//left->top matrix[last-offset][first]=matrix[last][last-offset];//bottom->left matrix[last][last-offset]=matrix[i][last];//right->bottom matrix[i][last]=top;//top->right } } }
- Write an algorithm such that if an element in an M*N matrix is 0,its entire row and column is set to 0.
分析:如果先遍历矩阵,出现0元素,就将所在的行列置零。但是这样的方法执行下来的话整个矩阵都变成了0了。
一个变通的方法,在另外一个MxN的矩阵中记录是否出现零的情况,然后根据记录对原来的矩阵中对相应的行列进行置零。可是这样方法的空间复杂度为O(MxN)。有没有改进的空间呢?经过观察,其实我们只需要记录哪一列和哪一行需要置零即可。那么我们新的记录方法即为:使用两个数组rows[]和col[]来记录需要置零的行列。void setZeros(int** matrix) { int* row = new int[M]; int* column = new int[N]; for(int i = 0;i < M;++i) { for(int j = 0;j < N;++j) { if(matrix[i][j]==0) { row[i]=1; column[j]=1; } } } for(int i = 0;i < M;++i) { for(int j = 0;j < N;++j) { if(row[i]==1 || column[j]==1) { matrix[i][j]=0; } } } }