《剑指offer》week7

发表于 | 分类于 ，

问题一：滑动窗口的最大值

问题描述

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口，它们的最大值分别为[4, 4, 6, 6, 6, 5]。

注意：

  • 数据保证k大于0，且k小于等于数组长度。

样例

1
2
3
输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

问题分析

(单调队列) $O(n)$

首先，最直接的做法当然是模拟滑动窗口的过程，每向右滑动一次都遍历一遍窗口内的数字找最大的输出，这样的复杂度是$O(kn)$，我们可以考虑优化一下。窗口向右滑动的过程实际上就是将处于窗口的第一个数字删除，同时在窗口的末尾添加一个新的数字，这就可以用双向队列来模拟，每次把尾部的数字弹出，再把新的数字压入到头部，然后找队列中最大的元素即可。

为了更快地找到最大的元素，我们可以在队列中只保留那些可能成为窗口最大元素的数字，去掉那些不可能成为窗口中最大元素的数字。考虑这样一个情况，如果队列中进来一个较大的数字，那么队列中比这个数更小的数字就不可能再成为窗口中最大的元素了，因为这个大的数字是后进来的，一定会比之前早进入窗口的小的数字要晚离开窗口，那么那些早进入且比较小的数字就“永无出头之日”，所以就可以弹出队列。

于是我们维护一个双向单调队列，队列放的是元素的下标。我们假设该双端队列的队头是整个队列的最大元素所在下标，至队尾下标代表的元素值依次降低。初始时单调队列为空。随着对数组的遍历过程中，每次插入元素前，首先需要看队头是否还能留在队列中，如果队头下标距离i超过了k，则应该出队。同时需要维护队列的单调性，如果nums[i]大于或等于队尾元素下标所对应的值，则当前队尾再也不可能充当某个滑动窗口的最大值了，故需要队尾出队。始终保持队中元素从队头到队尾单调递减。依次遍历一遍数组，每次队头就是每个滑动窗口的最大值所在下标。

时间复杂度分析：每个元素最多入队出队一次，复杂度为$O(n)$

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
    	vector<int> res;
    	deque<int> q;
    	for(int i=0;i<nums.size();i++){
  			if(!q.empty()&&i-q.front()>=k) q.pop_front();
  			while(!q.empty()&&q.back()<nums[i]) q.pop.back();
  			q.push_back(i);
  			if(i>=k-1) res.push_back(nums[q.front()]);
		}
		returnn res;
    }
};

总结

deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成员函数：

  • dequeq;//定义一个双向队列q，类型为int
  • q.push_front(a);//将a从队首插入队列
  • q.push_back(a);//将a从队尾插入队列
  • q.pop_front();//队首弹掉一个元素
  • q.pop_back();//队尾弹出一个元素
  • a=q.front();//返回队首元素
  • a=q.back();//返回队尾元素
  • a=q.size();//返回双向队列的大小
  • a=q.empty();//判断双向队列是否为空，为空返回1，不为空返回0
  • q.clear(); //将队列q清空

问题二：骰子的点数

问题描述

将一个骰子投掷n次，获得的总点数为s，s的可能范围为n~6n。

掷出某一点数，可能有多种掷法，例如投掷2次，掷出3点，共有[1,2],[2,1]两种掷法。

请求出投掷n次，掷出n~6n点分别有多少种掷法。

样例1

1
2
3
4
5
输入：n=1

输出：[1, 1, 1, 1, 1, 1]

解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。

样例2

1
2
3
4
5
6
7
输入：n=2

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

解释：投掷2次，可能出现的点数为2-12，共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。

      所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

问题分析

算法一：动态规划

  • 弄清楚状态的含义是什么，比如这里$f[i][j]$表示投掷$i$次总和为$j$的状态
  • 状态转换：第$i$次可以有哪些情况（热狗法），在这里第$i$次有$k$种情况，然后就可以得出状态转移，$f[i][j]+=f[i-1][j-k]$
  • 边界情况，考虑$i=0$或者$j=0$的情况，这里当i和j同时为0的时候，$f[0][0]=1$

算法二：递归

1、状态的含义是什么，同上

2、顺序是什么

3、边界

C++代码

算法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> numberOfDice(int n) {
    	vector<vector<int>> f(n+1,vector<int>(6*n+1,0));
    	f[0][0]=1;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=6*j;j++)
    			for(int k=1;k<=min(6,j);k++){
    				f[i][j]+=f[i-1][j-k];
				}
		vector<int> res;
		for(int i=n;i<=6*n;i++)
			res.push_back(f[n][i]);
    }
};

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> numberOfDice(int n) {
    	vector<int> res;
    	for(int i=n;i<=6*n;i++)
    	res.push_back(dfs(n,i))
    }
   	int dfs(int n,int sum){
  		if(n==0) return !sum;
  		if(sum<0) return 0;
  		int res;
  		for(int i=1;i<=6;i++){
  			res+=f(n-1,sum-i);
		}
		return res;
	}
}

问题三：扑克牌的顺子

问题描述

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。

2～10为数字本身，A为1，J为11，Q为12，K为13，大小王可以看做任意数字。

为了方便，大小王均以0来表示，并且假设这副牌中大小王均有两张。

样例1

1
2
3
输入：[8,9,10,11,12]

输出：true

样例2

1
2
3
输入：[0,8,9,11,12]

输出：true

问题分析

能组成顺子需要满足的两个条件是：

  • 除了0以外不能出现两个相同的数字；
  • 排序后两个相邻数字的差值不能大于0的个数。

按照这两个条件进行判断即可。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isContinuous( vector<int> nums) {
    	sort(nums.begin(),nums.end());
    	int zerocount=0;
    	for(int i=0;i<nums.size()-1;i++){
  			if(nums[i]==0) zerocount++;
  			else{
  				if(nums[i]==nums[i+1]) return false;
  				if(nums[i+1]-nums[i]>zerocount+1) return false;
  				else if(nums[i+1]-nums[i]<=zerocount+1) zerocount-=nums[i+1]-nums[i]-1;
			} 
		}
		return true;
	}
};

问题四：圆圈中最后剩下的数字

问题描述

0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。

求出这个圆圈里剩下的最后一个数字。

样例

1
2
3
输入：n=5 , m=3

输出：3

问题分析

约瑟夫环问题 递归

递推删除前和删除后数值的映射关系

在这$n$个数字中，第一个被删除的数字是$(m-1)%n$，为了简单起见，假设这个数字为$k$，那么删除k后剩下的n-1个数字为$0,1,…,k-1,k+1,…,n-1$，并且下一次删除从数字k+1开始计数。相当于在剩余的序列中，k+1是排在最前面，从而形成$k+1,…,n-1,0,1,…,k-1$.该序列最后的数字也是关于n和m的函数。我们把删除前得到的最后数字为f(n,m)，删除后的最后数字为$F(n-1,m)$，我们需要找到F和f之间的关系，这种关系也就是两种序列（删除前和删除后）之间的映射关系，然后将F用f表示，就可以用递推关系。

…..

$f(n,m)=(F(n-1,m)+m)%n$

C++代码

1
2
3
4
5
6
class Solution {
public:
    int lastRemaining(int n, int m){
    	return n==1?0:(lasrRemaining(n-1,m)+m)%n;   //这个就很牛逼了
    }
};

问题五：股票的最大利润

问题描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。

样例

1
2
3
输入：[9, 11, 8, 5, 7, 12, 16, 14]

输出：11

问题分析

扫描 $O(n)$

每扫描到一个位置的时候，用一个变量记录在这个元素之前最小的元素，就可以只用一次循环

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
//用一个变量记录下扫描到的元素之前的元素的最小值
public:
    int maxDiff(vector<int>& nums) {
    	if(nums.empty()) return 0;
    	int minv=nums[0];
    	int res=0;
    	for(int i=1;i<nums.size();i++){
  			res=max(nums[i]-minv,res);
  			minv=min(minv,nums[i]);
		}
		return res;
	}
};

问题六：求1+2+…+n

问题描述

求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

样例

1
2
3
输入：10

输出：55

问题分析

位运算

a&&b，如果a为真的话就会执行b，如果a为假就不会执行b。这个很好的性质就可以用在if语句中。

C++代码

1
2
3
4
5
6
7
8
class Solution {
public:
    int getSum(int n) {
        int res=n;
        n>0&&(res+=getSum(n-1));
        return res;
    }
};

问题七：不用加减乘除做加法

问题描述

写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。

样例

1
2
3
输入：num1 = 1 , num2 = 2

输出：3

问题分析

算法一：全加器

不能使用加减乘除，那么考虑使用位运算。最直接的是想到用全加器实现，即对于两个数字的每一位以及上一位的进位Cin，进行异或^操作得到该位的输出值S，进行与&操作得到进位Cout，再把Cout传递到下一位作为下一位的Cin。

$S=A⊕B⊕Cin$

$Co=ACin+BCin+AB$

其中$A,B$为要相加的数，$Cin$为进位输入；$S$为和，$Co$是进位输出；

时间复杂度分析：由于$num1$和$num2$都是$int$型，因此一共32位，对32位依次进行操作即可。

算法二：位运算

以5+17=22为例，参考十进制加法：1、只做各位相加不进位运算，即得到12,；2、做进位运算，即得到10,；3、把前面两个结果先相加，即得到22；

同样二进制加法也一样：

1、两个整数做异或^，得到各位相加不进位的运算结果；

2、两个整数做与&，然后再左移一位，即得到进位的运算结果；

3、将上面两个结果相加，即重复步骤1,2，直至进位的运算结果为0；

时间复杂度分析：$O(logN)$

C++代码

算法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int add(int num1, int num2){
    	int tmp=1;
    	int Cin=0;
    	int res=0;
    	for(int i=0;i<32;i++){
 			int a= num1&tmp;
 			int b= num2&tmp;
 			int s=a^b^Cin;
 			int Cout=(a&b)|(a&Cin)|(b&Cin);
 			cin=Cout<<1;
 			tmp=tmp<<1;
 			res+=s;
		}
		return res;
    }
};

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int add(int num1, int num2){
    	while(nums2){
  			int sum=num1^num2;
  			int carry=num1&num2;
  			num1=sum;
  			num2=carry;
		}
		return num1;
	}
};

问题八：构建乘积数组

问题描述

给定一个数组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]。

不能使用除法。

样例

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

输出：[120, 60, 40, 30, 24]

思考题：

  • 能不能只使用常数空间？（除了输出的数组之外）

问题分析

计算每一位的数值的时候，只需要计算这个数的左侧数字之积还有右侧的数字之积。

$B[i]=A[left(i)]*A[right(i)]$

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
    	vector<int> B(A.size(),0);
    	for(int i=1,p=1;i<A.size();i++){
  			B[i]=p;
  			p*=A[i];
		}
		for(int j=A.size()-1,p=1;j>=0;j++){
  			B[j]*=p;
  			p*=A[j];
		}
		return B;
	}
};

问题九： 把字符串转换成整数

问题描述

请你写一个函数StrToInt，实现把字符串转换成整数这个功能。

当然，不能使用atoi或者其他类似的库函数。

样例

1
2
3
输入："123"

输出：123

注意:

你的函数应满足下列条件：

  1. 忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
  2. 整数后可能有任意非数字字符，请将其忽略；
  3. 如果整数长度为0，则返回0；
  4. 如果整数大于INT_MAX(2^31 − 1)，请返回INT_MAX；如果整数小于INT_MIN(−2^31) ，请返回INT_MIN；

问题分析

  • 首先将空格去掉
  • 判断是否有加减号
  • 判断每一位是否是数字
  • 判断是否溢出
  • 如果为负值则乘以-1

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int strToInt(string str) {
    	long long res=0;
    	int k=0;
    	while(k<str.szie()&&str[k]==' ') k++;
    	bool minus=false;
    	if(str[k]=='+') k++;
    	if(str[k]=='-') k++,minus=true;
    	while(k<str.size()&&str[k]>='0'&&str[k]<='9'){
  			res+=res*10+str[k]-'0';
		}
		if(minus) res=-1*res;
		if(res>INT_MAX) return INT_MAX;
		if(res<INT_MIN) return INT_MIN;
		return res;
	}
};

问题十：树中两个结点的最低公共祖先

问题描述

给出一个二叉树，输入两个树节点，求它们的最低公共祖先。

一个树节点的祖先节点包括它本身。

注意：

  • 输入的二叉树不为空；
  • 输入的两个节点一定不为空，且是二叉树中的节点；

样例

1
2
3
4
5
6
7
8
9
10
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
    8
   / \
  12  2
     / \
    6   4

1. 如果输入的树节点为2和12，则输出的最低公共祖先为树节点8。

2. 如果输入的树节点为2和6，则输出的最低公共祖先为树节点2。

问题分析

算法1：查找路径 $O(n)$

分别找出根节点到两个节点的路径，则最后一个公共节点就是最低公共祖先了。

时间复杂度分析：需要在树中查找节点，复杂度为$O(n)$

算法2:递归 $O(n)$

考虑在左子树和右子树中查找这两个节点，如果两个节点分别位于左子树和右子树，则最低公共祖先为自己(root)，若左子树中两个节点都找不到，说明最低公共祖先一定在右子树中，反之亦然。考虑到二叉树的递归特性，因此可以通过递归来求得。

时间复杂度分析：需要遍历树，复杂度为$O(n)$

C++代码

算法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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 findPath(TreeNode*root, TreeNode* p, vector<TreeNode*>&path){
        if(!root)
            return 0;
        if(root->val==p->val){
            path.push_back(root);
            return 1;
        }
        int l = findPath(root->left,p,path);
        int r = findPath(root->right,p,path);
        if(l==1||r==1)
            path.push_back(root);
        return l==1||r==1;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*>path1,path2;
        findPath(root,p,path1);
        findPath(root,q,path2);
        if(path1.empty()||path2.empty())
            return NULL;
        TreeNode* res =NULL;
        for(int i = 0;i<path1.size();i++){
            if(i>=path1.size()||i>=path2.size())
                break;
            if(path1[path1.size()-1-i]==path2[path2.size()-1-i])
                res = path1[path1.size()-1-i];
            else
                break;
        }
        return res;
    }
};

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            return NULL;
        if(root==p||root==q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left&&right)
            return root;
        if(left==NULL)
            return right;
        else
            return left;
    }
};
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多