剑指offer
最近在牛客网上刷剑指offer的题目，现将题目和答案（均测试通过）总结如下：
- 二维数组的查找
- 替换空格
- 从尾到头打印链表
- 重建二叉树
- 用两个栈实现队列
- 旋转数组的最小数字
- 斐波那契数列
- 跳台阶
- 变态跳台阶
- 矩阵覆盖
- 二进制中1的位数
- 数值的整数次方
- 调整数组顺序使奇数位于偶数前面
- 链表中倒数第k个结点
- 反转链表
- 合并两个排序的链表
- 树的子结构
- 二叉树的镜像
- 顺时针打印矩阵
- 包含min函数的栈
- 栈的压入、弹出序列
- 从上往下打印二叉树
- 二叉搜索树的后序遍历序列
- 二叉树中和为某一值的路径
- 复杂链表的复制
- 二叉搜索树与双向链表
- 字符串的排列
- 数组中出现次数超过一半的数字
- 最小的K个数
- 连续子数组的最大和
- 整数中1出现的次数（从1到n整数中1出现的次数）
- 把数组排成最小的数
- 丑数
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] != '\0')
{
++ 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. 矩阵覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个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出现的次数）
求出113的整数中1出现的次数,并算出1001300的整数中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];
}
};
