几道算法题目

1. 求一个字符串的全排列，如果给出 abc 能够返回abc acb bac bca cab cba

思想：相当于每个字符加上其他字符的全排列，如abc的全排列就是a+bc全排列，b+ac，c+ab。 

2. 将一个int转成string

代码     int r = 1235656;
    char* str = new char[10];
    int i = 0;
    while(r>0)
    {
        str[i++] = (char)(r%10)+48;
        r/=10;
    }
    for(int j = 0;j<strlen(str)/2;j++)
    {
        swap(str[j],str[strlen(str)-1-j]);
    }
    cout<< str<<endl;

其实有更快的方法，而且可以支持负数。

3.计算一个数的二进制表达中1的个数

思想：用x与上x-1，就会把x的最后一个1变成0

4反转链表

代码 class node{
    public:
        int data;
        node *next;
        node(int a):data(a){}
        ~node(){
            cout<<"delete"<< data << endl;
        }
};


node *Reverse(node *head)
{
    node *tmp     = NULL;                // 缓冲变量
    node *newHead = NULL;                // 反转后的新头节点

    if ( head==NULL ) return head;       // 空链表的情况
    if ( head->next==NULL ) return head; // 链表只有一个节点的情况

    while ( head )                       // 判断有没有移动到最后
    {
       tmp=head->next;                  // 临时记录下一个节点
       head->next = newHead;            // 把原来链表中的节点放到新的链表的首部
       newHead = head;
       head = tmp;
    } // end of while

    return newHead;

}