数组中重复的数字 二维数组中查找 字符串 替换空格 二叉树的编码和解码 从尾到头打印链表 重建二叉树 二叉树的下一个节点 2个栈实现队列 斐波那契数列 旋转数字 矩阵中的路径 机器人的运动范围 剪绳子 二进制表示中1的个数 数值的整数次方 打印1到最大的n位数 在O(1)时间删除链表结点 删除链表中重复的结点 正则表达式匹配 表示数值的字符串 调整数组顺序使奇数位于偶数前面 链表中倒数第k个结点 一个链表中包含环，如何找出环的入口结点 反转链表 合并两个排序链表 输入两棵二叉树A，B，判断B是不是A的子结构(注意：是子结构，不是子树) 操作给定的二叉树，将其变换为源二叉树的镜像 判断二叉树是不是对称二叉树 顺时针打印矩阵 栈的压入、弹出序列 从上往下打印二叉树 Z打印二叉树 二叉树搜索的后序遍历序列 二叉树中和为某一值的路径 复杂链表的复制 二叉搜索树与双向链表 序列化二叉树 字符串的排列 数字出现的次数超过数组长度的一半 最小的k个数 数据流中的中位数 连续子数组的最大和 整数中1出现的次数 数字序列中某一位的数字 把数组排成最小的数 把数字翻译成字符串 最大价值的礼物 最长不含重复字符的子字符串 丑数 第一次只出现一次的字符的索引 字符流中第一个不重复的字符【不是求索引】 数组中的逆序对 两个链表的第一个公共结点 数字在排序数组中出现的次数 0-n-1中缺失的数字 二叉搜索树中第K小的元素 二叉树的深度 判断是否为平衡二叉树 数组中只出现一次的两个数字 数组中只出现一次的两个数字2 和为S的两个数 和为S的连续正数序列 翻转字符串 leetcode(151) 左旋转字符串 滑动窗口最大值 队列最大值 n个骰子的点数 扑克牌中的顺子 圆圈中最后剩下的数字 股票的最大利润 求1+2+3…+n 求两个整数之和 构建乘积数组 最低公共节点
数组中重复的数字
/*
第三题：数组中重复的数字
[2 3 1 0 2 5 3] 为 2或者3
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
*/
class class_3{
bool duplicate(int numbers[],int length,int *dup)
{
if(numbers==nullptr||length<=){
return false;
}
for (int i=; i<length; i++) {
if(numbers[i]>=length||numbers[i]<){
return false;
}
}
for (int i=; i<length; i++) {
while (i!=numbers[i]) { if(numbers[i]==numbers[numbers[i]]){
*dup=numbers[i];
return true;
} int temp=numbers[i];
numbers[i]=numbers[temp];
numbers[temp]=temp;
} }
return false;
}
};
二维数组中查找
/*
第四题：二维数组中查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
class class_2{
bool FindErWEi(vector<vector<int>>&matrix,int target)
{
bool found=false;
int row=;
int column=(int)matrix[].size()-;
while (row<matrix.size()&&column>=) {
if(matrix[row][column]==target){
found=true;
break;
}
else if(matrix[row][column]<target){
row++;
}
else{
column--;
}
}
return found;
}
};
字符串 替换空格
/*
第五题：字符串 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
注："a"和’a’的区别，前者是字符串，后者是字符。
思路：从后往前复制
*/
class class_5{
void ReplaceBlank(char string[],int length){ if(string==NULL||length<=)
{
return;
} int blankLen=;
int originLen=;
int i=;
while (string[i]!='\0') {
originLen++;
if(*string==' '){
blankLen++;
}
i++; }
int newLength=blankLen*+originLen;
if(newLength>length){
return;
}
int indexOfOrigin=originLen;
int indexOfNew=newLength;
//indexOfNew和indexOfOrigin相等就可以结束拷贝了，不加这个条件也是可以的
while (indexOfOrigin>=&&indexOfNew>indexOfOrigin) { if(string[indexOfOrigin]==' '){
string[indexOfNew--]='';
string[indexOfNew--]='';
string[indexOfNew--]='%';
}
else{
string[indexOfNew--]=string[indexOfOrigin];
} indexOfOrigin--;
} }
};
二叉树的编码和解码
/*
第六题：
二叉树的编码和解码
*/
class class_6{
//二叉树编解码
typedef struct TreeNode{
string val;
TreeNode *left;
TreeNode *right;
TreeNode(string x):val(x),left(NULL),right(NULL){}
} TreeNode; //二叉树的编码
void BianMa(TreeNode *root,string &ss){ if(root==NULL){
ss+="#_";
return;
}
string value=root->val;
ss+=value+"_"; BianMa(root->left, ss);
BianMa(root->right, ss);
}
//创建新的节点（忽略释放）
TreeNode *getNewNode(string s){
TreeNode *node=new TreeNode(s);
return node;
}
//递归前序插入节点
void insertNode(TreeNode* &root,vector<string>&ss,int &i){ if(i==ss.size()){
return;
}
string node=ss[i];
if(node=="#"){
root=NULL;
}
else{
if(root==NULL){
root= getNewNode(node);
}
else{
root->val=node;
}
i=i+;
insertNode(root->left, ss, i);
i=i+;
insertNode(root->right, ss, i);
} } //二叉树解码
void jiema(TreeNode *root,string &ss){ vector<string>sss;
string temp;
for (int i=; i<ss.length(); i++) {
if(ss[i]=='_'){
sss.push_back(temp);
temp="";
}
else{
temp+=ss[i];
}
}
int i=;
insertNode(root, sss, i); }
};
从尾到头打印链表
/*
第七题：从尾到头打印链表
方法1:用栈
方法2:递归
*/
class class_7{
struct Node{
Node * next;
int val;
};
//1->2->3
void PrintListReversingly(Node *head){
if(head){
if(head->next){
PrintListReversingly(head->next);
}
printf("%d ",head->val);
} }
};
重建二叉树
/*
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
*/
class class_7_2{ struct BinaryTreeNode{
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
int m_nValue;
};
BinaryTreeNode *Construct(int *preorder,int * inorder,int length){
if(preorder==nullptr||inorder==nullptr||length<=){
return nullptr;
}
return ConstructCore(preorder, preorder+length-, inorder, inorder+length-); }
BinaryTreeNode * ConstructCore(int *startPreorder,int *endPreorder,int *startInorder,int *endInorder){
int rootValue=startInorder[];
BinaryTreeNode *root=new BinaryTreeNode();
root->m_nValue=rootValue;
root->m_pLeft=NULL;
root->m_pRight=NULL; //边界条件 左边或者右边只剩下一个元素
if(startPreorder==endPreorder){
if(startInorder==endInorder){
if(*startPreorder==*startInorder){
return root;
}
else{
return NULL;//无效的输入
}
}
} //前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} //中序遍历找到跟节点
int *rootInorder=startInorder;
while (rootInorder<endInorder&&*rootInorder!=rootValue) {
++rootInorder;
}
if(rootInorder==endInorder&&*rootInorder!=rootValue){
return NULL;//无效输入. 没找到
}
//找出来的 *rootInorder =1
//划分左右子树，然后递归
int leftLength=(int)(rootInorder-startInorder);
int *leftPreorderEnd=startPreorder+leftLength; //存在左子树
if(leftLength>){
root->m_pLeft=ConstructCore(startPreorder+, leftPreorderEnd, startInorder, rootInorder-);
}
//看看是否存在右子树
//比较左子树的长度和总长度是否一样就可以
if(leftLength<endPreorder-startPreorder){
root->m_pRight=ConstructCore(leftPreorderEnd+, endPreorder, rootInorder+, endInorder);
}
return root;
}
};
二叉树的下一个节点
/*
第八题：二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分三种情况：
1 节点有右子树，那么下一个节点就是右子树中最左的节点
2 节点没有右子树，但是是父节点的左子树，下一个就是父亲节点
3 节点没有右子树，并且是父亲节点的右节点，下一个节点就是，从当前节点一直找他的父节点，直到找到的某个父节点是 他 父亲节点的左子树，那么 某个父节点的父亲节点，就是下一个节点
*/
class class_8{
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode* m_pParent;
};
BinaryTreeNode *GetNext(BinaryTreeNode*node){
if(node==nullptr){
return nullptr;
}
BinaryTreeNode *pNext=nullptr;
if(node->m_pRight){//情况一
BinaryTreeNode *pRight=node->m_pRight;
while (pRight->m_pLeft) {
pRight=pRight->m_pLeft;
}
pNext=pRight;
}
//没有右子树
else if(node->m_pParent){
//父节点是自己的左子树
BinaryTreeNode *pCurrent=node;
BinaryTreeNode *pParent=node->m_pParent;
if(pParent->m_pLeft==pCurrent){
pNext=pParent;
}
else{
//一直找，直到找到左子树的情况
while (pParent&&pCurrent==pParent->m_pRight) {
pCurrent=pParent;
pParent=pParent->m_pParent;
}
pNext=pParent;
}
}
return pNext;
} };
2个栈实现队列
/*
第九题：2个栈实现队列
*/
/*
方法一：临时栈方式，时间浪费在 push
*/
class class_9{
public:
class_9(){}
void push(int x){
std::stack<int>temp_stack;
while (!_data.empty()) {
temp_stack.push(_data.top());
_data.pop();
}
temp_stack.push(x);
while (!temp_stack.empty()) {
_data.push(temp_stack.top());
temp_stack.pop();
}
}
int pop(){
int x=_data.top();
_data.pop();
return x;
}
int peek(){
return _data.top();
}
bool empty(){
return _data.empty();
}
private:
std::stack<int>_data;
};
/*
方法二：双栈法
*/
class class_9_2 {
public:
class_9_2(){}
void push(int x){
_input.push(x);
}
int pop(){
adjust();
int x = _output.top();
_output.pop();
return x;
}
int peek(){
adjust();
return _output.top();
}
bool empty(){
return _input.empty() && _output.empty();
}
private:
void adjust(){
if(!_output.empty()){
return;
}
while (!_input.empty()) {
_output.push(_input.top());
_input.pop();
}
}
stack<int>_input;
stack<int>_output;
};
斐波那契数列
/*
第十题： 斐波那契数列
方法一：采用递归 方法二：动态规划
*/
class class_10 {
int Mehotd1(int n){
if(n==||n==){
return n;
}
return Mehotd1(n-)+Mehotd1(n-);
}
int Method2(int n){
vector<int>dp(n+,);
dp[]=;
dp[]=;
for (int i=; i<=n; i++) {
dp[i]=dp[i-]+dp[i-];
}
return dp[n];
}
};
旋转数字
/*
第十一题
旋转数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 1 5 7 10 15 22 30=> 7 10 15 22 30 1 5 此解法可以处理元素相同的情况，比如 [3，3，3，1]
*/
class class_11{
int minInOrder(vector<int>&nums,int begin,int end){
int result = nums[begin];
for (int i=begin+; i<=end; i++) {
if(result>nums[i]){
result = nums[i];
}
}
return result;
}
int getXuanZhuanMin(vector<int>&nums){
/*
考虑特殊情况
*/
if(nums.size()==){
return ;
}
if(nums.size()==){
return nums[];
}
if(nums[]<nums[nums.size()-]){
return nums[];
}
//
int begin=;
int end=(int)nums.size()-;
while (begin<=end) { int mid=(begin+end)/;
if(end-begin==){
mid=end;
return nums[mid];
}
//特殊情况
//如果下标为 begin，end，mid指向的三个数字相等，只能顺序查找
if(nums[begin]==nums[end]&&nums[begin]==nums[mid]){
return minInOrder(nums, begin, end);
}
//递增数组在前，旋转数组在后，最小值在后面
if(nums[begin]<=nums[mid]){ //7 10 15 22 30 1 5
begin=mid;
}
//递增数组在后，旋转数组在前，最小值在前面
else if(nums[begin]>=nums[mid]){ //22 30 1 5 7 10 15
end=mid;//
} }
return ;
}
};
矩阵中的路径
/*
第12题
矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路： 回溯法
*/
class class_12{
bool hasPathCore(const char *matrix,int rows,int cols,int row,int col,const char *str,int &pathLength,bool *visited){
if(str[pathLength]=='\0'){
return true;
}
bool hasPath=false;
if(row >= && row < rows && col >= && col < cols
&& matrix[row * cols + col] == str[pathLength]
&& !visited[row * cols + col]){ ++pathLength;
visited[row*cols+col]=true;
//循环遍历四个邻居
int rowN[]={,,-,};
int colN[]={-,,,};
for (int i=; i<; i++) {
hasPath= hasPathCore(matrix, rows, cols, row+rowN[i], col+colN[i], str, pathLength, visited);
if(hasPath==true){
return hasPath;
}
}
if(!hasPath){//四个角都没找到，回溯
pathLength--;
visited[row * cols + col]=false;
} }
return hasPath;
}
bool hasPath(const char * matrix,int rows,int cols,const char * str){
if(matrix==NULL||rows<||cols<||str==nullptr){
return false;
}
bool *visited = new bool[rows*cols];
memset(visited,,rows*cols);
int pathLength=;
for (int row=; row<rows; row++) {
for (int col=; col<cols; col++) {
if(hasPathCore(matrix, rows, cols, row,col,str,pathLength,visited)){
return true;
}
}
}
delete[] visited;
return false;
}
};
机器人的运动范围
/*
第十三题 机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
//test movingCount(5, 10, 10) 结果为21
*/
class class_13{
//入口方法
public:
int movingCount(int threshold,int rows,int cols){
if(threshold < || rows <= || cols <= )
return ;
bool *visited = new bool[rows * cols];
for(int i = ; i < rows * cols; ++i)
visited[i] = false; int count=;
movingCountCore(threshold,rows,cols,,,visited,count); delete []visited;
return count;
}
private:
void movingCountCore(int threshold, int rows, int cols, int row,
int col, bool* visited,int &count){
if(check(threshold, rows, cols, row, col, visited)){
count++;
visited[row * cols + col] = true;
//循环遍历四个邻居
int rowN[]={,,-,};
int colN[]={-,,,};
for (int i=; i<; i++) {
movingCountCore(threshold, rows, cols, row+rowN[i], col+colN[i], visited,count);
}
}
}
bool check(int threshold, int rows, int cols, int row, int col,
bool* visited)
{
if(row >= && row < rows && col >= && col < cols
&& getDigitSum(row) + getDigitSum(col) <= threshold
&& !visited[row* cols + col])
return true; return false;
} int getDigitSum(int number)
{
int sum = ;
while(number > )
{
sum += number % ;
number /= ;
} return sum;
}
};
剪绳子
/*
第14题
剪绳子
题目一：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],...,k[m]
.请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？
例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
*/
/*
方法一：动态规划
方法二：贪心（需要数学推算，略）
4个条件：
动态规划原理：
1.确认原问题与子问题: 求长度为n的绳子的最优解，子问题为求n-1，n-2的最优解
2.确认状态:
第i个状态，就是长度为i的绳子的最优解
3.确认边界状态的值:
f(0)=0 f(1)=0 f(2)=1 f(3)=2
4.确定状态转移方程: 将求第i个状态的值转移为求第i-1个状态
f(n)=max(f(i)*f(n-i)) 剪长度为i的最优解乘以 长度为 n-i的最优解
*/
class class_14 {
int maxProductAfterCutting(int length)
{
if(length<){
return ;
}
if(length==){
return ;
}
if(length==){
return ;
}
vector<int>products(length+);
products[]=;
products[]=;
products[]=;
products[]=;
int max=;
for (int i=; i<=length; i++) {
max=;
for (int j=; j<=i/; j++) {
int product=products[j]*products[i-j];
if(max<product){
max=product;
}
products[i]=max;
} }
max=products[length];
return max;
}
};
二进制表示中1的个数
/*
第15题
二进制表示中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
*/
class class_15 {
//常规方法
//flag左移，比如flag是32位，移动32位最后flag=0，结束循环
int NumberOf2(int n){
int count=;
unsigned int flag = ;
while (flag) {
if(n&flag){
count++;
}
flag=flag<<;
}
return count;
} //巧妙方法
/*
技巧：把一个整数减去1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中d最右边的1变为0
*/
int NumberOf3(int n){
int count=;
while (n) {
++count;
n=(n-)&n;//循环几次说明有几个1
}
return count;
}
};
数值的整数次方
/*
第16题
数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
*/
class class_16{
public:
//求平方
double Power(double base,int exponent){
g_InvalidInput = false;
if(equal(base, 0.0)&& exponent < ){
g_InvalidInput = true;
return 0.0;
}
unsigned int absExponent = (unsigned int) (exponent);
if(exponent<){
absExponent = (unsigned int)(-exponent);
}
double result = PowerWithUnsignedExponent2(base, absExponent);
if (exponent < )//负指数
result = 1.0 / result;
return result;
} bool g_InvalidInput = false; //判断是否相等
bool equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
} //递归方法
double PowerWithUnsignedExponent2(double base, unsigned int exponent){
if (exponent == )
return ;
if (exponent == )
return base;
double result = PowerWithUnsignedExponent2( base, exponent>>);//相当于除以2
result *= result;
if ((exponent & 0x1) == )
result *= base;
return result;
}
//普通方法
double PowerWithUnsignedExponent(double base, unsigned int exponent){
double result = 1.0; for (int i = ; i <= exponent; ++i)
result *= base; return result;
}
};
打印1到最大的n位数
/*
// 面试题17：打印1到最大的n位数
// 题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则
// 打印出1、2、3一直到最大的3位数即999。
要点 3位数所有的其实是1-9 的3个数的全排列 最大为999，最小为000,打印的时候，前面为0 的不打印
*/ class class_17{
void PrintToMaxofNDigits_2(int n){
if(n<=){
return;
}
char * number = new char[n+];
number[n]='\0';
for (int i=; i<; i++) {
number[] = i+'';
Print1ToMaxOfNDigitsRecursively(number,n,);
}
delete [] number;
}
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index){
if(index>=length-){//到了最低一位
//打印
PrintNumber(number);
return;
}
for (int i=; i<; i++) {
number[index+]=i+'';
Print1ToMaxOfNDigitsRecursively(number,length,index+);
}
}
// 字符串number表示一个数字，数字有若干个0开头
// 打印出这个数字，并忽略开头的0
void PrintNumber(char* number){
bool isBeginning0 = true;
int nLength = (int)strlen(number); for (int i=; i<nLength; i++) {
if (isBeginning0 && number[i] != '')
isBeginning0 = false;
if(!isBeginning0){
printf("%c", number[i]);
}
}
printf("\t"); }
};
在O(1)时间删除链表结点
// 面试题18（一）：在O(1)时间删除链表结点
// 题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该
// 结点。
class class_18{ void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if(!pListHead || !pToBeDeleted)
return; // 要删除的结点不是尾结点
//思路很巧妙，改变值来达到 删除的效果
if(pToBeDeleted->m_pNext != nullptr)
{
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext; delete pNext;
pNext = nullptr;
}
// 链表只有一个结点，删除头结点（也是尾结点）
else if(*pListHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = nullptr;
*pListHead = nullptr;
}
// 链表中有多个结点，删除尾结点
else
{
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
} pNode->m_pNext = nullptr;
delete pToBeDeleted;
pToBeDeleted = nullptr;
}
} };
删除链表中重复的结点
/*
// 面试题18（二）：删除链表中重复的结点
// 题目：在一个排序的链表中，如何删除重复的结点?
技巧：利用g一个 前置节点辅助会更简单
*/
class class_18_2{
struct Node{
int value;
Node *next;
};
Node *deleteDuplication(Node *head){
if(head==NULL)
return NULL;
Node *preHead = new Node;
preHead->next = head;
Node *p=head;
Node *last=preHead;
while (p&&p->next) {
if(p->value==p->next->value){
int value=p->value;
while (p && p->value==value) {
p=p->next;
}
last->next = p; }
else{
last=p;
p=p->next;
}
}
return preHead->next;
} };
正则表达式匹配
/*
//第19题 正则表达式匹配
// 题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'
// 表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题
// 中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"
// 和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
*/
class class_19{
bool match(const char* str, const char* pattern)
{
if(str == nullptr || pattern == nullptr)
return false; return matchCore2(str, pattern);
}
//aa a*ac*a
//ba a*bc*a
// "cb", "c*b"
bool matchCore2( const char* str, const char* pattern){
//结束条件为 都指向字符串末尾，然后返回true
if(*str=='\0' && *pattern=='\0')
return true;
//结束条件为字符串没有结束，模式指向尾部了（字符串结束，模式没有结束，不一定不匹配，比如ab abc*d*）
if(*str!='\0' && *pattern=='\0')
return false; if(*(pattern+)=='*'){
//如果*前面的字符和字符串匹配，那么有3种方式可以选择
if(*str==*pattern || (*pattern=='.' && *str!='\0')){
//1 *前面的字符可以在字符串中出现任意次，字符串后移，看看下一个是不是仍然匹配
bool result = matchCore2(str+,pattern);
//2 假设*前的字符和本次字符串指向的字符不匹配（略过本次的*），模式字符串后移2
bool result2 = matchCore2(str,pattern+);
// 假设匹配上了，那么字符串后移1，模式后移2，继续比较下一个
//"aaaaaaaaaaaaab" "a*a*a*a*a*a*a*a*a*a*a*a*b"
// ab a*b
//超时了
// bool result3 = matchCore2(str+1, pattern+2);
// //3个条件满足一个就可以
// return result || result2 || result3 ; //3个条件满足一个就可以
return result || result2 ; }
else{
//如果*前的和字符串不匹配，那么就理解为*前的字符串出现0次，也是符合条件的，然后模式字符串后移2
bool result = matchCore2(str,pattern+);
return result;
} }
if(*str==*pattern || (*pattern=='.' && *str!='\0')){
bool result = matchCore2(str+,pattern+);
return result;
}
return false; } void Test(const char* testName, const char* string, const char* pattern, bool expected)
{
if(testName != nullptr)
printf("%s begins: ", testName); if(match(string, pattern) == expected)
printf("Passed.\n");
else
printf("FAILED.\n");
} };
表示数值的字符串
/*
题目20:
表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
*/
class class_20{
// 数字的格式可以用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';
} bool scanUnsignedInteger(const char** str)
{
const char* before = *str;
while(**str != '\0' && **str >= '' && **str <= '')
++(*str); // 当str中存在若干0-9的数字时，返回true
return *str > before;
} // 整数的格式可以用[+|-]B表示, 其中B为无符号整数
bool scanInteger(const char** str)
{
if(**str == '+' || **str == '-')
++(*str);
return scanUnsignedInteger(str);
} };
调整数组顺序使奇数位于偶数前面
// 题目 21：调整数组顺序使奇数位于偶数前面
// 题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有
// 奇数位于数组的前半部分，所有偶数位于数组的后半部分。
class class_21 {
void ReorderOddEvent(int *pData,int length){
if(pData == nullptr || length == )
{
return; }
int *pBegin = pData;
int *pEnd = pData+length-;
while (pBegin<pEnd) {
// 向后移动pBegin，直到它指向偶数
while (pBegin<pEnd && ((*pBegin)&0x1 )!=) {
pBegin++;
}
// 向前移动pEnd，直到它指向奇数
while(pBegin < pEnd && (*pEnd & 0x1) == )
{
pEnd --; }
if(pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
} } };
链表中倒数第k个结点
/*
题目22:
：链表中倒数第k个结点
// 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，
// 本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，
// 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是
// 值为4的结点。
*/ class class_22{
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
if(pListHead == nullptr || k == )
return nullptr; ListNode *pAhead = pListHead;
ListNode *pBehind = nullptr; for(unsigned int i = ; i < k - ; ++ i)
{
if(pAhead->m_pNext != nullptr)
pAhead = pAhead->m_pNext;
else
{
return nullptr;
}
} pBehind = pListHead;
while(pAhead->m_pNext != nullptr)
{
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
} return pBehind;
} };
一个链表中包含环，如何找出环的入口结点
/*
题目23
// 题目：一个链表中包含环，如何找出环的入口结点？ 思路：快慢指针赛跑
先求出相遇点，然后根据数学公式
从相遇点出发和从head出发，相遇点就是 环入口点
*/
class class_23 {
ListNode *detectCycle2(ListNode *head){
ListNode *fast=head;
ListNode * slow=head;
ListNode *meet=NULL;
while (fast) {
slow=slow->m_pNext;
fast=fast->m_pNext;
if(!fast){
return NULL;
}
fast=fast->m_pNext;
if(fast==slow){
meet=fast;
break;
}
}
if(meet==NULL){
return NULL;
}
while (head&&meet) {
if(head==meet){
return head;
}
head=head->m_pNext;
meet=meet->m_pNext;
}
return NULL;
} };
反转链表
/*
题目24 反转链表
// 题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的
// 头结点。
*/
class class_24 {
//链表转置
ListNode * reverseList2(ListNode * head)
{
ListNode *new_head=NULL;//指向新链表头节点的指针
while(head){
ListNode *next= head->m_pNext;//备份head->next
head->m_pNext=new_head;//更新hea睨zhid->next;
new_head=head;//移动new_head;
head=next;//遍历链表
}
return new_head;//返回新链表头节点
}
// 5-4-3-2-1
//递归方法 1->2->3->4->5 5->4->3->2->1 1->2->3 3->2->1 1-> 3->2->1
ListNode * reverseList34(ListNode *head){
//终止条件，到了最后一个节点
if(head==NULL||head->m_pNext==NULL){
return head;
}
ListNode * next = head->m_pNext;
head->m_pNext=NULL;//这一步是为了第一个节点指向null ListNode * cur = reverseList34(next);
//这是关键一步，head的next A，反转之后，正好A的next就是head
next->m_pNext=head;
return cur; }
};
合并两个排序链表
/*
题目25:
合并两个排序链表
*/
class class_25 {
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
}; ListNode *mergeTwoLists(ListNode *l1,ListNode *l2){
ListNode temp_head();
ListNode *pre=&temp_head;
while (l1&&l2) {
if(l1->val < l2->val){
pre->next=l1;
l1=l1->next;
}
else{
pre->next=l2;
l2=l2->next;
}
pre=pre->next;
}
if(l1){
pre->next=l1;
}
if(l2){
pre->next=l2;
}
return temp_head.next;
} };
输入两棵二叉树A，B，判断B是不是A的子结构(注意：是子结构，不是子树)
/*
题目26 输入两棵二叉树A，B，判断B是不是A的子结构(注意：是子结构，不是子树)
*/ class class_26 {
struct TreeNode{
int value;
TreeNode *left;
TreeNode *right;
};
bool tree1HasTree2(TreeNode *t1,TreeNode*t2){ if(t1==nullptr){
return false;
}
if(t2==nullptr){
return true;
}
if(t1->value!=t2->value){
return false;
}
return tree1HasTree2(t1->left, t2->left) && tree1HasTree2(t1->right, t2->right); }
bool HasSubTree(TreeNode *t1,TreeNode*t2){
bool result=false;
if(t1 && t2){
result = tree1HasTree2(t1, t2);
if(!result){
result=HasSubTree(t1->left, t2);
}
if(!result){
result = HasSubTree(t1->right, t2);
} }
return result;
}
};
操作给定的二叉树，将其变换为源二叉树的镜像
/*
题目26 操作给定的二叉树，将其变换为源二叉树的镜像。
*/
class class_26_2 {
struct TreeNode{
int value;
TreeNode *left;
TreeNode *right;
};
void getMirroSubTree(TreeNode * left,TreeNode *right){ }
void getMirroTree(TreeNode * root){ if(root==nullptr)return;
if(!root->left && !root->right){
return;
}
TreeNode *left = root->left; TreeNode * right = root->right; TreeNode *temp= left;
left = right;
right=temp; if(root->left){
getMirroTree(root->left);
}
if(root->right){
getMirroTree(root->right);
}
} };
判断二叉树是不是对称二叉树
/*
题目28
判断二叉树是不是对称二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
*/
class class_28 {
struct TreeNode{
int value;
TreeNode *left;
TreeNode *right;
};
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot, pRoot);
} bool isSymmetrical(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1 == nullptr && pRoot2 == nullptr)
return true; if(pRoot1 == nullptr || pRoot2 == nullptr)
return false; if(pRoot1->value != pRoot2->value)
return false; return isSymmetrical(pRoot1->left, pRoot2->right)
&& isSymmetrical(pRoot1->right, pRoot2->left);
} };
顺时针打印矩阵
分析:
简单看看螺旋矩阵，其规律就是一圈一圈的往里绕，因此我们可以想象有一条贪吃蛇，它很听话，如果要出格子或者碰到格子里有数的时候就向右转一下，然后在它路过的格子里顺序填充上数字就好
栈的压入、弹出序列
/*
第31题
栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
*/
class class_31{ bool checkIsValied(queue<int>&order){
std::stack<int>S;//模拟战
int n=(int)order.size();//n为序列长度，将1-n按顺序入站
for (int i=; i<=n; i++) {
S.push(i); //将i入站
while (!S.empty()&&S.top()==order.front()) {
S.pop();
order.pop();//只要S不空且队列头部与战顶相同，即弹出元素
}
}
if(S.empty()!=false){//如果最终栈不空，则说明序列不合法
return false;
}
return true;
}
};
从上往下打印二叉树
/*
第32题
从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
换行打印
*/
class class_32{
struct TreeNode{
int value;
TreeNode *left;
TreeNode *right;
};
//按层打印
void Print(TreeNode* root){
queue<TreeNode*> qu;
int level=;
int toBeBehind=;
qu.push(root);
while (qu.empty()==false) {
TreeNode * node = qu.front();
qu.pop();
printf("%d",root->value);
if (node->left) {
qu.push(node->left);
level++;
}
if(node->right){
qu.push(node->right);
level++;
}
toBeBehind--;
if(toBeBehind==){
toBeBehind = level;
level=;
printf("\n");
} }
}}
;
Z打印二叉树
//Z打印二叉树
class class_32_2 {
struct TreeNode{
int value;
TreeNode *left;
TreeNode *right;
}; void PrintZ(TreeNode* root){
if(root==nullptr) return;
vector<vector<TreeNode*>>array;
stack<TreeNode*>s1;
stack<TreeNode*>s2;
int layer=;
s1.push(root);
while (s1.empty()==false || s2.empty()==false) {
vector<TreeNode*> vec;
while (s1.empty()==false && layer%==) {
TreeNode *node=s1.top();
s1.pop();
vec.push_back(node);
if(node->right){
s2.push(node->right);
}
if(node->left){
s2.push(node->left);
}
}
while (s2.empty()==false && layer%==) {
TreeNode *node=s2.top();
s2.pop();
vec.push_back(node);
if(node->left){
s2.push(node->left);
}
if(node->left){
s2.push(node->right);
}
}
if(vec.size()){
array.push_back(vec);
}
layer++; }
for (int i=; i<array.size(); i++) {
vector<TreeNode*>vec = array[i];
for (int j=; j<vec.size(); j++) {
printf("%d ",vec[j]->value);
}
printf("\n");
}
}
};
二叉树搜索的后序遍历序列
/*
第33题
二叉树搜索的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
如 {5,7,6,9,11,10,8} 返回true，{7,4,6,5} 返回false
*/
class class_33{ bool verifySqueenceOfBST(vector<int>vec){
if(vec.size()==){
return false;
}
int i=;
int begin=;
int end = (int)vec.size()-;
int root = vec[end];
////左子树的节点的值都比根节点小
for(i=begin;i<end;i++){
if(vec[i]>root){ ////如果大于root节点，直接跳出循环，判断该树是不是只有右子树
break;
}
}
// i 为右子树的第一个节点 ,j为右子树的最后一个节点
for (int j=i; j<end; j++) {
if(vec[j]<root){
return false;
}
} //到此 左右子树暂时符合条件，下面分别检测左子树 和右子树
bool left = true;
vector<int>leftVec;
for(int j=;j<i;j++){
leftVec.push_back(vec[j]);
}
if(leftVec.size()>){//有左子树
left= verifySqueenceOfBST(leftVec);
} bool right = true;
vector<int>rightVec;
for (int j=i; j<vec.size()-; j++) {
rightVec.push_back(vec[j]);
}
if(rightVec.size()>){
right= verifySqueenceOfBST(rightVec);
}
return left && right;
}
};
二叉树中和为某一值的路径
/*
第34题
二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径
*/
class class_34{
public:
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
};
vector<vector<int>>pathSum(TreeNode *root,int sum){
vector<vector<int>>result;
vector<int>path;
int path_value=;//过程中累加的和
preorder(root, path_value, sum, path, result);
return result;
}
private:
void preorder(TreeNode *node,int&path_value,int sum,vector<int>&path,
vector<vector<int>>&result){
if(node==NULL)
return;
path_value+=node->val;
path.push_back(node->val);
if(node->left==NULL&&node->right==NULL){
if(path_value==sum){
result.push_back(path);
} }
preorder(node->left, path_value, sum, path, result);
preorder(node->right, path_value, sum, path, result);
path_value-=node->val;
path.pop_back();//遍历完毕，将节点从栈中取出
}
};
复杂链表的复制
/*
第35题
复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
*/
class class_35{
class Node {
public:
int val;
Node* next;
Node* random; Node() {} Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
}; Node* copyRandomList(Node* head) {
if(head==nullptr)return nullptr;
Node * p = head;
//把原来的链表和新的链表 连接到一起
// 1->1'->2->2'->null
while (p) {
int value = p->val;
Node * cpNode = new Node();
cpNode->val=value;
cpNode->random=nullptr;
cpNode->next = p->next; p->next=cpNode; p=cpNode->next;
}
//赋值 随机链表
p=head;
while (p) {
Node * random = p->random;
Node *cp = p->next;
cp->random =random?random->next:nullptr; p=cp->next;
} //拆分出 新的链表
p=head;
Node * newHead= head->next;
while (p) {
Node * cp=p->next;
//记录下一个节点
Node *oldNext=cp->next;
Node * cpNext= oldNext? oldNext->next:nullptr; p->next=oldNext;
cp->next=cpNext; p=oldNext;
cp=cpNext; }
return newHead; }
};
二叉搜索树与双向链表
/*
第36题
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
*/
class class_36{
public:
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
};
void ConvertNode(TreeNode *node,TreeNode *& last){ if(node==nullptr){
return;
}
//中序遍历
TreeNode *current=node;//保存
///左子树
if(current->left){
ConvertNode(current->left,last);
} current->left =last; //当前的左指针指向last
if(last){
last->right=current;
}
//最后一个节点 更新为 current
last=current; //右子树
if(current->right){
ConvertNode(current->right, last);
} }
TreeNode * Convert(TreeNode * root){
TreeNode * last = nullptr;
ConvertNode(root, last);
//返回头节点
TreeNode * p = last;
while (p&&p->left) {
p = p->left;
}
return p;
}
};
序列化二叉树
/*
第36_2题
序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树 */
class class36_2 {
public:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
string intToString(int num){
string result ="";
if(num==){
result.push_back('');
}
bool isfu=false;
if(num<){
num=-num;
isfu=true;
}
while (num) {
char ch= num% +'';
result.push_back(ch);
num=num/;
} string newresult;
if(isfu){
newresult.push_back('-');
}
for(int i=(int)result.length()-;i>=;i--){
newresult.push_back(result[i]);
}
newresult+="_";
return newresult;
}
//
int stringToint(string s){
if(s.length()==){
return ;
}
char ch = s[];
int flag=;
if(ch=='-'){//负数
flag=;
}
int num=;
for (int i = flag?:; i<s.size(); i++) {
int t = s[i]-'';
num = num*+t;
}
return flag? -num:num;
} void BianMa(TreeNode *root,string &s){
if(root==nullptr){
s+="#_";
return;
}
s+=intToString(root->val);
BianMa(root->left, s);
BianMa(root->right, s);
}
void jieMa(vector<string>&vec,TreeNode *&root,int &i){
if(i==vec.size()){
return;
}
if(vec[i]=="#"){
root=nullptr;
return;
}
string s = vec[i];
int num= stringToint(s);
if(root==nullptr){
root = new TreeNode(num);
}
else {
root->val=num;
}
i+=;
jieMa(vec, root->left, i);
i+=;
jieMa(vec, root->right, i); } // Encodes a tree to a single string.
string serialize(TreeNode* root) {
string s="";
BianMa(root, s);
return s;
}
//1_2_3_#_4_
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
string item="";
vector<string> vec;
for (int i=; i<data.size(); i++) {
char ch =data[i];
if(ch=='_'){
vec.push_back(item);
item="";
}
else {
item+=ch;
}
}
TreeNode *root=nullptr;
int i=;
jieMa(vec, root, i);
return root;
}
};
字符串的排列
/*
37 题
字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路： 回溯法
*/
class class_37{
void preCHangeSUb(char *p,char *begin){
if(*begin=='\0'){
printf("%s \n",p);
}
for (char *ch=begin; *ch !='\0'; ch++) {
char temp = *begin;
*begin=*ch;
*ch=temp;
preCHangeSUb(p, begin+);
temp = *begin;
*begin=*ch;
*ch=temp;
}
}
void preChange(char * p){
if(p==nullptr){
return;
}
preCHangeSUb(p, p);
} };
数字出现的次数超过数组长度的一半
/*
39 题
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
*/
class class_39{
int MoreThanHalfNum(int * numbers,int length){
int result=numbers[];
int times=;
for (int i=; i<length; i++) {
if(times==){
result = numbers[i];
times=;
}
else if(numbers[i]==result){
times++;
}
else {
times--;
}
}
return result;
}
};
最小的k个数
/*
40题：
最小的k个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
*/
/*
方法：最大堆
*/
class class_40{
void findKthLargest(std::vector<int>&nums,int k)
{
//构建最大堆
std::priority_queue<int, std::vector<int> > Q;
for (int i=; i<nums.size(); i++) {
if(Q.size()<k){
Q.push(nums[i]);
}
else if(nums[i]<Q.top()){
Q.pop();
Q.push(nums[i]);
}
}
//遍历输出即可
vector<int>vec;
while (Q.empty()==false) {
vec.push_back(Q.top());
Q.pop();
}
auto it = vec.begin();
for (; it!=vec.end(); it++) {
printf("%d",*it);
}
}
};
数据流中的中位数
/*
41题
数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数
*/
class class_41 {
public:
/** initialize your data structure here. */
class_41() { } void addNum(int num) {
//bigqueue中保存最小的集合，small_queue保存最大的集合
if(big_queue.size()==){
big_queue.push(num);
}
else {
if(big_queue.size()==small_queue.size()){
if(num>big_queue.top()){
small_queue.push(num);
}
else {
big_queue.push(num);
}
}
else if(big_queue.size()>small_queue.size()){
if(big_queue.top()<num){
small_queue.push(num);
}
else {
int top = big_queue.top();
big_queue.pop();
big_queue.push(num);
small_queue.push(top);
}
}
else if(big_queue.size()<small_queue.size()){
if(small_queue.top()>num){
big_queue.push(num);
}
else {
int top = small_queue.top();
small_queue.pop();
small_queue.push(num);
big_queue.push(top);
} }
} } double findMedian() {
if(big_queue.size()==small_queue.size()){
return (big_queue.top()+small_queue.top())*0.5;
}
else if(big_queue.size()>small_queue.size()){
return big_queue.top();
}
else {
return small_queue.top();
}
}
private: std::priority_queue<double> big_queue;
std::priority_queue<double, std::vector<double>,
std::greater<double> > small_queue;
};
连续子数组的最大和
/*
42题
连续子数组的最大和
思路：动态规划
*/
class class_42 {
public:
int maxSubArray(vector<int>& nums) {
// i的状态为 以第i个数为结尾的最大和
vector<int>dp(nums.size());
dp[]=nums[];
int maxNum=dp[];
for (int i=; i<nums.size(); i++) {
dp[i]= max(dp[i-]+nums[i],nums[i]);
if(maxNum<dp[i]){
maxNum=dp[i];
}
}
return maxNum;
}
};
整数中1出现的次数
/*
43 题
整数中1出现的次数
与数学关系比较大，需要找数学规律
*/
//思路：
/*
在分析之前，首先需要知道一个规律： 从 1 至 10，在它们的个位数中，数字1出现了 1 次。
从 1 至 100，在它们的十位数中，数字1出现了 10 次。
从 1 至 1000，在它们的百位数中，数字1出现了 100 次。
依此类推，从 1 至 10i，在它们右数第二位中，数字1出现了10 ^ (i - 1)次。 对于 n = 2134,要找到从1 ~ 2134这2134个数字中所有1的个数。我们可以对2134进行逐位分析： (1)在个位上，从1~2130，包含213个10，因此数字1出现了213次，剩下的数字2131、2132、2133、2134中个位数上只有2131包含树脂字1，剩下的都不包含。所以个位数上的数字1的总数为213 + 1 = 214。 (2)在十位上，从1 ~ 2100，包含了21个100，因此数字1出现了21 * 10 = 210次，剩下的数字从2101 ~ 2134，只有2110 ~ 2119这10个数字中十位的数字为1，所以十位上的数字1的总数为210 + 10 = 220。 (3)在百位上，从1 ~ 2000，包含了2个1000，因此数字1出现了2 * 100 = 200次，剩下的数字从2001 ~ 2134，只有2100 ~ 2134这35个数字中的百位的数字为1，所以百位数上数字1的总数为200 + 35= 235。 (4)在千位上，包含了0个10000，因此数字1出现了0 * 1000 = 0次，剩下的数字中只有1000 ~ 1999这1000个数字中的千位的数字为1，所以千位上的数字1的总数为1000。 因此从1 ~ 2134这n个数字中，数字出现的总的次数为 214 + 220 + 235 +1000 = 1669。 总结一下以上的步骤，可以得到这么一个规律： 对于数字n，计算它的第i(i从1开始，从右边开始计数)位数上包含的数字1的个数： 假设第i位上的数字为x的话，则 1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）* 10 ^ (i-1) (其中高位数字是从i+1位一直到最高位数构成的数字) 2.如果x < 1的话，则第i位数上包含的1的数目为：(高位数字 ）* 10 ^ (i-1) 3.如果x == 1的话，则第i位数上包含1的数目为：(高位数字) * 10 ^ (i-1) +(低位数字+1) (其中低位数字时从第i - 1位数一直到第1位数构成的数字)
*/ //
class class_43 {
int NumberOfDigitOne(int n) {
if( n < )
return ;
int i = ;
int high = n;
int cnt = ;
while(high != )
{
high = n / pow( ,i);//high表示当前位的高位
int temp = n / pow(, i - );
int cur = temp % ;//cur表示第i位上的值，从1开始计算
int low = n - temp * pow(, i - );//low表示当前位的低位 if(cur < )
{
cnt += high * pow(, i - );
}
else if(cur > )
{
cnt += (high + ) * pow( ,i - ); }
else
{ cnt += high * pow(, i - );
cnt += (low + ); }
i++;
}
return cnt;
} };
数字序列中某一位的数字
/*
44题
数字序列中某一位的数字
题目要求：
数字以01234567891011121314...的格式排列。在这个序列中，第5位（从0开始计）是5，第13位是1，第19位是4。求任意第n为对应的数字。
//
解题思路：
与43题类似,都是数学规律题。如果用遍历的方式，思路代码都很简单，但速度较慢。更好的方式是借助于数字序列的规律，感觉更像是数学题。步骤大致可以分为如下三部分：
以第15位数字2为例（2隶属与12，两位数，位于12从左侧以0号开始下标为1的位置）
步骤1：首先确定该数字是属于几位数的;
如果是一位数，n<9;如果是两位数，n<9+90*2=189;
说明是两位数。
步骤2：确定该数字属于哪个数。10+(15-10)/2= 12。
步骤3：确定是该数中哪一位。15-10-(12-10)*2 = 1, 所以位于“12”的下标为1的位置，即数字2。 以第1001位数字7为例
步骤1：首先确定该数字是属于几位数的;
如果是一位数，n<9;如果是两位数，n<9+90*2=189;如果是三位数，n<189+900*3=2889;
说明是三位数。
步骤2：确定该数字属于哪个数。100+(1001-190)/3= 370。
步骤3：确定是该数中哪一位。1001-190-(370-100)*3 = 1,所以位于“370”的下标为1的位置，即数字1。 */ class class_44{
public:
//求的数字长度的所有数的总数
int lengthSum(int length){
int count = ;
for (int i=; i<length; i++) {
count *= ;
}
return count * length;
}
int digitAtIndex(int index){
if(index<)
return -;
if(index<)
return index;
int curIndex=;//当前多少个数
int length=;
int boundNum = ;
//看看index在几位数中间
while (curIndex+lengthSum(length)<index) {
curIndex+=lengthSum(length);
boundNum *= ;
length++;
}
//判断index在n位数中属于哪个数
int addNum = (index-curIndex)/length;
int curNum = boundNum + addNum;
//判断index在 这个curNum中的第几位
int finalIndex= index-curIndex-addNum*length;
string s = to_string(curNum).substr(finalIndex,);
return s[]-''; }
};
把数组排成最小的数
/*
45题
把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323
思路：定义一个字符串比较规则,挺巧妙
*/
class class_45 {
public:
string PrintMinNumber(vector<int> numbers) {
string res="";
int length = (int)numbers.size();
if(length==)
return "";
sort(numbers.begin(),numbers.end(),cmp);
for(int i=;i<length;i++)
res += to_string(numbers[i]);
return res;
}
static bool cmp(int a,int b){
string A = to_string(a)+to_string(b);
string B = to_string(b)+to_string(a);
return A<B; }
};
把数字翻译成字符串
/*
46题：
把数字翻译成字符串
给定一个数字，按照如下规则翻译成字符串：
0->a
1->b
...
25->z
因此一个数字可能有多种翻译。例如，12258有5种不同的翻译，bccfi,bwfi,bczi,mcfi,mzi。
请实现一个函数，计算数字有多少种翻译方法。 思路： 动态规划 */
class class_46 {
int GetTranslationCount22(string s){
/*
动态规划四个条件
1 子问题：求1位数的表达，2位数
2 边界条件： 最后一位值为1
3 状态： 第i位有几种表示
4公式： f(i)=f(i+1)+(0,1)*f(i+2)
*/
vector<int> vec();
for (int i= (int)s.length(); i>; i--) {
vec.push_back();
}
vec[s.length()]=;
vec[s.length()-]=; for (int i= (int)s.length()-; i>=; i--) {
int temp=(s[i]-'')* + (s[i+]-'');
int value=;
if(temp>=&&temp<=)
{
value=;
} vec[i] = vec[i+] + value * vec[i+]; }
return vec[];
}
};
最大价值的礼物
/*
47题
在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
思路：
很简单的动态规划
*/
class class_47 {
int getMaxValue_solution(vector<vector<int>> &nums){
vector<vector<int>>vec;
for (int i=; i<nums.size(); i++) {
vec.push_back(vector<int>());
for (int j=; j<nums[].size(); j++) {
vec[i].push_back();
}
}
int rows = (int)nums.size();
int columns= (int)nums[].size();
for (int i=; i<rows; i++) {
for(int j=;j<columns;j++){
int left=;
int up=;
if(i>){
up = vec[i-][j];
}
if(j>){
left = vec[i][j-];
}
vec[i][j]= max(up,left)+nums[i][j];
} }
return vec[rows-][columns-];
} };
最长不含重复字符的子字符串
/*
题目48、
最长不含重复字符的子字符串 */
// abcdfsdfefg
class class_48{ //方法一：哈希表
int lengthOfLongestSubstring(string s){
string word="";
int begin=;
char temp []={};
int result=;
for (int i=; i<s.length(); i++) { temp[s[i]]++;
if(temp[s[i]]==){
word+=s[i];
if(word.length()>result){
result = (int)word.length();
} }
else {
while (begin<i && temp[s[i]]>) {
temp[s[begin]]--;
begin++;
}
word="";
for (int j= begin; j<=i; j++) {
word+=s[j];
} } }
return result;
}
//方法二： 动态规划
// abdacadfsdfefg
int lengthOfLongestSubstring2(string s){
/*
动态规划四个条件：
子问题： 求一个字符的字符串，求二个字符
边界值： 一个字符的个数是1
状态：i的状态为 以第i个字符为结尾的最长子串
1 如果当前字符没有在之前扫描过的字符串中出现过，当前的就为 上次的f(i-1)+1
2 如果当前的字符 在上一次出现过
2.1 2个相同字符的距离超过 上一个状态的时候，f(i)=f(i-1)+1
2.2 2个相同字符的距离 没有超过上一个状态的时候，f(i)=2者的距离 */
if(s.length()==||s.length()==){
return (int)s.length();
}
vector<int>vec;
//记录最后一次某个字符出现的位置
map<char,int> charPosition; charPosition[s[]]=;
vec.push_back();
int maxLength0=;
for (int i=; i<s.length(); i++) {
char ch = s[i];
if( charPosition.find(ch)==charPosition.end()){//没出现过
vec.push_back(vec[i-]+);
}
else {//出现过
//2个相同字符的距离 没有超过上一个状态的时候
if(i - charPosition[ch] <=vec[i-]){
vec.push_back(i - charPosition[ch]);
}
else { //2个相同字符的距离超过 上一个状态的时候
vec.push_back(vec[i-]+);
}
}
if(vec[i]>maxLength0){
maxLength0 = vec[i];
}
charPosition[ch]=i;
}
return maxLength0; } };
丑数
/*
49题
丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，
因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数
*/
class class_49{ int Min2(int num1, int num2, int num3)
{
int min = num1 < num2 ? num1 : num2;
min = min < num3 ? min : num3; return min;
}
int nthUglyNumber2(int index) {
if (index <= )
{
return ;
} vector<int> uglyNumbers(index);
uglyNumbers[] = ;
int nextUglyIndex = ; int multiply2 = ;//记录 乘以2第一个大于 目前最大丑数的 位置
int multiply3 = ;
int multiply5 = ;
int min = ; while (nextUglyIndex < index) //1 2 3
{
min = Min2(uglyNumbers[multiply2] * , uglyNumbers[multiply3] * , uglyNumbers[multiply5] * );
uglyNumbers[nextUglyIndex] = min; while (uglyNumbers[multiply2] * <= uglyNumbers[nextUglyIndex])
{
multiply2++;
} while (uglyNumbers[multiply3] * <= uglyNumbers[nextUglyIndex])
{
multiply3++;
} while (uglyNumbers[multiply5] * <= uglyNumbers[nextUglyIndex])
{
multiply5++;
} nextUglyIndex++;
} int result = uglyNumbers[index - ]; return result;
}
};
第一次只出现一次的字符的索引
/*
第50题：
第一次只出现一次的字符的索引
*/
//bcdefab
class class_50{
/*
第一次只出现一次的字符的索引
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,
如果没有则返回 -1（需要区分大小写）
*/
int firstUniqChar(string s) {
int temp[]={};
map<char, int> _map;
for (int i=; i<s.length(); i++) {
temp[s[i]]++;
_map[s[i]]=i; }
for (int i=; i<s.length(); i++) {
if(temp[s[i]]==){
return _map[s[i]];
}
}
return -;
} };
字符流中第一个不重复的字符【不是求索引】
/*
50题-2
字符流中第一个不重复的字符【不是求索引】
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
*/
class class_50_2{ class CharStatistics
{
public:
CharStatistics() : index()
{
for(int i = ; i < ; ++i)
occurrence[i] = -;
} void Insert(char ch)
{
if(occurrence[ch] == -)
occurrence[ch] = index;
else if(occurrence[ch] >= )
occurrence[ch] = -; index++;
} char FirstAppearingOnce()
{
char ch = '\0';
int minIndex = numeric_limits<int>::max();
for(int i = ; i < ; ++i)
{
if(occurrence[i] >= && occurrence[i] < minIndex)
{
ch = (char) i;
minIndex = occurrence[i];
}
} return ch;
} private: // occurrence[i] = -1: 字符没有找到;
// occurrence[i] = -2: 字符找到许多次
// occurrence[i] >= 0: 字符只被找到一次
int occurrence[];
int index;
}; };
数组中的逆序对
/*
51题
数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路：二叉排序树
*/
class class_51 {
public:
struct BSTNode {
int val;
int count;//左子树的数目
BSTNode *left;
BSTNode *right;
BSTNode(int x) : val(x), left(NULL), right(NULL), count() {}
}; std::vector<int> countSmaller(std::vector<int>& nums) {
std::vector<int> result;
std::vector<BSTNode *> node_vec;
std::vector<int> count; for (int i = (int)nums.size() - ; i >= ; i--){
node_vec.push_back(new BSTNode(nums[i]));
} count.push_back();
for (int i = ; i < node_vec.size(); i++){
int count_small = ;
BST_insert(node_vec[], node_vec[i], count_small);
count.push_back(count_small);
}
for (int i = (int)node_vec.size() - ; i >= ; i--){
delete node_vec[i];
result.push_back(count[i]);
}
return result;
}
private:
void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small){
if (insert_node->val <= node->val){
node->count++;
if (node->left){
BST_insert(node->left, insert_node, count_small);
}
else{
node->left = insert_node;
}
}
else{
count_small += node->count + ;
if (node->right){
BST_insert(node->right, insert_node, count_small);
}
else{
node->right = insert_node;
}
}
}
};
两个链表的第一个公共结点
/*
52题 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
1-2-3-4-5
2-4-5-6-7 */
class class_52 {
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2)
{ unsigned int nLength1 = GetListLength(pHead1);
unsigned int nLength2 = GetListLength(pHead2);
int nLengthDif = nLength1 - nLength2; ListNode* pListHeadLong = pHead1;
ListNode* pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
} for(int i = ; i < nLengthDif; ++i)
pListHeadLong = pListHeadLong->m_pNext; while((pListHeadLong != nullptr) &&
(pListHeadShort != nullptr) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
} ListNode* pFisrtCommonNode = pListHeadLong; return pFisrtCommonNode;
} unsigned int GetListLength(ListNode* pHead)
{
unsigned int nLength = ;
ListNode* pNode = pHead;
while(pNode != nullptr)
{
++nLength;
pNode = pNode->m_pNext;
} return nLength;
} };
数字在排序数组中出现的次数
/*
53题 数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。
*/
class class_53 {
public:
int leftSearch(vector<int>&nums,int target){
int begin=;
int end=(int)nums.size()-;
int index=-;
while (begin<=end) { int mid = (begin+end)/;
if(target==nums[mid]){
if(mid==||target>nums[mid-]){
index=mid;
break;
}
else {
end = mid-;
} }
else if(target<nums[mid]){
end=mid-;
}
else if(target>nums[mid]){
begin=mid+;
}
}
return index; }
int rightSearch(vector<int>&nums,int target){
int begin=;
int end=(int)nums.size()-;
int index=-;
while (begin<=end) { int mid = (begin+end)/;
if(target==nums[mid]){
if(mid==nums.size()-||target<nums[mid+]){
index=mid;
break;
}
else {
begin = mid+;
} }
else if(target<nums[mid]){
end=mid-;
}
else if(target>nums[mid]){
begin=mid+;
}
}
return index; }
int searchRange(vector<int>& nums, int target) {
int a = leftSearch(nums, target);
int b = rightSearch(nums, target);
if(a!=- && b!=-){
return b-a+;
}
return -;
}
};
0-n-1中缺失的数字
/*
53题目-2：0-n-1中缺失的数字
长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
思路：二分查找
*/
class class53_2{ int GetMissingNumber(const int* numbers, int length)
{
if(numbers == nullptr || length <= )
return -; int left = ;
int right = length - ;
while(left <= right)
{
int middle = (right + left) >> ;
if(numbers[middle] != middle)
{
if(middle == || numbers[middle - ] == middle - )
return middle;
right = middle - ;
}
else{
left = middle + ;
} } if(left == length)
return length; // 无效的输入，比如数组不是按要求排序的，
// 或者有数字不在0到n-1范围之内
return -;
} };
二叉搜索树中第K小的元素
/*
54题目：
二叉搜索树中第K小的元素
思路：中序遍历
*/
class class_54 {
public:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void ksmallSub(TreeNode * root,int &i,int k,int &value,bool &find){
if(root==nullptr || find){
return;
}
if(root->left){ ksmallSub(root->left, i, k,value,find);
}
if(i==k-&&find==false){
value = root->val;
find = true;
return ;
}
i=i+;
if(root->right){
ksmallSub(root->right, i, k,value,find);
}
}
int kthSmallest(TreeNode* root, int k) {
int i=;
int value = ;
bool find = false;
ksmallSub(root,i,k,value,find);
return value;
}
};
二叉树的深度
/*
55题 二叉树的深度
*/
class class_55 {
public:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int TreeDepth(TreeNode *root){
if(root==nullptr){
return ;
}
int left = TreeDepth(root->left);
int right = TreeDepth(root->right);
return (left>right)?(left+):(right+);
} };
判断是否为平衡二叉树
/*
55-2题 判断是否为平衡二叉树
//思路： 后序遍历
*/ class class_55_2{
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/*
方法一：根据求深度来遍历（会重复计算很多次，效率不高）
*/
int TreeDepth(TreeNode *root){
if(root==nullptr){
return ;
}
int left = TreeDepth(root->left);
int right = TreeDepth(root->right);
return (left>right)?(left+):(right+);
}
bool isBalanced2(TreeNode* root) {
if(root==nullptr){
return true;
}
int left = TreeDepth(root->left);
int right = TreeDepth(root->right);
int diff = left - right;
if(diff> || diff<-){
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
} /*
方法二：后序遍历
*/
bool isBlancedSub(TreeNode * root,int &depth){
if(root==nullptr)
{
depth=;
return true;
}
if(root->left==nullptr&&root->right==nullptr){
depth = ;
return true;
}
int depth1=;
int depth2=;
bool result = isBlancedSub(root->left, depth1);
bool result2 = isBlancedSub(root->right, depth2);
if(result&&result2){
int diff = depth1-depth2;
if(abs(diff)<=){
depth = max(depth1, depth2)+;
return true;
} } return false;
}
bool isBalanced(TreeNode* root) {
int depth=;
return isBlancedSub(root, depth);
} };
数组中只出现一次的两个数字
/*
56 题
面试题56：数组中只出现一次的两个数字 题目要求：
一个整数数组里除了两个数字出现一次，其他数字都出现两次。请找出这两个数字。要求时间复杂度为o(n)，空间复杂度为o(1)。
解题思路：
这道题可以看成“数组中只出现一次的一个数字”的延伸。如果所有数字都出现两次，只有一个数字是出现1次，那么可以通过把所有所有进行异或运算解决。因为x^x = 0。
但如果有两个数字出现一次，能否转化成上述问题？依旧把所有数字异或，最终的结果就是那两个出现一次的数字a,b异或的结果。因为a，b不想等，因此结果肯定不为0，那么结果的二进制表示至少有一位为1，找到那个1的位置p，然后我们就可以根据第p位是否为1将所有的数字分成两堆，这样我们就把所有数字分成两部分，且每部分都是只包含一个只出现一次的数字、其他数字出现两次，从而将问题转化为最开始我们讨论的“数组中只出现一次的一个数字”问题。 实例分析(以2,4,3,6,3,2,5,5为例)：
相关数字的二进制表示为：
2 = 0010 3 = 0011 4 = 0100
5 = 0101 6 = 0110 步骤1 全体异或：2^4^3^6^3^2^5^5 = 4^6 = 0010
步骤2 确定位置：对于0010，从右数的第二位为1，因此可以根据倒数第2位是否为1进行分组
步骤3 进行分组：分成[2,3,6,3,2]和[4,5,5]两组
步骤4 分组异或：2^3^6^3^2 = 6，4^5^5 = 4，因此结果为4，6。
*/
class class56 {
public:
int findIndexOne(int p){
int index=;
while ((p&)==) {
p=p>>;
index++;
}
return index; } int isBitOne(int num,int index){
return (num>>index)&;
}
vector<int> singleNumber(vector<int>& nums) {
int p=;
for (int i=; i<nums.size(); i++) {
p=p^nums[i];
}
//找出p从右向左第一次二进制 1 的位置
int index = findIndexOne(p);
//根据当前位置 index 是否为1 ，把数组分为2份
vector<int>vec;
vec.push_back();
vec.push_back();
for (int i=; i<nums.size(); i++) {
if(isBitOne(nums[i],index)){
vec[]=vec[]^nums[i];
}
else {
vec[]=vec[]^nums[i];
}
}
return vec;
}
};
数组中只出现一次的两个数字2
/*
56题-2
数组中只出现一次的两个数字2
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
*/
class class56_2{
int singleNumber(vector<int>& nums) {
// [111,111,111,101] = 4 3 4
// 第一步：遍历数组，对每一个元素的 32位 ，都相加
int lengthTotal = * sizeof(int);
vector<int>bits(lengthTotal,);
for (int i=; i<nums.size(); i++) {
int num = nums[i];
int bitMask = ;
for (int j=; j<lengthTotal; j++) {
if( num & bitMask){
bits[j] += ;
}
bitMask = bitMask << ; } }
// 对3取余数，不为0 ，就是 单独数字的对应 位数位1
//从最高位开始，然后 左移一位，相当于乘以2 int index=;
for (int i=lengthTotal- ; i>=; i--) {
index = index << ;
int v = bits[i]%;
if(v){//有余数
index+=v;//+1
} } return index;
}
};
和为S的两个数
/*
57题目
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，
如果有多对数字的和等于S，输出任意一对即可
*/
class Class_57{
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> result;
int len = (int)array.size();
if(len<=)return result;
int Sum;
int i = ;
int j = len - ;
while(i<j){
Sum = array[i] + array[j];
if(Sum>sum) j--;
else if(Sum<sum) i++;
else{
result.push_back(array[i]);
result.push_back(array[j]);
break;
}
}
return result;
} };
和为S的连续正数序列
/*
第57-2题
和为S的连续正数序列
输入一个正数s,打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15；所以打印出三个连续序列1~5,4~6,7~8；
*/
class Class_57_2{
public:
void FindContinuousSequence(int sum)
{
if(sum < )
return; int small = ;
int big = ;
int middle = ( + sum) / ;
int curSum = small + big; while(small < middle)//循环到中间值即可，之后的值的和肯定是大于sum
{
if(curSum == sum)
PrintContinuousSequence(small, big); while(curSum > sum && small < middle)
{
curSum -= small;
small ++; if(curSum == sum)
PrintContinuousSequence(small, big);
} big ++;
curSum += big;
}
} void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d ", i); printf("\n");
}
};
翻转字符串 leetcode(151)
/*
58题：翻转字符串 leetcode(151)
给定一个字符串，逐个翻转字符串中的每个单词。
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
*/
class class58{
void reverse2(string& s,int i ,int j){
int begin=i;
int end = j;
while (begin<end) {
char temp = s[begin];
s[begin]=s[end];
s[end]=temp;
begin++;
end--;
}
}
// abc edf abc
string reverseWords(string s) {
string finalS = s;
reverse2(finalS,,(int)s.length()-);
string temp="";
string newStr="";
finalS+=' ';
for(int i=;i<finalS.length();i++){
if(finalS[i]==' '){ if(finalS[i+]==' '){//连续的空格
}
else if(temp.length()==){//字符串开头就有空格
}
else{ //到了单词的底部了
reverse2(temp, , (int)temp.length()-);
newStr+=temp+' ';
temp="";
} }
else{
temp+=finalS[i];
} }
return newStr.length()>?newStr.substr(,newStr.length()-):newStr;
} };
左旋转字符串
/*
58题-2：左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串坐旋转操作的功能。比如输入字符串“abcdefg"和数字2，该函数将返回左旋转两位得到的结果：”cdefgab"
*/
class class58_2 {
void reverse2(string& s,int i ,int j){
int begin=i;
int end = j;
while (begin<end) {
char temp = s[begin];
s[begin]=s[end];
s[end]=temp;
begin++;
end--;
}
}
string LeftRotateString(string s,int n){
int nLength = (int)s.length();
if(nLength > && n > && n < nLength)
{
int pFirstStart = ;
int pFirstEnd = n - ;
int pSecondStart = n;
int pSecondEnd = nLength - ;
reverse2(s,pFirstStart, pFirstEnd);
reverse2(s,pSecondStart, pSecondEnd);
reverse2(s,pFirstStart, pSecondEnd);
}
return s;
} };
滑动窗口最大值
/*
59题目
滑动窗口最大值
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，{2,3,4,2,6,2,5,1}以及窗口大小3，那么存在6个滑动窗口，最大值分别为{4,4,6,6,6,5} 滑动 思路
滑动窗口可以看作是队列，为了得到滑动窗口的最大值，队列可以从两端删除元素，因此使用双向队列。 原则：对于新来的元素k，将其与队列中元素比较， 1、若队列中有元素比k小，直接将之前比k小的元素移除队列（因为不可能再成为后面滑动窗口的最大值），压入k 2、若队列中元素x比k大，则根据下标检测x是否在窗口内，如果不在则移除队列，压入k 队列的第一个元素是滑动窗口的最大值，同时要存储数字在数组的下标，而不是数值，用来判断滑动窗口是否包含数字 举例说明： 1、将2压入队列 2、3比2大，弹出2，压入3 3、4比3大，弹出3，压入4 4、2比4小，4还在窗口内，保留4，压入2 5、6比4和2都大，因此弹出4和2，压入6 6、2比6小，6在窗口内，保留6，压入2 7、5比2大，比6小，且6还在窗口内，弹出2，压入5 8、1比6和5都小，但是6不在窗口内，6弹出，压入1
*/
class class59_1 {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int size) {
vector<int>maxInWindows;
if(nums.size()>=size && size>= ){
deque<int>index;
for (int i=; i<size; i++) {
while (index.size()!= && nums[i]>= nums[index.back()]) {
index.pop_back();//从队尾出来
}
index.push_back(i);//对头是最大值
}
for (int i = size; i<nums.size(); i++) { //继续向后遍历
//把上一组的最大值加入到vector
maxInWindows.push_back(nums[index.front()]);//对头放最大值
//继续寻找下一组的最大值 while (index.size()>&&nums[i]>= nums[index.back()]) {//当前元素的值大于队尾，让他们出列
index.pop_back();
}
//当前处理的下标和头部的下标大于等于 size的时候，对头的就出列
if(index.size()> && i-index.front()>=size){
index.pop_front();
}
index.push_back(i); }
//把最后一组最大值加入vector
maxInWindows.push_back(nums[index.front()]); }
return maxInWindows;
}
};
队列最大值
/*
题目59-2
请定义一个队列并实现函数max得到队列里的最大值，要求函数max，push_back，pop_front的时间复杂度都是O(1)
思路：
和上一题类似，
1新建一个保持最大值的双向队列，最大值始终放到队列头
2 移除的元素如果是最大值，才需要移除索引队列
*/
class class59_2{
public:
class59_2() : currIndex() {} void push_back(int number)
{
while (!maxisium.empty() && number > maxisium.back().number)
maxisium.pop_back(); Inner inner = { number, currIndex };
data.push_back(inner);
maxisium.push_back(inner); ++currIndex;
} void pop_front()
{
if (data.front().index == maxisium.front().index)
maxisium.pop_front(); data.pop_front();
} int max()
{
return maxisium.front().number;
} private:
struct Inner
{
int number;
int index;
};
deque<Inner> maxisium;
deque<Inner> data;
int currIndex;
};
n个骰子的点数
/*题目60
n个骰子的点数
把n个骰子扔到地上，所有骰子朝上一面的点数之后为s. 输入n，打印出s所有可能的值出现的概率。（每个骰子6个面，点数从1到6）
*/
class class_60{
/*
方法一：回溯法：仅供测试，未剪枝
*/
//2 3 4 2 6 2 5 1 size = 3
void shaziSub(vector<vector<int>>vecs,int n,int s,int &count,int &curSum,int m){ if(m==n){//最后一个骰子已经算完
if(curSum==s){
count++;
}
return;
}
vector<int>curVec = vecs[m];//当前第几个骰子 for (int i=; i<; i++) {//遍历骰子的6个值
curSum+=curVec[i];
//看下一个骰子
shaziSub(vecs, n, s, count, curSum,m+);
//回溯
curSum-=curVec[i]; }
}
int shaziDianshu(int n,int s){
vector<vector<int>> vec;
for (int i=; i<n; i++) {
vector<int>subVec;
for (int j=; j<=; j++) {
subVec.push_back(j);
}
vec.push_back(subVec);
}
int count=;
int curSum=;
int m=;//第几个骰子
shaziSub(vec, n, s, count,curSum, m);
return count;
} /*
方法二：
递归
缺点，：很多重复计算
比如 计算和为4，要从1开始加，不能利用之前计算的结果
递归的思想一般是分而治之，把n个骰子分为第一个和剩下的n-1个。先计算第一个骰子每个点数出现的次数，再计算剩余n-1个骰子出现的点数之和。求n-1个骰子的点数之的方法和前面讲的一样，即再次把n-1个骰子分成两堆------第一个和剩下的n-2个。n个骰子，每个骰子6个面，总共有6n个组合。这6n个组合之中肯定有重复的，我们知道其范围是n~6n,对于每种情况我们可以用缓存机制记录下来，每当其发生一次我们令其对应的单元加1。 我们定义一个长度为6n-n+1的数组，和为s的点数出现的次数保存到数组第s-n个元素里。为什么是6n-n+1呢？因为n个骰子的和最少是n，最大是6n，介于这两者之间的每一个情况都可能会发生，总共6n-n+1种情况。
*/
int g_maxValue = ;
void Probability(int original, int current, int sum,
int* pProbabilities)
{
if(current == )
{
pProbabilities[sum - original]++;
}
else
{
for(int i = ; i <= g_maxValue; ++i)
{
Probability(original, current - , i + sum, pProbabilities);
}
}
}
void Probability(int number, int* pProbabilities)
{
for(int i = ; i <= g_maxValue; ++i)
Probability(number, number, i, pProbabilities);
}
void PrintProbability_Solution1(int number)
{
if(number < )
return; int maxSum = number * g_maxValue;
int* pProbabilities = new int[maxSum - number + ]; for(int i = number; i <= maxSum; ++i)
pProbabilities[i - number] = ; Probability(number, pProbabilities); int total = pow((double)g_maxValue, number);
for(int i = number; i <= maxSum; ++i)
{
// double ratio = (double)pProbabilities[i - number] / total;
double ratio = (double)pProbabilities[i - number];
printf("%d: %f\n", i, ratio);
} delete[] pProbabilities;
} /*
方法三：
动态规划:
基于循环，时间性能好
递归一般是自顶向下的分析求解，而基于循环的方法则是自底向上。
基于循环的一般需要更少的空间和更少的时间，性能较好，但是一般代码比较难懂。
思路关键点：
我们考虑一个骰子一个骰子的放，比如 第一次剖第一个，那么和为1-6 的次数都是1
然后放置第二个骰子， 和的集合为 2-12 ，第二个骰子仍然是6个面，大小为 1 2 3 4 5 6
比如 计算 和为 8 ，可以是 1和f(7)， 2和f(6) ，3和f(5),4和f(4),5和f(3), 6和f(2)
也就是上一次所有骰子的f(7) f(6) f(5) f(4) f(3) f(2) 的总和,有点动态规划的意思
*/
void PrintProbability_Solution3(int number)
{
if(number < )
return; int* pProbabilities[];
pProbabilities[] = new int[g_maxValue * number + ];
pProbabilities[] = new int[g_maxValue * number + ];
for(int i = ; i < g_maxValue * number + ; ++i)
{
pProbabilities[][i] = ;
pProbabilities[][i] = ;
} int flag = ;
for (int i = ; i <= g_maxValue; ++i){
pProbabilities[flag][i] = ; //[0][1] [0][2] [0][3] [0][4] [0][5] [0][6] = 1
} //从第二次开始掷骰子，假设第一个数组中的第n个数字表示骰子和为n出现的次数，
//在下一循环中，我们加上一个新骰子，此时和为n的骰子出现次数应该等于上一次循环中骰子点数和为n-1,n-2,n-3,n-4,n-5，
//n-6的次数总和，所以我们把另一个数组的第n个数字设为前一个数组对应的n-1,n-2,n-3,n-4,n-5，n-6之和
for (int k = ; k <= number; ++k)//剩下的骰子
{
//第k次掷骰子，和最小为k，小于k的情况是不可能发生的！所以另不可能发生的次数设置为0！
for(int i = ; i < k; ++i){
pProbabilities[ - flag][i] = ; //[1][0] [1][1] = 0
}
//第k次掷骰子，和最小为k，最大为g_maxValue*k
for (int i = k; i <= g_maxValue * k; ++i)// 2 - 12
{
//初始化，因为这个数组要重复使用，上一次的值要清0
pProbabilities[ - flag][i] = ; for(int j = ; j <= i && j <= g_maxValue; ++j)
{ pProbabilities[ - flag][i] += pProbabilities[flag][i - j];
} } flag = - flag;
}
double total = pow((double)g_maxValue, number);
for(int i = number; i <= g_maxValue * number; ++i)
{
double ratio = (double)pProbabilities[flag][i];
printf("%d: %f\n", i, ratio);
} delete[] pProbabilities[];
delete[] pProbabilities[];
} };
扑克牌中的顺子
/*
题目：61 扑克牌中的顺子
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。
思路：
1 数组排序
2 统计 0 的个数
3 统计 连续数字之间空缺的个数，如果0>=空缺的个数，就是顺子
*/
bool IsContinuous( vector<int> numbers ) {
if(numbers.size()==){
return false;
}
sort(numbers.begin(), numbers.end());
int zeroCount=;
int gapCount=;
//统计0 的个数
for(int i=;i<numbers.size();i++){
if(numbers[i]==){
zeroCount++;
}
}
for (int i = zeroCount+; i<numbers.size(); i++) {
//如果两个相等，说明有对子，不是顺子
if(numbers[i]==numbers[i-]){
return false;
}
gapCount+= numbers[i-]-numbers[i]+;
}
return gapCount>zeroCount?false:true; }
圆圈中最后剩下的数字
/*
题目62 有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。
每次喊到m-1的那个小朋友要出列并且不再回到圈中,从他的下一个小朋友开始,
继续0…m-1报数….这样下去….直到剩下最后一个小朋友,求最后一个小朋友的编号
*/
class class62{ int LastRemaining(int n ,int m){//n=5 m=3
if(n<||m<){
return -;
} //先组装
vector<int>vec;
for(int i=;i<n;i++){
vec.push_back(i);//编号
} if(m==){
return vec[n-];
}
int index=;
auto it = vec.begin();
while (vec.size()>) {
++index;
it++;
if(it==vec.end()){ //超出底部了。回归0
it = vec.begin();
}
if(index%m==){
vec.erase(it);//it特点，删除之后，it自动指向下一个位置
if(it==vec.end()){//到底之后，重新到头
it= vec.begin();
}
index=;
}
}
return vec[];
} };
股票的最大利润
/*
63题目：股票的最大利润
股票的最大利润（一次卖出）
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？
例子：
例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。
如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.
*/
//动态规划
/*
4个步骤
1 单个问题：
总共有n天，求最大利润
1天，求最大利润
2天，求最大利润
2 边界值
第一天 利润为0，最小值为9
3 状态i 为 截止到i天 ，所获的的最大利润
4 方程
f(n) =max(f(n-1),n天的价格-最小值)
*/
// 9 11 8 5 7 12 16 14
class class_63{
int maxProfit(vector<int>& prices) {
int num = (int)prices.size();
if(num==){
return ;
}
vector<int>vec;
int min=prices[];
for (int i =; i<num; i++) {
vec.push_back();
} for (int i=; i<num; i++) {
int day = prices[i];
if(day<min){
min=day;
}
vec[i]=max(vec[i-],day-min);
}
return vec[num-];
} };
求1+2+3…+n
/*
64题目：求1+2+3…+n
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
*/
class class_64{
public:
int Sum_Solution(int n) {
int res = n;
//递归跳出条件，当res为假时,无需判断后序语句，返回res
res&&(res+=Sum_Solution(n-));
return res; } };
求两个整数之和
/*
65题目：
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
*/
class class_65{
int Add(int num1,int num2){
int sum;
int carry;
do {
sum = num1^num2;
carry = (num1 & num2) << ;
num1 = sum;
num2 = carry;
} while (num2!=);
return num1;
}
};
构建乘积数组
/*
66题目
构建乘积数组
给定一个数组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 class_66{
void BuildProductionArray(const vector<double>& input, vector<double>& output)
{
int length1 = (int)input.size();
int length2 = (int)output.size(); if(length1 == length2 && length2 > )
{
output[] = ;
for(int i = ; i < length1; ++i)
{
output[i] = output[i - ] * input[i - ];
} double temp = ;
for(int i = length1 - ; i >= ; --i)
{
temp *= input[i + ];
output[i] *= temp;
}
}
}
};
最低公共节点
/*
67题目：
最低公共节点：
*/
class class_67{
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/*
变式1 树是二叉搜索树
*/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!p||!q){
return nullptr;
}
if(root==nullptr)return nullptr;
int v = root->val;
int v1 = p->val;
int v2 = q->val;
if((v>v1&&v<v2)||(v>v2&&v<v1)){
return root;
}
else if(v>v1&&v>v2){
return lowestCommonAncestor(root->left, p, q);
}
else if(v<v1&&v<v2){
return lowestCommonAncestor(root->right, p, q);
}
else if(v==v1||v==v2){
return root;
}
return nullptr;
}
/*
变式2 树是普通的二叉树(不是二叉树，而是树的话也是一个道理，就类似于图了)
*/
/*思考：
1.两个节点的公共祖先一定在从根节点，至这两个节点的路径上。
2.由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路
径上的离根节点最远的节点(或离两个最近)。
3.最终算法即:求p节点路径，q节点路径，两路径上最后一个相同 的节点。
所以，我们先求跟节点到某节点的路径的函数（深度搜索）
步骤：
1.从根节点遍历(搜索)至该节点，找到该节点后就结束搜索。
2.将遍历过程中遇到的节点按照顺序存储起来，这些节点即路径节点。
*/
/*
参数1：正在遍历的节点
参数2:待搜索的节点
参数3:遍历时的节点路径
参数4:最终搜索到节点search的路径结果
参数5:记录是否找到节点search变量，未找到是0，找到是1
*/ void preorder22(TreeNode *node,TreeNode *search,
vector<TreeNode*>&path,vector<TreeNode*>&result,int &finish)
{
if(node==NULL||finish){
return;
}
path.push_back(node);
if(node==search){
finish=;
result=path;
}
preorder22(node->left, search, path, result,finish);
preorder22(node->right, search, path, result,finish);
path.pop_back();//b结束遍历node时，将node从栈中弹出
} /*
然后求两路径上最后一个相同的节点
步骤：
1.求出较短路径的长度n。
2.同时遍历p节点的路径与q节点的路径，遍历n个节点，最后一个发现的相同节点，即最近公共祖先。
*/ TreeNode *lowestCommonAncestor2(TreeNode *root,TreeNode*p,TreeNode *q)
{
vector<TreeNode*>path;//声明遍历用的临时栈
vector<TreeNode*>node_p_path;
vector<TreeNode*>node_q_path;
int finish=;
//求出p的路径
preorder22(root, p, path, node_p_path, finish);
//清空path,finish,计算q节点路径
path.clear();
finish=;
preorder22(root, q, path, node_p_path, finish);
//较短路径的长度
int path_len=;
if(node_p_path.size()<node_q_path.size()){
path_len=(int)node_p_path.size();
}
else{
path_len=(int)node_q_path.size();
}
//同时遍历根到p，q两个节点的路径上的节点
TreeNode * result=;
for (int i=; i<path_len; i++) {
if(node_p_path[i]==node_q_path[i]){
result=node_p_path[i];//找到最近公共祖先
}
}
return result;
} };