若干数据结构 && 算法面试题【三】

发布时间：2020-07-13 09:42:46 来源：网络阅读：3334 作者：shangluyi 栏目：编程语言

这是我的第三个面试题汇总。

想看之前的内容，请移步：

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)   //这个判断条件一开始没有加，牛客一直报段错误。。  后来才发现的，什么时候会出现这种情况呢？比如说某个节点，左孩子存在，右孩子为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

向AI问一下细节

若干数据结构 && 算法面试题【三】

猜你喜欢

最新资讯

相关推荐

相关标签