1、滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, int size)
{
//返回的数组大小为num.size()-size+1
vector<int> res;
if(size>num.size() || size == 0) return res;
deque<int> q; //保留最大值的下标
for(int i=0;i<num.size();i++)
{
while(!q.empty() && num[q.back()] < num[i])
q.pop_back();
while(!q.empty() && i-q.front()+1 > size)
q.pop_front();
q.push_back(i);
if(i+1>=size)
res.push_back(num[q.front()]);
}
return res;
}
};
2、二叉搜索树的第k个结点
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<TreeNode*> node;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
//二叉搜索树的节点分布为层序遍历，按从小到大输出的话是中序遍历
if(k<=0 || pRoot==NULL ) return NULL;
InOrder(pRoot);
return k<=node.size()? node[k-1]: NULL;
}
void InOrder(TreeNode* pRoot)
{
if(pRoot == NULL) return;
InOrder(pRoot->left);
node.push_back(pRoot);
InOrder(pRoot->right);
}
};
3、构建乘积数组
给定一个数组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]。不能使用除法。
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size(),1);
int product=1;
for(int i=0,product=1; i<A.size();product *= A[i],i++)
B[i] = product;
for(int i=A.size()-1,product=1; i>=0; product *= A[i],i--)
B[i] *= product;
return B;
}
};
4、把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
class Solution {
public:
int StrToInt(string str) {
bool ispositive = true;
if (str[0] == '-')
ispositive = false;
int res = 0;
for (int i = 0; i<str.length(); i++)
{
if (i == 0 && (str[i] == '+' || str[i] == '-'))
continue;
if (str[i] >= '0' && str[i] <= '9')
res = res * 10 + (str[i] - '0');
else
return 0;
}
return ispositive == false ? -res : res;
}
};
5、不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
class Solution {
public:
int Add(int num1, int num2)
{
//return num1+num2;
return num2 == 0 ? num1 : Add(num1^num2, (num1&num2) << 1);
}
};
6、求1+2+3+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
class Solution {
public:
int Sum_Solution(int n) {
int sum=n;
n && (sum+=Sum_Solution(n-1));
return sum;
}
};
7、孩子们的游戏(圆圈中最后剩下的数)
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n<=0) return -1;
if(n==1) return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;
}
};
8、扑克牌顺子
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的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
sort(numbers.begin(),numbers.end());
int len = numbers.size();
if(len <5) return false;
int cnt=0;
for(int i=0; i<len-1;i++)
{
if(numbers[i] == 0)
cnt++; //记录有几个大小王
else if(numbers[i] != 0 && numbers[i] == numbers[i+1])
return false;
else
cnt -= numbers[i+1]-numbers[i]-1;
}
return cnt>=0?true:false;
}
};
9、翻转单词顺序列
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
class Solution {
public:
string ReverseSentence(string str) {
string res="", temp="";
for (int i = 0; i < str.length(); i++)
{
if (str[i] == ' ')
{
res = temp + " " + res;
temp = "";
}
else
temp += str[i];
}
res = temp + " " + res;
res = res.substr(0, str.length());
return res;
}
};
10、左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.length();
if(len == 0) return str;
n = n%len;
string left = str.substr(0,n);
string right = str.substr(n);
right += left;
return right;
}
};
11、数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int diff = 0;
for (int i = 0; i<data.size(); i++)
{
diff ^= data[i];
}
int n = diff & -diff; //找到diff中第一个为1的位置
for (int i = 0; i<data.size(); i++)
{
if ((data[i] & n )== 0) //注意这里逻辑操作符的顺序，不确定就加上括号
*num1 ^= data[i]; //传的是指针，要修改原数一定要用*取值
else
*num2 ^= data[i];
}
}
};
12、平衡二叉树
入一棵二叉树，判断该二叉树是否是平衡二叉树。
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == NULL) return true;
int left = depth(pRoot->left);
int right = depth(pRoot->right);
return abs(left - right) <= 1 && IsBalanced_Solution(pRoot->left)
&& IsBalanced_Solution(pRoot->right);
}
int depth(TreeNode* pRoot)
{
if(pRoot == NULL) return 0;
else
return max(depth(pRoot->left), depth(pRoot->right)) + 1;
}
};
13、二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == NULL) return 0;
else
return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
}
};
14、数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
if(data.size() == 0) return 0;
int cnt=0;
int left = 0, right = data.size()-1;
while(left <= right)
{
int mid = (left+right)/2;
if(data[mid] == k)
return countk(data, left, right, k);
else if(data[mid] < k) //在右边
left = mid+1;
else
right = mid-1;
}
return cnt;
}
int countk(vector<int> data, int left, int right, int k)
{
int cnt=0;
for(int i= left; i<=right; i++)
{
if(data[i] == k)
cnt++;
else if(data[i] > k)
break;
}
return cnt;
}
};
15、两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *l1 = pHead1, *l2 = pHead2;
while (l1 != l2)
{
l1 = l1 == NULL ? pHead2 : l1->next;
l2 = l2 == NULL ? pHead1 : l2->next;
}
return l1;
}
};
16、数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
class Solution {
public:
int *temp;
long long cnt=0;
int InversePairs(vector<int> data) {
////方法一：暴力求解法
//int ressum = 0;
//vector<int> res(data.size(),0), sorted;
//for (int i = data.size() - 1; i >= 0; i--)
//{
// auto loc = lower_bound(sorted.begin(), sorted.end(), data[i]);
// res[i] = distance(sorted.begin(), loc);
// sorted.insert(loc, data[i]);
//}
//for (int i = 0; i < res.size(); i++)
// ressum += res[i];
//return ressum;
//这种算法适用于数组大小不是特别大的情况，当数组特别大的时候，就不能暴力了，应该用二分法
//暴力法的原理是：从后往前遍历，每个数的逆序数只与它后面的数有关，且只与后面数的数值有关，与顺序无关。
//因此对每一个数，从后往前依次将它们顺序的插入到新的数组中去，每个数的逆序数=新插入时的位置
//方法二：二分+合并排序法
int left = 0, right = data.size() - 1;
temp = new int[right + 1];
memset(temp, 0, (right + 1)*sizeof(int));
mergesort(data, 0, right); //注意vector作为函数参数时，如果没有在函数声明中加上&，那么就是传值调用，不能在函数中修改
//原数组的数值，如果要修改，比如加上&或*，这样才是引用调用|地址调用
return cnt % 1000000007;
}
void mergesort(vector<int> &data, int left, int right)
{
if (left >= right)
return;
//int mid = (right + left) / 2; //这种相加除以2的方法可能会溢出，数值并不会变，所以大数据时一般采用下面一种方法
int mid = left + (right - left) / 2;
mergesort(data, left, mid);
mergesort(data, mid+1, right);
merge(data, left, mid, right);
}
void merge(vector<int> &data, int left, int mid, int right)
{
int i = left, j = mid + 1, k = left;
while (i <= mid || j <= right)
{
if (i > mid)
temp[k] = data[j++];
else if (j > right)
temp[k] = data[i++];
else if (data[i] < data[j]) //没有逆序
temp[k] = data[i++];
else
{
temp[k] = data[j++];
cnt += mid - i + 1;
}
k++;
}
for (k = left; k <= right; k++)
data[k] = temp[k];
}
};
17、第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
class Solution {
public:
int FirstNotRepeatingChar(string str) {
//这到题和前面有一题求第一个只出现一次的字符类似，区别是这题要输出的是这个字符的下标
//所以做法类似，只是队列在存储是存储的是pair<char,int>对，字符和对应下标
queue<pair<char, int>> q;
int len = str.length();
if(len == 0) return -1;
int cnt[100] = {0};
for (int i = 0; i < len; i++)
{
q.push(make_pair(str[i], i));
cnt[str[i]-'A']++;
while (!q.empty() && cnt[q.front().first - 'A'] > 1)
q.pop();
}
return q.front().second;
}
};
18、丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
//1,2,3,4,5,6,8,9,10,12,15 都是丑数
if (index <= 6) return index;
int *uglyNum = new int[index];
int m2 = 0, m3 = 0, m5 = 0;
int next2 = 0, next3 = 0, next5 = 0;
uglyNum[0] = 1;
for (int i = 1; i<index; i++)
{
next2 = uglyNum[m2] * 2;
next3 = uglyNum[m3] * 3;
next5 = uglyNum[m5] * 5;
int next = min(next2, min(next3, next5));
uglyNum[i] = next;
if (next == next2)
m2++;
if (next == next3) //注意这里不能用else if，因为有可能next2 == next3，这种情况m2 m3都需要++
m3++;
if (next == next5)
m5++;
}
/*for (int i = 0; i < index; i++)
cout << uglyNum[i] << " ";*/
return uglyNum[index - 1];
}
};
19、把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
class Solution {
public:
string PrintMinNumber(vector<int> nums) {
if (nums.size() == 0) return "";
auto cmp = [](int a, int b)
{
string as = to_string(a);
string bs = to_string(b);
return as + bs < bs + as;
};
sort(nums.begin(), nums.end(), cmp);
string res = "";
for (int n : nums)
{
res += to_string(n);
}
//cout << res << endl;
return res;
}
};
20、和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
class Solution {
public:
vector<vector<int> > res57;
vector<vector<int> > FindContinuousSequence(int sum) {
if (sum<3) return res57;
for (int i = 1; i<=sum / 2; i++)
{
for (int j = i + 1; j <= sum; j++)
{
if ((i + j)*(j - i + 1) == 2 * sum)
{
inputres(i, j);
break;
}
else if ((i + j)*(j - i + 1) > 2 * sum)
break;
}
}
return res57;
}
void inputres(int left, int right)
{
vector<int> temp;
while(left<=right)
temp.push_back(left++);
res57.push_back(temp);
}
};
21、整数中1出现的次数（从1到n整数中1出现的次数）
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{ //3101592 31015 9 2 10
if(n == 0) return 0;
int pre =0, cur=0, suf=0;
int res = 0;
for(int i=1, q=n; i<=n; i*=10, q/=10)
{
pre = n/(i*10);
cur = q % 10;
suf = n % i;
res += pre*i;
if(cur > 1)
res+= i;
else if(cur == 1)
res += suf+1;
else
res += 0;
}
return res;
}
};
22、和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
int left=0,right= array.size()-1;
vector<int> res;
while(left<right)
{
if((array[left]+array[right])==sum)
{
res.push_back(array[left]);
res.push_back(array[right]);
break;
}
else if((array[left]+array[right])<sum)
left++;
else
right--;
}
return res;
}
};
23、连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int presum=0, maxsum=array[0];
for(int i=0; i< array.size(); i++)
{
presum = presum<0? array[i]:presum+array[i];
maxsum = max(maxsum,presum);
}
return maxsum;
}
};
24、字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
class Solution
{
public:
//Insert one char from stringstream
queue<char> q;
char cnt[257] = {0};
void Insert(char ch)
{
cnt[ch]++;
q.push(ch);
while (!q.empty() && cnt[q.front()] > 1)
q.pop();
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
return q.empty() ? '#' : q.front();
}
};
25、 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
class Solution {
public:
priority_queue<int> left; //left左边是最大堆，堆顶是最大元素
priority_queue<int, vector<int>, greater<int> > right; //右边是最小堆，堆顶是最小元素，且右边元素一定都比左边元素大
//当插入了奇数个元素时，取right的堆顶，插入了偶数个元素时，取左右的堆顶除以2
int N = 0;
void Insert(int num)
{
if (N % 2 == 0) //N为偶数时，插入到右边，因为要保证右边一定大于左边，所以先插到左边，然后从左边取出最大值插入到右边
{
left.push(num);
int leftroot = left.top();
left.pop();
right.push(leftroot);
}
else
{
right.push(num);
int rightroot = right.top();
right.pop();
left.push(rightroot);
}
N++;
}
double GetMedian()
{
if (N % 2 == 0)
return (left.top() + right.top()) / 2.0;
else
return right.top();
}
};
26、最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
class Solution {
public:
struct cmp40
{
bool operator ()(const int a, const int b)
{
return a > b;
}
};
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
//priority_queue<int, vector<int>, less<int>> minmum; //默认是最大堆，用less表示，也可以不写，与下面这种作用相同
//priority_queue<int> minnum;
if (k > input.size() || k <= 0) return res;
priority_queue<int, vector<int>, cmp40> minmum;
for (int i = 0; i < input.size(); i++)
minmum.push(input[i]);
while (k--)
{
//int num = minmum.top();
res.push_back(minmum.top());
//cout << num << " ";
minmum.pop();
}
return res;
}
};
27、数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> num) {
int cnt=1;
int candidate = num[0];
for(int i=1; i<num.size(); i++)
{
cnt = candidate==num[i]?cnt+1:cnt-1;
if(cnt == 0)
{
candidate = num[i];
cnt=1;
}
}
cnt=0;
for(int n:num)
{
if(n==candidate)
cnt++;
}
if(cnt>num.size()/2)
return candidate;
else
return 0;
}
};
28、字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
class Solution {
public:
vector<string> res;
vector<string> Permutation(string str) {
backtracking(str,0);
return res;
}
void backtracking(string str, int k)
{
if ( k == str.length()-1)
res.push_back(str);
sort(str.begin() + k, str.end());
set<char> s;
for (int i = k; i< str.length(); i++)
{
if (s.find(str[i]) == s.end()) //没有找到
{
s.insert(str[i]);
swap(str[k], str[i]);
backtracking(str, k + 1);
swap(str[k], str[i]);
}
}
}
};
29、序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
public class Solution {
String Serialize(TreeNode root) {
if(root==null)
return "#";
return root.val+" "+Serialize(root.left) +" "+Serialize(root.right);
}
String destr;
TreeNode Deserialize(String str) {
destr = str;
return Deserialize();
}
TreeNode Deserialize() {
if(destr.length() == 0)
return null;
int cutloc = destr.indexOf(" ");
String value = cutloc == -1 ? destr: destr.substring(0,cutloc);
destr = cutloc == -1 ? "": destr.substring(cutloc+1);
if(value.equals("#"))
return null;
int val = Integer.valueOf(value);
TreeNode root = new TreeNode(val);
root.left = Deserialize();
root.right = Deserialize();
return root;
}
}
30、二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* pre = NULL;
TreeNode* head = NULL;
TreeNode* Convert(TreeNode* pRootOfTree)
{
InOrder(pRootOfTree);
return head;
}
void InOrder(TreeNode* root)
{
if(root == NULL) return;
InOrder(root->left);
root->left = pre;
if(pre != NULL)
pre->right = root;
pre = root;
if(head == NULL)
head = root;
InOrder(root->right);
}
};
31、复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
//这题的难度在于有个随机指向的指针，并且不能使用原有节点，所以要考虑相对的位置
//因此在各个原有节点的后面复制前面一个，然后随机指针就能同通过相对位置确定，然后将两个链表拆分
if(pHead == NULL) return NULL;
RandomListNode* cur = pHead, *nextnode = NULL;
//在原位置后面复制
while (cur != NULL)
{
RandomListNode* newnode = new RandomListNode(cur->label); //复制前面一个节点
nextnode = cur->next;
cur->next = newnode;
newnode->next = nextnode;
cur = nextnode;
}
//复制随机指针
cur = pHead;
while (cur != NULL)
{
nextnode = cur->next;
if(cur->random != NULL)
nextnode->random = cur->random->next;
cur = nextnode->next; //隔一个跳
}
//拆分两个链表
cur = pHead;
RandomListNode *clone = pHead->next;
while (cur->next != NULL)
{
nextnode = cur->next;
cur->next = nextnode->next;
cur = nextnode;
}
return clone;
}
};
32、二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
class Solution {
public:
vector<vector<int> > res34;
vector<vector<int> > FindPath(TreeNode* root,int key) {
if (root == NULL) return res34;
FindPathing(root, key, vector<int>());
return res34;
}
void FindPathing(TreeNode* root, int key, vector<int> path)
{
if (root == NULL) return;
path.push_back(root->val);
int target = key - root->val;
if (target == 0 && root->left == NULL && root->right == NULL)
res34.push_back(path);
else
{
FindPathing(root->left, target, path);
FindPathing(root->right, target, path);
}
path.pop_back();
}
};
33、二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0) return false;
int left = 0,right = sequence.size()-1;
return Verify(sequence,left,right);
}
bool Verify(vector<int> seq, int left, int right)
{
if(right-left<=1) return true;
int mid = seq[right];
int rlloc=left;
while(left<=right && seq[rlloc] < mid)
rlloc++;
for(int i=rlloc; i<right; i++)
if(seq[i] < mid)
return false;
return Verify(seq,left,rlloc-1) && Verify(seq,rlloc,right-1);
}
};
34、按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
queue<TreeNode*> q;
vector<vector<int> > res;
if (pRoot == NULL) return res;
q.push(pRoot);
int level = 1;
while (!q.empty())
{
int cnt = q.size();
vector<int> temp;
while (cnt--) //cnt为每一层的节点数
{
TreeNode* node = q.front();
q.pop();
temp.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
if(level++ %2 ==1) //正序
res.push_back(temp);
else
{
temp=reverse(temp);
res.push_back(temp);
}
}
/*
for (int i = 0; i < res.size(); i++)
{
for (int num : res[i])
cout << num << " ";
cout << endl;
}*/
return res;
}
vector<int> reverse(vector<int > arrays)
{
vector<int> res;
for(int i=arrays.size()-1;i>=0;i--)
res.push_back(arrays[i]);
return res;
}
};
35、把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
queue<TreeNode*> q;
vector<vector<int> > res;
if(pRoot == NULL) return res;
q.push(pRoot);
while(!q.empty())
{
int cnt = q.size();
vector<int> temp;
while(cnt--)
{
TreeNode* node = q.front();
q.pop();
temp.push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
res.push_back(temp);
}
return res;
}
};
36、从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;
if(root==NULL) return res; //WO CAO! 少了这一行就一直报数组越界的错！
q.push(root);
while (!q.empty())
{
TreeNode* node = q.front();
res.push_back(node->val);
//cout << node->val << " ";
q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
return res;
}
};
37、栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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) {
stack<int> s;
int in=0,out=0;
int len = pushV.size();
for(;in<len,out<len;in++)
{
s.push(pushV[in]);
while(!s.empty() && out<len && s.top() == popV[out])
{
s.pop();
out++;
}
}
return s.empty();
}
};
38、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
class Solution {
public:
stack<int> s;
stack<int> descend;
void push(int value) {
s.push(value);
if(descend.empty())
descend.push(value);
else
descend.push(std::min(value,descend.top()));
}
void pop() {
if(!s.empty())
{
s.pop();
descend.pop();
}
else
return;
}
int top() {
return s.top();
}
int min() {
return descend.top();
}
};
39、顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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 row = matrix.size() - 1, col = matrix[0].size() - 1;
int r = 0, c = 0;
vector<int> res;
while (r <= row && c <= col)
{
for (int i = c; i <= col; i++)
res.push_back(matrix[r][i]);
for (int i = r + 1; i <= row; i++)
res.push_back(matrix[i][col]);
if (r != row)
{
for (int i = col - 1; i >= c; i--)
res.push_back(matrix[row][i]);
}
if (c != col)
{
for (int i = row - 1; i > r; i--)
res.push_back(matrix[i][c]);
}
row--, col--;
r++, c++;
}
return res;
}
};
40、对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL)
return true;
return isSymmetrical(pRoot->left, pRoot->right);
}
bool isSymmetrical(TreeNode* left, TreeNode* right)
{
if(left == NULL || right == NULL) //同为空返回T，一为空一不为空，返回F
return left == right;
if(left->val != right->val)
return false;
return isSymmetrical(left->left, right->right) && isSymmetrical(left->right, right->left);
}
};
41、 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return;
swap(pRoot);
Mirror(pRoot->right);
Mirror(pRoot->left);
}
void swap(TreeNode *pRoot)
{
TreeNode *node = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = node;
}
};
42、 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
class Solution {
public:
bool HasSubtree(TreeNode* s, TreeNode* t)
{
if (s == NULL || t == NULL) return false;
return isSame(s, t) || HasSubtree(s->left, t) || HasSubtree(s->right, t);
}
bool isSame(TreeNode* s, TreeNode* t)
{
if (t == NULL ) return true;
if (s == NULL ) return false;
if (s->val != t->val) return false;
return isSame(s->left, t->left) && isSame(s->right, t->right);
}
};
43、 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* headnode = new ListNode(-1); //新添头结点
ListNode* cur = headnode;
while(pHead1 && pHead2)
{
if(pHead1->val <= pHead2->val)
{
cur->next = pHead1;
pHead1 = pHead1->next;
}
else
{
cur->next = pHead2;
pHead2 = pHead2->next;
}
cur = cur->next;
}
if(pHead1 ==NULL)
cur->next = pHead2;
else
cur->next = pHead1;
return headnode->next;
}
};
44、反转链表
输入一个链表，反转链表后，输出新链表的表头。
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL || pHead->next == NULL)
return pHead;
//翻转链表用相邻的三个节点维护
ListNode* pre = pHead, *cur=pHead, *next = pHead;
while(cur)
{
next = cur->next;
if(cur == pHead)
{
cur->next = NULL;
}
else
{
cur->next = pre;
pre = cur;
}
cur = next;
}
return pre;
}
};
45、链表中环的入口结点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode *fast=pHead,*slow=pHead;
if(fast == NULL || fast->next == NULL) return NULL; //空或只有一个
while(fast->next->next!=NULL )
{
fast = fast->next->next;
slow=slow->next;
if(fast == slow)
break;
}
if(fast->next->next==NULL)
return NULL;
else //找到了环
{
fast = pHead;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
};
46、链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, int k) {
//确定步数差的快慢指针
if (k <= 0) return NULL;
ListNode *fast = pListHead, *slow = pListHead;
while (fast != NULL && k-- > 0)
{
fast = fast->next;
}
if (k > 0)
return NULL;
while (fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
47、调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
class Solution {
public:
void reOrderArray(vector<int> &array) {
int oddnum=0, len=array.size();
vector<int> res(len,0);
for(int i=0;i<len;i++)
{
if(array[i]%2==1)
{
res[oddnum++] = array[i];
}
}
for(int i=0;i<len;i++)
{
if(array[i]%2==0)
{
res[oddnum++] = array[i];
}
}
array = res;
}
};
48、表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
#include <regex>
class Solution {
public:
bool isNumeric(char* string)
{
regex pattern("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
bool res = regex_match(string, pattern);
return res;
}
};
49、 正则表达式匹配
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
class Solution {
public:
bool match(char* str, char* pattern)
{
int len1 = strlen(str), len2 = strlen(pattern);
int i = 0, j = 0;
bool **dp = new bool*[len1 + 1];
//memset(dp, false, (len1 + 1)*(len2 + 1)); //千万不要这样对二维数组初始化！memset只适用于一维连续数组！
for (i = 0; i <= len1; i++)
{
dp[i] = new bool[len2 + 1];
memset(dp[i], false, len2 + 1);
}
dp[0][0] = true;
for (i = 2; i <= len2; i++)
{
if (pattern[i - 1] == '*')
dp[0][i] = dp[0][i - 2];
}
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
{
if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
dp[i][j] = dp[i - 1][j - 1];
else if (pattern[j - 1] == '*')
{
if (str[i-1] == pattern[j - 2] || pattern[j - 2] == '.')
{
dp[i][j] |= dp[i][j - 1] | dp[i - 1][j] | dp[i][j - 2];
//a* counts as single a | multiple a | empty
}
else
dp[i][j] = dp[i][j - 2]; //a* only counts as empty
}
}
}
return dp[len1][len2];
}
};
50、删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead == NULL || pHead->next == NULL) return pHead;
ListNode* cur = pHead;
ListNode* next = pHead->next;
if(pHead->val == next->val)
{
while(next != NULL && pHead->val == next->val )
next = next->next;
return deleteDuplication(next);
}
else{
pHead ->next = deleteDuplication(next);
return pHead;
}
}
};
51、 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class Solution {
public:
double Power(double base, int exponent) {
if (exponent == 0)
return 1;
if(base == 0)
return 0;
if (exponent == 1)
return base;
double pow=0;
bool isPositive = true;
if(exponent < 0)
{
isPositive = false;
exponent = -exponent;
}
pow = Power(base, exponent>>1); //数右移一位在结果上与数除以2等价，但是效率上远胜于除
pow *= pow; //与以前提交的代码相比，尽量避免了递归地操作，能少用递归就少用
if (exponent % 2 == 1)
pow = base * pow;
return isPositive? pow : 1/pow;
}
};
52、二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n)
{
count++;
n &= n-1;
}
return count;
}
};
53、机器人的运动范围
地上有一个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 k, int rows, int cols)
{
if(k<0 || rows<=0 || cols<=0) return 0;
bool *visited = new bool[rows*cols];
memset(visited, 0, rows*cols);
int row=0,col=0,count=0;
return movingCountCore(k,rows,cols,row,col,visited);
}
int movingCountCore(int k, int rows, int cols, int row, int col,bool *visited)
{
int count = 0;
if(row >=0 && col >=0 && row<rows && col <cols && !visited[row*cols+col] && isAccessed(row,col,k))
{
count++;
visited[row*cols+col] = true;
count += movingCountCore(k,rows,cols,row+1,col,visited)+
movingCountCore(k,rows,cols,row-1,col,visited)+
movingCountCore(k,rows,cols,row,col+1,visited)+
movingCountCore(k,rows,cols,row,col-1,visited);
}
return count;
}
bool isAccessed(int row,int col,int k)
{
int rowsum=0,colsum=0;
while(row>0)
{
int a = row/10;
rowsum+=row-a*10;
row = a;
}
while(col>0)
{
int a = col/10;
colsum+=col-a*10;
col = a;
}
if(rowsum+colsum<= k)
return true;
else
return false;
}
};
54、矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(matrix == NULL || rows <= 0 || cols <= 0 || str == NULL) return false;
bool *visited = new bool[rows*cols];
memset(visited,0,rows*cols);
int row= 0,col = 0,pathLen=0;
for(row = 0; row < rows; row++)
for(col = 0; col < cols; col++)
if(hasCorePath(matrix, rows, cols, row, col, str, pathLen, visited))
return true;
return false;
//return true;
}
bool hasCorePath(char* matrix,int rows, int cols, int row, int col, char* str, int pathLen, bool *visited)
{
if(pathLen == strlen(str)) return true;
bool hasPath = false;
if(row<rows && col<cols && row>=0 && col>=0 && matrix[row*cols+col] == str[pathLen] && !visited[row*cols+col])
{
visited[row*cols+col] = true;
pathLen++;
hasPath = hasCorePath(matrix, rows, cols, row-1, col, str, pathLen, visited)||
hasCorePath(matrix, rows, cols, row+1, col, str, pathLen, visited)||
hasCorePath(matrix, rows, cols, row, col-1, str, pathLen, visited)||
hasCorePath(matrix, rows, cols, row, col+1, str, pathLen, visited);
if(!hasPath)
{
visited[row*cols+col] = false;
pathLen--;
}
}
return hasPath;
}
};
55、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution {
public:
//11、旋转数组的最小值
int minNumberInRotateArray(vector<int> nums) {
if (nums.size() == 0) return 0;
int right = nums.size() - 1, left = 0, mid = 0;
return seqfind(nums, left, right);
while (nums[left] >= nums[right])
{
if (right - left == 1)
{
return nums[right];
}
mid = (right + left) / 2;
if (nums[mid] >= nums[left]) //左边递增（非减），则在右边
{
left = mid;
}
else if (nums[mid] <= nums[right]) //左边递增（非减），则在左边
{
right = mid;
}
else if (nums[mid] == nums[left] && nums[mid] == nums[right])
{
return seqfind(nums, left, right);
}
}
return nums[left];
}
int seqfind(vector<int> nums, int left, int right)
{
int res = nums[0];
for (int i = left + 1; i <= right; i++)
if (res > nums[i])
return nums[i];
return res;
}
};
56、矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution {
public:
int rectCover(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int prepre=1, pre=1, res = 0;
for(int i = 2; i <= n; i++)
{
res = prepre+pre;
prepre = pre;
pre = res;
}
return res;
}
};
57、变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
class Solution {
public:
int jumpFloorII(int n) {
vector<int> num(n+1, 0);
num[0] = 1;
num[1] = 1;
for (int i = 2; i <= n; i++)
{
for(int j=0; j<i; j++)
num[i] += num[j];
}
return num[n];
}
};
58、跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
class Solution {
public:
int jumpFloor(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
int prepre=1, pre=1, res = 0;
for(int i = 2; i <= n; i++)
{
res = prepre+pre;
prepre = pre;
pre = res;
}
return res;
}
};
59、斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
class Solution {
public:
int Fibonacci(int n) {
/*
if(n == 1) return 1;
if(n == 0) return 0;
return Fibonacci(n-1)+Fibonacci(n-2);
*/
/*
vector<int> num(n+1, 0);
num[0] = 0;
num[1] = 1;
for (int i = 2; i <= n; i++)
{
num[i] = num[i - 1] + num[i - 2];
}
return num[n];
*/
if(n == 0) return 0;
if(n == 1) return 1;
int prepre=0, pre=1, res = 0;
for(int i = 2; i <= n; i++)
{
res = prepre+pre;
prepre = pre;
pre = res;
}
return res;
}
};
60、用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty())
{
while(!stack1.empty())
{
int value = stack1.top();
stack1.pop();
stack2.push(value);
}
}
if(stack2.empty()) return -1;
else
{
int value = stack2.top();
stack2.pop();
return value;
}
}
private:
stack<int> stack1;
stack<int> stack2;
};
61、 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (pNode == NULL) return NULL;
if (pNode->right != NULL) //往右子树的最左边找，右子树不为空，那么右子树的最左边就是下一个节点
{
TreeLinkNode* node = pNode->right;
while (node->left != NULL)
node = node->left;
return node;
}
while (pNode->next != NULL) //右子树为空, 那么一直往上寻找，直到找到某个节点是他父节点的左节点
{
TreeLinkNode* node = pNode->next;
if (node->left == pNode)
return node;
pNode = pNode->next;
}
return NULL;
}
};
62、重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return constructBT(pre,0,pre.size()-1,vin,0,vin.size()-1);
}
TreeNode* constructBT(vector<int> pre,int pl,int pr, vector<int> vin, int ml,int mr)
{
if (pl > pr || ml > mr) return NULL;
else
{
TreeNode *root = new TreeNode(pre[pl]);
for (int loc = ml; loc <= mr; loc++)
{
if (vin[loc] == pre[pl])
{
int len = loc - ml;
root->left = constructBT(pre, pl + 1, pl + len, vin, ml, loc - 1);
root->right = constructBT(pre, pl + len + 1, pr, vin, loc + 1, mr);
break;
}
}
return root;
}
}
};
63、从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> nums;
vector<int> res;
ListNode* cur = head;
while (cur)
{
nums.push(cur->val);
cur = cur->next;
}
while (!nums.empty())
{
res.push_back(nums.top());
nums.pop();
}
return res;
}
};
64、 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str,int length) {
int count = 0;
for (int i = 0; i<strlen(str); i++)
if (str[i] == ' ')
count++;
int newlen = strlen(str) + count * 2;
if (newlen > length) return;
str[newlen] = '\0';
int j = newlen-1;
for (int i = strlen(str) - 1; i >= 0; i--)
{
if (str[i] == ' ')
{
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
}
else
{
str[j--] = str[i];
}
}
cout << str << endl;
}
};
65、二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row=0,col=array[0].size()-1; //右上角
while(row<array.size() && col>=0) //左下角
{
if(target <array[row][col])
col--;
else if(target > array[row][col])
row++;
else
return true;
}
return false;
}
};
66、数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int nums[], int length, int* duplication) {
for(int i=0; i<length; i++)
{
while(nums[i] != i)
{
if(nums[i] != nums[nums[i]])
swap(&nums[i],&nums[nums[i]]);
else
{
*duplication = nums[i];
return true;
}
}
}
return false;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
};
网友评论