剑指offer题目及答案
剑指offer
最近在牛客网上刷剑指offer的题目，现将题目和答案总结如下：
1. 二维数组的查找
2. 替换空格
3. 从尾到头打印链表
4. 重建二叉树
5. 用两个栈实现队列
6. 旋转数组的最小数字
7. 斐波那契数列
8. 跳台阶
9. 变态跳台阶
10. 矩阵覆盖
11. 二进制中1的位数
12. 数值的整数次方
13. 调整数组顺序使奇数位于偶数前面
14. 链表中倒数第k个结点
15. 反转链表
16. 合并两个排序的链表
17. 树的子结构
18. 二叉树的镜像
19. 顺时针打印矩阵
20. 包含min函数的栈
21. 栈的压入、弹出序列
22. 从上往下打印二叉树
23. 二叉搜索树的后序遍历序列
24. 二叉树中和为某一值的路径
25. 复杂链表的复制
26. 二叉搜索树与双向链表
27. 字符串的排列
28. 数组中出现次数超过一半的数字
29. 最小的K个数
30. 连续子数组的最大和
31. 整数中1出现的次数（从1到n整数中1出现的次数）
32. 把数组排成最小的数
33. 丑数
34. 第一个只出现一次的字符
35. 数组中的逆序对
36. 两个链表的第一个公共结点
37. 数字在排序数组中出现的次数
38. 二叉树的深度
39. 平衡二叉树
40. 数组中只出现一次的数字
41. 和为S的连续正数序列
42. 和为S的两个数字
43. 左旋转字符串
44. 翻转单词顺序列
45. 扑克牌顺子
46. 孩子们的游戏(圆圈中最后剩下的数)
47. 求1+2+3+…+n
48. 不用加减乘除做加法
49. 把字符串转换成整数
50. 数组中重复的数字
51. 构建乘积数组
52. 正则表达式匹配
53. 表示数值的字符串
54. 字符流中第一个不重复的字符
55. 链表中环的入口结点
56. 删除链表中重复的结点
57. 二叉树的下一个结点
58. 对称的二叉树
59. 按之字形顺序打印二叉树
60. 把二叉树打印成多行
61. 序列化二叉树
62. 二叉搜索树的第k个结点
63. 数据流中的中位数
64. 滑动窗口的最大值
65. 矩阵中的路径
66. 机器人的运动范围
1. 二维数组的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
/* 思路： 依次比较右上角的数字；如果该数字大于要查找的数字，则剔除列；如果该数字大于要查找的数字，则剔除行；
复杂度：O(m+n), 行数m，列数n */
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
bool found=false;
if (array.empty())
return found;
int rows, columns, row, column;
rows = array.size();
columns = array[0].size();
row = 0;
column = columns - 1;
while(row < rows && column >= 0)
{
if(array[row][column] == target)
{
found = true;
break;
}
else if (array[row][column] > target)
-- column;
else
++ row;
}
return found;
}
};2. 替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
/* 思路：首先计算原字符串长度，空格个数；然后计算替换之后的长度；设置两个指针分别指向原，新字符串的尾部，逐个赋值；
复杂度：O(n) */
class Solution {
public:
void replaceSpace(char *str,int length) {
if(str == nullptr || length <=0)
return;
int original_length = 0;
int number_of_space = 0;
int i = 0;
while(str[i] != " ")
{
++ original_length;
if(str[i] == " ")
++ number_of_space;
++ i;
}
if (number_of_space <= 0)
return;
int new_length = original_length + 2*number_of_space;
int index_of_original = original_length;
int index_of_new = new_length;
while(index_of_original>=0 && index_of_new>=index_of_original)
{
if(str[index_of_original] == " ")
{
str[index_of_new--] = "0";
str[index_of_new--] = "2";
str[index_of_new--] = "%";
}
else
{
str[index_of_new--] = str[index_of_original];
}
-- index_of_original;
}
}
};3. 从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
// 思路：借助辅助栈，或者使用递归；
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> reverse_list;
stack<int> nodes;
ListNode *p_node = head;
while(p_node != nullptr)
{
nodes.push(p_node->val);
p_node = p_node->next;
}
int tempVal;
while(!nodes.empty())
{
tempVal = nodes.top();
reverse_list.push_back(tempVal);
nodes.pop();
}
return reverse_list;
}
};4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/* 思路（递归）：根据前序遍历的第一个数字创建根节点；在中序便利找到根节点的位置；确定左右子树节点数量；递归构建左右子树；*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || vin.empty() || pre.size()!=vin.size())
return nullptr;
vector<int> left_pre, right_pre, left_vin, right_vin;
TreeNode *node = new TreeNode(pre[0]);
int left_length = 0;
while(pre[0]!=vin[left_length] && left_length < pre.size())
++ left_length;
for(int i=0; i<left_length; i++)
{
left_pre.push_back(pre[i+1]);
left_vin.push_back(vin[i]);
}
for(int i=left_length+1; i<pre.size(); i++)
{
right_pre.push_back(pre[i]);
right_vin.push_back(vin[i]);
}
node->left = reConstructBinaryTree(left_pre, left_vin);
node->right = reConstructBinaryTree(right_pre, right_vin);
return node;
}
};5.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
/*思路：stack1:负责压栈，stack2负责弹栈（如果为空，则将stack1中元素压入stack2）；*/
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty())
{
while(!stack1.empty())
{
int val = stack1.top();
stack1.pop();
stack2.push(val);
}
}
int val = stack2.top();
stack2.pop();
return val;
}
private:
stack<int> stack1;
stack<int> stack2;
};6. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
/*简单方法*/
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray)
{ //数组为空时
if(rotateArray.size() == 0)
return -1;
//前部分数据旋转
for(int i = 0; i < rotateArray.size() - 1; i++)
{
if (rotateArray[i] > rotateArray[i + 1])
return rotateArray[i + 1];
}
//全部数据旋转，相当于没有旋转，最小数即为第一个数
return rotateArray[0];
}
};
/*思路：二分查找思想*/
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int length = rotateArray.size();
if (length == 0)
return 0;
int left = 0, right = length-1;
int mid;
while(rotateArray[left] >= rotateArray[right])
{
if(left == right - 1)
return rotateArray[right];
mid = (left + right)/2;
if(rotateArray[left] == rotateArray[mid] &&
rotateArray[mid] == rotateArray[right])
{
int min_num = rotateArray[left];
for(int i=left; i < right; i++)
min_num = rotateArray[i]<min_num? rotateArray[i]:min_num;
return min_num;
}
if(rotateArray[left] <= rotateArray[mid])
left = mid;
else
right = mid;
}
return rotateArray[left];
}
};7.斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
/* 思路： 循环，保存中间结果（递归的话，重复计算太多）*/
class Solution {
public:
int Fibonacci(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
int fib1=1, fib2=0;
int fibn;
for(int i=2; i<=n; i++)
{
fibn = fib1+fib2;
fib2 = fib1;
fib1 = fibn;
}
return fibn;
}
};8. 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
class Solution {
public:
int jumpFloor(int number) {
if(number == 1)
return 1;
int pre1=1, pre2=1;
int cur;
for(int i=2; i<=number; i++)
{
cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return cur;
}
};9.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
思路：其实是隔板问题，假设n个台阶，有n-1个空隙，可以用0~n-1个隔板分割，c(n-1,0)+c(n-1,1)+...+c(n-1,n-1)=2^(n-1)，其中c表示组合。 有人用移位1<<--number，这是最快的。
class Solution {
public:
int jumpFloorII(int number) {
int jump_number = 1;
for(int i=0; i<number-1; i++)
jump_number = jump_number * 2;
return jump_number;
}
};
/**********更加简单的方法**********/
class Solution {
public:
int jumpFloorII(int number) {
return 1<<(--number);
}
};
10. 矩阵覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
/* 思路：
第一块有两种方式：横着放和竖着放
横这放对应为发f(n-2);
竖着放下一步的放方法为f(n-1);
所以总的放的方法为f(n)=f(n-1)+f(n-2);
*/
class Solution {
public:
int rectCover(int number) {
if(number <= 2)
return number;
int pre1 = 2, pre2 = 1;
int cur;
for(int i=2; i<number; i++)
{
cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return cur;
}
};11. 二进制中1的位数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
/************ 简单方法 ************/
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(n & flag)
++ count;
flag = flag << 1;
}
return count;
}
};
/******* 巧妙方法 *******/
思路：一个整数减去1，在与原整数做与运算，会将最右边的一个1变成0.
那么二进制中有多少个1，可进行这样的操作多少次；
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n)
{
++ count;
n = (n-1)&n;
}
return count;
}
};
12. 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
/*思路 需要考虑以下几种情况
1) base的正负；
2) base是否等于0；
3) exponent的正负；
4) exponent是否为1；*/
class Solution {
public:
double Power(double base, int exponent) {
if (base>-0.0000001 && base<0.0000001 && exponent<0)
return 0.0;
double result = 1.0;
unsigned int abs_exponent = (unsigned int) exponent;
if(exponent < 0)
abs_exponent = (unsigned int) (-exponent);
/*
for(int i=0; i<abs_exponent; i++)
result = result * base;
*/
//
if(abs_exponent == 0)
return 1.0;
if(abs_exponent == 1)
return base;
result = base;
abs_exponent = abs_exponent >> 1;
while(abs_exponent)
{
result *= result;
abs_exponent = abs_exponent >> 1;
}
if(exponent & 0x1 == 1)
result *= base;
//
if(exponent < 0 && result > 0.0)
result = 1.0 / result;
return result;
}
};13. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
注：相比剑指offer书要难（要保证相对顺序不变）
class Solution {
public:
void reOrderArray(vector<int> &array) {
int length = array.size();
if(length==0 || length==1)
return;
int index_even=0, index_odd;
while(index_even<length)
{
while(index_even<length && !isEven(array[index_even]))
++ index_even;
index_odd = index_even+1;
while(index_odd<length && isEven(array[index_odd]))
++ index_odd;
if(index_odd<length)
{
int temp = array[index_odd];
for(int i=index_odd; i>index_even; i--)
array[i] = array[i-1];
array[index_even] = temp;
}
else
break;
}
}
bool isEven(int number){
if((number & 0x1) == 0)
return true;
return false;
}
};
/*************方法二 申请空间***********/
class Solution {
public:
void reOrderArray(vector<int> &array) {
int length = array.size();
if(length==0 || length ==1)
return;
vector<int> res;
for(int i=0; i<length; i++)
{
if((array[i]&0x1) != 0)
res.push_back(array[i]);
}
for(int i=0; i<length; i++)
{
if((array[i]&0x1) == 0)
res.push_back(array[i]);
}
array = res;
}
};14. 链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
// 定义快慢指针，快的先走K步；
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead == nullptr || k==0)
return nullptr;
ListNode *pAhead = pListHead;
ListNode *pAfter = pListHead;
for(int i=0; i<k-1; i++)
{
if(pAhead->next != nullptr)
pAhead = pAhead->next;
else
return nullptr;
}
while(pAhead->next != nullptr)
{
pAhead = pAhead->next;
pAfter = pAfter->next;
}
return pAfter;
}
};15. 反转链表
输入一个链表，反转链表后，输出链表的所有元素。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
/* 思路：定义三个指针，分别指向当前结点，前一个结点，后一个结点 */
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == nullptr)
return nullptr;
if(pHead->next == nullptr)
return pHead;
ListNode *pPreNode=pHead, *pCurNode=pHead->next, *pNextNode;
pPreNode->next = nullptr;
while(pCurNode->next != nullptr)
{
pNextNode = pCurNode->next;
pCurNode->next = pPreNode;
pPreNode = pCurNode;
pCurNode = pNextNode;
}
pCurNode->next = pPreNode;
return pCurNode;
}
};16.合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
/*------------------------------方法一 递归版本--------------------------*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == nullptr)
return pHead2;
else if(pHead2 == nullptr)
return pHead1;
ListNode *pMerge;
if(pHead1->val <= pHead2->val)
{
pMerge = pHead1;
pHead1->next = Merge(pHead1->next, pHead2);
}
else
{
pMerge = pHead2;
pHead2->next = Merge(pHead1, pHead2->next);
}
return pMerge;
}
};
17. 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/*分两步，判断根节点是否相等；判断子结构是否相等*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool result = false;
if(pRoot1!=nullptr && pRoot2!=nullptr)
{
if(pRoot1->val == pRoot2->val)
result = DoesTree1HaveTree2(pRoot1, pRoot2);
if(!result)
result = HasSubtree(pRoot1->left, pRoot2);
if(!result)
result = HasSubtree(pRoot1->right, pRoot2);
}
return result;
}
bool DoesTree1HaveTree2(TreeNode *Tree1, TreeNode *Tree2)
{
if(Tree2 == nullptr)
return true;
if(Tree1 == nullptr)
return false;
if(Tree1->val != Tree2->val)
return false;
return DoesTree1HaveTree2(Tree1->left, Tree2->left) &&
DoesTree1HaveTree2(Tree1->right, Tree2->right);
}
};18. 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/* 思路：相当于树的遍历 */
/*-------------- 递归方法 ------------*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == nullptr || (pRoot->left==nullptr && pRoot->right==nullptr))
return;
if(pRoot->left != nullptr)
Mirror(pRoot->left);
if(pRoot->right != nullptr)
Mirror(pRoot->right);
TreeNode *temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;
}
};
/*------------- 使用栈 ------------------*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == nullptr || (pRoot->left==nullptr && pRoot->right==nullptr))
return;
stack<TreeNode*> stackNodes;
stackNodes.push(pRoot);
while(stackNodes.size() > 0)
{
TreeNode *pNode = stackNodes.top();
stackNodes.pop();
TreeNode *pTemp = pNode->left;
pNode->left = pNode->right;
pNode->right = pTemp;
if(pNode->left != nullptr)
stackNodes.push(pNode->left);
if(pNode->right != nullptr)
stackNodes.push(pNode->right);
}
}
};19. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
int rows, columns;
if(matrix.size()>0)
{
rows = matrix.size();
columns = matrix[0].size();
}
vector<int> result;
int startX = 0, endX = columns-1;
int startY = 0, endY = rows-1;
while(startX <= endX && startY<=endY)
{
if(startX<=endX && startY<=endY)
{
for(int i=startX; i<=endX; i++)
result.push_back(matrix[startY][i]);
++ startY;
}
if(startY<=endY && startX<=endX)
{
for(int i=startY; i<=endY; i++)
result.push_back(matrix[i][endX]);
-- endX;
}
if(startX<=endX && startY<=endY)
{
for(int i=endX; i>=startX; i--)
result.push_back(matrix[endY][i]);
-- endY;
}
if(startY<=endY && startX<=endX)
{
for(int i=endY; i>=startY; i--)
result.push_back(matrix[i][startX]);
++ startX;
}
}
return result;
}
};20. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
/* 借助辅助栈，保存每次压栈之后的最小值 */
class Solution {
public:
void push(int value) {
if(s_data.empty()){
s_data.push(value);
s_min.push(value);
}
else{
s_min.push(value<s_min.top()?value:s_min.top());
s_data.push(value);
}s
}
void pop() {
s_data.pop();
s_min.pop();
}
int top() {
return s_data.top();
}
int min() {
return s_min.top();
}
private:
stack<int> s_data;
stack<int> s_min;
};21. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
/* 辅助栈：模拟整个过程 */
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int length = pushV.size();
int length2 = popV.size();
if(length<=0 || length2<=0 || (length!=length2))
return false;
stack<int> stackV;
int index_push = 0, index_pop=0;
while(index_pop < length)
{
while(stackV.empty() || stackV.top()!=popV[index_pop])
{
if(index_push == length)
break;
stackV.push(pushV[index_push++]);
}
if(stackV.top() != popV[index_pop])
break;
++ index_pop;
stackV.pop();
}
if(stackV.empty() && index_pop==length)
return true;
else
return false;
}
};22. 从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/* 思路：辅助队列 */
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root){
vector<int> result;
if(root == nullptr)
return result;
queue<TreeNode *> nodes;
nodes.push(root);
while(!nodes.empty())
{
TreeNode *pNode = nodes.front();
result.push_back(pNode->val);
if(pNode->left != nullptr)
nodes.push(pNode->left);
if(pNode->right != nullptr)
nodes.push(pNode->right);
nodes.pop();
}
return result;
}
};23. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
/* 递归判断：左子树<根节点<右子树，不满足则为false，否则为true； */
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()<=0)
return false;
int start=0, end=sequence.size()-1;
return isLastOrder(sequence, start, end);
}
private:
bool isLastOrder(vector<int> &sequence, int start, int end)
{
if(start > end)
return false;
int root = sequence[end];
int i = start;
for(; i<end; i++)
{
if(sequence[i]>root)
break;
}
int j = i;
for(; j<end; j++)
{
if(sequence[j]<root)
return false;
}
bool left = true;
if(i-1 > start)
left = isLastOrder(sequence, start, i-1);
bool right = true;
if(i < end-1)
right = isLastOrder(sequence, i, end-1);
return(left && right);
}
};24. 二叉树中和为某一值的路径
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/* 回溯法，终止条件是为叶子节点，且值相等； */
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> pathes;
if(root==nullptr)
return pathes;
vector<int> onePath;
int curSum = 0;
findPath(root, pathes, onePath, expectNumber, curSum);
return pathes;
}
private:
void findPath(TreeNode *pRoot,vector<vector<int>> &pathes, vector<int> onePath, int expectNumber, int &curSum)
{
curSum += pRoot->val;
onePath.push_back(pRoot->val);
bool isLeaf = false;
if(pRoot->left==nullptr && pRoot->right==nullptr)
isLeaf = true;
if(isLeaf && curSum==expectNumber)
{
pathes.push_back(onePath);
}
if(pRoot->left != nullptr)
findPath(pRoot->left, pathes, onePath, expectNumber, curSum);
if(pRoot->right != nullptr)
findPath(pRoot->right, pathes, onePath, expectNumber, curSum);
curSum -=pRoot->val;
onePath.pop_back();
}
};25. 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
/*分为三步：
1）在旧链表中创建新链表，此时不处理新链表的兄弟节点 ；
2）根据旧链表的兄弟节点，初始化新链表的兄弟节点；
3）从旧链表中拆分得到新链表；*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
// step.1 Copy Node
RandomListNode *pNode=pHead;
while(pNode!=nullptr)
{
RandomListNode* pCloned = new RandomListNode(pNode->label);
pCloned->next = pNode->next;
// newNode->random = nullptr;
pNode->next = pCloned;
pNode = pCloned->next;
}
// step.2 Copy random
pNode = pHead;
while(pNode!=nullptr)
{
RandomListNode *pCloned = pNode->next;
if(pNode->random != nullptr)
pCloned->random = pNode->random->next;
pNode = pCloned->next;
}
// step.3 Split
pNode = pHead;
RandomListNode *pCloneHead, *pCloneNode;
if(pNode!=nullptr)
{
pCloneHead = pCloneNode = pHead->next;
pNode->next = pCloneNode->next;
pNode = pNode->next;
}
while(pNode != nullptr)
{
pCloneNode->next = pNode->next;
pCloneNode = pCloneNode->next;
pNode->next = pCloneNode->next;
pNode = pNode->next;
}
return pCloneHead;
}
};26. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/*解题思路：递归版
1.将左子树构造成双链表，并返回链表头节点。2.定位至左子树双链表最后一个节点。3.如果左子树链表不为空的话，将当前root追加到左子树链表。4.将右子树构造成双链表，并返回链表头节点。5.如果右子树链表不为空的话，将该链表追加到root节点之后。6.根据左子树链表是否为空确定返回的节点。*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==nullptr)
return nullptr;
pRootOfTree = ConvertNode(pRootOfTree);
while(pRootOfTree->left!=nullptr)
pRootOfTree = pRootOfTree->left;
return pRootOfTree;
}
TreeNode* ConvertNode(TreeNode *pRoot)
{
if(pRoot==nullptr)
return nullptr;
if(pRoot->left!=nullptr)
{
TreeNode *left = ConvertNode(pRoot->left);
while(left->right!=nullptr)
left = left->right;
pRoot->left = left;
left->right = pRoot;
}
if(pRoot->right != nullptr)
{
TreeNode *right=ConvertNode(pRoot->right);
while(right->left!=nullptr)
right = right->left;
pRoot->right = right;
right->left = pRoot;
}
return pRoot;
}
};27. 字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
/*全排列问题*/
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> result;
if(str.size()<=0)
return result;
PermutationCore(result, str, 0);
sort(result.begin(), result.end());
return result;
}
void PermutationCore(vector<string> &result, string str, int begin)
{
if(begin == str.size()-1)
result.push_back(str);
else
{
for(int i=begin; i<str.size(); i++)
{
if(i!=begin && str[i]==str[begin])
continue;
swap(str[i], str[begin]);
PermutationCore(result, str, begin+1);
swap(str[i], str[begin]);
}
}
}
};28. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
/*一个思路是基于快排中partition（会修改数组中的值）；
还有就是：定义一个times记录当前牟数字出现的次数，如果小于0则替换；
复杂度都是O(n)
*/
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size() <= 0)
return 0;
int result = numbers[0];
int times = 1;
for(int i=0; i<numbers.size(); i++)
{
if(times==0)
{
result = numbers[i];
times = 1;
}
else if(times>0 && result==numbers[i])
++ times;
else
-- times;
}
if(!isMoreThanHalf(numbers, result))
return 0;
return result;
}
private:
bool isMoreThanHalf(vector<int> numbers, int result)
{
int times = 0;
for(int i=0; i<numbers.size(); i++)
if(numbers[i] == result)
++ times;
if(2*times <= numbers.size())
return false;
return true;
}
};29. 最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
/*复杂度为O(n logn)*/
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
if(input.size()<k || k<1)
return result;
sort(input.begin(),input.end());
for(int i=0; i<k; i++)
result.push_back(input[i]);
return result;
}
};
/*复杂度为O(nlogk), 基于红黑树*/
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<k || k<0)
return vector<int> ();
multiset<int, greater<int>> leastNumbers;
vector<int>::const_iterator iter=input.begin();
for(; iter!=input.end(); iter++)
{
if(leastNumbers.size() < k)
leastNumbers.insert(*iter);
else
{
multiset<int, greater<int>>::iterator iterGreatest=leastNumbers.begin();
if(*iter < *iterGreatest)
{
leastNumbers.erase(*iterGreatest);
leastNumbers.insert(*iter);
}
}
}
return vector<int>(leastNumbers.begin(), leastNumbers.end());
}
};30. 连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
/* 思路：动态规划复杂度为O(n)， 首先定义一个值保存当前最大值；
如果当前和为负数，直接舍弃；如果不为负数，则累加；得到 当前和 与 当前最大值 比较*/
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() < 1)
return 0;
int curSum = array[0];
int greatestSum = array[0];
for(int i=1; i<array.size(); i++)
{
if(curSum < 0)
curSum = array[i];
else
curSum += array[i];
if(greatestSum < curSum)
greatestSum = curSum;
}
return greatestSum;
}
};31. 整数中1出现的次数（从1到n整数中1出现的次数）
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
/*思路：穷举*/
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
if(n < 1)
return 0;
int count=0;
for(int i=1; i<=n; i++)
{
count += NumberOfN(i);
}
return count;
}
int NumberOfN(int n)
{
int count=0;
while(n)
{
if(n%10 == 1)
count += 1;
n = n/10;
}
return count;
}
};32. 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
/*思路：通过字符串解决大数问题，然后通过自定义的字符串比较规则，对字符串排序*/
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
if(numbers.size()<1)
return string();
string result;
vector<string> numberString;
for(int i=0; i<numbers.size(); i++)
{
stringstream ss;
ss<<numbers[i];
string s = ss.str();
numberString.push_back(s);
}
sort(numberString.begin(), numberString.end(), Compare);
for(int i=0; i<numberString.size(); i++)
result.append(numberString[i]);
return result;
}
static bool Compare(const string &str1, const string &str2)
{
string s1 = str1+str2;
string s2 = str2+str1;
return s1<s2;
}
};33. 丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
/* 思路:创建数组保存已经找到的丑数，空间换时间； */
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
vector<int> res(index);
res[0] = 1;
int t2=0, t3=0, t5=0;
for(int i=1; i<index; i++)
{
res[i] = min(2*res[t2], min(3*res[t3], 5*res[t5]));
while(res[i] >= 2*res[t2]) ++t2;
while(res[i] >= 3*res[t3]) ++t3;
while(res[i] >= 5*res[t5]) ++t5;
}
return res[index-1];
}
};34. 第一个只出现一次的字符
在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符,并返回它的位置。
/*思路：借助哈希表，但是空间复杂度为O(1)，时间复杂度为O(n); */
class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(str.size()<=0)
return -1;
int tableSize = 256;
vector<int> numOfChar(tableSize, 0);
for(int i=0; i<str.size(); i++)
++numOfChar[str[i]];
for(int i=0; i<str.size(); i++)
if(numOfChar[str[i]]==1 && str[i]!=" ")
return i;
return -1;
}
};35.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
/* 思路：归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余 */
class Solution {
public:
int InversePairs(vector<int> data) {
int length = data.size();
if(length <= 0)
return 0;
int count = MergeSort(data, 0, length-1);
return count % 1000000007;
}
int MergeSort(vector<int> &data, int start, int end)
{
if(start >= end)
return 0;
int mid = (start+end)/2;
int left = MergeSort(data, start, mid);
int right = MergeSort(data, mid+1, end);
vector<int> copy(data);
int i = mid;
int j = end;
int counts = 0;
int indexCopy = end;
while(i>=start && j>=mid+1)
{
if(data[i] > data[j])
{
copy[indexCopy--] = data[i--];
counts += (j - mid);
}
else
copy[indexCopy--] = data[j--];
}
while(i >= start)
copy[indexCopy--] = data[i--];
while(j >= mid+1)
copy[indexCopy--] = data[j--];
for(int k=start; k<=end; k++)
data[k] = copy[k];
return left+right+counts;
}
};36. 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
/*思路：统计两个链表的长度，计算差值k，定义快慢指针，长链表先走k步*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==nullptr || pHead2==nullptr)
return nullptr;
int length1 = getListLength(pHead1);
int length2 = getListLength(pHead2);
ListNode *pAhead = pHead1;
ListNode *pBehind = pHead2;
int diff = length1-length2;
if(length1 < length2)
{
pAhead = pHead2;
pBehind = pHead1;
diff = length2-length1;
}
for(int i=0; i<diff; i++)
pAhead = pAhead->next;
while(pAhead!=nullptr && pBehind!=nullptr)
{
if(pAhead == pBehind)
return pAhead;
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return nullptr;
}
private:
int getListLength(ListNode *pHead)
{
if(pHead == nullptr)
return 0;
int length = 0;
while(pHead != nullptr)
{
++ length;
pHead = pHead->next;
}
return length;
}
};
37.数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
/*思路：基于二分查找复杂度为O(logn)；二分查找开始位置，二分查找结尾位置，做差；*/
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int length = data.size();
if(length <= 0)
return 0;
int first = firstIndex(data, k);
int last = lastIndex(data, k);
if(first > -1 && last > -1)
return last-first+1;
return 0;
}
int firstIndex(vector<int> data, int k)
{
int low = 0;
int high = data.size()-1;
int midIndex, midData;
while(low <= high)
{
midIndex = (low+high)/2;
midData = data[midIndex];
if(midData == k)
{
if(midIndex == 0 || data[midIndex-1] != k)
return midIndex;
else
high = midIndex-1;
}
else if(midData > k)
high = midIndex-1;
else
low = midIndex+1;
}
return -1;
}
int lastIndex(vector<int> data, int k)
{
int low = 0;
int high = data.size()-1;
int midIndex, midData;
while(low <= high)
{
midIndex = (low+high)/2;
midData = data[midIndex];
if(midData == k)
{
if(midIndex == data.size()-1 || data[midIndex+1] != k)
return midIndex;
else
low = midIndex+1;
}
else if(midData > k)
high = midIndex-1;
else
low = midIndex+1;
}
return -1;
}
};38.二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/********** 递归版本 **********/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)
return 0;
int left = TreeDepth(pRoot->left);
int right = TreeDepth(pRoot->right);
return left>=right?(left+1):(right+1);
}
};
/********** 循环版本 **********/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
queue<TreeNode*> q;
if(!pRoot)
return 0;
q.push(pRoot);
int level=0;
while(!q.empty())
{
int len=q.size();
level++;
while(len--)
{
TreeNode *tmp=q.front();
q.pop();
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
}
return level;
}
};
39.平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
/* 递归判断左右子树的方法重复计算太多；
下面的方法相当于从叶节点向上遍历，只需要遍历一次。记录每个结点到叶节点的长度； */
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == nullptr)
return true;
int depth=0;
return IsBalanced(pRoot, &depth);
}
private:
bool IsBalanced(TreeNode *pRoot, int *depth)
{
if(pRoot == nullptr)
{
*depth = 0;
return true;
}
int left, right;
if(IsBalanced(pRoot->left, &left) && IsBalanced(pRoot->right, &right))
{
int diff = left - right;
if(diff <= 1 && diff >= -1)
{
*depth = left>right?(left+1):(right+1);
return true;
}
}
return false;
}
};40. 数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
/*思路：可以用位运算实现，如果将所有所有数字相异或，则最后的结果肯定是那两个只出现一次的数字异或的结果；
所以根据异或的结果1所在的最低位，把数字分成两半，每一半里都还有只出现一次的数据和成对出现的数据；
这样继续对每一半相异或则可以分别求出两个只出现一次的数字*/
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length < 2)
return;
int xorNumber = 0;
for(int i=0; i<length; i++)
xorNumber ^= data[i];
int indexOf1 = findFirstBitIs1(xorNumber);
*num1 = 0;
*num2 = 0;
for(int i=0; i<length; i++)
{
if(isBit1(data[i], indexOf1))
*num1 ^= data[i];
else
*num2 ^= data[i];
}
}
int findFirstBitIs1(int number)
{
int indexBit = 0;
while((number&1)==0 && indexBit<8*sizeof(int))
{
number = number >> 1;
++ indexBit;
}
return indexBit;
}
bool isBit1(int number, int indexBit)
{
number = number >> indexBit;
return (number & 1);
}
};41.和为S的连续正数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
(小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! )
/*用两个数字small和big分别表示序列的最大值和最小值，首先将small初始化为1，end初始化为2.
如果从small到big的和大于s，我们就从序列中去掉较小的值(即增大small)
相反，只需要增大big。终止条件为：一直增加small到(1+sum)/2并且big小于sum为止*/
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > result;
if(sum < 3)
return result;
int small = 1;
int big = 2;
int middle = (1+sum)/2;
int curSum = small + big;
while(small < middle) //这里一定是小于，不能是小于等于
{
if(curSum == sum)
insertIntoResult(result, small, big);
while(curSum > sum && small < middle)
{
curSum -= small;
++ small;
if(curSum == sum)
insertIntoResult(result, small, big);
}
++ big;
curSum += big;
}
return result;
}
private:
void insertIntoResult(vector<vector<int> > &result, int small, int big)
{
vector<int> tmpSeq;
for(int i=small; i<=big; i++)
tmpSeq.push_back(i);
result.push_back(tmpSeq);
}
};
42.和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述: 对应每个测试案例，输出两个数，小的先输出。
/*思路：数列满足递增，设两个头尾两个指针i和j；
若ai + aj == sum，就是答案（相差越远乘积越小）
若ai + aj > sum，j -= 1
若ai + aj < sum，i += 1 */
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> result;
int length = array.size();
if(length < 2)
return result;
int start = 0;
int end = length - 1;
// sort(array.begin(), array.end());
while(start < end)
{
int curSum = array[start]+array[end];
if(curSum == sum)
{
result.push_back(array[start]);
result.push_back(array[end]);
return result;
}
else if(curSum < sum)
++ start;
else
-- end;
}
return result;
}
};43.左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
/* 思路：三次翻转 */
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.size();
if(len < 0 || len < n)
return str;
for(int i=0, j=n-1; i<j; i++, j--)
swap(str[i], str[j]);
for(int i=n, j=len-1; i<j; i++, j--)
swap(str[i], str[j]);
for(int i=0, j=len-1; i<j; i++, j--)
swap(str[i], str[j]);
return str;
}
};
/*************** 也可以写函数 **************/
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.size();
if(len < 0 || len < n)
return str;
reverseString(str, 0, n-1);
reverseString(str, n, len-1);
reverseString(str, 0, len-1);
return str;
}
void reverseString(string &str, int start, int end)
{
for(int i=start, j=end; i<j; i++, j--)
swap(str[i], str[j]);
}
};
44.翻转单词顺序列
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
/* 思路：两次翻转 */
class Solution {
public:
string ReverseSentence(string str) {
int len = str.size();
if(len <= 0)
return str;
reverseString(str, 0, len-1);
int i = 0, j = 0;
while(j <= len)
{
if(str[j]==" " || j==len)
{
reverseString(str, i, j-1);
i = j + 1;
j = i + 1;
}
else
++ j;
}
return str;
}
void reverseString(string &str, int start, int end)
{
for(int i=start, j=end; i<j; i++, j--)
swap(str[i], str[j]);
}
};45.扑克牌顺子
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。
/*
1.对数组排序；
2.统计0的个数；
3.统计间隔数；
4.对比nZ，nG；
*/
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
int length = numbers.size();
if(length < 5)
return false;
sort(numbers.begin(), numbers.end());
int i, numberOfZero = 0, numberOfGap = 0;
for(i=0; i<length && numbers[i]==0; i++)
++ numberOfZero;
int small=i, big=small+1;
while(big < length)
{
if(numbers[small] == numbers[big])
return false;
numberOfGap += numbers[big]-numbers[small]-1;
++ small;
++ big;
}
return numberOfZero>=numberOfGap?true:false;
}
};46.孩子们的游戏(圆圈中最后剩下的数)
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
/*
思路一：用STL中std::list来模拟这个环形列表。由于list并不是一个环形的结构，因此每次跌代器扫描到列表末尾的时候，要记得把跌代器移到列表的头部。这样就是按照一个圆圈的顺序来遍历这个列表了。这种思路需要一个有n个结点的环形列表来模拟这个删除声明：该文观点仅代表作者本人，入门客AI创业平台信息发布平台仅提供信息存储空间服务，如有疑问请联系rumenke@qq.com。
- 上一篇：没有了
- 下一篇： python字符串多个分割符（借助正则表达式re）
