第二十一题：输入m、n，打印出1~n中所有和等于m的组合(01背包问题)

递归法：

void printSolution(int *flag){    for(int i=1;i<100;++i)        if(flag[i]!=0)cout<<<" ";    cout<
        
         m)n=m;    if(n==m){
     //end , print it        flag[n]=1;        printSolution(flag);        flag[n]=0;    }    flag[n]=1;//select n    bao(m-n,n-1,flag);    flag[n]=0;    bao(m,n-1,flag);//not select n}
        

动态规划：适用于寻找最大值的情况。但需要打印出所有值时比较复杂。

第二十四题：合并但链表

先把原来的两个链表排序，然后在搞两个指针代表两个链表的当前节点。比较两个节点后决定新链表的新节点连接哪个，连了以后指向下一个节点。没什么好说的。。。想不通看会源代码。

第二十五题：找出最长的连续数字子串

一个变量记录当前最长字符串，一个变量记录全局最长字符串

bool is_digit(char c){    if(c>='0' && c<='9')return true;    return false;} void strcpy(const char *from,char *to,int count){    for(int i=0;i
       
        max){                max=thismax;                pmax=p-max;            }        }else thismax++;        if(*p++=='\0')break;    }    strcpy(pmax,outputstr,max);    return max;}
       

第二十六题：左旋字符串

使用之前reversestring的函数，进行反转再反转。第一次翻转复杂度为O(n/2)，再翻转也是，总共就O(n)

 

第二十七题：n级楼梯，一次可以跳一步或者两步，一共有多少种跳法

第k个台阶的时候，可以从第k-1跳一步到达，也可以从k-2步跳2步到达。也就是是f(n)=f(n-1)+f(n-2)，也就是裴波拉奇数列。用动态规划解决。

 

第二十八题：判断一个整数的二进制数中1的个数

法1：除以2看余数是否为1，是则加一，直到0.

法2：右移一位，判断最低位是否为1，是则加一。O(k),k is the bit length of int

int countOne2(int n){    int cnt=0;    while(n){        if(n&1!=0)cnt++;        n>>=1;    }    return cnt;}

法3：n & n-1会将最低位的1变成0，如 1010 % 1001 = 1000，不断操作直至n=0，每次操作count+1. O(k),k is the number of 1 in n

int countOne3(int n){    int cnt=0;    while(n){        cnt++;        n&=n-1;    }    return cnt;}

第二十九题：判断一个序列是否是一个push序列的pop序列

根据堆栈的性质用一个stack来模拟看能否全部用上两个序列即可

int judgeStackSequence(int *push,int *pop,int count){    int iPop=count,iPush=count-1;    stack
       
         buf;    buf.push(*push++);    while(iPush>0){        while(!buf.empty() && buf.top()!=*pop){            buf.push(*push++);            iPush--;        }        while(!buf.empty() && buf.top()==*pop){            buf.pop();            iPop--;            pop++;        }    }    return iPop==0?1:0;}
       

第三十题：1到N的整数中出现1的次数

高效的方法太复杂了，低效的方法很简单，就是%10看余数，再除以10.

int helper(int n){    int k=n;    int cnt=0;    while(n!=0){        if(n%10==1)cnt++;        n/=10;    }    return cnt;} int countOne(int n){    int cnt=0;    for(int i=1;i<=n;++i)cnt+=helper(i);    return cnt;}