剑指offer
最近在牛客网上刷剑指offer的题目，现将题目和答案（均测试通过）总结如下：
- 第一个只出现一次的字符
- 数组中的逆序对
- 两个链表的第一个公共结点
- 数字在排序数组中出现的次数
- 二叉树的深度
- 平衡二叉树
- 数组中只出现一次的数字
- 和为S的连续正数序列
- 和为S的两个数字
- 左旋转字符串
- 翻转单词顺序列
- 扑克牌顺子
- 孩子们的游戏(圆圈中最后剩下的数)
- 求1+2+3+…+n
- 不用加减乘除做加法
- 把字符串转换成整数
- 数组中重复的数字
- 构建乘积数组
- 正则表达式匹配
- 表示数值的字符串
- 字符流中第一个不重复的字符
- 链表中环的入口结点
- 删除链表中重复的结点
- 二叉树的下一个结点
- 对称的二叉树
- 按之字形顺序打印二叉树
- 把二叉树打印成多行
- 序列化二叉树
- 二叉搜索树的第k个结点
- 数据流中的中位数
- 滑动窗口的最大值
- 矩阵中的路径
- 机器人的运动范围
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]!='\0')
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个结点的环形列表来模拟这个删除的过程，因此内存开销为O(n)。而且这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O(mn)；
思路二：数学归纳法
{ 0 n=1
f(n,m)={
{ [f(n-1,m)+m]%n n>1
时间复杂度为O(n)，空间复杂度为O(1)的方法；
*/
//思路一
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n < 1 || m < 1)
return -1;
unsigned int i = 0;
list<int> integers;
for(i = 0; i < n; ++ i)
integers.push_back(i);
list<int>::iterator curinteger = integers.begin();
while(integers.size() > 1)
{
for(int i = 1; i < m; ++ i)
{
curinteger ++;
if(curinteger == integers.end())
curinteger = integers.begin();
}
list<int>::iterator nextinteger = ++ curinteger;
if(nextinteger == integers.end())
nextinteger = integers.begin();
-- curinteger;
integers.erase(curinteger);
curinteger = nextinteger;
}
return *(curinteger);
}
};
//思路二
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n <= 0 || m < 0)
return -1;
int lastinteger = 0;
for (int i = 2; i <= n; i ++)
lastinteger = (lastinteger + m) % i;
return lastinteger;
}
};
47.求1+2+3+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
//解题思路：1.需利用逻辑与的短路特性实现递归终止
//2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。
class Solution {
public:
int Sum_Solution(int n) {
int sum = n;
bool ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
return sum;
}
};
48.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
/*
考虑位运算，分三步：
第一步：不进位加 n1
第二步：计算进位 n2
第三步：n1 和 n2 求和（重复第一步，直到进位为0，即n2=0)
在第一步中，采用异或
第二步中，采用按位与，左移一位
*/
class Solution {
public:
int Add(int num1, int num2)
{
int sum, carry;
do
{
sum = num1 ^ num2; //异或
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
while(num2 != 0);
return num1;
}
};
49.把字符串转换成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入一个字符串,包括数字字母符号,可以为空;
如果是合法的数值表达则返回该数字，否则返回0;
/*
考虑首字符的正负；
字符是否有效；
数字是否溢出；
*/
class Solution {
public:
int StrToInt(string str) {
if(str.empty())
return 0;
int symbol = 1;
if(str[0] == '-')
{
symbol = -1;
str[0] = '0';
}
else if(str[0] == '+')
{
symbol = 1;
str[0] = '0';
}
int sum = 0;
for(int i=0; i<str.size(); i++)
{
if(str[i] < '0' || str[i] > '9')
{
sum = 0;
break;
}
sum = sum * 10 + str[i] - '0';
}
return symbol * sum;
}
};
50.数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
/*
思路一（会修改原数组）：通过比较这个数字(m)是不是等于i，如果是，接着扫描下一个数字。如果不是则拿它和第m个数字进行比较，如果和第m个数字相等，则找到一个重复的数字。如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。复杂度为O(n)
*/
class Solution {
public:
bool duplicate(int numbers[], int length, int* duplication) {
if(numbers == nullptr || length<=0)
return false;
for(int i=0; i<length; i++)
if(numbers[i]<0 || numbers[i]>length-1)
return false;
for(int i=0; i<length; i++)
{
while(numbers[i] != i)
{
if(numbers[i] == numbers[numbers[i]])
{
*duplication = numbers[i];
return true;
}
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
}
return false;
}
};
51.构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
/*
思路一：直接用连乘的话，复杂度为O(n^2);
思路二：将其构建为一个矩阵(对角值全为1)，先求左边（从上往下）的连乘结果，在求右边（从下往上）的连乘结果；
左右两侧结果相乘即可；复杂度为O(n);
*/
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int length = A.size();
vector<int> B;
if(length <= 0)
return B;
for(int i=0; i<length; i++)
B.push_back(1);
for(int i=1; i<length; i++)
B[i] = B[i-1] * A[i-1];
int tmp = 1;
for(int i=length-2; i>=0; i--)
{
tmp *= A[i+1];
B[i] *= tmp;
}
return B;
}
};
52.正则表达式匹配
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
/*
非确定有限状态机
*/
class Solution {
public:
bool match(char* str, char* pattern)
{
if(str == nullptr || pattern == nullptr)
return false;
return matchCore(str, pattern);
}
private:
bool matchCore(char *str, char * pattern)
{
if(*str == '\0' && *pattern == '\0')
return true;
if(*str != '\0' && *pattern == '\0')
return false;
if(*(pattern + 1) == '*' )
{
if(*pattern == *str || (*pattern == '.' && *str != '\0'))
return matchCore(str+1, pattern+2)
|| matchCore(str+1, pattern)
|| matchCore(str, pattern+2);
else
return matchCore(str, pattern+2);
}
if(*str == *pattern || (*pattern == '.') && *str != '\0')
return matchCore(str+1, pattern+1);
return false;
}
};
53.表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
/*
1.首先判断第一位是不是正负号；
2.接下来是若干个0~9之间的数；
3.如果有小数点，则后面有若干个0~9的数字；
4.科学记数法，'e','E';
*/
class Solution {
public:
// 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，其中A和C都是
// 整数（可以有正负号，也可以没有），而B是一个无符号整数
bool isNumeric(const char* str)
{
if(str == nullptr)
return false;
bool numeric = scanInteger(&str);
// 如果出现'.'，接下来是数字的小数部分
if(*str == '.')
{
++str;
// 下面一行代码用||的原因：
// 1. 小数可以没有整数部分，例如.123等于0.123；
// 2. 小数点后面可以没有数字，例如233.等于233.0；
// 3. 当然小数点前面和后面可以有数字，例如233.666
numeric = scanUnsignedInteger(&str) || numeric;
}
// 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
if(*str == 'e' || *str == 'E')
{
++str;
// 下面一行代码用&&的原因：
// 1. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
// 2. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
numeric = numeric && scanInteger(&str);
}
return numeric && *str == '\0';
}
private:
bool scanUnsignedInteger(const char** str)
{
const char* before = *str;
while(**str != '\0' && **str >= '0' && **str <= '9')
++(*str);
// 当str中存在若干0-9的数字时，返回true
return *str > before;
}
// 整数的格式可以用[+|-]B表示, 其中B为无符号整数
bool scanInteger(const char** str)
{
if(**str == '+' || **str == '-')
++(*str);
return scanUnsignedInteger(str);
}
};
54.字符流中第一个不重复的字符
一个链表中包含环，请找出该链表的环的入口结点。
/*
借助hash表；
*/
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
s += ch;
hash[ch] ++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int size = s.size();
for(int i=0; i<size; ++i)
{
if(hash[s[i]] == 1)
return s[i];
}
return '#';
}
private:
string s;
char hash[256] = {0};
};
55.链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。
/*
1.定义快慢指针，找到相遇节点；
2.计算环的长度length；
3.在定义快慢指针，先让快指针走length步，在让慢指针走。直到两个指针相等时，即为入口节点；
复杂度为O(n);
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode *meetNode = meetingNode(pHead);
if(meetNode == nullptr)
return nullptr;
int loopLength=1;
ListNode *pNode1 = meetNode->next;
while(pNode1 != meetNode)
{
++ loopLength;
pNode1 = pNode1->next;
}
pNode1 = pHead;
ListNode *pNode2 = pHead;
for(int i=0; i<loopLength; i++)
pNode1 = pNode1->next;
while(pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
ListNode* meetingNode(ListNode *pHead)
{
if(pHead == nullptr)
return nullptr;
ListNode *pSlow = pHead->next;
if(pSlow == nullptr)
return nullptr;
ListNode *pFast = pSlow->next;
while(pFast != nullptr && pSlow != nullptr)
{
if(pFast == pSlow)
return pFast;
pSlow = pSlow->next;
pFast = pFast->next;
if(pFast != nullptr)
pFast = pFast->next;
}
return nullptr;
}
};
56.删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/************* 不保留重复节点版本 *****************/
// 1 2 2 3 4 4 5
// 1 3 5
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
ListNode *pCurNode = pHead;
ListNode *pPreNode = nullptr;
while(pCurNode != nullptr)
{
ListNode *pNext = pCurNode->next;
bool toBeDeleted = false;
if(pNext != nullptr && pCurNode->val == pNext->val)
toBeDeleted = true;
if(!toBeDeleted)
{
pPreNode = pCurNode;
pCurNode = pCurNode->next;
}
else
{
int value = pCurNode->val;
ListNode *delNode = pCurNode;
while(delNode!=nullptr && delNode->val==value)
{
pNext = delNode->next;
delete delNode;
delNode = pNext;
}
if(pPreNode == nullptr)
pHead = pNext;
else
pPreNode->next = pNext;
pCurNode = pNext;
}
}
return pHead;
}
};
/************* 保留重复节点版本 *****************/
// 1 2 2 3 4 4 5
// 1 2 3 4 5
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
ListNode *pCurNode = pHead;
while(pCurNode != nullptr)
{
ListNode *pNext = pCurNode->next;
if(pNext != nullptr && pCurNode->val == pNext->val)
{
int value = pCurNode->val;
ListNode *delNode = pNext;
while(delNode!=nullptr && delNode->val==value)
{
pNext = delNode->next;
delete delNode;
delNode = pNext;
}
pCurNode->next = pNext;
pCurNode = pCurNode->next;
}
else
pCurNode = pCurNode->next;
}
return pHead;
}
};
57.二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next; // next 指向父节点；
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
思路：有两种情况
1.存在右孩子，那么下一个节点就是右孩子的左孩子（的左孩子的左孩子......）
2.不存在右节点，下一个就是是其父节点且满足该父节点是其父节点的左孩子；
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == nullptr)
return nullptr;
TreeLinkNode* pNext = nullptr;
if(pNode->right != nullptr)
{
TreeLinkNode* pRight = pNode->right;
while(pRight->left != nullptr)
pRight = pRight->left;
pNext = pRight;
}
else if(pNode->next != nullptr)
{
TreeLinkNode* pCurrent = pNode;
TreeLinkNode* pParent = pNode->next;
while(pParent != nullptr && pCurrent == pParent->right)
{
pCurrent = pParent;
pParent = pParent->next;
}
pNext = pParent;
}
return pNext;
}
};
58.对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
思路：递归判断：R1->left与R2->right比较，R2->left与R1->right比较；
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot, pRoot);
}
private:
bool isSymmetrical(TreeNode *pRoot1, TreeNode *pRoot2)
{
if(pRoot1 == nullptr && pRoot2 == nullptr)
return true;
if(pRoot1 == nullptr || pRoot2 == nullptr)
return false;
if(pRoot1->val != pRoot2->val)
return false;
return isSymmetrical(pRoot1->left, pRoot2->right)
&& isSymmetrical(pRoot1->right, pRoot2->left);
}
};
59.按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
/*
借助两个辅助栈；
在打印某一行节点时，把下一层的子节点保存到相应的栈里。
如果当前打印的是奇数层（一，三层等），则先保存左子结点再保存右子结点到第一个栈里；
如果当前打印的是偶数层（二，四层等），则先保存右子结点再保存左子结点到第二个栈里；
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
if(pRoot == nullptr)
return result;
stack<TreeNode*> levels[2];
int current = 0;
int next = 1;
levels[current].push(pRoot);
vector<int> oneRow;
while(!levels[0].empty() || !levels[1].empty())
{
TreeNode *pNode = levels[current].top();
levels[current].pop();
oneRow.push_back(pNode->val);
if(current == 0)
{
if(pNode->left != nullptr)
levels[next].push(pNode->left);
if(pNode->right != nullptr)
levels[next].push(pNode->right);
}
else
{
if(pNode->right != nullptr)
levels[next].push(pNode->right);
if(pNode->left != nullptr)
levels[next].push(pNode->left);
}
if(levels[current].empty())
{
result.push_back(oneRow);
oneRow.clear();
current = 1 - current;
next = 1 - next;
}
}
return result;
}
};
60.把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
/*
借助队列存在要打印的结点；
引入两个变量：
toBePrinted表示当前层中还没有打印的个数；
nextLevel表示下一层的结点数；
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int> > result;
if(pRoot == nullptr)
return result;
std::queue<TreeNode*> nodes;
nodes.push(pRoot);
int nextLevel = 0;
int toBePrinted = 1;
vector<int> oneRow;
while(!nodes.empty())
{
TreeNode* pNode = nodes.front();
oneRow.push_back(pNode->val);
if(pNode->left != nullptr)
{
nodes.push(pNode->left);
++nextLevel;
}
if(pNode->right != nullptr)
{
nodes.push(pNode->right);
++nextLevel;
}
nodes.pop();
--toBePrinted;
if(toBePrinted == 0)
{
result.push_back(oneRow);
oneRow.clear();
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return result;
}
};
61.序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
/*
1. 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点
不为空时，在转化val所得的字符之后添加一个' ， '作为分割。对于空节点则以 '#' 代替。
2. 对于反序列化：按照前序顺序，递归的使用字符串中的字符创建一个二叉树(特别注意：
在递归时，递归函数的参数一定要是char ** ，这样才能保证每次递归后指向字符串的指针会
随着递归的进行而移动！！！)
*/
class Solution {
public:
char* Serialize(TreeNode *root) {
if(root == NULL)
return NULL;
string str;
Serialize(root, str);
char *ret = new char[str.length() + 1];
int i;
for(i = 0; i < str.length(); i++){
ret[i] = str[i];
}
ret[i] = '\0';
return ret;
}
void Serialize(TreeNode *root, string& str){
if(root == NULL){
str += '#';
return ;
}
string r = to_string(root->val);
str += r;
str += ',';
Serialize(root->left, str);
Serialize(root->right, str);
}
TreeNode* Deserialize(char *str) {
if(str == NULL)
return NULL;
TreeNode *ret = Deserialize(&str);
return ret;
}
TreeNode* Deserialize(char **str){//由于递归时，会不断的向后读取字符串
if(**str == '#'){ //所以一定要用**str,
++(*str); //以保证得到递归后指针str指向未被读取的字符
return NULL;
}
int num = 0;
while(**str != '\0' && **str != ','){
num = num*10 + ((**str) - '0');
++(*str);
}
TreeNode *root = new TreeNode(num);
if(**str == '\0')
return root;
else
(*str)++;
root->left = Deserialize(str);
root->right = Deserialize(str);
return root;
}
};
62.二叉搜索树的第k个结点
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
//中序遍历
//中序遍历的结果就是有序序列，第K个元素就是vec[K-1]存储的节点指针；
/********** 递归版本中序遍历 ********/
class Solution {
public:
//中序遍历的结果就是有序序列，第K个元素就是vec[K-1]存储的节点指针；
TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
{
if(pRoot==NULL||k<=0) return NULL;
vector<TreeNode*> vec;
Inorder(pRoot,vec);
if(k>vec.size())
return NULL;
return vec[k-1];
}
//中序遍历，将节点依次压入vector中
void Inorder(TreeNode* pRoot,vector<TreeNode*>& vec)
{
if(pRoot==NULL) return;
Inorder(pRoot->left,vec);
vec.push_back(pRoot);
Inorder(pRoot->right,vec);
}
};
/********** 非递归版本中序遍历 ********/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
int count = 0;
stack<TreeNode*> s;
TreeNode *p = pRoot;
while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
} else if (!s.empty()) {
p = s.top();
s.pop();
if (++count == k)
return p;
p = p->right;
}
}
return nullptr;
}
};
63.数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
/*
插入的复杂度：O(logn), 得到中位数的复杂度:O(1)
核心思路：
1.维护一个大顶堆，一个小顶堆，且保证两点：
1）小顶堆里的全大于 大顶堆里的；
2）2个堆个数的差值小于等于1
2.当insert的数字个数为奇数时：使小顶堆个数比大顶堆多1；
当insert的数字个数为偶数时，使大顶堆个数跟小顶堆个数一样。
3.那么当总数字个数为奇数时，中位数就是小顶堆堆头；
当总数字个数为偶数时，中卫数就是 2个堆堆头平均数
*/
class Solution {
public:
void Insert(int num)
{
count+=1;
// 元素个数是偶数时,将小顶堆堆顶放入大顶堆
if(count%2==0){
big_heap.push(num);
small_heap.push(big_heap.top());
big_heap.pop();
}
else{
small_heap.push(num);
big_heap.push(small_heap.top());
small_heap.pop();
}
}
double GetMedian()
{
if(count&0x1){
return big_heap.top();
}
else{
return double((small_heap.top()+big_heap.top())/2.0);
}
}
private:
int count=0;
priority_queue<int, vector<int>, less<int>> big_heap; // 左边一个大顶堆
priority_queue<int, vector<int>, greater<int>> small_heap; // 右边一个小顶堆
// 大顶堆所有元素均小于等于小顶堆的所有元素.
};
64.滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
/*时间复杂度o（n），空间复杂度为o（n）
思路就是采用双端队列，队列中的头节点保存的数据比后面的要大。
比如当前假如的数据比队尾的数字大，说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
，而之前队尾的数字不可能最大了，所以要删除队尾元素。
此外，还要判断队头的元素是否超过size长度，由于存储的是下标，所以可以计算得到；
特别说明，我们在双端队列中保存的数字是传入的向量的下标；
*/
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> vec;
if(num.size()<=0 || num.size()<size ||size<=0) return vec;//处理特殊情况
deque<int> dq;
//处理前size个数据，因为这个时候不需要输出最大值；
for(unsigned int i=0;i<size;i++)
{
//假如当前的元素比队列队尾的元素大，说明之前加入的这些元素不可能是最大值了。因为当前的这个数字比之前加入队列的更晚
while(!dq.empty()&&num[i]>=num[dq.back()])
dq.pop_back();//弹出比当前小的元素下标
dq.push_back(i);//队尾压入当前下标
}
//处理size往后的元素，这时候需要输出滑动窗口的最大值
for(unsigned int i=size;i<num.size();i++)
{
vec.push_back(num[dq.front()]);
while(!dq.empty()&&num[i]>=num[dq.back()])
dq.pop_back();
if(!dq.empty() && dq.front()<=(int)(i-size))//判断队头的下标是否超出size大小，如果超过，要删除队头元素
dq.pop_front();//删除队头元素
dq.push_back(i);//将当前下标压入队尾，因为可能在未来是最大值
}
vec.push_back(num[dq.front()]);//最后还要压入一次
return vec;
}
};
65.矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵，其包含字符串"bcced"的路径，但是矩阵中不包含“abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
/*
分析：回溯算法
这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置.
*/
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(str==NULL||rows<=0||cols<=0)
return false;
bool *isOk=new bool[rows*cols]();
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
if(isHsaPath(matrix,rows,cols,str,isOk,i,j))
return true;
}
return false;
}
private:
bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury)
{
if(*str=='\0')
return true;
if(cury==cols)
{
curx++;
cury=0;
}
if(cury==-1)
{
curx--;
cury=cols-1;
}
if(curx<0||curx>=rows)
return false;
if(isOk[curx*cols+cury]||*str!=matrix[curx*cols+cury])
return false;
isOk[curx*cols+cury]=true;
bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury)
||isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury)
||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1)
||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1);
isOk[curx*cols+cury]=false;
return sign;
}
};
66.机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
bool* flag=new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
flag[i]=false;
int count=moving(threshold,rows,cols,0,0,flag);//从（0,0）坐标开始访问;
delete[] flag;
return count;
}
//计算最大移动位置
int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
{
int count=0;
if(check(threshold,rows,cols,i,j,flag))
{
flag[i*cols+j]=true;
//标记访问过，这个标志flag不需要回溯，因为只要被访问过即可。
//因为如果能访问，访问过会加1.不能访问，也会标记下访问过。
count=1+moving(threshold,rows,cols,i-1,j,flag)
+moving(threshold,rows,cols,i,j-1,flag)
+moving(threshold,rows,cols,i+1,j,flag)
+moving(threshold,rows,cols,i,j+1,flag);
}
return count;
}
//检查当前位置是否可以访问
bool check(int threshold,int rows,int cols,int i,int j,bool* flag)
{
if(i>=0 && i<rows && j>=0 && j<cols
&& getSum(i)+getSum(j)<=threshold
&& flag[i*cols+j]==false)
return true;
return false;
}
//计算位置的数值
int getSum(int number)
{
int sum=0;
while(number>0)
{
sum+=number%10;
number/=10;
}
return sum;
}
};
