1.二维数组中的查找在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
由题可知，右边的值比左边的大，下面的值比上面的大。如果从左上角开始，当前值比目标值小那么就应该向下或向右移动，可是如果向右移动了一格左边所有的数就被遗漏了，向下同理。适当的方式应该是从左下角或者右上角开始，以左下角为例，如果当前值比目标值小，就向右移动，比目标值大，向上移动。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if(array.empty())
return false;
else if(array[0].empty())
return false;
int i=array.size()-1;
int j=0;
while(1){
if(array[i][j]==target)
return true;
else if(array[i][j]<target){
j++;
}
else
i--;
if(i<0||j>array[0].size()-1)
return false;
}
}
};
2.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：创建一个新的字符串，遍历原字符串如果遇到字符加入字符，遇到空格加入%20
string replaceSpace(string s) {
string ns;
for(int i=0;i<s.length();i++){
if(s[i]==' ')
ns+="%20";
else
ns+=s[i];
}
return ns;// write code here
}
3.从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：把链表节点压入栈
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> s;
vector<int> v;
ListNode* p=head;
while(p){
s.push(p->val);
p=p->next;
}
while(!s.empty()){
v.push_back(s.top());
s.pop();
}
return v;
}
};
4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：根据遍历序列的关系，前序序列确定根节点，到后序遍历去找到对应索引，根节点以前的是左子树的节点，后面是右子树的节点。截取遍历序列，递归调用建立左右子树。
class Solution {
private:
int preIndex;
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty())
return NULL;
int head=pre[0];
int headIdexInVin=find(head,vin);
vector<int> leftPre(pre.begin()+1,pre.begin()+headIdexInVin+1);
vector<int> leftVin(vin.begin(),vin.begin()+headIdexInVin);
vector<int> rightPre(pre.begin()+headIdexInVin+1,pre.end());
vector<int> rightVin(vin.begin()+headIdexInVin+1,vin.end());
TreeNode* tn=new TreeNode(head);
tn->left=reConstructBinaryTree(leftPre,leftVin);
tn->right=reConstructBinaryTree(rightPre, rightVin);
return tn;
}
int find(int target,const vector<int>& v){
for(int i=0;i<v.size();i++){
if(target==v[i])
return i;
}
return -1;
}
};
5.用两个栈实现一个队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：stack1，stack2，push操作直接压入stack1，pop的时候判断stack2是否为空，如果为空先将stack1的全部元素pop，再push到stack2中，然后stack2pop顶层元素。否则，直接弹出stack2顶层元素
class Solution {
private:
int preIndex;
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty())
return NULL;
int head=pre[0];
int headIdexInVin=find(head,vin);
vector<int> leftPre(pre.begin()+1,pre.begin()+headIdexInVin+1);
vector<int> leftVin(vin.begin(),vin.begin()+headIdexInVin);
vector<int> rightPre(pre.begin()+headIdexInVin+1,pre.end());
vector<int> rightVin(vin.begin()+headIdexInVin+1,vin.end());
TreeNode* tn=new TreeNode(head);
tn->left=reConstructBinaryTree(leftPre,leftVin);
tn->right=reConstructBinaryTree(rightPre, rightVin);
return tn;
}
int find(int target,const vector<int>& v){
for(int i=0;i<v.size();i++){
if(target==v[i])
return i;
}
return -1;
}
};
6.旋转数组中的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：1.如果有当前节点大于后一节点，那么后节点就是最小节点，否则第一个节点最小O(n)
2.二分查找，旋转数组中，有两组非递减数组，第一组所有元素都大于（除非全等）整个数组中的最后元素，第二组都小于等于最后元素。二分查找，用中间元素与最后的元素对比，如果中间元素大，则最小元素在中间元素右边，否则在中间元素左边，或者是他本身。O(logn)
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0)
return 0;
for(int i=0;i<(rotateArray.size()-1);i++){
if(rotateArray[i]>rotateArray[i+1])
return rotateArray[i+1];
}
return rotateArray[0];
}
};
7.斐波那契数列
要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。
思路：菲波那切数列：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
递归，或者动态规划的存储值的方式（这里两个变量就够了）
class Solution {
public:
int Fibonacci(int n) {
vector<int> v(n+1,-1);
return Fib(v,n);
}
int Fib(vector<int>& v,int n){
if(n<2)
return n;
else if(v[n]!=-1)
return v[n];
else{
return v[n]=Fib(v,n-1)+Fib(v,n-2);
}
}
};
8.跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：同样的递归，或者存储值，跳上n级台阶，分两种情况，1.最后一步跳了一级2.最后一步跳了两级
f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2
class Solution {
public:
int jumpFloor(int number) {
vector<int> v(number+1,-1);
return jump(v,number);
}
int jump(vector<int>& v,int number){
if(number<=2)
return v[number]=number;
else if(v[number]!=-1)
return v[number];
else
return v[number]=jump(v,number-1)+jump(v,number-2);
}
};
9.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：跟上面思路差不多，最后一步可以是跳了1，2，3，4...n
f(n)=f(n-1)+f(n-2)...f(0),f(n-1)=f(n-2)...f(0),f(n)=2f(n-1)
f(0)=0,f(1)=1,f(2)=2
int jumpFloorII(int number)
{
if(number<=2)
return number;
else
return 2*jumpFloorII(number-1);
}
10.矩阵覆盖
我们可以用2* 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2* 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：n的时候，最后一步可以是横着放f(n-1),竖着放f(n-2)
f(n)=f(n-1)+f(n-2)
如果改一下题，可以用21,23的小矩阵，那么最后一步就有三种了，f(n)=f(n-1)+f(n-2)+f(n-3)
class Solution {
public:
int rectCover(int number) {
if(number<=2)
return number;
else return rectCover(number-1)+rectCover(number-2);
}
};
11.二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。例如，9表示1001，因此输入9，输出2。
思路：1.定义一个数从1，2，4，8，去跟这个整数做&操作
2.任何非零的数都至少有一个1，n=n&(n-1)可以消除n最右边的1，当全部消除n就等于0
class Solution {
public:
int NumberOf1(int n) {
int num=0;
while(n){
n=n&(n-1);
num++;
}
return num;
}
};
12.数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路：需要特别考虑base=0,exponent=0,exponent<0的情况
其他的直接连乘或者递归就可以了
class Solution {
public:
double Power(double base, int exponent) {
if(base==0)
return 0;
else if(exponent==0)
return 1;
else if(exponent<0)
return 1/(Power(base,-exponent-1)*base);
else
return Power(base,exponent-1)*base;
}
};
13.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：1.两个数组，一个放奇数一个放偶数，最后连起来
2.两个指针，i指向第一个偶数，j指向i之后的第一个奇数，两个作交换
vector<int> reOrderArray(vector<int>& array) {
// write code here
vector<int> vo;
vector<int> vj;
for(int i=0;i<array.size();i++){
if(array[i]%2==1)
vj.push_back(array[i]);
else
vo.push_back(array[i]);
}
for(int i=0;i<vo.size();i++){
vj.push_back(vo[i]);
}
return vj;
}
14.链表中的倒数第K个节点
输入一个链表，输出该链表中倒数第k个结点。
思路：快慢指针，j指向i后面的第k个，当j到结尾的时候，i就是倒数第k个
ListNode* FindKthToTail(ListNode* pHead, int k) {
// write code here
if(!pHead)
return NULL;
ListNode* p=pHead,*q=pHead;
int n=k-1;
while(n--){
q=q->next;
if(!q)
return NULL;
}
while(q->next!=NULL){
p=p->next;
q=q->next;
}
return p;
}
15.反转链表
输入一个链表，反转链表后，输出新链表的表头。
思路：主要是首尾的处理比较麻烦
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(!pHead)
return NULL;
else if(!(pHead->next)){
return pHead;
}
else{
ListNode *p=pHead,*q=pHead->next,*r=pHead->next->next;
while(r){
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;
pHead->next=NULL;
pHead=q;
return pHead;
}
}
};
16.合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：维护一个已连接链表，pq分别指向两个链表还未连接的头，不断加入pq指向的节点中小的节点
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* head,* tail,*p,*q;
p=pHead1;
q=pHead2;
if(p==NULL&&q==NULL)
return NULL;
else if(p==NULL)
return q;
else if(q==NULL)
return p;
if((p->val)>(q->val)){
head=q;
q=q->next;
}
else{
head=p;
p=p->next;
}
tail=head;
while(p!=NULL&&q!=NULL){
if((p->val)>(q->val)){
tail->next=q;
tail=q;
q=q->next;
}
else{
tail->next=p;
tail=p;
p=p->next;
}
}
if(p==NULL){
tail->next=q;
}
if(q==NULL){
tail->next=p;
}
return head;
}
};
17.树的子结构输入两棵二叉树A，B，判断B是不是A的子结构。（空树不是任意一个树的子结构）
思路：定义一个包含关系，A包含B，A与B头节点相等且A的左右子树分别包含B的左右子树
B是A的子结构，要满足，A包含B或者，A的子树包含B，直接看代码比较容易理解
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(!pRoot1||!pRoot2)
return false;
if(Baohan(pRoot1,pRoot2))
return true;
if(HasSubtree(pRoot1->left,pRoot2))
return true;
if(HasSubtree(pRoot1->right,pRoot2))
return true;
return false;
}
bool Baohan(TreeNode* pRoot1,TreeNode* pRoot2){
if(!pRoot2)
return true;
if(!pRoot1&&pRoot2)
return false;
if(pRoot1->val!=pRoot2->val)
return false;
if(!Baohan(pRoot1->left,pRoot2->left))
return false;
if(!Baohan(pRoot1->right,pRoot2->right))
return false;
return true;
}
};
18.二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
思路：递归，交换左右子树指针
TreeNode* Mirror(TreeNode* pRoot) {
if(pRoot==NULL)
return NULL;
else if(pRoot->left==NULL&&pRoot->right==NULL)
return pRoot;
else if(pRoot->left==NULL)
{
pRoot->left=pRoot->right;
pRoot->right=NULL;
Mirror(pRoot->left);
return pRoot;
}
else if(pRoot->right==NULL)
{
pRoot->right=pRoot->left;
pRoot->left=NULL;
Mirror(pRoot->right);
return pRoot;
}
else{
TreeNode* temp;
temp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=temp;
Mirror(pRoot->left);
Mirror(pRoot->right);
return pRoot;
}
// write code here
}
19.顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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) {
if(matrix.size()==0)
return vector<int>();
if(matrix[0].size()==0)
return vector<int>();
deque<deque<int>> q;//把vector转为deque
for(auto &i:matrix){
auto b=i.begin();
auto e=i.end();
deque<int> d(b,e);
q.push_back(d);
}
vector<int> v;
while(1){
for(auto i:q.front()){
v.push_back(i);
}
q.pop_front();
if(q.empty())
return v;
q=Rotate(q);
}
}
deque<deque<int>> Rotate(deque<deque<int>>& q){
deque<deque<int>> dq;
for(int j=q[0].size()-1;j>=0;j--){
deque<int> d;
for(int i=0;i<q.size();i++){
d.push_back(q[i][j]);
}
dq.push_back(d);
}
return dq;
}
};
20.包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：维护两个stack，stack1正常存取，stack2存入当前顶层元素和目标元素的小的那个（stack2其实每层存的是stack1中这层以及它下面的层里最小的那个），看图方便理解
class Solution {
public:
void push(int value) {
s1.push(value);
int minValue=s2.empty()?value:std::min(s2.top(),value);
s2.push(minValue);
}
void pop() {
s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int min() {
return s2.top();
}
private:
stack<int> s1;
stack<int> s2;
};
21.栈的压入、弹出
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：构造一个stack用于模拟过程，按压入序列向stack压入直到遇到弹出序列顶端元素，弹出该元素，并且弹出序列指针后移，最后如果压入序列都完了stack里还有就返回false，否则返回true
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> s;
int i=0,j=0;
while(j<popV.size()){
if(s.empty()||s.top()!=popV[j])
{
if(i>=pushV.size())
return false;
else{
s.push(pushV[i]);
i++;
}
}
else{
s.pop();
j++;
}
}
return true;
}
};
22.从上到下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：二叉树的层序遍历，用queue
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> v;
queue<TreeNode*> q;
TreeNode* p;
p=root;
q.push(p);
while(!q.empty()){
p=q.front();
q.pop();
if(p){
v.push_back(p->val);
q.push(p->left);
q.push(p->right);
}
}
return v;
}
};
23.二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：跟前面的前中序差不多，递归，后序遍历序列最后是根节点，小于根节点的是左子树，大于的是右子树
24.二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路：先序递归遍历，维护一个路径数组(vector)每访问一个节点就将其加入数组，同时维护一个sum值，如果等于指定值，将当前路径数组保存，然后弹出数组最后元素。
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<int> v;
addV(v,root,expectNumber);
return vout;
}
void addV(vector<int> &v,TreeNode* root,int expectNumber){
if(!root)
return;
if(!root->left&&!root->right)
{
v.push_back(root->val);
int sum=Sum(v);
if(sum==expectNumber){
vout.push_back(v);
}
v.pop_back();
return;
}
v.push_back(root->val);
addV(v,root->left,expectNumber);
addV(v,root->right,expectNumber);
v.pop_back();
}
int Sum(vector<int>& v){
int sum=0;
for(int i=0;i<v.size();i++){
sum+=v[i];
}
return sum;
}
private:
vector<vector<int>> vout;
};
25.复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
暂无
26.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：中序遍历
27.字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
28.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：１.先排序，如果存在中间那个元素就是这个数。２.或者为每个数字建立一个桶（哈希表），每访问到该元素，数目加一，最后遍历。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
quick_sort(numbers,0,numbers.size()-1);
int count=0;
int target=numbers[numbers.size()/2];
for(auto &i:numbers){
if(i==target)
count++;
}
if(count>numbers.size()/2)
return target;
else
return 0;
}
void quick_sort(vector<int>& numbers,int left,int right){
if(right<=left)
return;
int pivot=numbers[left];
int i=left,j=right+1;
while(1){
while(numbers[++i]<pivot&&i<=right);
while(numbers[--j]>pivot&&j>=left);
if(i>j)
break;
swap(numbers[i],numbers[j]);
}
swap(numbers[left],numbers[j]);
quick_sort(numbers,left,j-1);
quick_sort(numbers,j+1,right);
}
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
};
29.最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：１.排序２.建立ｋ个数最大堆，保证了这ｋ个数不超过顶部元素大小，如果外边有更小的数，就赋给堆顶元素，再对堆进行调整。
30.连续子数组的最大和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路：１.动态规划，定义f(n)为以第n个元素为终止的最大子序列和，f(n)=min(f(n-1)+n,n),如果f(n-1)小于0，f(n)=n
2.用一个局部和(local_sum)，和一个全局和(global_sum)来寻找，局部和保证了子序列和不小于0，全局和保存当前遇到的最大的局部和。
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int local_sum=0,global_sum=0;
int maxN=array[0];
for(auto i:array){
if(i>maxN)
maxN=i;
}
if(maxN<0)
return maxN;
for(int i=0;i<array.size();i++){
local_sum=max(local_sum+array[i],0);
global_sum=max(local_sum,global_sum);
}
return global_sum;
}
};
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
vector<int> dp(array.size());
dp[0]=array[0];
int maxSum=dp[0];
for(int i=1;i<array.size();i++){
dp[i]=max(dp[i-1],0)+array[i];
maxSum=max(maxSum,dp[i]);
}
return maxSum;
}
};
