1. 按螺旋方式打印矩阵：
Print in spiral form as shown below
For n=23 20 1For n=34 3 25 0 16 7 8For n=415 14 13 124 3 2 115 0 1 106 7 8 9一看到这个题目应该比较容易想到递归，不过这个递归里面有些细节需要特别注意，代码如下：
#include <iostream> #include <math.h> using namespace std; struct Position { Position( int _x, int _y) { x = _x; y = _y;} int x, y; }; Position *CalculatePosition( int value, int xb, int yb) // xb和yb表示x和y的边界，并不表示一个点，这个也是需要搞清楚的，对某个n值而言，应该分别取什么样的值，需要计算清楚了 { int n = sqrt(value)+ 1; int t1 = n*n; int t2 = (n- 1)*(n- 1); int t3 = t1 - t2; if(n% 2) { if(value >=(t2+n- 1)) return new Position(xb+value-t2-n+ 1,yb); // 四种移动方式，每种的计算公式需要特别仔细地搞清楚 else return new Position(xb, value-t2); } else { if(value >=(t1-n)) return new Position(xb+t1-value- 1, yb-n); else return new Position(xb+n- 1,t1-n-value); } } void printspiral( int n) { int data[n][n]; int startx,starty; int total = n*n; int counting = 0; int i = n*n- 1; int t = n; int xb = 0, yb = t; bool xinc = true ; while(i>= 0) { if(i>(t*t- 1)) // 之前这里比较的是和t*t的关系，但是后来做了调整，==应该判断和t*t-1的关系，而这里就没有相应的改变一下，就出现了一个错误 { Position *p = CalculatePosition(i,xb,yb); cout<< " x = "<<p->x<< " y = "<<p->y<<endl; } else if(i == (t*t- 1)) { xinc = (xinc == false)? true: false; // 之前的写法是xinc == false? true:false，这个语句根本不会给xinc赋值，这个错误有点傻了 if(xinc) xb++; else yb--; t--; Position *p = CalculatePosition(i,xb,yb); cout<< " x = "<<p->x<< " y = "<<p->y<<endl; } else cout<< " assert "<<endl; // assert(false); i--; } } int main( int argc, char **argv) { printspiral( 5); }
2. 在一个字符串中找出由2个字符构成的最长的字符串，比如aaabbc中aaabb由2个字符组成，且长度为5，所以返回结构应该是5：
#include <iostream> #include < string.h> using namespace std; int getL2Substring( const char *src, int len) { int prevIndex = 0, prevCount = 0; int currentIndex = 0, currentCount = 0; int max = 0; for( int i = 0;i<len;i++) { if(src[i] == src[currentIndex]) { currentCount++; } else { if((prevCount + currentCount)>max) max = prevCount + currentCount; prevIndex = currentIndex; prevCount = currentCount; currentIndex = i; currentCount = 1; // 这个地方应该是1， 而不是0，要考虑清楚了！！！ } } cout<< " max len is "<<max<<endl; return max; } int main( int argc, char **argv) { char *src = " caaaabbbccccdefghighk "; getL2Substring(src, strlen(src)); }
3. 给定一个很长的字符串str 还有一个字符集比如{a,b,c} 找出str里包含{a,b,c}的最短子串。比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc。 要求复杂度为O(n)，代码如下：
用两个变量 front rear 指向一个的子串区间的头和尾，用一个数组记录当前这个子串里 字符集a,b,c 各自的个数，一个变量sum记录字符集里有多少个了。rear 一直加，更新cnt[]和sum的值，直到 sum等于字符集个数
然后front++,直到cnt[]里某个字符个数为0，这样就找到一个符合条件的字串了，继续前面的操作，就可以找到最短的了。
#include <iostream> #include <map> using namespace std; const int CHARNUM = 26; int records[CHARNUM]; bool chckexistenceinsubset( char c, const char *subset, int len) { for( int i = 0 ;i<len;i++) if(subset[i] == c) return true; return false; } int getLSL( const char *src, int len1, const char *subset, int len2) { if(src==NULL || len1 == 0) return 0; if(subset ==NULL || len2 == 0) return 0; for( int i = 0 ;i < len2;i++) records[*(subset+i)- ' a '] = 0; int front = 0, end = 0; int sum = 0; int min = 10000; bool found = false; while(end<len1) { while(sum != len2 && end<= len1) { if(chckexistenceinsubset(src[end], subset, len2)) records[src[end]- ' a ']++; if(records[src[end]- ' a '] == 1) sum++; end++; } while(!found && sum == len2 && front <=end) { if(chckexistenceinsubset(src[front], subset, len2)) { records[src[front]- ' a ']--; if(records[src[front]- ' a '] == 0) sum--; if(sum == (len2- 1)) found = true; } front++; } if(found && (end-front+ 1)<min) { min = end-front+ 1; found = false; } } cout<< " min is "<<min<< " from "<<front<< " to "<<end<<endl; return min; } int main( int argc, char **argv) { char * src = " fadabecfdcba "; getLSL(src, strlen(src), " abc ", 3); }