若干數據結構 && 算法面試題【三】

這是我的第三個面試題匯總。

想看之前的內容，請移步：

http://zhweizhi.blog.51cto.com/10800691/1763237

（ 若干數據結構 && 算法面試題【一】（更新完畢））

http://zhweizhi.blog.51cto.com/10800691/1775780

（ 若干數據結構 && 算法面試題【二】（更新完畢））

另外，我的全部刷題代碼都在這里：

https://github.com/HonestFox/BrushQuestion

這里開始我會逐漸提高難度。

畢竟接觸并解決自己不會難題才是刷題真正的目的，

一直在自己的舒適區內刷題，意義已經不大了。

就好像寫1W行Hello world 依然學不好編程一樣。

----------------------------------------------------------------------------

一、連續子數組的組大和

題目描述:

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會后,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠??？

思路：

窮舉法O(N^2)

貪婪法O(N)

代碼：

//窮舉法，時間復雜度O(N^2)
	int FindGreatestSumOfSubArray(vector<int> array) 
	{
		if (array.size() == 0)
		{
			return 0;
		}
		int Max = array[0];
		int Sum = 0;
		for (int i = 0; i < array.size(); ++i)
		{
			Sum = 0;
			int Max1 = Max;
			for (int j = i; j < array.size(); ++j)
			{
				Sum += array[j];
				if (Sum > Max)
				{
					Max1 = Sum;
				}
			}
			if (Max1 > Max)
			{
				Max = Max1;
			}
		}
		return Max;
	}
	//貪心法，時間復雜度為O(N)
	int FindGreatestSumOfSubArray_Better(vector<int> array)
	{
		if (array.size() == 0)
		{
			return 0;
		}
		int Max = 0xffffffff;
		int Sum = 0;
		int NegMax = 0x80000000;
		for (int i = 0; i < array.size(); ++i)
		{
			Sum += array[i];
			if (Sum < 0)
			{
				Sum = 0;
			}
			if (Sum > Max)
			{
				Max = Sum;
			}
			if (NegMax < array[i])
			{
				NegMax = array[i];
			}
		}
		return Max > 0 ? Max : NegMax;
	}

github：

https://github.com/HonestFox/BrushQuestion/blob/master/31_%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%A4%A7%E5%92%8C

二、一組整數中1出現的次數

題目描述：
求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？
為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了。
ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。

 代碼：

 //暴力點的方法，窮舉法
 int NumberOf1Between1AndN_Solution(int n)
 {
  int ret = 0;
  for (int i = 1; i <= n; ++i)
  {
   ret += Get1Count(i);
  }
  return ret;
 }
protected:
 int Get1Count(int n)
 {
  int count = 0;
  while (n != 0)
  {
   if (n % 10 == 1)
   {
    ++count;
   }
   n /= 10;
  }
  return count;
 }
};

當然這只是最笨的方法

貼一段最佳的實現方法：

編程之美上給出的規律：       101

1. 如果第i位（自右至左，從1開始標號）上的數字為0，則第i位可能出現1的次數由更高位決定（若沒有高位，視高位為0），等于更高位數字X當前位數的權重10^i-1。

2. 如果第i位上的數字為1，則第i位上可能出現1的次數不僅受更高位影響，還受低位影響（若沒有低位，視低位為0），等于更高位數字X當前位數的權重10^i-1+（低位數字+1）。

3. 如果第i位上的數字大于1，則第i位上可能出現1的次數僅由更高位決定（若沒有高位，視高位為0），等于（更高位數字+1）X當前位數的權重10^i-1。

int NumberOfXBetween1AndN_Solution(int n,int x) 
{
    if(n<0||x<1||x>9)
    { 
        return 0;
    }
    int high,low,curr,tmp,i = 1;
    high = n;
    int total = 0;
    while(high!=0)
    {
        high = n/(int)Math.pow(10, i);// 獲取第i位的高位
        tmp = n%(int)Math.pow(10, i);
        curr = tmp/(int)Math.pow(10, i-1);// 獲取第i位
        low = tmp%(int)Math.pow(10, i-1);// 獲取第i位的低位
        if(curr==x)
        {
            total+= high*(int)Math.pow(10, i-1)+low+1;
        }
        else if(curr<x)
        {
            total+=high*(int)Math.pow(10, i-1);
        }
        else
        {
            total+=(high+1)*(int)Math.pow(10, i-1);
        }
        i++;
    }
    return total;       
}

 github：

https://github.com/HonestFox/BrushQuestion/blob/master/32_%E6%95%B4%E6%95%B0%E4%B8%AD1%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0

三、二叉樹和為某一值的路徑

題目描述
輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

代碼：

vector<vector<int> > FindPath(TreeNode* root, int expectNumber)
 {
  vector<vector<int> > ret;
  if (root == NULL)
  {
   return ret;
  }
  vector<int> vcur;
  TreeNode *cur = root;
  int sum = 0;
  _FindPath(cur, expectNumber, ret, vcur, sum);
  return ret;
 } 
 
 
 //-------------------------------------------------------------------------
 //上面的函數調用這個
 static void _FindPath(TreeNode *cur, int expectNumber, vector<vector<int> > &ret, vector<int> &vcur, int &sum)
 {
  if (cur == NULL)   //這個判斷條件一開始沒有加，?？鸵恢眻蠖五e誤。。  后來才發現的，什么時候會出現這種情況呢？比如說某個節點，左孩子存在，右孩子為NULL的時候，如果不在這里處理這種情況，那么在下一個if語句中程序就會崩潰
  {
   return;
  }
  if (cur->left == NULL && cur->right == NULL)
  {
   if (sum + cur->val == expectNumber)
   {
    vcur.push_back(cur->val);
    ret.push_back(vcur);
    vcur.pop_back();
   }
   return;
  }
  sum += cur->val;
  vcur.push_back(cur->val);
  _FindPath(cur->left, expectNumber, ret, vcur, sum);
  _FindPath(cur->right, expectNumber, ret, vcur, sum);
  //當把當前結點的左右都訪問了之后，要用sum減去當前結點的值，并把當前結點出棧處理
  if (!vcur.empty())
  {
   sum -= vcur.back();
   vcur.pop_back();
  }
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/33_%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84

 四、把數組排成最小的數

 題目描述:
輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。
例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為321323。

code:

class Solution 
{
public:
 string PrintMinNumber(vector<int> numbers) 
 {
  string RetString;
  while (!numbers.empty())
  {
   int index = GetMinIndex(numbers);
   char *tmpstr = new char[200];
   unique_ptr<char> c1(_itoa(numbers[index], tmpstr, 10));
   RetString += c1.get();
   //刪掉這個用過的結點
   swap(numbers[index], numbers[numbers.size() - 1]);
   numbers.pop_back();
  }
  return RetString;
 }
protected:
 int GetMinIndex(vector<int> &numbers)
 {
  int RetIndex = 0;
  int Min = numbers[0];
  for (int i = 0; i < numbers.size(); ++i)
  {
   if (_IsPrevMin(numbers[i], Min))
   {
    Min = numbers[i];
    RetIndex = i;
   }
  }
  return RetIndex;
 }
protected:
 bool _IsPrevMin(int num1, int num2)
 {
  if (num1 == num2)
  {
   return true;
  }
  char *tmp1 = new char[200];
  char *tmp2 = new char[200];
  unique_ptr<char> c1(_itoa(num1, tmp1, 10));
  unique_ptr<char> c2(_itoa(num2, tmp2, 10));
  int Index = 0;
  while (c1.get()[Index] != '\0' && c2.get()[Index] != '\0')
  {
   if (c1.get()[Index] < c2.get()[Index])
   {
    return true;
   }
   else if (c1.get()[Index] > c2.get()[Index])
   {
    return false;
   }
   ++Index;
  }
  //走到這里，說明短的那個走完了
  char *Long = c1.get();
  char EndPos = c1.get()[Index - 1];
  bool ISLeftShort = false;
  if (c1.get()[Index] == '\0')
  {
   EndPos = c2.get()[Index - 1];
   Long = c2.get();
   ISLeftShort = true;
  }
  
  if (*(Long + Index) <= EndPos)
  {
   if (ISLeftShort)
   {
    return false;
   }
   return true;
  }
  else
  {
   if (ISLeftShort)
   {
    return true;
   }
   return false;
  }
 }
};

（寫的時候忘記了有to_string(), 整型轉字符直接用指針，然后為了保證內存不泄漏，又用了智能指針，這樣其實麻煩了很多）

github：

https://github.com/HonestFox/BrushQuestion/blob/master/34_%E6%8A%8A%E6%95%B0%E7%BB%84%E6%8E%92%E6%88%90%E6%9C%80%E5%B0%8F%E7%9A%84%E6%95%B0

五、丑數

題目描述:
把只包含因子2、3和5的數稱作丑數（Ugly Number）。
例如6、8都是丑數，但14不是，因為它包含因子7。
習慣上我們把1當做是第一個丑數。求按從小到大的順序的第N個丑數。

代碼：(這是最笨的方法)

int GetUglyNumber_Solution(int index)
 {
  if (index < 1)
  {
   return -1;
  }
  int count = 1;
  int ret = 1;
  vector<int> ValBox;
  ValBox.push_back(2);
  ValBox.push_back(3);
  ValBox.push_back(5);
  while (count < index)
  {
   //找當前最小的 
   int MinIndex = _GetMinIndex(ValBox);
   ret = ValBox[MinIndex];
   swap(ValBox[MinIndex], ValBox[ValBox.size() - 1]);
   ValBox.pop_back();
   ++count;
   if (!_IsRepeat(ValBox, 2 * ret))
   {
    ValBox.push_back(2 * ret);
   }
   if (!_IsRepeat(ValBox, 3 * ret))
   {
    ValBox.push_back(3 * ret);
   } if (!_IsRepeat(ValBox, 5 * ret))
   {
    ValBox.push_back(5 * ret);
   }
  }
  return ret;
 } 
 int _GetMinIndex(const vector<int> &ValBox)
 {
  int Min = ValBox[0];
  int Index = 0;
  for (int i = 0; i < ValBox.size(); ++i)
  {
   if (ValBox[i] < Min)
   {
    Min = ValBox[i];
    Index = i;
   }
  }
  return Index;
 }
 bool _IsRepeat(const vector<int> &ValBox, int val)
 {
  for (auto &i : ValBox)
  {
   if (i == val)
   {
    return true;
   }
  }
  return false;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/35_%E4%B8%91%E6%95%B0%EF%BC%88%E9%87%8D%E5%86%99%EF%BC%89

六、第一個只出現一次的字符位置

題目描述:
在一個字符串(1<=字符串長度<=10000，全部由字母組成)中找到第一個只出現一次的字符的位置。
若為空串，返回-1。位置索引從0開始

代碼：

 int FirstNotRepeatingChar(string str) 
 {
  int list[256] = { 0 };
  if (str.size() == 0)
  {
   return -1;
  }
  for (size_t i = 0; i < str.size(); ++i)
  {
   ++list[str[i]];
  }
  for (size_t i = 0; i < str.size(); ++i)
  {
   if (list[str[i]] == 1)
   {
    return i;
   }
  }
  return -1;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/36_%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E5%AD%97%E7%AC%A6%E4%BD%8D%E7%BD%AE

 七、逆序對

題目描述：
在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。

代碼：

//最笨的方法
 int InversePairsFool(vector<int> data)
 {
  int RetCount = 0;
  for (int i = 0; i < data.size(); ++i)
  {
   for (int j = 0; j < i; j++)
   {
    if (data[j] > data[i])
    {
     ++RetCount;
    }
   }
  }
  return RetCount;
 } 
 
 
 //改進，用一個輔助數組
 int InversePairs(vector<int> data)
 {
  int RetCount = 0;
  if (data.empty())
  {
   return RetCount;
  }
  vector<int> UsedVal;
  for (int i = 0; i < data.size(); ++i)
  {
   int tmp = data[i];
   int usize = UsedVal.size() - 1;
   if (UsedVal.empty())
   {
    UsedVal.push_back(tmp);
    continue;
   }
   UsedVal.push_back(tmp);
   ++usize;
   while (usize >= 1 && UsedVal[usize] < UsedVal[usize - 1])
   {
    swap(UsedVal[usize], UsedVal[usize - 1]);
    ++RetCount;
    --usize;
   }
  }
  return RetCount;
 }
 
 
 //最佳方法：利用歸并排序的思想（轉貼的）
 //c++歸并排序版本
class Solution {
public:
    int InversePairs(vector<int> data)
    {
        int len = data.size();
        if(len<2)
            return 0;
        vector<int> p(data.begin(),data.end());
        return mergesort(data,0,len-1,p);
    }
 
    int mergesort(vector<int> &array,int begin,int end,vector<int> &temp)
    {
        int count = 0;
        if(begin <end)
        {
            int mid = (begin + end)/2; 
 
            count += mergesort(array,begin,mid,temp);
            count += mergesort(array,mid+1,end,temp);
            count += MergeArray(array,begin,mid,end,temp);
        }
        return count;
    }
 
    int MergeArray(vector<int> &a,int begin,int mid,int end,vector<int> &temp)
    {
        int i = begin;
        int j = mid+1;
        int index = begin;
        int count = 0;
        while(i<=mid && j<=end)
        {
            if(a[i]<=a[j]) 
            {
                temp[index++] = a[i++];
            }
            else
            {
                temp[index++] = a[j++];
                count += mid - i + 1;
            }
 
        }
 
        while(i<=mid) temp[index++] = a[i++];
        while(j<=end) temp[index++] = a[j++];
 
        for(i=begin;i<=end;i++)
            a[i] = temp[i];
        return count;
    }
};

github：

https://github.com/HonestFox/BrushQuestion/blob/master/37_%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9 

八、相交鏈表的第一個公共結點

題目描述 :
輸入兩個鏈表，找出它們的第一個公共結點。

代碼：

 ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2)
 {
  if (pHead1 == NULL || pHead2 == NULL)
  {
   return NULL;
  }
  int length2 = 0;
  int length3 = 0;
  ListNode *cur = pHead1;
  while (cur)
  {
   cur = cur->next;
   ++length2;
  }
  cur = pHead2;
  while (cur)
  {
   cur = cur->next;
   ++length3;
  }
  int gap = length2 - length3;
  ListNode *LongList = pHead1;
  ListNode *ShortList = pHead2;
  if (gap < 0)
  {
   LongList = pHead2;
   ShortList = pHead1;
  }
  while (gap--)
  {
   LongList = LongList->next;
  }
  while (LongList != ShortList)
  {
   LongList = LongList->next;
   ShortList = ShortList->next;
  }
  return LongList;
 }
 ListNode* FindFirstCommonNode_2(ListNode *pHead1, ListNode *pHead2)
 {
  ListNode *p1 = pHead1;
  ListNode *p2 = pHead2;
  while (p1 != p2) {
   p1 = (p1 == NULL ? pHead2 : p1->next);
   p2 = (p2 == NULL ? pHead1 : p2->next);
  }
  return p1;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/38_%E4%B8%A4%E4%B8%AA%E7%9B%B8%E4%BA%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%85%AC%E5%85%B1%E7%BB%93%E7%82%B9

九、數字在排序數組中出現的次數

題目描述:
統計一個數字在排序數組中出現的次數。

代碼：

//普通方法
 int GetNumberOfK_Normal(vector<int> data, int k) 
 {
  if (data.empty())
  {
   return 0;
  }
  int RetCount = 0;
  for (auto &i : data)
  {
   if (i == k)
   {
    ++RetCount;
   }
   if (RetCount != 0 && i != k)
   {
    break;
   }
  }
  return RetCount;
 }
 //______________________________________________________________________________________
 //______________________________________________________________________________________
 //深度優化
public:
 int GetNumberOfK_Improve(const vector<int> &data, int k)
 {
  if (data.empty())
  {
   return 0;
  }
  int RightIndex = data.size() - 1;
  int LeftIndex = 0;
  int RetCount = 0;
  //先找一個在范圍內的點
  int MidAroundIndex = FindIndex(data, LeftIndex, RightIndex, k);
  //如果沒有找到，返回0
  if (MidAroundIndex == -1)
  {
   return 0;
  }
  while (LeftIndex < MidAroundIndex && data[LeftIndex] <= data[MidAroundIndex])
  {
   int tmp = LeftIndex;
   if (data[LeftIndex] < data[MidAroundIndex])
   {
    LeftIndex = FindIndex(data, LeftIndex, MidAroundIndex, k);
   }
   else
   {
    LeftIndex = FindIndex(data, 0, LeftIndex, k);
   }
   if (tmp == LeftIndex)
   {
    break;
   }
  }
  int LeftEdge = LeftIndex;
  while (RightIndex > MidAroundIndex && data[RightIndex] >= data[MidAroundIndex])
  {
   int tmp = RightIndex;
   if (data[RightIndex] > data[MidAroundIndex])
   {
    RightIndex = FindIndex(data, MidAroundIndex, RightIndex, k);
   }
   else
   {
    RightIndex = FindIndex(data, RightIndex, data.size() - 1, k);
   }
   if (tmp == RightIndex)
   {
    break;
   }
  }
  int RightEdge = RightIndex;
  RetCount = RightEdge - LeftEdge + 1;
  return RetCount;
 }
 
 
 int FindIndex(const vector<int> &data, int left, int right, int aim)  //[ ]
 {
  if (left == right)
  {
   return data[left] == aim ? left : -1;
  }
  int mid = (left - right) / 2 + right - 1;
  while (left <= right)
  {
   if (data[mid] == aim)
   {
    return mid;
   }
   else if (data[mid] < aim)
   {
    left = mid + 1;
    mid = (mid - right) / 2 + right;
   }
   else if (data[mid] > aim)
   {
    right = mid - 1;
    mid = (mid - left) / 2 + left;
   }
  }
  if (data[mid] != aim)
  {
   return -1;
  }
  return mid;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/39_%E6%95%B0%E5%AD%97%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0

十、二叉樹的深度

題目描述:
輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

思路：

非遞歸有兩種實現方式：

    第一種（我用的）：

        用棧，遇到有左右子樹的結點，將該結點入棧

    第二種：

        用隊列

遞歸：

    在下一道題中用到

github:

https://github.com/HonestFox/BrushQuestion/blob/master/40_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6

十一、判斷一棵樹是否為平衡二叉樹

題目描述:
輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

（7.3補充）

這是一種方法，但其實還有種更優的方法，還是遞歸，求每個子樹的平衡因子（即左右子樹樹高之差），如果平衡因子在 -1 ~ +1 之間，才求當前子樹的樹高（即左右子樹樹高高的值再 + 1），依此類推

代碼：

class Solution
{
public:
 bool IsBalanced_Solution(TreeNode* pRoot)
 {
  if (pRoot == NULL)
  {
   return true;
  }
  TreeNode *cur = pRoot;
  int left = Height(cur->left);
  int right = Height(cur->right);
  if (right - left < -1 || right - left > 1)
  {
   return false;
  }
  return (IsBalanced_Solution(cur->left) && IsBalanced_Solution(cur->right));
 }
 int Height(TreeNode *pRoot)
 {
  return _Height(pRoot);
 }
protected:
 int _Height(TreeNode *pRoot)
 {
  if(pRoot == NULL)
  {
   return 0;
  }
  if (pRoot->left == 0 && pRoot->right == 0)
  {
   return 1;
  }
  int LeftHeight = _Height(pRoot->left);
  int RightHeight = _Height(pRoot->right);
  return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
 }
};

github:

https://github.com/HonestFox/BrushQuestion/blob/master/41_%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E4%B8%BA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91

十二、找出兩個只出現1次的數字

題目描述：
一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。

這里提供兩種方法，

第一種方法借助哈希實現，

第二種方法利用異或實現，

我覺得這兩種方法的復雜度都差不多

 代碼：

//方法1：用哈希
 void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) 
 {
  vector<int> hash;
  int max = data[0];
  int min = data[0];
  int sz = data.size();
  for (int i = 0; i < sz; ++i)
  {
   if (max < data[i])
   {
    max = data[i];
   }
   if (min > data[i])
   {
    min = data[i];
   }
  }
  int HashSize = max - min + 1;
  hash.resize(HashSize);
  for (int i = 0; i < sz; ++i)
  {
   ++hash[data[i] - min];
  }
  for (int i = 0; i < HashSize; ++i)
  {
   if (hash[i] == 1)
   {
    if (!*num1)
    {
     *num1 = i + min;
    }
    else
    {
     *num2 = i + min;
     return;
    }
   }
  }
  *num2 = 0;
 }
 //方法2 用異或
 void FindNumsAppearOnce_2(vector<int> data, int *num1, int *num2)
 {
  if (data.size() < 2)
  {
   return;
  }
  int val = data[0];
  for (int i = 1; i < data.size(); ++i)
  {
   val ^= data[i];
  }
  int count = 0;
  int num = 1;
  while ((val & num) == 0)
  {
   num <<= 1;
   ++count;
  }
  int pos = 1;
  while (count--)
  {
   pos <<= 1;
  }
  vector<int> v1;
  vector<int> v2;
  for (int &i : data)
  {
   if ((i & pos) == 0) //注意優先級
   {
    v1.push_back(i);
   }
   else
   {
    v2.push_back(i);
   }
  }
  //再分別找
  int val1 = v1[0];
  int val2 = v2[0];
  for (int i = 1; i < v1.size(); ++i)
  {
   val1 ^= v1[i];
  }
  *num1 = val1;
  for (int i = 1; i < v2.size(); ++i)
  {
   val2 ^= v2[i];
  }
  *num2 = val2;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/42_%E6%89%BE%E5%87%BA%E8%BF%99%E4%B8%A4%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0%E5%AD%97 

十三、和為S的連續正數序列

題目描述:
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。
但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。
沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。
現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列?
輸出描述:
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序

代碼：

vector<vector<int> > FindContinuousSequence(int sum)
 {
  vector<vector<int> > ret;
  for (int i = 2; ( (sum / i) - (i / 2) ) >= 0; ++i)
  {
   vector<int> tmp;
   int index = 0;
   int begin = sum / i - i / 2;
   if (i % 2 == 0)
   {
    ++begin;
   }
   
   if (begin <= 0)
   {
    continue;
   }
   //排除幾種情況
   if (sum % 2 == 0)
   {
    if (i % 2 != 0 && sum % i != 0)
    {
     continue;
    }
    else if (i % 2 == 0 && (begin + begin + i - 1) * i / 2 != sum)
    {
     continue;
    }
   }
   else if (sum % 2 != 0 && i != 2)
   {
    if (i % 2 == 0)
    {
     continue;
    }
    else if (sum % i != 0)
    {
     continue;
    }
   }
   while (index < i)
   {
    int CurVal = begin;
    CurVal += index;
    tmp.push_back(CurVal);
    index++;
   }
   ret.push_back(tmp);
  }
  return ret;
 }

github:

https://github.com/HonestFox/BrushQuestion/blob/master/43_%E5%92%8C%E4%B8%BAS%E7%9A%84%E8%BF%9E%E7%BB%AD%E6%AD%A3%E6%95%B0%E5%BA%8F%E5%88%97

十四、和為S的兩個數字

（關于第二種優化方法本來寫了一段分析的，結果居然沒保存。。。 實在懶得重寫了，就光把兩種實現的代碼貼上吧）

代碼：

 //很笨的方法   O(N)
 vector<int> FindNumbersWithSum(vector<int> array, int sum)
 {
  vector<int> ret;
  if (array.empty())
  {
   return ret;
  }
  for (size_t i = 0; i < array.size(); ++i)
  {
   if (array[i] >= sum)
   {
    break;
   }
   int val1 = array[i];
   for (size_t j = i; j < array.size(); ++j)
   {
    if (array[j] >= sum)
    {
     break;
    }
    int val2 = array[j];
    if (val1 + val2 == sum)
    {
     ret.push_back(val1);
     ret.push_back(val2);
     return ret;
    }
   }
  }
  return ret;
 }
 
 //優化
  //O(N)
 vector<int> FindNumbersWithSumImprove(vector<int> array, int sum)   
 {
  vector<int> ret;
  int begin = 0;
  int end = array.size() - 1;
  while (begin < end)
  {
   if (array[begin] * array[end] == sum)
   {
    ret.push_back(array[begin]);
    ret.push_back(array[end]);
    break;
   }
   while (array[begin] * array[end] < sum)
   {
    ++begin;
   }
   while (array[begin] * array[end] > sum)
   {
    --end;
   }
  }
  return ret;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/44_%E5%92%8C%E4%B8%BAS%E7%9A%84%E4%B8%A4%E4%B8%AA%E6%95%B0%E5%AD%97

十四、左旋轉字符串

題目描述:
匯編語言中有一種移位指令叫做循環左移（ROL）。
現在有個簡單的任務，就是用字符串模擬這個指令的運算結果。
對于一個給定的字符序列S，請你把其循環左移K位后的序列輸出。
例如，字符序列S="abcXYZdef”,要求輸出循環左移3位后的結果，即“XYZdefabc”。是不是很簡單？OK，搞定它！

github：

https://github.com/HonestFox/BrushQuestion/blob/master/45_%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2 

十五、反轉單詞順序列

題目描述:
?？妥罱鼇砹艘粋€新員工Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。
同事Cat對Fish寫的內容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。
例如，“student. a am I”。后來才意識到，這家伙原來把句子單詞的順序翻轉了，正確的句子應該是“I am a student.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他么？

github:

https://github.com/HonestFox/BrushQuestion/blob/master/46_%E5%8F%8D%E8%BD%AC%E5%8D%95%E8%AF%8D%E9%A1%BA%E5%BA%8F%E5%88%97

十六、撲克牌順子

題目描述:
LL今天心情特別好,因為他去買了一副撲克牌,發現里面居然有2個大王,2個小王(一副牌原本是54張^_^)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育×××,嘿嘿??！
“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育×××啦。 現在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何。為了方便起見,你可以認為大小王是0

github：

https://github.com/HonestFox/BrushQuestion/blob/master/47_%E6%89%91%E5%85%8B%E7%89%8C%E9%A1%BA%E5%AD%90

十七、約瑟夫環問題

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

github:

https://github.com/HonestFox/BrushQuestion/blob/master/48_%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E9%97%AE%E9%A2%98

十八、特定條件下求前n項和

題目描述:
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。

github:

https://github.com/HonestFox/BrushQuestion/blob/master/49_%E7%89%B9%E5%AE%9A%E6%9D%A1%E4%BB%B6%E4%B8%8B%E6%B1%82%E5%89%8Dn%E9%A1%B9%E5%92%8C

十九、特定條件下求前n項和

題目描述:
寫一個函數，求兩個整數之和，要求在函數體內不得使用+、-、*、/四則運算符號。

int Add(int num1, int num2)   
 {
  if (num1 == 0)
  {
   return num2;
  }
  return Add((num1 & num2) << 1, (num1 ^ num2) );
 }

github: 

https://github.com/HonestFox/BrushQuestion/blob/master/50_%E4%B8%8D%E7%94%A8%E5%9B%9B%E5%88%99%E8%BF%90%E7%AE%97%E6%B1%82%E5%8A%A0%E6%B3%95

(這個還挺有意思的，有時間的話我要仔細描述一下，最近實在太忙了)

二十、把字符串轉換成整數

題目描述
將一個字符串轉換成一個整數，要求不能使用字符串轉換整數的庫函數。

代碼：

int StrToInt(string str) 
 {
  int ret = 0;
  int cur = 0;
  int sz = str.size();
  bool IsNeg = false;
  if (str[0] == '+')
  {
   ++cur;
  }
  else if (str[0] == '-')
  {
   IsNeg = true;
   ++cur;
  }
  while (cur < sz )
  {
   if (str[cur] < '0' || str[cur] > '9')
   {
    return 0;
   }
   ret = ret * 10 + ( str[cur++] - '0');
  }
  if (IsNeg)
  {
   ret *= -1;
  }
  return ret;
 }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/51_%E6%8A%8A%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%BD%AC%E6%8D%A2%E6%88%90%E6%AD%A3%E6%95%B0

 二十一、正則表達式的匹配

（這個寫得太糟糕了，完全是反面教材，有空我會補上更優的解法）

 題目描述：
請實現一個函數用來匹配包括'.'和'*'的正則表達式。
模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）。    （要考慮一種情況 ————".*"）
在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配

github：

https://github.com/HonestFox/BrushQuestion/blob/master/53_%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D 

 二十二、表示數值的字符串

題目描述
請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。
但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

github:https://github.com/HonestFox/BrushQuestion/blob/master/54_%E8%A1%A8%E7%A4%BA%E6%95%B0%E5%80%BC%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2