1.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身
思路：利用递归，如果当前结点 root等于NULL，则直接返回NULL；如果 root 等于 p 或者 q ，那这棵树一定返回p 或者q；然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用left 和 right表示；此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left；如果 left 和 right都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先如果 left 和 right 都为空，则返回空。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr) return nullptr;
if(root==p||root==q) return root;
TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
if(left==nullptr) return right;
if(right==nullptr) return left;//一个为空的话，另一个就是公共祖先
if(left&&right)
{
return root;//都非空的话，此时p,q分别位于最大的左右子树
}
return nullptr;
}
};2.字符串的序列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：循环里套递归，得到所有排列组合，注意当放入一个字符串时，要判断当前结果数组里有没有这个字符串。
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> result;
if(str.empty()) return result;
exChange(str,result,0);
sort(result.begin(),result.end());
return result;
}
void exChange(string str,vector<string> &result,int begin)
{
if(begin==str.size()-1)
{
if(find(result.begin(),result.end(),str)==result.end())
{
result.push_back(str);//不重复的放进去
}
}
else
{
for(int i=begin;i<str.size();i++)
{
swap(str[i],str[begin]);
exChange(str,result,begin+1);//递归排列剩下的序列
swap(str[i],str[begin]);//换回来再换回去
}
}
}
void swap(char &x,char &y)
{
char z;
z=x;
x=y;
y=z;
}
};3.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：从头开始遍历，首先记录第一个数，记出现次数为1，如果下一个数等于它，则次数++，如不等于，则次数--。当次数为0时，开始设置记录下一个数，扔记出现次数为1.最后计算剩下的数字在数组中出现的次数，如大于1/2数组长度，返回这个数；否则，数组内没有出现次数超过一半的数字。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int len=numbers.size();
if(len==0) return 0;
int res=numbers[0];
int count=1;
for(int i=1;i<len;i++)
{
if(numbers[i]==res)
{
count++;//相等，次数+1
}
else
{
count--;//不等，次数-1
}
if(count==0)
{
res=numbers[i];
count=1;//重新记录下一个数
}
}
count=0;
for(int i=0;i<len;i++)
{
if(numbers[i]==res)
{
count++;//记录最后剩下的数在数组中出现的总次数
}
}
return count*2>len?res:0;
}
};4.最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：基于快速排序。随机生成一个index，如果这个index等于k-1，说明此数包括前面的数正好是最小的k个数。（因为快排，index前面的数都小于它，后面的数都大于它）。
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
int len=input.size();
if(len<=0||k<=0||k>len) return res;
int start=0;
int end=len-1;
int index=Partition(input,len,start,end);
while(index!=k-1)
{
if(index>k-1)//说明最小的k个数字在前面
{
end=index-1;
index=Partition(input,len,start,end);
}
else//说明最小的k个数字在后面
{
start=index+1;
index=Partition(input,len,start,end);
}
}//直到index为k时，此时前k个数就是最小的k个数
for(int i=0;i<k;i++)
res.push_back(input[i]);
return res;
}
int Partition(vector<int> &numbers,int length,int start,int end)//快排核心函数
{
if(length<=0||start<0||end>=length)
return false;
int index=RandomInRange(start,end);
Swap(&numbers[index],&numbers[end]);//随机生成一个点，与尾结点互换
int small=start-1;
for(index=start;index<end;index++)
{
if(numbers[index]<numbers[end])
{
++small;
if(small!=index)
Swap(&numbers[index],&numbers[small]);//说明small与index之间有大于end下标的数字，把小于数组尾的数放到前面
}
}
++small;
Swap(&numbers[small],&numbers[end]);
return small;//small前面，都小于它，后面都大于它
}
int RandomInRange(int start,int end)
{
srand (time(NULL));
return rand() % (end-start+1) + start;//随机数函数
}
void Swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
};PS：快速排序代码
void QuickSort(int data[],int length,int start,int end)
{
if(start==end)
return;//终止条件
int index=Partition(data,length,start,end);
if(index>start)
{
QuickSort(data,length,start,index-1);
}
if(index<end)
{
QuickSort(data,length,index+1,end);
}
}
京公网安备 11010502036488号