- 消除字符串中的重复字符
题目：不使用额外缓冲。注意：一两个变量使用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; } } } }
