1. 下面代碼的輸出是什么

int GetSize(int data[])
{
    return sizeof(data);
}
int main()
{

    int data1[]= {1,2,3,4,5};
    int size1 = sizeof(data1);
    int *data2 = data1;
    int size2 = sizeof(data2);
    int size3 = GetSize(data1);
    cout <<size1 << " " << size2 << "  " << size3 << endl;
}

20 8  8

因為sizeof(data1)是求數(shù)組的大小酥诽，每個整數(shù)占4個字節(jié)；
第二個是因為指針占8個字節(jié)皱埠；
第三個是因為數(shù)組作為函數(shù)參數(shù)進(jìn)行傳遞肮帐，數(shù)組退化為指針，也為8個字節(jié)边器。

2. 面試題：找出數(shù)組中任意一個重復(fù)的數(shù)字泪姨，數(shù)組滿足：長度為n的數(shù)組里所有數(shù)字都在0~n-1的范圍內(nèi)。

• 思路：若不重復(fù)饰抒，每個下標(biāo)對應(yīng)一個等于下標(biāo)值的數(shù)肮砾。對下標(biāo)i與m=arr[i]作比較，不相等交換arr[i]與arr[m]
• 時間復(fù)雜度袋坑，空間復(fù)雜度仗处。

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool duplicate(vector<int> &arr, int &answer)
{
  for(auto i:arr)
    if(i<0 ||i>arr.size()-1)
      return false;
  for(auto i=0; i<arr.size();++i)
  {
    while(arr[i]!=i)
    {
      if(arr[i]==arr[arr[i]])
      {
        answer = arr[i];
        return true;
      }
      else
      {
        swap(arr[i], arr[arr[i]]);
      }
    }
  }
  return false;
}
int main() {
  int answer;
  vector<int> t={2,3,1,0,2,5,3};
  if(duplicate(t, answer))
    cout << "one duplicate number is: " << answer << endl;
  else
    cout << "no duplicate number ." << endl;
}

one duplicate number is: 2

3. 不修改數(shù)組找出重復(fù)的數(shù)字，數(shù)組滿足：長度為n+1的數(shù)組里所有的數(shù)字都在1~n范圍內(nèi)枣宫，因此至少有一個數(shù)字是重復(fù)的婆誓。找出任意一個數(shù)字。

• 思路：輔助數(shù)組的方法時間復(fù)雜度也颤，空間復(fù)雜度洋幻，空間換時間；折半查找的方法時間復(fù)雜度,空間復(fù)雜度翅娶，時間換空間文留。
• 排查數(shù)組哪一半的數(shù)字有重復(fù)好唯，遍歷數(shù)組所有數(shù)，計數(shù)每個數(shù)是否在下標(biāo)范圍燥翅，總計數(shù)值超過的這一半的大小的話骑篙，有重復(fù)元素；

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;


int countRage(const vector<int> &arr,const int &start,const int &end)
{
  int count = 0;
  for(auto iter:arr)
  {
    if(start<=iter && iter<=end)
      ++count;
  }
  return count;
}
int getDuplication(const vector<int> &arr)
{
  int start =1;
  int end = arr.size()-1;
  //直到二分?jǐn)?shù)組大小為1為止
  while(end>=start)
  {
    int middle=((end-start)>>1) + start;
    int count=countRage(arr, start, middle);
    //大小為1
    if (end==start)
    {
      //單個數(shù)字的計數(shù)是否重復(fù)
      if(count>1)
        return start;
      else
        break;
    }
    
    if(count > middle-start+1) //是否在左側(cè)
      end = middle;
    else
      start = middle+1;
  }
  return -1;
}

int main() {
 
  vector<int> t={2,3,5,4,3,2,6,7};
  int answer=getDuplication(t);
  if(answer>=0)
    cout << "one duplicate number is: " << answer << endl;
  else
    cout << "no duplicate number ." << endl;
}

方法2：

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
    for(int i=0;i!=length;++i){
        int index=numbers[i]%length;
        if(numbers[index]>=length){
            *duplication=index;
            return 1;
        }              
        numbers[index]+=length;  
    }
    return 0;
}
};

4. 有規(guī)律的二維數(shù)組中找出某一個數(shù)：數(shù)組滿足每行數(shù)大小遞增森书，每一列大小遞增靶端。

• 從第一行最后一列排除：

//number 是要找的數(shù)
bool Find(vector<vector<int>> &mat,const int &rows, const int &columns, const int &number)
{
  bool find = false;
  if (rows>0 && columns>0)
  {
    int row=0, column=columns-1;
    while(row<rows && column >=0)
    {
      if(mat[row][column] == number)
      {
        find = true;
        break;
      }
      else if(mat[row][column] > number)
        --column;
      else
        ++row;
    }
  }
  return find;
}

int main() {
 
  vector<vector<int>> test={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
  int ans=7;
  int answer=Find(test,0, 4, ans);
  if(answer>=0)
    cout << "find answer: " << ans << endl;
  else
    cout << "no answer ." << endl;
}

16. 數(shù)值的整數(shù)次方：給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方凛膏。

• 解：
  利用了公式：
  

實現(xiàn)的時候先對目標(biāo)的一半運算出來杨名，然后判斷是否是奇數(shù)。

class Solution {
public:
    double Power(double base, int exponent) {
        // 直接返回
        if(base==0)
            return 0;
        //對數(shù)的絕對值
        unsigned int absExponent=(unsigned int)(abs(exponent));
        double ans = _power(base, absExponent);
        if(exponent<0)
            ans = 1.0/ans;
        return ans;
    }
private:
    //避免復(fù)雜度高猖毫，利用公式遞歸求解台谍；
    double _power(int base, unsigned int absExponent)
    {
        if(absExponent==0)
            return 1;
        if(absExponent==1)
            return base;
        //遞歸公式
        double result=_power(base, absExponent>>1);
        //還剩一半的部分
        result *= result;
        //若為奇數(shù)值，乘上少乘的一個基底
        if(absExponent&0x1 ==1)
            result*=base;
        return result;
    }
};

21. 調(diào)整數(shù)組順序使得奇數(shù)位于偶數(shù)前面

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

• 解：
  相對位置不變--->保持穩(wěn)定性骂因；奇數(shù)位于前面炎咖，偶數(shù)位于后面 --->存在判斷，挪動元素位置寒波； 這些都和內(nèi)部排序算法相似乘盼，考慮到具有穩(wěn)定性的排序算法不多，例如插入排序俄烁，歸并排序等绸栅；

class Solution {
public:
    static bool isOk(int n){return (n&0x1)==1;}
    //stable_partition 這個函數(shù)函數(shù)功能是將數(shù)組中　isOk為真的放在數(shù)組前，假的放在數(shù)組后页屠，和題意相符
    //stable_partition函數(shù)源碼其實是開辟了新的空間粹胯，然后把符合條件的放在新空間的前面，其他的放在后面辰企。
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(),array.end(),isOk);
    }

};

29风纠、順時針打印矩陣

輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字牢贸，例如竹观，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

• 解：需要分析它的邊界：
  打印四個邊，什么時候退出：行、列數(shù)目大于2倍起點的時候臭增；起點是每次的左上角位置懂酱；

打印第一步：因為打印一圈至少有一步，所以直接打铀僦贰玩焰；
打印第二步：行號大于起點行號才能多處行往下打佑删浴芍锚；
打印第三步：考慮這時候不能為一行一列的打印，至少是兩行兩列蔓榄；
打印第四步：考慮已經(jīng)少了一行數(shù)目并炮；

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        if(matrix.empty()) return ans;
        int rows=matrix.size();
        int cols=matrix[0].size();
        int position = 0;
        //退出條件是兩倍位置大小
        while(rows> 2*position && cols > 2*position)
        {
            print(matrix,position,rows,cols, ans);
            ++position;
        }
        return ans;
    }
private:
    void print(const vector<vector<int>> &mat,int position, int rows, int cols,vector<int>& ans)
    {
        rows = rows-position-1;
        cols = cols-position-1;
        
        //case1:多余的列存在
        for(int i=position; i<=cols; ++i)
        {
            ans.push_back(mat[position][i]);
        }
        //case2:多余的行存在
        if(position<rows)
        {
            for(int i=position+1;i<=rows;++i)
            {
                ans.push_back(mat[i][cols]);
            }
        }
        //case3:從右到左打印;排除一行一列的打印
        if(position<rows && position<cols)
        {
            for(int i=cols-1;i>=position;--i)
            {
                ans.push_back(mat[rows][i]);
            }
        }
        //case4:從下到上打印
        if(position+1<rows && position<cols)
        {
            for(int i=rows-1;i>=position+1;--i)
                ans.push_back(mat[i][position]);
        }     
    }
};

39、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半甥郑，請找出這個數(shù)字逃魄。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次澜搅，超過數(shù)組長度的一半伍俘，因此輸出2。如果不存在則輸出0勉躺。

• 解： 兩種方法實現(xiàn)：1,快排分割癌瘾，元素被放置在中間位置，則找到結(jié)果饵溅；2.設(shè)置每次遇到的該數(shù)為result妨退，并計數(shù)1，若下次遇到的
  是該數(shù)蜕企，計數(shù)增加咬荷，若不是，計數(shù)減少轻掩，當(dāng)計數(shù)為0幸乒，設(shè)result為新的該數(shù)字，最后被保存的result肯定是超過一半的數(shù)字

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
        int result = numbers[0];
        int count = 1;
        for(int i=1; i<numbers.size();++i)
        {
            if(numbers[i] == result)
            {
                count++;
            }
            else
            {
                count--;
                if (count==0)
                {
                    result = numbers[i];
                    count=1;
                }
            }
        }
        //檢查該數(shù)組是否是滿足題意的數(shù)組唇牧；
        count=0;
        for(int i=0; i<numbers.size(); ++i)
        {
            if(numbers[i]==result)
                count++;
        }
        if(count*2<=numbers.size())
            return false;
        return result;
    }
};

方法1：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
        int middle = numbers.size()>>1;
        int start = 0;
        int end = numbers.size()-1;
        int index = partition(start, end, numbers);
        while(index!=middle)
        {
            //在下標(biāo)小于中位數(shù)罕扎，它的middle應(yīng)該在右邊
            if(index<middle)
            {
                start = index+1;
                index = partition(start,end, numbers);
            }
            else
            {
                end = index-1;
                index = partition(start, end, numbers);
            }
        }
        //檢查是否有是合格的組數(shù)
        int result = numbers[index];
        int count = 0;
        for(int i=0; i<numbers.size(); ++i)
        {
            if(numbers[i] == result)
                count++;
        }
        if(count*2<=numbers.size())
            return false;
        return result;
    }
private:
    //返回元素的中間位置
    int partition(int start,int end,vector<int>& arr)
    {
        int pivot = arr[start];
        size_t position = start;//記錄哨兵最后放置的位置
        for(int i=start+1; i<= end; ++i)
        {
            if(arr[i]<pivot)//只放置小的在左邊就行
            {
                position++;//遇到一個小的元素，往前走一步做交換
                if(i!=position)//頭元素是povit奋构，這個位置最后交換
                    swap(arr[i], arr[position]);
            }
        }
        swap(arr[position], arr[start]);
        return position;
    }
};

40壳影、最小的k個數(shù)

輸入n個整數(shù)，找出其中最小的K個數(shù)弥臼。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字宴咧，則最小的4個數(shù)字是1,2,3,4,。

• 解析：第一種一般可想到是堆排序径缅，且不會修改輸入數(shù)據(jù)掺栅，適合在處理海量數(shù)據(jù)中進(jìn)行查找烙肺，STL中的set與multiset的底層是紅黑樹實現(xiàn)的，可以滿足在時間內(nèi)完成查找氧卧、刪除桃笙、插入。第二種方法是partition.

方法1：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len<=0 || k>len || k<=0) return vector<int>();
        vector<int> ans;
        for(int i=0;i<k;++i)//先插入前main的k個后建立大頂堆
            ans.push_back(input[i]);
        //建堆
        make_heap(ans.begin(), ans.end());
        for(int i=k; i<input.size(); ++i)
        {
            if(input[i]<ans[0]) //比堆頂元素還大沙绝，那么替換該元素放入ans搏明，然后維持堆性質(zhì)
            {
                pop_heap(ans.begin(), ans.end()); //最大元素放到末尾；
                ans.pop_back();//彈出最大的元素
                ans.push_back(input[i]); 
                push_heap(ans.begin(), ans.end());//維持堆性質(zhì)
            }     
        }
        //使其從小到大輸出
        sort_heap(ans.begin(),ans.end());
        return ans;
    }
};

方法2：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len<=0||k>len || k<=0) return vector<int>();
         
        //仿函數(shù)中的greater<T>模板闪檬，從大到小排序
        multiset<int, greater<int> > leastNums;
        vector<int>::iterator vec_it=input.begin();
        for(;vec_it!=input.end();vec_it++)
        {
            //將前k個元素插入集合
            if(leastNums.size()<k)
                leastNums.insert(*vec_it);
            else
            {
                //第一個元素是最大值
                multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
                //如果后續(xù)元素<第一個元素星著，刪除第一個，加入當(dāng)前元素
                if(*vec_it<*(leastNums.begin()))
                {
                    leastNums.erase(greatest_it);
                    leastNums.insert(*vec_it);
                }
            }
        }
         
        return vector<int>(leastNums.begin(),leastNums.end());
    }
};

41粗悯、數(shù)據(jù)流中的中位數(shù)

如何得到一個數(shù)據(jù)流中的中位數(shù)虚循？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值样傍。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值横缔，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流衫哥，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)茎刚。

• 解析： 假設(shè)整個數(shù)據(jù)容器分割為兩部分，位于容器左邊的部分比右邊的部分锌婚荨斗蒋；容器左數(shù)組的最右邊指向該部分最大的數(shù)；同樣笛质， 容器右數(shù)組的最左邊指向該部分最小的數(shù)泉沾；
  具體實現(xiàn)：左邊用最大堆，右邊用最小堆妇押；首先保證數(shù)據(jù)平均分配到兩個堆中跷究，因此這兩個堆中的數(shù)據(jù)數(shù)目之差不超過1，用偶數(shù)的數(shù)字都插入最小堆敲霍；保證最大堆中的數(shù)都小于最小堆俊马，當(dāng)前插入數(shù)字小于最大堆堆頂元素，可以把該堆的堆頂元素排除肩杈，插入到最小堆柴我，然后把該數(shù)字插入最大堆中.

class Solution {
private:
        vector<int> min;
        vector<int> max;
public:
        //第0個元素先插入到min中，之后第1個元素插入到max中.若元素有5個扩然，那么0,2,4被插入到min中艘儒，可以看到
        //若元素有6個,0,2，4，被插入到min中界睁，1,3,5被插入到max中觉增。
        //因此min只用的元素大于等于max
        //元素為奇數(shù)時，返回min的元素
        void Insert(int num)
        {
           if(((min.size()+max.size())&1)==0)//偶數(shù)時 翻斟，放入最小堆
           {
              if(max.size()>0 && num<max[0])
              {
                // push_heap (_First, _Last),要先在容器中加入數(shù)據(jù)逾礁，再調(diào)用push_heap ()
                 max.push_back(num);//先將元素壓入容器
                 push_heap(max.begin(),max.end(),less<int>());//調(diào)整最大堆
                 num=max[0];//取出最大堆的最大值
                 //pop_heap(_First, _Last)，要先調(diào)用pop_heap()再在容器中刪除數(shù)據(jù)
                 pop_heap(max.begin(),max.end(),less<int>());//刪除最大堆的最大值
                 max.pop_back(); //在容器中刪除
              }
              min.push_back(num);//壓入最小堆
              push_heap(min.begin(),min.end(),greater<int>());//調(diào)整最小堆
           }
           else//奇數(shù)時候访惜，放入最大堆
           {
              if(min.size()>0 && num>min[0])
              {
                // push_heap (_First, _Last),要先在容器中加入數(shù)據(jù)嘹履，再調(diào)用push_heap ()
                 min.push_back(num);//先壓入最小堆
                 push_heap(min.begin(),min.end(),greater<int>());//調(diào)整最小堆
                 num=min[0];//得到最小堆的最小值（堆頂）
                 //pop_heap(_First, _Last)，要先調(diào)用pop_heap()再在容器中刪除數(shù)據(jù)
                 pop_heap(min.begin(),min.end(),greater<int>());//刪除最小堆的最大值
                 min.pop_back(); //在容器中刪除
              }
              max.push_back(num);//壓入數(shù)字
              push_heap(max.begin(),max.end(),less<int>());//調(diào)整最大堆
           }   
        }
        /*獲取中位數(shù)*/      
        double GetMedian()
        {
            int size=min.size()+max.size();
            if(size<=0) //沒有元素疾牲，拋出異常
                return 0;//throw exception("No numbers are available");
            if((size&1)==0)//偶數(shù)時植捎，去平均
                return ((double)(max[0]+min[0])/2);
            else//奇數(shù)衙解，去最小堆阳柔，因為最小堆數(shù)據(jù)保持和最大堆一樣多，或者比最大堆多1個
                return min[0];
        }
};

42蚓峦、連續(xù)子數(shù)組的最大和

HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學(xué)舌剂。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個負(fù)數(shù),并期望旁邊的正數(shù)會彌補它呢暑椰？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)霍转。給一個數(shù)組，返回它的最大連續(xù)子序列的和一汽，你會不會被他忽悠妆芟？(子向量的長度至少是1)

• 解析：1召夹。動態(tài)規(guī)劃問題岩喷，設(shè)在位置處結(jié)尾的數(shù)組最大和為,那前面長度為的數(shù)組的最大連續(xù)子序列的和為：
  

可以理解，如果前面的結(jié)尾的子串為負(fù)數(shù)监憎，可以不加纱意；若為正數(shù)，可以考慮加上這個值鲸阔。最后還需要求 找出最大的和：

class Solution {
public:
    /*
    dp = max{f(i)},i=0,1,...,N
    f(i) = f(i-1) + data[i] if (i偷霉！= 0 && f(i-1)>0) else data[i].
    */
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty()) return 0;
        vector<int> arr;
        int ans = INT_MIN;
        for(int i=0; i<array.size(); ++i)
        {
           ans = max(ans, dp(i,arr,array));
        }
        return ans;
    }
private:
    //position給出結(jié)尾的位置
    //position結(jié)尾的最大和存入arr
    //target是原來的數(shù)組，用來查看當(dāng)前的結(jié)尾數(shù)
    int dp(int position,vector<int>& arr,const vector<int> &target)
    {
        if(position && arr[position-1] > 0)
        {
            int ans = target[position] + arr[position-1];
            arr.push_back(ans);
            return ans;
        }
        else
        {
            arr.push_back(target[position]);
            return target[position];
        }
    }
};

2.跟據(jù)求和的性質(zhì)褐筛，若為負(fù)类少，丟棄當(dāng)前和，并記錄每一的最大和渔扎；

public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
        {
            InvalidInput = true;//判斷是否無效輸入而非最大和為0
            return 0;
        }
        int nCurSum=0;
        int great =0x80000000;
        for(int i=0; i<array.size();++i)
        {
            if(nCurSum<=0) //若為0或負(fù)值硫狞，那么略去這個求和，設(shè)新的求和為當(dāng)前數(shù)
                nCurSum=array[i]; //
            else
                nCurSum+=array[i];
            if(nCurSum>great)//記錄最大子數(shù)組和
                great = nCurSum;
        }
        return great;
        
    }
private:
    bool InvalidInput = false;
};

43、1~n整數(shù)中1出現(xiàn)的次數(shù)

求出1_{13的整數(shù)中1出現(xiàn)的次數(shù),并算出100}1300的整數(shù)中1出現(xiàn)的次數(shù)妓忍？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1虏两、10、11世剖、12定罢、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）旁瘫。

• 解析： 方法1:nlog(n)暴力搜索祖凫，對每一個數(shù)求一個計數(shù)1的函數(shù)；
  方法2:log(n) 考慮問題本身的性質(zhì)酬凳；

//方法1：nlog(n)
class Solution {
public:
    /*
    方法1:nlog(n)暴力搜索惠况，對每一個數(shù)求一個計數(shù)1的函數(shù)；
    方法2:log(n) 考慮問題本身的性質(zhì)宁仔；
    */
    int NumberOf1Between1AndN_Solution(int n)
    {
        int number = 0;
        for(int i=1; i<=n; ++i)
        {
            number += Numberi(i);
        }
        return number;
    }
private:
    int Numberi(int i)
    {
        int number=0;
        while(i)
        {
            if(i%10==1)
                number+=1;
            i=i/10;
        }
        return number;
    }
};

方法2：參考第三題：http://www.reibang.com/p/1582fbaf05f7

當(dāng) N 為 1 位數(shù)時稠屠，對于 N>=1，1 的個數(shù) f(N) 為1翎苫。
當(dāng) N 為 2 位數(shù)時权埠，則個位上1的個數(shù)不僅與個位數(shù)有關(guān)，還和十位數(shù)字有關(guān)煎谍。
比如當(dāng) N=23 時攘蔽，個位上 1 的個數(shù)有 1、11呐粘、21 共3個满俗，十位上1的個數(shù)為10，11...19 共10個作岖，所以 1 的個數(shù) f(N) = 3+10 = 13唆垃。
看出來有規(guī)律一：
如果 N 的個位數(shù) >=1，則個位出現(xiàn)1的次數(shù)為十位數(shù)的數(shù)字加1鳍咱；如果 N 的個位數(shù)為0降盹，則個位出現(xiàn) 1 的次數(shù)等于十位數(shù)的數(shù)字。
十位數(shù)上出現(xiàn)1的次數(shù)類似谤辜，如果N的十位數(shù)字等于1蓄坏，則十位數(shù)上出現(xiàn)1的次數(shù)為各位數(shù)字加1；如果N的十位數(shù)字大于1丑念，則十位數(shù)上出現(xiàn)1的次數(shù)為10涡戳。
當(dāng) N 為 3 位數(shù)時，同樣分析可得1的個數(shù)脯倚。如 N=123渔彰，可得 1出現(xiàn)次數(shù) = 13+20+24 = 57嵌屎。當(dāng) N 為 4,5...K 位數(shù)時，

我們假設(shè) N=abcde恍涂，則要計算百位上出現(xiàn)1的數(shù)目宝惰，則它受到三個因素影響：百位上的數(shù)字，百位以下的數(shù)字再沧，百位以上的數(shù)字尼夺。
如果百位上數(shù)字為0，則百位上出現(xiàn)1的次數(shù)為更高位數(shù)字決定炒瘸。如 N=12013淤堵，則百位出現(xiàn)1的數(shù)字有100~199， 1000~1199顷扩， 2100_2199...11100111999 共 1200 個拐邪，等于百位的更高位數(shù)字(12)當(dāng)前位數(shù)(100)。
如果百位上數(shù)字為1隘截，則百位上出現(xiàn)1的次數(shù)不僅受更高位影響扎阶，還受低位影響。如12113技俐，則百位出現(xiàn)1的情況共有 1200+114=1314 個乘陪，也就是高位影響的 12 * 100 + 低位影響的 113+1 = 114 個。
如果百位上數(shù)字為其他數(shù)字雕擂，則百位上出現(xiàn)1的次數(shù)僅由更高位決定。如 12213贱勃，則百位出現(xiàn)1的情況為 (12+1)100=1300井赌。

總共有12*100個1出現(xiàn)在百位。結(jié)論是位數(shù)為0時戚绕，只受高位數(shù)的影響纹坐，為高位數(shù)的值 * 當(dāng)前位 。其他位的分析類似舞丛。

有以上分析思路耘子，寫出下面的代碼。其中 low 表示低位數(shù)字球切，curr 表示當(dāng)前考慮位的數(shù)字谷誓，high 表示高位數(shù)字。一個簡單的分析吨凑，考慮數(shù)字 123捍歪，則首先考慮個位户辱，則 curr 為 3，低位為 0糙臼，高位為 12庐镐；然后考慮十位，此時 curr 為 2变逃，低位為 3焚鹊，高位為 1。其他的數(shù)字可以以此類推韧献，實現(xiàn)代碼如下：

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;//1的個數(shù)
        int i = 1;//乘積因子
        int current = 0,after = 0,before = 0;
        while((n/i)!= 0){           
            current = (n/i)%10; //當(dāng)前位數(shù)字
            before = n/(i*10); //高位數(shù)字
            after = n-(n/i)*i; //低位數(shù)字
            //如果為0,出現(xiàn)1的次數(shù)由高位決定,等于高位數(shù)字 * 當(dāng)前位數(shù)
            if (current == 0)
                count += before*i;
            //如果為1,出現(xiàn)1的次數(shù)由高位和低位決定,高位*當(dāng)前位+低位+1
            else if(current == 1)
                count += before * i + after + 1;
            //如果大于1,出現(xiàn)1的次數(shù)由高位決定,//（高位數(shù)字+1）* 當(dāng)前位數(shù)
            else{
                count += (before + 1) * i;
            }    
            //前移一位
            i = i*10;
        }
        return count;
    }
};

45末患、把數(shù)組排成最小的數(shù)

輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)锤窑，打印能拼接出的所有數(shù)字中最小的一個璧针。例如輸入數(shù)組{3，32渊啰，321}探橱，則打印出這三個數(shù)字能排成的最小數(shù)字為321323。

• 解析：數(shù)組內(nèi)的數(shù)變?yōu)閟tring之后做拼接绘证，按照字符串排序便可隧膏，拼接之后字符串AB>BA，那么有B<A,應(yīng)該把B排前面嚷那。

class Solution {
public:
    //數(shù)組內(nèi)的數(shù)變?yōu)閟tring之后做拼接排序
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), cmp);
        string ans="";
        for(int i=0; i<int(numbers.size());++i) ans+=to_string(numbers[i]);
        return ans;
    }
private:
    static bool cmp(int a, int b)
    {
        string sa=to_string(a), sb =to_string(b);
        return sa +sb < sb + sa;
    }
};

做法2：

//寫的比較騷氣的整型到string
string itos(int x){
    return (x > 9 ? itos(x / 10) : "") + char(x % 10 + '0');
}
//比較字符函數(shù)
bool cmp(int a, int b){
    return itos(a) + itos(b) < itos(b) + itos(a);
}

class Solution {
public:
    string PrintMinNumber(vector<int> a) {
        sort(a.begin(), a.end(), cmp);
        string s = "";
        //轉(zhuǎn)為字符再追加到s
        for(int i = 0; i < int(a.size()); ++i) s += itos(a[i]);
        return s;
    }
};

49胞枕、第N個丑數(shù)。

把只包含質(zhì)因子2魏宽、3和5的數(shù)稱作丑數(shù)（Ugly Number）腐泻。例如6、8都是丑數(shù)队询，但14不是派桩，因為它包含質(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)蚌斩。求按從小到大的順序的第N個丑數(shù)铆惑。

• 解析：
  空間換時間，記錄存儲下丑數(shù)送膳，丑數(shù)按遞增大小尋找员魏；
  當(dāng)前的丑數(shù)已經(jīng)被找到,那么該丑數(shù)之前的數(shù)字都是排好序的，
  下一個丑數(shù)也是2肠缨、3逆趋、5的倍數(shù)，且大于當(dāng)前丑數(shù)晒奕；找到每一個2闻书、3名斟、5倍數(shù)里最小的作為下一個丑數(shù)
  排序好的丑數(shù)中，前面的丑數(shù)是后面選出的丑數(shù)的因子之一魄眉，用下標(biāo)跟隨前面的因子與2砰盐、3、5的乘積>大于當(dāng)前丑數(shù)
  丑數(shù)定義：1是最小的丑數(shù)坑律，只能被2或者3或者5整除的數(shù)是丑數(shù);

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        vector<int> uglyVec={1}; 
        //作為下標(biāo)記錄2岩梳、3、5因子里前面
        int index2=0, index3=0, index5=0;
        while(uglyVec.size()<index)
        {
            uglyVec.push_back(min(uglyVec[index2]*2, min(uglyVec[index3]*3, uglyVec[index5]*5)));
            if(uglyVec[index2]*2== uglyVec.back()) //等號的意義是丑數(shù)不重復(fù)
                index2++;
            if(uglyVec[index3]*3 == uglyVec.back())
                index3++;
            if(uglyVec[index5]*5== uglyVec.back())
                index5++;
        }
        return uglyVec.back();
    }
};

51晃择、逆序?qū)?/p>

在數(shù)組中的兩個數(shù)字冀值，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)馈］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P列疗。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007

• 解析：

/*歸并排序的改進(jìn)浪蹂，把數(shù)據(jù)分成前后兩個數(shù)組(遞歸分到每個數(shù)組僅有一個數(shù)據(jù)項)抵栈，

合并數(shù)組，合并時坤次，出現(xiàn)前面的數(shù)組值array[i]大于后面數(shù)組值array[j]時古劲；則前面

數(shù)組array[i]~array[mid]都是大于array[j]的，count += mid+1 - i

參考劍指Offer缰猴，但是感覺劍指Offer歸并過程少了一步拷貝過程产艾。

還有就是測試用例輸出結(jié)果比較大罢屈，對每次返回的count mod(1000000007)求余

*/

/*參考《劍指offer》蔓倍，有兩種思路。第一就是暴力求解法蕴掏，時間復(fù)雜度為o（n^2）,空間復(fù)雜度o(1)
第二種思路就是使用歸并排序的思想進(jìn)行處理蹬挤，時間復(fù)雜度o(nlog(n)),空間復(fù)雜度0（n）*/
class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<=1) return 0;//如果少于等于1個元素，直接返回0
        int* copy=new int[data.size()];
        //初始化該數(shù)組棘幸，該數(shù)組作為存放臨時排序的結(jié)果焰扳，最后要將排序的結(jié)果復(fù)制到原數(shù)組中
        for(unsigned int i=0;i<data.size();i++)
            copy[i]=0;
        //調(diào)用遞歸函數(shù)求解結(jié)果
        int count=InversePairCore(data,copy,0,data.size()-1);
        delete[] copy;//刪除臨時數(shù)組
        return count;
    }
     //程序的主體函數(shù)
    int InversePairCore(vector<int>& data,int*& copy,int start,int end)
    {
        if(start==end)
        {
            copy[start]=data[start];
            return 0;
        }
        //將數(shù)組拆分成兩部分
        int length=(end-start)/2;//這里使用的下標(biāo)法，下面要用來計算逆序個數(shù)误续；也可以直接使用mid=（start+end）/2
        //分別計算左邊部分和右邊部分
        int left=InversePairCore(data,copy,start,start+length)%1000000007;
        int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
        //進(jìn)行逆序計算
        int i=start+length;//前一個數(shù)組的最后一個下標(biāo)
        int j=end;//后一個數(shù)組的下標(biāo)
        int index=end;//輔助數(shù)組下標(biāo)吨悍，從最后一個算起
        int count=0;
        while(i>=start && j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[index--]=data[i--];
                //統(tǒng)計長度
                count+=j-start-length;
                if(count>=1000000007)//數(shù)值過大求余
                    count%=1000000007;
            }
            else
            {
                copy[index--]=data[j--];
            }
        }
        for(;i>=start;--i)
        {
            copy[index--]=data[i];
        }
        for(;j>=start+length+1;--j)
        {
            copy[index--]=data[j];
        }
        //排序
        for(int i=start; i<=end; i++) {
            data[i] = copy[i];
        }
        //返回最終的結(jié)果
        return (count+left+right)%1000000007;
    }
};

56、數(shù)組中數(shù)字出現(xiàn)的次數(shù)

一個整型數(shù)組里除了兩個數(shù)字之外蹋嵌，其他的數(shù)字都出現(xiàn)了兩次育瓜。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度,空間復(fù)雜度.

• 解析：

61栽烂、撲克牌順子

LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張^_)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿ｕ锍稹恋脚！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”焰手。LL決定去買體育彩票啦糟描。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何， 如果牌能組成順子就輸出true书妻，否則就輸出false船响。為了方便起見,你可以認(rèn)為大小王是0

• 解析：/先計算0，然后去掉0的部分躲履，遍歷這個數(shù)組见间，看相等的時候直接返回0,不連續(xù)的時候，累加間隔大小

class Solution {
public:
    bool IsContinuous( vector<int> numbers) {
        if(numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int countZero=0,unequal=0; //計數(shù)0的個數(shù)工猜，計算不等數(shù)字的間隔
        for(int i=0;i<numbers.size() && numbers[i]==0;++i)
            countZero++;
        //先計算出0的個數(shù)米诉，這些0不在我們的規(guī)則內(nèi)；
        for(int i=countZero+1; i<numbers.size(); ++i)
        {
            if(numbers[i]==numbers[i-1])
                return false;
            if(numbers[i-1]+1 != numbers[i])
                unequal= unequal + numbers[i] - numbers[i-1] - 1;
        }
        if(unequal>countZero)
            return false;
        else
            return true;
    }
};

62域慷、約斯夫環(huán)

每年六一兒童節(jié),呕脑客都會準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為庞贪客的資深元老,自然也準(zhǔn)備了一些小游戲抵窒。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)叠骑。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到爬罨剩客名貴的“名偵探柯南”典藏版(名額有限哦!!^_)。請你試著想下,哪個小朋友會得到這份禮品呢宙枷？(注：小朋友的編號是從0到n-1)

• : 約瑟夫環(huán)兩種解法掉房，1循環(huán)鏈表，2是找規(guī)律直接算出結(jié)果慰丛；

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0) return -1;
        list<int> numbers;
        for(unsigned int i=0; i<n;++i)
            numbers.push_back(i);
        list<int>::iterator iter = numbers.begin();
        while(numbers.size()>1)
        {
            //先游走m步卓囚，這里的i=1，因為刪除第m個
            for(int i=1; i<m; ++i)
            {
                iter++;
                if(iter==numbers.end())
                    iter = numbers.begin();
            }
            //查看是否是迭代器最后一個位置
            list<int>::iterator next=++iter;
            if(next==numbers.end()) next = numbers.begin();
            --iter;
            numbers.erase(iter);
            iter = next;
        }
        return *(iter);
    }
};

66诅病、乘積數(shù)組

給定一個數(shù)組A[0,1,...,n-1],請構(gòu)建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]哪亿。不能使用除法。

• 解析：分析遞歸式如圖：
  劍指的思路：

B[i]的值可以看作下圖的矩陣中每行的乘積贤笆。

下三角用連乘可以很容求得蝇棉，上三角，從下向上也是連乘芥永。

因此我們的思路就很清晰了篡殷，先算下三角中的連乘，即我們先算出B[i]中的一部分埋涧，然后倒過來按上三角中的分布規(guī)律板辽，把另一部分也乘進(jìn)去奇瘦。

841505_1472459965615_8640A8F86FB2AB3117629E2456D8C652.jpg

//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
//從左到右算 B[i]=A[0]*A[1]*...*A[i-1]
//從右到左算B[i]*=A[i+1]*...*A[n-1]
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
     
        int n=A.size();
        vector<int> b(n);
        int ret=1;
        for(int i=0;i<n;ret*=A[i++]){
            b[i]=ret;
        }
        ret=1;
        for(int i=n-1;i>=0;ret*=A[i--]){
            b[i]*=ret;
        }
        return b;
    }
};

64、

• 利用短路原理：

class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
};

65戳气、不用加減乘除法做加法

寫一個函數(shù)链患，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+瓶您、-麻捻、*、/四則運算符號呀袱。

• 分析：考慮位運算贸毕，先相加，不進(jìn)位夜赵，對進(jìn)位的位置再做相加明棍。

class Solution {
public:
    int Add(int num1, int num2)
    {
        int sum, carry;
        do
        {
            sum = num1 ^ num2; // 異或運算：0+1、1+0都是1寇僧，其他都是0摊腋；
            carry = (num1 & num2) << 1; //與運算，只有1+1才為1嘁傀，然后左移1位兴蒸；
            num1 = sum;    // 第三部求和是一個循環(huán)過程，直到?jīng)]有進(jìn)位细办，也就是num2為0
            num2 = carry;  // 下一次循環(huán)中更新sum
        }
        while(num2!=0);
        return num1;
        
    }
};