若干數(shù)據(jù)結(jié)構(gòu)&&算法面試題【三】-創(chuàng)新互聯(lián)

這是我的第三個(gè)面試題匯總。

創(chuàng)新互聯(lián)長期為千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為東寶企業(yè)提供專業(yè)的成都做網(wǎng)站、網(wǎng)站建設(shè)，東寶網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

想看之前的內(nèi)容，請(qǐng)移步：

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

（若干數(shù)據(jù)結(jié)構(gòu) && 算法面試題【一】（更新完畢））

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

（若干數(shù)據(jù)結(jié)構(gòu) && 算法面試題【二】（更新完畢））

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

https://github.com/HonestFox/BrushQuestion

這里開始我會(huì)逐漸提高難度。

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

一直在自己的舒適區(qū)內(nèi)刷題，意義已經(jīng)不大了。

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

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

一、連續(xù)子數(shù)組的組大和

題目描述:

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

思路：

窮舉法O(N^2)

貪婪法O(N)

代碼：

//窮舉法，時(shí)間復(fù)雜度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;
	}
	//貪心法，時(shí)間復(fù)雜度為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

二、一組整數(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次,但是對(duì)于后面問題他就沒轍了。
ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)。

代碼：

 //暴力點(diǎn)的方法，窮舉法
 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;
 }
};

當(dāng)然這只是最笨的方法

貼一段最佳的實(shí)現(xiàn)方法：

編程之美上給出的規(guī)律： 101

1. 如果第i位（自右至左，從1開始標(biāo)號(hào)）上的數(shù)字為0，則第i位可能出現(xiàn)1的次數(shù)由更高位決定（若沒有高位，視高位為0），等于更高位數(shù)字X當(dāng)前位數(shù)的權(quán)重10^i-1。

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

3. 如果第i位上的數(shù)字大于1，則第i位上可能出現(xiàn)1的次數(shù)僅由更高位決定（若沒有高位，視高位為0），等于（更高位數(shù)字+1）X當(dāng)前位數(shù)的權(quán)重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

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

題目描述
輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。

代碼：

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;
 } 
 
 
 //-------------------------------------------------------------------------
 //上面的函數(shù)調(diào)用這個(gè)
 static void _FindPath(TreeNode *cur, int expectNumber, vector<vector<int> > &ret, vector<int> &vcur, int &sum)
 {
  if (cur == NULL)   //這個(gè)判斷條件一開始沒有加，?？鸵恢眻?bào)段錯(cuò)誤。。  后來才發(fā)現(xiàn)的，什么時(shí)候會(huì)出現(xiàn)這種情況呢？比如說某個(gè)節(jié)點(diǎn)，左孩子存在，右孩子為NULL的時(shí)候，如果不在這里處理這種情況，那么在下一個(gè)if語句中程序就會(huì)崩潰
  {
   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);
  //當(dāng)把當(dāng)前結(jié)點(diǎn)的左右都訪問了之后，要用sum減去當(dāng)前結(jié)點(diǎn)的值，并把當(dāng)前結(jié)點(diǎn)出棧處理
  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

四、把數(shù)組排成最小的數(shù)

題目描述:
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。
例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為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();
   //刪掉這個(gè)用過的結(jié)點(diǎn)
   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;
  }
  //走到這里，說明短的那個(gè)走完了
  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;
  }
 }
};

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

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

五、丑數(shù)

題目描述:
把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。
例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。
習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。

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

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)
  {
   //找當(dāng)前最小的 
   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

六、第一個(gè)只出現(xiàn)一次的字符位置

題目描述:
在一個(gè)字符串(1<=字符串長度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符的位置。
若為空串，返回-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

七、逆序?qū)?/p>

題目描述：
在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)。

代碼：

//最笨的方法
 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;
 } 
 
 
 //改進(jìn)，用一個(gè)輔助數(shù)組
 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;
 }
 
 
 //最佳方法：利用歸并排序的思想（轉(zhuǎn)貼的）
 //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

八、相交鏈表的第一個(gè)公共結(jié)點(diǎn)

題目描述 :
輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。

代碼：

 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

九、數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

題目描述:
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

代碼：

//普通方法
 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;
 }
 //______________________________________________________________________________________
 //______________________________________________________________________________________
 //深度優(yōu)化
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;
  //先找一個(gè)在范圍內(nèi)的點(diǎn)
  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

十、二叉樹的深度

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

思路：

非遞歸有兩種實(shí)現(xiàn)方式：

第一種（我用的）：

用棧，遇到有左右子樹的結(jié)點(diǎn)，將該結(jié)點(diǎn)入棧

第二種：

用隊(duì)列

遞歸：

在下一道題中用到

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補(bǔ)充）

這是一種方法，但其實(shí)還有種更優(yōu)的方法，還是遞歸，求每個(gè)子樹的平衡因子（即左右子樹樹高之差），如果平衡因子在 -1 ~ +1 之間，才求當(dāng)前子樹的樹高（即左右子樹樹高高的值再 + 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

十二、找出兩個(gè)只出現(xiàn)1次的數(shù)字

題目描述：
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

這里提供兩種方法，

第一種方法借助哈希實(shí)現(xiàn)，

第二種方法利用異或?qū)崿F(xiàn)，

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

代碼：

//方法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) //注意優(yōu)先級(jí)
   {
    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的連續(xù)正數(shù)序列

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

代碼：

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的兩個(gè)數(shù)字

（關(guān)于第二種優(yōu)化方法本來寫了一段分析的，結(jié)果居然沒保存。。。實(shí)在懶得重寫了，就光把兩種實(shí)現(xiàn)的代碼貼上吧）

代碼：

 //很笨的方法   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;
 }
 
 //優(yōu)化
  //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

十四、左旋轉(zhuǎn)字符串

題目描述:
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）。
現(xiàn)在有個(gè)簡單的任務(wù)，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果。
對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出。
例如，字符序列S="abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“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

十五、反轉(zhuǎn)單詞順序列

題目描述:
牛客最近來了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志，寫些句子在本子上。
同事Cat對(duì)Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。
例如，“student. a am I”。后來才意識(shí)到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”。Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么？

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今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張^_^)...他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育×××,嘿嘿??！
“紅心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的運(yùn)氣如何。為了方便起見,你可以認(rèn)為大小王是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

十七、約瑟夫環(huán)問題

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

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項(xiàng)和

題目描述:
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字及條件判斷語句（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項(xiàng)和

題目描述:
寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。

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

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

二十、把字符串轉(zhuǎn)換成整數(shù)

題目描述
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)。

代碼：

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

二十一、正則表達(dá)式的匹配

（這個(gè)寫得太糟糕了，完全是反面教材，有空我會(huì)補(bǔ)上更優(yōu)的解法）

題目描述：
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包括'.'和'*'的正則表達(dá)式。
模式中的字符'.'表示任意一個(gè)字符，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）。（要考慮一種情況 ————".*"）
在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"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

二十二、表示數(shù)值的字符串

題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。
但是"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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證，機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

名稱欄目：若干數(shù)據(jù)結(jié)構(gòu)&&算法面試題【三】-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://www.bm7419.com/article16/dcdogg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、虛擬主機(jī)、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站改版、軟件開發(fā)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容