问题一：0到n-1中缺失的数字

问题描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。

在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

样例

1
2
3

输入：[0,1,2,4]

输出：3

问题分析

算法一：二分查找 $O(logn)$

二分查找主要就是考虑我们要查找的值是在哪个区间，以及能否查找得到。

为什么说能否查找得到呢，比如这个题目里面，我们要查找的数是不在这个数组中的，但是我们知道这个数应该是在这个排序好的数组中的哪个区间。按照下面两种模板进行考虑

版本1

当区间[l, r]的更新操作是r = mid; l = mid + 1;时，计算mid时不需要加1。

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

算法二：高斯公式 $O(n)$

0~n-1这总共是含有n个数的，可以先计算出这n个数的总和，然后把这n个数全部加起来，也就是利用高斯公式。然后依次遍历nums数组，依次减去遍历到的值，最终总和剩下的值就是缺失的值。

C++代码

算法一：

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
    	int l=0,r=nums.size()-1;
      	while(l<r){
  			int mid=l+r>>1;
          	if(nums[mid]==mid) l=mid+1;  //我们要查找的数是在右区间
          	else r=mid;   //我们要查找的数是在左区间
		}
      	if(nums[r]==r) r++;
      	return r;   //这里是按照模板一来进行查找的，最终是定位在最大值的最小值上，所以要减一
    }
};

算法二：

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
      	int n=nums.size();
      	int count=(n-1)*n/2;
      	for(auto x:nums){
  			count-=x;
		}
      return x;
    }
}

总结

整数域二分

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。l和r的确定就是判别条件进行更新，判断我们要查找的值是在哪个区间。

版本1

当区间[l, r]的更新操作是r = mid; l = mid + 1;时，计算mid时不需要加1。

C++ 代码模板：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

解读

我们要在下面一串数中用上面的二分查找代码查找 11

第一次查询，$(l+r)/2=4$，查到 $8$ ，是小于$11$ 的，于是更新，$l=4+1=5$

第二次查询，$(l+r)/2=6$，查到 $12$ ，是大于$11$ 的，于是更新，$r=mid=6$

第三次查询，$(l+r)/2=5$ ，查到$10$，是小于$11$的，于是更新，$l=5+1=6$

最终得到结果为$12$ 。$12$是我们查找到这一串数中，大于等于11(查找数)中最小值。

我们可以得到一个结论：以上二分模板用来解，最大值最小问题。

版本2

当区间[l, r]的更新操作是r = mid - 1; l = mid;时，计算mid时需要加1。

C++ 代码模板：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

解读

我们要在下面一串数中用上面的二分查找代码查找 11

第一次查询，$(l+r+1)/2=4$，查到 $8$ ，是小于 $11$ 的，于是更新，$l=4$

问题二：数组中数值和下标相等的元素

问题描述

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组[-3, -1, 1, 3, 5]中，数字3和它的下标相等。

样例

1
2
3

输入：[-3, -1, 1, 3, 5]

输出：3

注意:如果不存在，则返回-1。

问题分析

二分查找

C++代码

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
    	int l=0,r=nums.size()-1;
    	while(l<r){
  			int mid=l+r+1>>1;
  			if(nums[mid]>mid) r=mid-1;
  			else l=mid;
		}
		if(nums[l]==l) return l;
		else return -1;
	}
};

总结

这个题目很明显是使用了模板二，在最后循环结束后我们需要判断一下l和r对应的数是否查找到了，也就是代码10、11行，因为有可能没有查找到，比如上一题就是没有找到。

问题三：二叉搜索树的第k个结点

问题描述

给定一棵二叉搜索树，请找出其中的第k小的结点。

你可以假设树和k都存在，并且1≤k≤树的总结点数。

样例

输入：root = [2, 1, 3, null, null, null, null] ，k = 3

    2
   / \
  1   3

输出：3

问题分析

中序遍历

二叉搜索数有一个很好地性质就是中序遍历的结果是递增的。

C++代码

/**
 * 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 {
//找中序遍历的第k个节点

public:
    TreeNode *ans;
    TreeNode* kthNode(TreeNode* root, int k) {
    	dfs(root,k);
    	return ans;
    }
    TreeNode* dfs(TreeNode* root,int &k){
  		if(!root) return null;
  		dfs(root->left,k);
  		k--;
  		if(!k) return root;
  		if(k>0) dfs(root->right,k);
	}
};

总结

中序遍历模板

void InOrder(TreeNode* root){
  	if(root){
  		InOrder(root->left);
  		visit(root);
  		InOrder(root->right);
	}
}

具体到这个题目中，中序遍历中的visit(root)就是判断k

问题四：二叉树的深度

问题描述

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

样例

输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
    8
   / \
  12  2
     / \
    6   4

输出：3

问题分析

算法一：递归

树的高度为左子树和右子树最大值加1，每次只要一次遍历每个子树，得到每棵子树的高度

算法二：层序遍历

设置变量level记录当前结点所在的层数，设置变量last指向当前层最右节点，每次遍历出队的时候与last指针比较，若两者相等，那么层数加1，并让last指向下一层最右节点，直至遍历完成，level的值即为二叉树的高度

循环过程中队列中的元素只可能是两层：当前层和下一层节点，last始终指向当前层最右端节点，若当前层节点到了当前层节点的最后一个时，那么加入到队列中的节点就是下一层的最右端节点

C++代码

算法一:

/**
 * 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:
    int treeDepth(TreeNode* root) {
      	if(!root) return 0;
      	int left=tressDepth(root->left),right=treeDepth(root->right);
      	return max(left,right)+1;
    }
};

算法二：

/**
 * 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:
    int treeDepth(TreeNode* root) {
    	queue<TreeNode*> q;
    	q.push(root);
    	TreeNode* last=root;
      	int level=0; 
    	while(q.size()){
  			auto t=q.front();
  			q.pop();
  			if(q->left) q.push(q->left);
  			if(q->right) q.push(q->right);
          	if(t==last){
  				last=q.back();
              	level++;
			}
		}
      	return leval;
    }
};

问题五：平衡二叉树

问题描述

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

注意：

规定空树也是一棵平衡二叉树。

样例

输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
    5
   / \
  7  11
    /  \
   12   9

输出：true

问题分析

只要求出左右子树的高度，然后判断左右子树的高度是否满足平衡二叉树的定义即可

C++代码

/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int left=treeDepth(root->left);
        int right=treeDepth(root->right);
        if(left-right>1||right-left>1) return false;
        return isBalanced(root->left)&&isBalanced(root->right);
    }
    int treeDepth(TreeNode* root){
        if(!root) return 0;
        return max(treeDepth(root->left),treeDepth(root->right))+1;
    }
};

问题六：数组中只出现一次的两个数字

问题描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

1
2
3

输入：[1,2,3,3,4,4]

输出：[1,2]

问题分析

位运算

考虑数组中只有一个数字只出现了一次，而其他数字出现了两次，我们只要将这所有的数字进行异或操作，那么最终得到的结果就是那一个只出现一次的数字。然而这个题目中是只出现了一次的数字有两个，我们也可以采用异或运算得出结果。

我们首先也是将所有的数字进行异或操作，得到的结果就是代表着两个只出现一次的数字。那么如何具体地根据这个结果求出这两个数字？

上一步得到的结果我们可以知道二进制表示中一定有某个位数上为1，那么根据这个位数上的1，我们将原来的数组可以分为两组，这两个数一定是分别在这两组中，每组所有数字异或操作完的结果就是这个只出现一次的数！

C++代码

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
    	int sum=0;
    	for(auto x:nums){
  			sum^=x;
		}
		int k=1;
		while(!((sum>>k)&1)) k++;
		int first=0,second=0;
		for(auto x:nums){
  			if(x>>k&1) first^=x;
  			else second^=x;
		}
		return vector<int>({first,second});
    }
};

总结

vector介绍

vector v(n,val) v中包含了n个重复的val值

vector v{a,b,c,d} v中包含了a、b、c、d四个元素

vector v={a,b,c,d} 等价于上面一条

问题七：数组中唯一只出现一次的数字

问题描述

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 $O(n)$的时间和额外 $O(1)$ 的空间，该怎么做呢？

样例

1
2
3

输入：[1,1,1,2,2,2,3,4,4,4]

输出：3

问题分析

算法一：状态机

初始状态为(0,0),遇1变为(1,0),遇1变为(0,1)，遇1变为(0,0),如果遇到0则发生不变

算法二：位运算

我们把数组中所有的数字的二进制表示的每一位都加起来，如果某一位的和能被3整除，那么那个只出现一次的数字的二进制表示中对应的那一位是0；否则就是1。

C++代码

算法一：

class Solution {
/*
采用状态机，初始状态为(0,0),遇1变为(1,0),遇1变为(0,1)，遇1变为(0,0),如果遇到0则发生不变
*/
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int ones=0,twos=0;
        for(auto x:nums){
            ones=(ones^x)&~twos;
            twos=(twos^x)&~ones;
        }
        return ones;
    }
};

算法二：

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
    	vector<int> bit(32,0);
    	for(int i=0;i<nums.size();i++){
    		int bitmask=1;
  			for(int j=31;j>=0;j--){
  				int bit=nums[i]&bitmask;
  				if(bit){
  					bit[j]+=1;
				}
				bitmask<<1;
			}
		}
		int result=0;
		for(int i=0;i<32;i++){
  			result=result<<1;
  			result+=bit[i]%3;
		}
		return result;
    }
}

问题八：和为S的两个数字

问题描述

输入一个数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。

如果有多对数字的和等于s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

样例

1
2
3

输入：[1,2,3,4] , sum=7

输出：[3,4]

问题分析

算法一：暴力枚举 $O(n^2)$

设置两个指针i和j，依次扫描

算法二：哈希表 $O(n)$

使用C++中的哈希表——unordered_map hash.

循环一遍 $nums$ 数组，在每步循环中我们做两件事：

判断$target−nums[i]$是否在哈希表中；
将$nums[i]$插入哈希表中；
解释：由于数据保证有且仅有一组解，假设是$i,j$，则我们循环到$j$时，$nums[i]$一定在哈希表中，且有 $nums[i]+nums[j]==target$，所以我们一定可以找到解。
时间复杂度：由于只扫描一遍，且哈希表的插入和查询操作的复杂度是 $O(1)$，所以总时间复杂度是$O(n)$.

C++代码

算法一：

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
    	vector<int> v;
    	for(int i=0;i<nums.size();i++){
  			for(int j=0;j<i;j++)
  				if(nums[i]+nums[j]==target)
  					v.push_back(nums[i]);
  					v.push_back(nums[j]);
  					break;
		}
		return v;
    }
};

算法二：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> res;
        unordered_set<int,int> hash;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int another = target - nums[i];
            if (hash.count(another))
            {
                res = vector<int>({hash[another], i});
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};

问题九：和为S的连续正数序列

问题描述

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

样例

1
2
3

输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

问题分析

双指针法

C++代码

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;
        vector<int> path;
        for(int i=0,j=1;j<nums.size()&&i<j;){
  			int count=(i+j)*(j-i+1)/2;
  			if(count==sum){
  				path.push_back(i);
  				path.push_back(j);
  				res.push_back(path);
  				path.clear();
  				i++;
  				j++;
			}
			else if(count>sum) i++;
			else j++;
		}
	}
};

总结

双指针法

适合条件：两个指针是单调递增的，结果是两个指针所指范围内的

三种情形：

两个指针之间的范围满足条件，找到一种答案，并让两个指针都向后移
快指针向后移
满指针向后移

问题十：翻转单词顺序

问题描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

为简单起见，标点符号和普通字母一样处理。

例如输入字符串"I am a student."，则输出"student. a am I"。

样例

1
2
3

输入："I am a student."

输出："student. a am I"

问题分析

先将句子翻转，然后将翻转后的每个单词进行翻转

C++代码

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(),s.end());
        for(int i=0;i<s.size();i++){
            int j=i;
            while(j<s.size()&&s[j]!=' ') j++;
            reverse(s.begin()+i,s.begin()+j);
            i=j;
        }
        return s;
    }
};

问题十一：左旋转字符串

问题描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。

注意：

数据保证n小于等于输入字符串的长度。

样例

1
2
3

输入："abcdefg" , n=2

输出："cdefgab"

问题分析

先将整个字符翻转，然后将左边的翻转，最后把右边的翻转

C++代码

class Solution {
public:
    string leftRotateString(string str, int n) {
    	reverse(str.begin(),str.end());
    	reverse(str.begin(),str.begin()+str.size()-n);
    	reverse(str.end()-n,str.end());
    	return str;
    }
};

总结

str.end()表示的是str最后一个元素的下一个位置

问题一：0到n-1中缺失的数字

问题描述

问题分析

C++代码

总结

问题二：数组中数值和下标相等的元素

问题描述

问题分析

C++代码

总结

问题三：二叉搜索树的第k个结点

问题描述

问题分析

C++代码

总结

问题四：二叉树的深度

问题描述

问题分析

C++代码

问题五：平衡二叉树

问题描述

问题分析

C++代码

问题六： 数组中只出现一次的两个数字

问题描述

问题分析

C++代码

总结

问题七：数组中唯一只出现一次的数字

问题描述

问题分析

C++代码

问题八：和为S的两个数字

问题描述

问题分析

C++代码

问题九：和为S的连续正数序列

问题描述

问题分析

C++代码

总结

问题十： 翻转单词顺序

问题描述

问题分析

C++代码

问题十一：左旋转字符串

问题描述

问题分析

C++代码

总结

问题六：数组中只出现一次的两个数字

问题十：翻转单词顺序