11. 二進制中1的個數(shù)

• 輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。其中負數(shù)用補碼表示。

// Solution:位運算
// Tips:整數(shù)右移一位與整數(shù)除以二在數(shù)學(xué)上等價，但除法效率很低
// （1）如果整數(shù)右移一位，再與1做與運算判斷最后一位是不是1，負數(shù)會造成死循環(huán)
// （2）因此，采用整數(shù)與1按位與，然后把1左移1位，再按位與...
// （3）把一個整數(shù)減去1，再和原整數(shù)按位與，會將最右邊的1變成0；所以一個整數(shù)的二進制有多少1，就可進行多少次操作。
class Solution {
public:
     int  NumberOf1(int n) {
         /*（2）
         int count = 0;
         unsigned int flag = 1;
         while (flag) {
             if (n & flag) {
                 count ++;
             }
             flag = flag << 1;
         }
         return count;*/
         // （3）
         int count = 0;
         while(n) {
             count ++;
             n = n & (n-1);
         }
         return count;
     }
};

12. 數(shù)值的整數(shù)次方

• 給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。

// Solution: 需要考慮多種邊界條件，以及使用斐波那契乘方、位運算提高循環(huán)乘法效率
// Tips:(1)考慮指數(shù)<=0,小于0時需要先求|e|,再求倒數(shù),此時要求base!=0;
//      (2)e=0時，0^0沒有意義，可考慮輸出1或0；
//      (3)double/float浮點數(shù)判斷相等，不使用==，|做差|<sigma；

class Solution {
public:
    bool gInvalidInput = false;
    
    double Power(double base, int exponent) {
        gInvalidInput = false;
        
        // 判斷指數(shù)e<0時，底數(shù)base是否等于0.0
        if (exponent <= 0 && (equal(base, 0.0))) {
            gInvalidInput = true;
            return 0.0;
        }
        
        // 判斷指數(shù)e<0時，需要求-e，并計算指數(shù)結(jié)果后求倒數(shù)
        unsigned int absExponent = (unsigned int)exponent;
        if (exponent < 0) {
            absExponent = (unsigned int)(-exponent);
        }
        
        double result = PowerWithUnsignedExponent(base, absExponent);
        if (exponent < 0)
            result = 1.0 / result;
        return result;
    }
    
    bool equal(double num1, double num2) {
        if ((num1 - num2 < 0.0000001) && (num1 - num2 > -0.0000001))
            return true;
        else
            return false;
    }
    
    double PowerWithUnsignedExponent(double base, unsigned int exponent) {
        /* 效率較低的循環(huán)乘法
        double res = 1.0;
        for (int i=1; i <= exponent; i ++) {
            res *= base;
        }*/
        
        // 使用a^n公式及位運算：
        // （1）n為偶數(shù)，a^n = a^(n/2) * a^(n/2)
        // （2）n為奇數(shù)，a^n = a^(（n-1）/2) * a^((n-1)/2) * a
        if (exponent == 0)
            return 1;
        if (exponent == 1)
            return base;
        
        double res = PowerWithUnsignedExponent(base, exponent >> 1);
        res *= res;
        if (exponent & 0x1 == 1)
            res *= base;
        return res;
    }        
};

《劍指offer面試題12：打印1到最大的n位數(shù)》
（1）大數(shù)用字符串表示，最前補0；
（2）遞歸打印0~9的全排列。
（3）特殊輸入如0，-1等需要考慮。

《劍指offer面試題13：在O(1)時間刪除鏈表結(jié)點》給定單向鏈表頭指針和一個結(jié)點指針，刪除該結(jié)點
（1）O(n)順序找到要刪除結(jié)點的前一個結(jié)點， 更改pNext；
（2）O(1)復(fù)制下一個結(jié)點，刪除下一個結(jié)點，尾結(jié)點費時（另需考慮僅一個結(jié)點），時間復(fù)雜度=[(n-1)*O(1)+O(n)]/n=O(1)。

13. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面（注意erase時，iterator需要變化）

• 輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if (array.size() == 0) {
            return;
        }
        vector<int> right;
        vector<int>::iterator itArray;
        for (itArray = array.begin(); itArray != array.end(); itArray ++) {
            if (isEven(*itArray)) {
                right.push_back(*itArray);
                array.erase(itArray);
                itArray --; // 因為刪除vector元素后，循環(huán)itArray++會導(dǎo)致跳過訪問一個元素，以及后續(xù)訪問溢出
            }
        }
        vector<int>::iterator itRight;
        for (itRight = right.begin(); itRight != right.end(); itRight++) {
            array.push_back(*itRight);
        }
    }
    // 解耦判斷條件
    bool isEven(int n) {
        return !(n & 1);
    }
};

14. 鏈表中的倒數(shù)第k個結(jié)點

• 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。

// Tips:(1)pListHead==NULL; (2)unsigned int k==0時， k-1是4294967295; (3)鏈表個數(shù)<k.
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL || k == 0) {//k==0時，不返回，unsigned int會導(dǎo)致循環(huán)崩潰
            return NULL;
        }
        
        ListNode* pAhead = pListHead;
        ListNode* pBehind = pListHead;
        for (unsigned int i=0; i < k-1; i ++) {
            if (pAhead->next != NULL) {//鏈表個數(shù)小于k時
                pAhead = pAhead->next;
            } else {
                return NULL;
            }
        }
        
        while (pAhead->next != NULL) {
            pAhead = pAhead->next;
            pBehind = pBehind->next;
        }
        return pBehind;
    }
};

15. 反轉(zhuǎn)鏈表

• 輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

// Solution:使用三個指針pPrev，pNode，pNext完成反轉(zhuǎn)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pPrev = NULL;
        ListNode* pNode = pHead;
        // ListNode* pReverseHead = NULL;  
        while (pNode != NULL) {
            ListNode* pNext = pNode->next;
            // if (pNext == NULL) {
            //     pReverseHead = pNode;
            // } 
            pNode->next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        // return pReverseHead;
        return pPrev;
    }
};