Leetcode常见题型

发表于 | 分类于 ，

写在前面

断更好久了，最近一直忙着实验室的项目的事，在此期间也刷完了一些算法题，比如剑指offer，但经历一两次面试后发现这些体量还是不够，决定要看看leetcode上面的常见题型，后面不间断地更新在准备秋招的过程中常见的题型，做一个记录

字典序的排序

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
起始我们放置[1，9]
	|放置1，我们放置[10，19]，递归
	|	放置[10,19]
	|		|首先放置10,然后放置[100, 109]，递归
	|		|	放置[100,109]
	|		|		|放置100，然后放置[1000,1009]，递归
	|		|		|放置101，然后放置[1010,1019]，递归
	|		|		|.
	|		|		|放置109，然后放置[1090,1099]，递归
	|		|
	|		|然后放置11,再放置[110, 119]，递归
	|		|.
	|		|最后放置19，再放置[190, 199]，递归
	|接着放置2，然后放置[20, 29]，递归
	|接着放置3，然后放置[30, 39]，递归
	|接着放置4，然后放置[40, 49]，递归
	|.
	|接着放置9，然后放置[90, 99]，递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
public:
	vector<int> res;
	vector<int> lexicalOrder(int n){
		myDFS(n,0);   //从0开始搜索
		return res;
	}
	void myDFS(int n,int lastNum){
		int nowNum=lastNum*10;   //将上一次的结果向左移一位，留出10个空
		if(nowNum!=0&&nowNum<=n){   //先处理末位为0的情况，如果是0的话那么就不需要添加到结果数组中
			res.push_back(nowNum);
			myDFS(n,nowNum);
		}
		for(int index=1;index<10&&nowNum+index<=n;index++){   //然后处理末位为1~9的情况
			res.push_back(nowNum+index);
			myDFS(n,nowNum+index);
		}
	}
}

字典序中第k小的数

思路

这其实是一个先序遍历的过程

仔细观察字典顺序的数组，我们可以发现，其实这是个十叉树Denary Tree，就是每个节点的子节点可以有十个，比如数字1的子节点就是10到19，数字10的子节点可以是100到109，但是由于n大小的限制，构成的并不是一个满十叉树。我们分析题目中给的例子可以知道，数字1的子节点有4个(10,11,12,13)，而后面的数字2到9都没有子节点，那么这道题实际上就变成了一个先序遍历十叉树的问题，那么难点就变成了如何计算出每个节点的子节点的个数，我们不停的用k减去子节点的个数，当k减到0的时候，当前位置的数字即为所求。现在我们来看如何求子节点个数，比如数字1和数字2，我们要求按字典遍历顺序从1到2需要经过多少个数字，首先把1本身这一个数字加到step中，然后我们把范围扩大十倍，范围变成10到20之前，但是由于我们要考虑n的大小，由于n为13，所以只有4个子节点，这样我们就知道从数字1遍历到数字2需要经过5个数字，然后我们看step是否小于等于k，如果是，我们cur自增1，k减去step；如果不是，说明要求的数字在子节点中，我们此时cur乘以10，k自减1，以此类推，直到k为0推出循环，此时cur即为所求：

代码

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
class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur = 1;
        --k;//初始化为cur = 1，k需要自减1
        while (k > 0) {
            long long step = 0, first = cur, last = cur + 1;
            //统计这棵子树下所有节点数（step）
            while (first <= n) {
                step += min((long long)n + 1, last) - first;//不能超过n的值，并不是所有节点都有十个子节点
                first *= 10;
                last *= 10;
            }
            if (step <= k) {//不在子树中
                ++cur;
                k -= step;
            } 
            else {//在子树中，进入子树
                cur *= 10;
                --k; 
            }
        }
        return cur;
    }
};

编辑距离

思路

状态表示：f[i,j]表示将word1 的前 $i$ 个字符变成 word2 的前$j$个字符，最少需要进行多少次操作。
状态转移，一共有四种情况：

以下两种可能性：

1.x==y，那么不用做任何编辑操作，所以$dp[i][j] = dp[i-1][j-1]$

2.x != y

(1) 在word1插入y， 那么$dp[i][j] = dp[i][j-1] + 1$

(2) 在word1删除x， 那么$dp[i][j] = dp[i-1][j] + 1$

(3) 把word1中的x用y来替换，那么$dp[i][j] = dp[i-1][j-1] + 1$

最少的步骤就是取这三个中的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        if (!n || !m) return n + m;
        vector<vector<int>>f = 
            vector<vector<int>>(n + 1, 
            vector<int>(m + 1));
        f[0][0] = 0;
        for (int i = 1; i <= n; i ++ ) f[i][0] = i;  //其中一个为空的时候操作次数就是另一个的长度
        for (int j = 1; j <= m; j ++ ) f[0][j] = j;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j - 1] + 
                    (word1[i - 1] != word2[j - 1]);
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
            }
        return f[n][m];
    }
};

连续子数组最大乘积

思路

其实是一个动态地过程，我们只需要记录扫描到每一个数的时候，对应的最大值和最小值就可以了，然后将当前最大值和之前的最大值进行比较。记录当前乘积的最大和最小，遍历的时候每个最大来自于当前数、当前数乘以最大值、当前数乘以最小值中产生，最小同样。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
public:
	int maxProduct(vector<int> &nums){
		if(nums.size()==0)
			return 0;
  		int maxP=nums[0],minP=nums[0],res=nums[0];
  		for(int i=1;i<nums.size();i++){
  			int num=nums[i],mp=maxP;
  			maxP=max(num,max(mp*num,minP*num));
  			minP=min(num,min(mp*num,minP*num));
  			res=max(maxP,res);
		}
		return res;
	}
};

没有重复数字的全排列

思路

(深度优先遍历+回溯) $O(n×n!)$

  • 我们从前往后，一位一位枚举，每次选择一个没有被使用过的数。
  • 选好之后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。
  • 递归返回时，不要忘记将该数的状态改成“未被使用”，并将该数从相应位置上删除。

代码

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
class Solution{
public:
	vector<vector<int>> res;
	vector<bool> st;
	vector<int> path;
	vector<vector<int>> permute(vector<int>& nums) {
		for (int i = 0; i < nums.size(); i ++ ) st.push_back(false);   //将所有的数字状态置为false
  		dfs(nums,0);
  		return res;
	}
	void dfs(vector<int>& nums,int u){
		if(u==nums.size()){
  			res.push_back(path);
          	return;
		}
  		for(int i=0;i<nums.size();i++){
  			if(!st[i]){
  				path.push_back(nums[i]);
  				st[i]=true;
  				dfs(nums,u+1);
  				st[i]=false;  //递归返回时需要将第i个数值的状态置为未被使用
  				path.pop_back();   //并将第i个数字剔除掉
			}
		}
	}
};

有重复数字的全排列

思路

先对容器nums进行排序，保证重复数字相邻，这样在后续操作中，利用条件，若后一数与前一数相等，则不处理;

边界条件：

若当前值已使用过，不处理；
若当前值与前一值相等，且前一值未使用过，不处理
（举例：112，循环第一个1作第一位时，第二位是第二个1，会被记录，但是循环第二个1做第一位时，第二位是第一个1，就不会被记录，避免重复）

代码

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
class Solution{
private:
	vector<vector<int>> res;
	vector<int> path;
	vector<bool> st;
	vector<vector<int>> permuteUnique(vector<int>& nums) {
  		sort(nums.begin(),nums.end());
  		dfs(nums,st,path,res);
  		return res;
	}
	void dfs(vector<int>& nums,vector<bool>& st,vector<int>& path,vector<vector<int>>& res){
		if(path.size()==nums.size()){
  			res.push_back(path);
  			return;
		}
		for(int i=0;i<nums.size();i++){
  			if(st[i])
  				continue;
  			if(i&&nums[i]==nums[i-1]&&!st[i-1])
  				continue;
  			st[i]=true;
  			path.push_back(nums[i]);
  			dfs(nums,st,path,res);
  			st[i]=false;
  			path.pop_back();
		}
	}
};

最长上升子序列

思路

(动态规划) $O(n^2)$

  • $f(i)$表示以$i$为结尾最长上升子序列的长度，$g(i)$表示以$i$为结尾最长上升子序列的个数。
  • 转移$f(i)$是经典问题，只需找到$nums[j]f(i)$，则$f(i)=f(j)+1$，同时 $g(i)=g(j)$；若$f(j)+1=f(i)$，则$g(i)=g(i)+g(j)$。
  • 所有$f(i)$和$g(i)$的初始值都是1；最后累加所有位置$i$的$g(i)$，满足$f(i)$等于最长长度。

代码

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
class Solution{
public:
	int findNumberOfLIS(vector<int>& nums) {
		int n=nums.size()-1;
  		vector<int> f(n,1),g(n,1);
  		int res=0,tot=0;
  		for(int i=0;i<n;i++){
  			for(int j=0;j<i;j++){
  				if(nums[j]<nums[i]){
  					if(f[i]<f[j]+1){
  						f[i]=f[j]+1;
  						g[i]=g[j];
					}
					else if(f[i]==f[j]+1){
  						g[i]+=g[j];
					}
				}
			}
			res=max(res,f[i]);
		}
		for(int i=0;i<n;i++){
  			if(f[i]==res){
  				tot+=g[i];
			}
		}
		return tot;
	}
};

返回出现次数最多的k个数

思路

(哈希表，计数排序) $O(n)$

计数排序的基本思想为在排序前先统计这组数中其它数小于这个数的个数,其时间复杂度为$O(n+k)$，其中$n$为整数的个数，$k$为所有数的范围，是一种以时间换空间的做法

具体到这个题目，我们首先用哈希表计算出每个元素出现的次数。然后用一个数组统计出出现该次数的数的个数。最后找出下界，然后将所有出现次数大于下界的数进行输入。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class  Solution{
public:
	vector<int> topKFrequent(vector<int>& nums, int k) {
  		unordered_map<int,int> hash;
  		for(auto x:nums) hash[x]++;    //每个数出现的次数
  		int n=nums.size();
  		vector<int> s(n+1);
  		for(auto &item:hash) s[item.second]++;   //数组中的数出现的次数对应的数的个数
  		int i=n,t=0;
  		while(t<k) t+=s[i--];
  		vector<int> res;
  		for(auto &item:hash){
  			if(item.second>i)
  				res.push_back(item.first);
		}
	}
    return res;
};

3 sum

思路

(两重枚举，无重复构造) $O(n^2)$

首先将数组中所有元素都排一个序

同样是一重循环st无重复枚举第一个数字，然后接下来采用两头向里寻找的方式无重复的构造剩下的两个数字，具体在循环中：

  • 初始化l为st+1，r为n-1。
  • 当l<r时，如果当前nums[l] + nums[r] == target，则增加答案并同时向后无重复移动l，向前无重复移动r；否则根据nums[l] + nums[r]与target的关系判断移动l还是移动r。

时间复杂度

排序的时间复杂度为$O(nlogn)$。

第一层$for$循环执行$n$次，每次内部会遍历$st$后所有的数字一次，故时间复杂度为$O(n^2)$。

空间复杂度

需要数组存储所有答案，故空间复杂度最高为$O(n^2)$。

代码

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int st = 0; st < nums.size(); st++) {
            while (st != 0  && st < nums.size() && nums[st] == nums[st - 1])
                st++;
            //此时的st表示的是相同一串数字最后一个数字
            int l = st + 1, r = nums.size() - 1;
            while (l < r) {
                if (nums[st] + nums[l] + nums[r] == 0) {
                    res.push_back({nums[st], nums[l], nums[r]});
                    do { l++; }while (l < r && nums[l - 1] == nums[l]);
                    do { r--; }while (l < r && nums[r] == nums[r + 1]);
                }
                else if (nums[st] + nums[l] + nums[r] < 0) {
                    do { l++; }while (l < r && nums[l - 1] == nums[l]);
                }
                else {
                    do { r--; }while (l < r && nums[r] == nums[r + 1]);
                }
            }
        }
        return res;
    }
};

合并k个有序链表

思路

利用小顶推，首先将每一个链表的表头节点插入到小顶堆中，然后依次将弹出堆顶元素，然后再将该节点的后续节点加入到小顶堆中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct cmp{
  	bool operator()(ListNode *a,ListNode *b){
  		return a->val>b->val;
	}
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
  	if(lists.size()==0)
  		return null;
  	priority_queue<TreeNode*,vector<TreeNode*>,cmp> q;
  	for(int i=0;i<lists.size();i++){
  		q.push(lists[i]);
	}
	for (auto node : lists) {
            if (node) q.push(node);
    }
    ListNode *dummy = new ListNode(-1), *cur = dummy;
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        cur->next = t;
        cur = cur->next;
        if (cur->next) q.push(cur->next);
    }
    return dummy->next;
}

最长公共子序列

思路

(动态规划) $O(nm)$

  • 设$f(i,j)$表示第一个字符串的前$i$个字符和第二个字符串的前$j$个字符的最长公共子序列。这里的字符串的下标假设从 1 开始。
  • 初始时$f(0,j)=f(i,0)=0$，表示空串不和任何字符串有公共子序列。
  • 转移时，如果$s1(i)==s2(j)$，则$f(i,j)=max(f(i−1,j),f(i,j−1),f(i−1,j−1)+1)$，表示既可以忽视$s1(i)$，也可以忽视$s2(j)$，也可以让$s1(i)$和$s2(j)$匹配。
  • 否则，$f(i,j)=max(f(i−1,j),f(i,j−1))$，表示只能忽视 $s1(i)$或忽视$s2(j)$。
  • 最后答案为$f(n,m)$。

时间复杂度

状态数为$O(nm)$，转移为常数，故总时间复杂度为$O(nm)$。

空间复杂度

空间复杂度和状态数一致，为$O(nm)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    f[i][j] = max(f[i - 1][j - 1] + 1,
                                  max(f[i - 1][j], f[i][j - 1]));
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }

        return f[n][m];
    }
};

求3D立体的表面积

思路

(枚举) $O(n2)$

  • 逐一枚举每个非$0$的格子，上下两面对答案的贡献总共为 2；
  • 然后再遍历这个格子周围的$4$个格子，对于每个方向，假设高度为$h$，则对答案的贡献为$max(0, grid[i][j] - h)$；若这个格子在边界，则在边界的面上直接加上$grid[i][j]$即可。其原理就是除去挡住的部分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
  		int n=grid.size();
  		int m=grid[0].size();
  		int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
  		for(int i=0;i<n;i++){
  			for(int j=0;j<m;j++){
  				if(!grid[i][j]) continue;
  				int res=2;
  				for(int k=0;k<4;k++){
  					int x=i+dx[k],y=j+dy[k];
  					if(x<0||x>=n||y<0||y>=m){
  						res+=grid[i][j];
					}
					else
						res+=max(0, grid[i][j] - grid[x][y]);
				}
				
			}
		}
	}
};

抖音红人

思路

参考链接

数据是一个有向图，$(A,B)$代表$A$关注$B$，那么在这条关系在图中，存$B$指向$A$。

要考虑个整个图可能不是连通的，所以需要对每个节点分别进行深度遍历。

对每个节点进行深度遍历：每调用一次就让这个节点的粉丝数加1，注意在递归函数调用中，需要建立一个visited数组，代表节点以访问过，访问过的就不能遍历下去。

每次深度遍历开始前，对$visited$清空，再对$visited[起点]=True$，代表起点已经走过了。

代码

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
from collections import defaultdict
#提交代码时，取消以下注释
##n = eval(input())
##m = eval(input())
##li = list( map(int,input().split()))

#提交代码时，删除以下代码
n = 3
m = 3
li = [1,2,2,1,2,3]

#测试用例里，用户索引从1开始，本文从0开始
son = defaultdict(list)
fans = [1]*n#存直接或间接粉丝，自己也算自己的粉丝，所以初始为1
visited = [False]*n

for i in range(m):
    a = i*2
    b = i*2 +1
    #a关注b
    son[li[b]-1].append(li[a]-1)
    #原输入是123，那么程序里就是012
#建立好了有向图

def findson(origi,i):#origi代表起点
    for j in son[i]:        
        if visited[j] != True:            
            fans[origi] += 1
            visited[j] = True
            #print(i,j,visited)
            findson(origi,j)

for i in range(n):
    visited = [False]*n
    visited[i] =True 
    findson(i,i)   #首先从自己的这边开始递归

count = 0
for i in fans:
    if(i == n):#如果粉丝为n
        count +=1
print(count)

二叉树最大路径和

题目描述

给定一个非空二叉树，找到路径权值和的最大值。
在这道题目中，路径是指从树中某个节点开始，沿着树中的边走，走到某个节点为止，路过的所有节点的集合。
路径的权值和是指路径中所有节点的权值的总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：[1,2,3]
       1
      / \
     2   3
输出：6

输入：[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出：42

思路

(递归，树的遍历) $O(n^2)$

树中每条路径，都存在一个离根节点最近的点，我们把它记为割点，用割点可以将整条路径分为两部分：从该节点向左子树延伸的路径，和从该节点向右子树延伸的部分，而且两部分都是自上而下延伸的。如下图所示，蓝色的节点为割点：

我们可以递归遍历整棵树，递归时维护从每个节点开始往下延伸的最大路径和。
对于每个点，递归计算完左右子树后，我们将左右子树维护的两条最大路径，和该点拼接起来，就可以得到以这个点为割点的最大路径。
然后维护从这个点往下延伸的最大路径：从左右子树的路径中选择权值大的一条延伸即可。

时间复杂度分析：每个节点仅会遍历一次，所以时间复杂度是$O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
public:
	int ans;
  	int maxPath(TreeNode *root){
  		ans=INT_MIN;
  		dfs(root);
  		return ans;
	}
	int dfs(TreeNode *root){    //求以root为根节点的最大路径，可能是左路径可能是右路径
  		if(!root) return 0;
  		int left=dfs(root->left);
  		int right=dfs(root->right);
  		ans=max(ans,root->val+left+right);
  		return root->val+max(left,right);
	}
};

小偷偷东西

题目描述

这是一场有预谋的盗窃活动。现在一条路上有一排房间，每个房间都有一些钱。盗窃不能同时出现在两个相邻的房间，否则会触发警报。

现在给定这些房间的钱的数量，问在不触动警报的情况下最多能拿到多少钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: [1,2,3,1]
Output: 4
解释: 盗窃房间 1 (钱数 = 1) 然后盗窃房间 3 (钱数 = 3).
             盗窃的钱数总和 = 1 + 3 = 4.


Example 2:

Input: [2,7,9,3,1]
Output: 12
解释: 盗窃房间 1 (钱数 = 2), 盗窃房间 3 (钱数 = 9) 然后盗窃房间 5 (钱数 = 1).
             盗窃的钱数总和 = 2 + 9 + 1 = 12.

思路

(动态规划) $O(n)$

  • 令$f[i]$表示盗窃了第i个房间所能得到的最大收益，$g[i]$表示不盗窃第$i$个房间所能得到的最大收益。
  • $f[i] = g[i - 1] + nums[i]$，$g[i] = max(f[i - 1], g[i - 1])$。
  • 初始值$f[0] = nums[0], g[0] = 0$，答案为$max(f[n - 1], g[n - 1])$。

优化

  • 由于每次更新只用到了上一层的信息，故可以优化空间为常数。

时间复杂度

状态数为$O(n)$，转移数为$O(1)$，转移时间为$O(1)$，故总时间复杂度为$O(n)$。

代码

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
class Solution{
public:
	int rob(vector<int> nums){
  		int n=nums.size();
  		if(n==0)
  			return 0;
  		vector<int> f(n);
  		vector<int> g(n);
  		f[0]=nums[0];
  		g[0]=0;
  		for(int i=1;i<n;i++){
  			f[i]=g[i-1]+nums[i];
  			g[i]=max(g[i-1],f[i-1]);
		}
		return max(f[n-1],g[n-1]);
	}
};
/*
时间复杂度为O(n)
空间复杂度为O(1)
class Solution{
public:
	int rob(vector<int> nums){
  		int n=nums.size();
  		if(n==0)
  			return 0;
  		int f=nums[0],g=0;
  		for(int i=1;i<n;i++){
  			int last_f=f,last_g=g;
  			f=last_f+nums[i];
  			g=max(last_f,last_g);
		}
		return max(f,g);
	}
};
*/

多次买入卖出股票的最大利润

一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易两次，手上最多只能持有一支股票，求最大收益。

思路

动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit[i]，和第i天之后进行一次交易的最大收益postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    if (prices.size() < 2) {
        return 0;
    }
    vector<int> left(prices.size(), 0);
    vector<int> right(prices.size(), 0);
    int min_ = prices[0], max_ = prices[prices.size() - 1], res = 0;
    for (int i = 1; i < prices.size(); i++) {
        min_ = min(min_, prices[i]);   //记录左边最小的
        left[i] = max(prices[i] - min_, left[i - 1]);
    }
    for (int i = prices.size() - 2; i >= 0; i--) {
        max_ = max(max_, prices[i]);   //记录右边最大的
        right [i] = max(max_ - prices[i], right[i + 1]);
    }
    for (int i = 1; i < prices.size(); i++) {
        res = max(res, left[i] + right[i]);
    }
    return res;
}

右边第一个比其大的元素

题目描述

给定两个没有重复元素的数组$nums1$和$nums2$，其中$ nums1$ 是$ nums2 $的子集。找到$ nums1 $中每个元素在 $nums2$ 中的下一个比其大的值。

$nums1 $中数字$ x $的下一个更大元素是指$ x$ 在 $nums2$ 中对应位置的右边的第一个比 $x $大的元素。如果不存在，对应位置输出 -1。

1
2
3
4
5
6
7
8
9
10
11
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于 nums1 中的数字 4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于 nums1 中的数字 1，第二个数组中数字1右边的下一个较大数字是 3。
    对于 nums1 中的数字 2，第二个数组中没有下一个更大的数字，因此输出 -1。
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 nums1 中的数字 2，第二个数组中的下一个较大数字是 3。
    对于 nums1 中的数字 4，第二个数组中没有下一个更大的数字，因此输出 -1。

思路

(哈希表+单调队列) $O(n)$

维护一个单调递减的单调栈，每次入栈的的时候将入栈元素和栈顶元素相比较，如果新入栈的元素要大于栈顶元素，那么将栈顶元素都pop出来，直至新入栈元素要比栈顶元素要大或者是说栈为空。在出栈的过程中就确定了右边第一个比自己大的元素了，那些没有出栈的元素也就是右边没有比它们大的元素。

代码

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
class Solution{
pubilc:
	vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums){
  		int n=nums.size();
  		unordered_map<int,int> map(n);
  		for(int i=0;i<n;i++){
  			map[nums[i]]=i;
		}		
		stack<int> st;
		greater<int>(n);   //greater[i]表示在位置i右边第一个比i位置上的数大的数
		for(int i=0;i<n;i++){
  			while(st.size()&&nums[st.top()]<=nums[i]){
  				greater[st.top()]=nums[i];
  				st.pop();
			}
			st.push(i);
		}
		while(st.size()){
  			greater[st.top()]=-1;
  			st.pop();
		}
		vector<int> res(findNums.size());
		for(int i=0;i<findNums.size();i++){
  			res.push_bcak(greater[map[findNums[i]]]);
		}
		return res;
	}
};

单链表的快速排序

思路

我们设置两个指针 i，j，其中 i 初始时指向数组的第一个元素，j 初始化为 i+1。 然后，我们设定 i 指向的元素为基准数字。我们要做的事情，就是在一趟排序中，把那些比基准数字小的数，移动到前面。

具体的算法如下：

  • 如果 j 指向的值大于等于基准数字（如果比基准大，直接跳过）
    • j ++
  • 如果 j 指向的值小于基准数字，（如果比基准小，交换 i 和 j 位置的值）
    • i ++
    • swap(i， j)
    • j ++

以【4，2，5，3，7，9，0，1】为例，我们来模拟一趟快排的过程。

1、初始化时，i指向链表首元素4；j = i +1，指向2。基准数字为当前i 指向的数字：4。

2、随后开始循环，j 当前指向2，因为2小于4，所以要把2移动到前面去。按照我们的算法步骤操作：

  • i ++，首先 i 向后移动一位，指向2
  • swap(i， j) ，随后交换 i、j 位置的值，这里面是2和2自己交换
  • j ++，然后 j 向后移动一位，指向5

执行一次交换后的结果如下：

3、接下来，由于 j 指向的值5 大于4，直接跳过，执行j++，此时 j 指向3

4、 j 指向的值为3，小于4，仿照步骤2，我们再次执行一次交换移动过程。

  • i ++，首先 i 向后移动一位，指向5
  • swap(i， j) ，随后交换 i、j 位置的值，这里面是5和3交换
  • j ++，然后 j 向后移动一位，指向7

交换后的结果如下：

5、 j指向的值为7，大于4，所以直接跳过，执行 j++，j 指向9

6、同理，j 指向的值为9，也大于4，跳过，执行 j++，j 指向0

7、 j 指向的值为0，小于4，执行一次交换过程

  • i ++，首先 i 向后移动一位，指向5
  • swap(i， j) ，随后交换 i、j 位置的值，这里面是5和0交换
  • j ++，然后 j 向后移动一位，指向1

交换后的结果如下：

8、 j 指向的值为1，小于4，我们再执行一次交换过程

  • i ++，首先 i 向后移动一位，指向7
  • swap(i， j) ，随后交换 i、j 位置的值，这里面是7和1交换
  • j ++，然后 j 向后移动一位，已经超过了链表的长度，不再向后移动。

交换后的结果如下：

9、最后，交换当前 i指向的值1，和4。得到【1、2、3、0、4、9、5、7】，一趟排序结束。

在交换的时候，为什么要让i先向后移动呢？

这是因为，在整个排序的过程中，i 前面指向的都是小于4的数字，i 后面指向的都是大于4的数字，i 是左右两边的分界线。我们交换的目的是把小于4的交换到前面，把大于4的交换到后面，所以 i 要先向后移动1位，找到后面第一个大于4的数，然后把这个大于4的数，和后面小于4的数交换。

代码

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
43
44
45
46
47
48
import java.util.*;

public class Main{

    // 交换
    public static void swap(LinkedList<Integer> list, int i, int j) {
        int t = list.get(j);
        list.set(j, list.get(i));
        list.set(i, t);
    }
    public static void qsort(LinkedList<Integer> list, int left, int right) {

        if(left < right) {
            int i = left; // 初始化i，为链表第一个元素（最左边的元素）
            int j = i + 1; // 初始化j = i + 1
            int x = list.get(i); // 基准数字

            while(j <= right) { // 大循环条件，j不能超过链表长度

                // 如果 j 指向的值大于等于基准数字（如果比基准大，直接跳过）
                while(j <= right && list.get(j) >= x) j++;

                // 否则，j 指向的值小于基准，则交换
                if(j <= right) {
                    i++; // 交换时，i 首先要向后移动一位
                    swap(list, i, j); // 交换
                    j++; // 随后，j向后移动一位
                }

            } 
            swap(list, left, i); // 最后，交换 i 位置的值和基准元素。一趟排序结束。
            qsort(list, left, i-1);   // 递归排序左边
            qsort(list, i+1, right);  // 递归排序右边
        }
    }


    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList();
        int[] arr = {4,2,5,3,7,9,0,1}; // test case 1
//      int[] arr = {5,4,3,2,1,6,7,9,8,10}; // test case 2
        for(int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        qsort(list, 0, arr.length-1);
        System.out.println(list.toString());
    }
}

判断一个数是否是素数

思路

大家中学都学过，就不过多介绍了，大致提两点：

  • 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
  • 0和1既不是质数也不是合数，最小的质数是2

假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。由此我们可以改进上述方法优化循环次数。

质数还有一个特点，就是它总是等于$6x-1$或者$6x+1$，其中$x$是大于等于1的自然数。如何论证这个结论呢，其实不难。首先$6x $肯定不是质数，因为它能被 6 整除；其次 $6x+2$ 肯定也不是质数，因为它还能被2整除；依次类推，$6x+3$ 肯定能被 3 整除；$6x+4 $肯定能被 2 整除。那么，就只有$ 6x+1 $和$ 6x+5$ (即等同于$6x-1$) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isPrime(int num){
  	if(num<=3){
  		return n>1;
	}
	if(num%6!=1&&num%6!=5){    //不在6两侧的一定不是素数
  		return false;
	}
	int sqrt=(int)sqrt(num);
	for(int i=5;i<=sqrt;i++){
  		if(num%i==0||num%(i+2)==0){   //依次从小到大遍历所有可能的素数，看num是否是这些素数的倍数
  			return false;
		}
	}
	return true;
}

判断一棵树是否为二叉搜索树（BST）

思路

时间复杂度：$O(n)$ 每次只访问一个节点

每次限定一个节点在一个范围内[min,max]，递归地判断每个节点是否是在这个范围内

代码

1
2
3
4
5
6
7
8
9
10
11
bool isBST(TreeNode *root){
    return isBSTUtil(root,INT_MIN,INT_MAX);
}
bool isBSTUtill(TreeNode *root,int min,int max){
    if(root==NULL)
        return true;
    if(root->val<min||root->val>max)
        return false;
    return isBSTUtill(root->left,INT_MIN,root->val-1)&&
           isBSTUtill(root->right,root->val+1,INT_MAX);
}

不包含重复数字的子集

思路

(集合的二进制表示) $O(2^nn)$

假设集合大小是 $n$，我们枚举 $0…2n−1$，一共 $2^n$ 个数。

每个数表示一个子集，假设这个数的二进制表示的第 $i $位是1，则表示该子集包含第 $i$ 个数，否则表示不包含。

时间复杂度分析：一共枚举 $2^n$ 个数，每个数枚举 n 位，所以总时间复杂度是 $O(2^nn)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for (int i = 0; i < (1 << n); i ++ )
        {
            vector<int> temp;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                    temp.push_back(nums[j]);
            res.push_back(temp);
        }
        return res;
    }
};

含重复数字的子集

思路

(暴力枚举) $O(n^2n)$

为了方便处理，我们先将数组排序，这样相同元素就会排在一起。

然后暴力搜索所有方案，搜索顺序是这样的：

我们先枚举每个不同的数，枚举到数 $x$ 时，我们再求出 $x$ 的个数 $k$，然后我们枚举在集合中放入 $0,1,2,…k$ 个 x，共 $k+1$ 种情况。
当枚举完最后一个数时，表示我们已经选定了一个集合，将该集合加入答案中即可。

时间复杂度分析：不同子集的个数最多有 $2^n$ 个，另外存储答案时还需要 $O(n)$ 的计算量，所以时间复杂度是 $O(n^2n)$。

代码

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return ans;
    }

    void dfs(int u, vector<int>&nums)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }
        int k = u;
        while (k < nums.size() && nums[k] == nums[u]) k ++ ;
        dfs(k, nums);  //不将这个数放入
        for (int i = u; i < k; i ++ )   //依次将这个数放入1~k-u次
        {
            path.push_back(nums[i]);
            dfs(k, nums);
        }
        path.erase(path.end() - (k - u), path.end());
    }
};

子数组为k的倍数的个数

思路

(哈希表，前缀和) $O(n)$

很容易可以发现，如果我们求出了前缀和数组 $s$，如果原数组区间$ [j, i] $能被$ K $整除，则$ (s[i] - s[j - 1]) mod K == 0$，即 $s[j - 1] mod K == s[i] mod K$。

故我们只需要记录$ i $之前，有多少位置的$ s[j] $在模 K 后的值和$ s[i] mod K $相等，这就需要用一个哈希表。
具体来看，我们开一个哈希表，初始化$ hash[0] = 1$；然后遍历每一个位置 $i$，求出$ s[i] mod K$，如果哈希表中已经有了这个值，则总答案累计上$ hash[s[i] mod K]$。然后将$ hash[s[i] mod K] $自增 1。

时间复杂度

哈希表的查询和插入均为常数，所以只需要遍历一次数组，故总时间复杂度为 $O(n)$。

空间复杂度

前缀和数组可以省略，只需要额外哈希表的空间，哈希表最多存放 $K$个数，故总空间复杂度为 $O(K)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int subarraysDivByK(vector<int>& A, int K) {
    int n=A.size();
    unordered_map<int,int> map;
    map[0]=1;   //代表和为 0 的前缀和初始时有 1 种情况，主要考虑假如数组中第一个数就是K的倍数。
    int ans=0,
    for(int i=0;i<n;i++){
        int s=((s+A[i])%K+K)%K;   //记录当前第i个位置之前的前缀和的余数
        if(map.find(s)==map.end()){
			map[s]=0;
        }
        ans+=map[s];
        map[s]++;
    }
    return ans;
}

二维数组的范围内和

思路

(前缀和) 初始化:$O(n^2)$,sumRange:$O(1)$
首先初始化出部分和数组$f[N][N]，f[i][j]$表示(i, j)左上部分区域的和。

然后我们考虑如何计算矩形区域(row1, col1) 的和。

如下图所示，$S_{r 1, c 1, r 2, c 2}=S_{0,0, r 2, c 2}-S_{0,0, r 1, c 2}-S_{0,0, r 2, c 1}+S_{0,0, r 1, c 1}$

时间复杂度分析：初始化要遍历整个矩阵，时间复杂度是 $O(n^2)$；计算矩形区域的和时只需要常数次计算，时间复杂度是 $O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumMatrix {
public:
    vector<vector<int>> f;

    NumMatrix(vector<vector<int>> matrix) {
        if (matrix.empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] = f[i - 1][j] + matrix[i - 1][j - 1];   //先把该位置上方加上

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] += f[i][j - 1];   //再把该位置左方加上
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return f[row2 + 1][col2 + 1] - f[row2 + 1][col1] - f[row1][col2 + 1] + f[row1][col1];
    }
};

01数组中和为K的个数

思路

(前缀和) $O(n)$
最暴力的做法是依次枚举区间的起点、终点，然后求区间总和，时间复杂度是 $O(n^3)$。

然后我们考虑一下怎么优化？

可以预处理出数组前缀和，这样求区间和时可以用 $O(1)$ 的时间算出，比如区间$[i, j]$的和是$sum[j] - sum[i - 1]$。时间复杂度降为 $O(n^2)$。

我们可以从前往后枚举区间终点，同时用一个数组记录当前不同前缀和的数量，比如f[i]表示和为$i$的前缀个数。假设枚举的当前坐标是$j$，那么我们的目标就是计算j之前共有多少个前缀和是$sum[j] - S$，这个值就是$f[sum[j] - S]$；

最后将所有终点对应的区间个数累加起来，就是答案。

时间复杂度分析：

  • 求前缀和的时间复杂度是 $O(n)$；
  • 遍历区间终点，同时更新 f[i] 的时间复杂度也是 $O(n)$；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int n = A.size();
        vector<int> sum(n + 1, 0), f(n + 1, 0); // f[i] 记录前面有多少个和为i的前缀
        for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + A[i - 1];
        f[0] = 1;
        int res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s = sum[i];
            if (s >= S) res += f[s - S];
            f[s] ++ ;
        }
        return res;
    }
};

相同数量的01个数

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组。

思路

(前缀和，哈希表) $O(n)$

  • 将数组中的 0 视作 -1，则求连续相同 0 和 1 个数的子数组就是求连续和为 0 的子数组。
  • 连续子数组的和可以用两个前缀和相减得到，故这里就是求下标差距最大的两个相等的前缀和。
  • 使用哈希表记录前缀和及其下标。遍历时，若当前的前缀和在哈希表中出现，则更新答案；否则将其值和下标加入哈希表。
  • 注意哈希表中需要初始化一个前缀和 0。

时间复杂度

每个数字仅遍历一次，哈希表的单次操作时间复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

需要额外的哈希表空间，故空间复杂度为 $O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findMaxLength(vector<int>& nums) {
    int n = nums.size(), ans = 0;
    unordered_map<int, int> hash;
    hash[0] = 0;
    int x = 0;
    for (int i = 1; i <= n; i++) {
        x += (nums[i - 1] == 1 ? 1 : -1);
        if (hash.find(x) != hash.end())    //当前前缀和在哈希表中出现过
            ans = max(ans, i - hash[x]);
        else
            hash[x] = i;    //当前前缀和还没有在哈希表中出现过
    }
    return ans;
}

分饼干(candy)

有 N 个孩子站在一排，每个孩子都有一个排名值。
你需要给这些孩子分配糖果，满足下列要求：

  • 每个孩子至少有一块糖果；
  • 相邻的孩子中，高排名值的糖果数要严格大于底排名值的。

求最少需要花费多少糖果。

思路

(前向扫描+后向扫描) $O(n)$

1.初始化一个糖果列表，给每个孩子初始化1个糖果；
2.从左往右，如果当前的孩子比左边孩子优秀，他的糖果比前面的多1；
3.从右往左，如果当前孩子比右边孩子优秀，他的糖果比右边至少多1.
4.对糖果列表求和。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Candy(vector<int> nums){
    int n=nums.size();
    vector<int> candies(n,1);
    for(int i=1;i<n;i++){
        if(nums[i]>nums[i-1]){
            candies[i]=candies[i-1]+1;
        }
    }
    for(int i=n-2;i>=0;i--){
        if(nums[i]>nums[i+1]){
            candies=max(candies[i],candies[i+1]+1);   //取最大值是因为左右都要满足
        }
    }
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=candies[i];
    }
    return sum;
}

01矩形连通图个数

给定一个二维的网格图，包含1和0，分别代表陆地和水，计算其中岛屿的个数。岛屿均有水包围，并且由水平或竖直方向上的陆地连接而成。你可以假设网格的四周均被水包围。

思路

(DFS) $O(nm)$

  • 从任意一个陆地点开始，即可通过四连通的方式，深度优先搜索遍历到所有与之相连的陆地，即遍历完整个岛屿；遍历结束后将遍历过的点清0。
  • 重复以上过程，记录起点的个数即可。

时间复杂度

由于每个点最多被遍历常数次，故时间复杂度为$O(nm)$。

代码

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
class Solution{
public:
	int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
    void dfs(vector<vector<char>>& nums,int x,int y){
        nums[x][y]='0';
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<nums.size()&&b>=0&&b<nums[0].size()&&nums[a][b]=='1'){
                dfs(nums,a,b);
            }
        }
    } 
    int island(vector<vector<char>> island){
        int n=island.size();
        int m=island[0].size();
        if(n==0){
            return 0;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(island[i][j]=='1'){
                    dfs(island,i,j);
                    ans++;
                }
            }
        }
        return ans;
    }
}

最小窗口子字符串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

思路

(哈希表+双指针) $O(m+n)$

由于只要求包含T的所有字母，并不要求出现的顺序也相同，我们可以先开一个哈希表记录T中每个字符出现的次数。然后我们可以枚举窗口的终点，然后从终点到起点扫描S串，每次将头指针的字符放入另一个哈希表，当队头字符在两个哈希表中的次数相同时，我们将cnt加一，当cnt为哈希表的大小时说明此时窗口包含了全部的字符，更新答案。

可以观察到本题具有单调性：当我们枚举窗口的终点时，对于每个终点（自变量），如果存在以它为终点的包含T的所有字符的窗口，那么在这些窗口中一定存在一个最近的起点（因变量），而当终点右移的时候，起点也一定往后移动，所以可以用双指针来处理。每次将右边界向后移动，当左边界的字符个数超出需要的个数时，我们移动左边界，因为此时窗口比之前的窗口更优。

同样是用双指针，不过这里移动左边界的逻辑与leetcode3稍有不同，它是当右边界字符不满足要求时移动左边界。

注意一些边界条件的处理，对于S串中T串不包含的字符我们也可以放入哈希表中，这样可以方便处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minWindows(string s,int t){
    unordered_map<char,int> hash;
    unordered_map<char,int> map;
    for(auto c:t){
        hash[c]++;
    }
    int n=hash.size();
    string res;
    for(int i=0,j=0,cnt=0;j<s.size();j++){
        map[s[j]]++;
        if(map[s[j]]==hash[s[j]]) cnt++;
        while(map[s[i]]>hash[s[j]]){
            map[s[i++]]--;
        }
        if(cnt==n&&(res.empty()||j-i+1<res.size())){
            res=s.substr(i,j-i+1);
        }
    }
    return res;
}

奇增偶降链表

一个链表，奇数下标递增，偶数下标递减，使其总体递增。

思路

  • 首先根据奇数位和偶数位拆分成两个链表。

  • 然后对偶数链表进行反转。

  • 最后将两个有序链表进行合并。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void help(ListNode *head){
    ListNode *head1,*head2;
    head1=head;
    head2=head->next;
    ListNode *list1=head1,*list2=head2;
    auto cur=head->next->next;
    int count=0;
    while(cur){
        count++;
        if(count%2==1){
            list1->next=cur;
        }
        else{
            list2->next=cur;
        }        
        cur=cur->next;        
    }
    head2=reverse(head2);   //反转
    merge(head1,head2);   //合并
}

小兔的棋盘

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024

思路

这个题要特别注意一下里面有个要求即不能越过对角线！，所以可以分开处理，即将其分成上半边和下半边。只需要求出一个半边，之后乘2即可。

这个题一开始我想进行组合来着，但是后来发现因为不能越过对角线，所以不可以进行组合，所以就用类似斐波那契数列进行，即每次到一个格子的的方式的数量由走到下一个格子和走到左一个格子的方式的数量之和。而对角线因为特殊所以要单独处理，即走到对角线的方式的数量仅有下边一个格子决定，每次都要算到$(n,n)$，即每次循环存储的时候都要到$(i,i)$；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstring>

using namespace std;
long long a[37][37];
int main()
{
    int i,j,n;
    memset(a,0,sizeof(a));
    for(i=1;i<36;++i){
        a[i][0]=1;
        for(j=1;j<i;++j){
            a[i][j]=a[i-1][j]+a[i][j-1];
        }
        a[i][i]=a[i][i-1];   //对角线上的元素为
    }
    int num=0;
    while(cin >> n&&n!=-1){
            num++;
        cout << num << " " << n << " "<< 2*a[n][n] << endl;
    }
    return 0;
}

第K小的质分数

一个已排序好的表$ A$，其包含 1 和其他一些素数。当列表中的每一个 $p < q$ 时，我们可以构造一个分数 $p / q$ 。

那么第 K 个最小的分数是多少呢？以整数数组的形式返回你的答案，这里 answer[0] = p 且 answer[1] = q。

思路

(堆，贪心) $O(Klogn)$

  • 经过试验，直接构造所有的分数然后排序的暴力做法会超时。

  • 我们可以利用贪心巧妙的构造，我们首先令$ A[0] / A[1], A[0] / A[2], …, A[0] / A[n - 1] $插入到小根堆，因为这是最小的 n 个数。

  • 然后我们每次从小根堆中弹出最小的分数，假设弹出的分数为$ A[i] / A[j]$，如果这不是第 K 次弹出且 i + 1 < j，则我们将$ A[i + 1] / A[j] $插入到小根堆中，因为这是以 A[j] 为分母时，目前最小的一个分数。

  • 如此弹出 K 次，第 K 次弹出的分数一定是第 K 小的分数。

时间复杂度

堆中至多有 $n$ 个元素，操作一次的时间复杂度为 $O(logn)$，共操作 $K$次，故时间复杂度为 $O(Klogn)$。

空间复杂度

存放堆需要 $O(n)$ 的空间。

代码

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
class MyPair {
public:
    int x, y;
    int first, second;

    MyPair(int x_, int y_, int first_, int second_): 
        x(x_), y(y_), first(first_), second(second_) {}

    bool operator < (const MyPair &other) const {
        return x * other.y > y * other.x;
    }
};

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        int n = A.size();

        priority_queue<MyPair> q;

        for (int i = 1; i < n; i++)
            q.push(MyPair(A[0], A[i], 0, i));

        while (K--) {
            auto tp = q.top();
            if (K == 0) 
                return {q.top().x, q.top().y};

            q.pop();
            if (tp.first + 1 == tp.second)
                continue;
            q.push(MyPair(A[tp.first + 1], A[tp.second], tp.first + 1, tp.second));
        }
        return {-1, -1};
    }
};

切分回文串1

给定一个字符串 $s$，将 $s$ 划分成若干部分，使得每一部分都是回文串。

请返回所有合法的划分方案。

1
2
3
4
5
6
输入："aab"
输出：
[
  ["aa","b"],
  ["a","a","b"]
]

思路

(暴搜+剪枝) $O(2^nn)$

暴力枚举所有方案。

对字符串从前往后搜索，搜索时维护如下几个状态：

1.已经划分好的区间列表；
2.当前正在枚举的区间；
3.枚举到的字符串 $s$ 的下标；
4.字符串 $s$；

在搜索时：分情况处理：

  • 如果已经遍历完字符串 s，则递归终止。终止前判断方案是否合法：即判断当前区间是否是回文串；
  • 否则，字符串 $s$ 还没遍历完，则
    • 如果当前区间不是回文串，则只能继续在该区间添加字符；
    • 如果当前区间是回文串，则既可以在该区间添加字符，也可以将该区间保存，并开启一个新的区间；

时间复杂度分析：首先考虑最多有多少个合法方案，我们可以考虑在相邻字符之间放板子，每种放板子的方法都对应一种划分方案，而每个字符间隔有放和不放两种选择，所以总共有 $2n−1$ 个方案。另外对于每个方案，需要 $O(n)$ 的时间记录方案。所以总时间复杂度是 $O(2^nn)$。

代码

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
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;

    vector<vector<string>> partition(string s) {
        dfs("", 0, s);
        return ans;
    }

    bool check(string &now)
    {
        if (now.empty()) return false;
        for (int i = 0, j = now.size() - 1; i < j; i ++, j -- )
            if (now[i] != now[j])
                return false;
        return true;
    }

    void dfs(string now, int u, string &s)   //now表示当前已经枚举完的区间，u表示当前正在扫描到的区间
    {
        if (u == s.size())   //表示当前已经扫描完所有的元素
        {
            if (check(now))  //检查已经枚举完的区间是否是回文串
            {
                path.push_back(now);
                ans.push_back(path);
                path.pop_back();   //进行回溯
            }
            return;   //进行返回
        }

        if (check(now))
        {
            path.push_back(now);
            dfs("", u, s);
            path.pop_back();
        }

        dfs(now + s[u], u + 1, s);
    }
};

切分回文串2

给定一个字符串 $s$，请将它划分成若干部分，使得每一部分都是回文串。
求最少需要切几刀。

1
2
3
输入："aab"
输出：1
解释：可以划分成：["aa","b"]，所以只用切1刀。

思路

(动态规划) $O(n^2)$

一共进行两次动态规划。

第一次动规：计算出每个子串是否是回文串。
状态表示：$st[i][j]$ 表示 $s[i…j]$ 是否是回文串;
转移方程：$s[i…j]$是回文串当且仅当 $s[i]$等于$s[j]$并且 $s[i+1…j−1]$ 是回文串；
边界情况：如果$s[i…j]$的长度小于等于2，则$st[i][j]=(s[i]==s[j])$;

在第一次动规的基础上，我们进行第二次动规。
状态表示：$f[i]$ 表示把前 $i$ 个字符划分成回文串，最少划分成几部分；
状态转移：枚举最后一段回文串的起点 $j$，然后利用$ st[j][i] $可知 $s[j…i]$是否是回文串，如果是回文串，则$ f[i]$ 可以从 $f[j−1]+1$ 转移；

边界情况：0个字符可以划分成0部分，所以 $f[0]=0$。

题目让我们求最少切几刀，所以答案是$ f[n]−1$。

时间复杂度分析：两次动规都是两重循环，所以时间复杂度是 $O(n^2)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int>f(n + 1);
        vector<vector<bool>> st(n, vector<bool>(n, false));

        for (int i = 0; i < n; i ++ )
            for (int j = i; j >= 0; j -- )
                if (i - j <= 1) st[j][i] = s[j] == s[i];
                else st[j][i] = s[j] == s[i] && st[j + 1][i - 1];

        f[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = INT_MAX;
            for (int j = 0; j < i; j ++ )
                if (st[j][i - 1])
                    f[i] = min(f[i], f[j] + 1);
        }
        return max(0, f[n] - 1);
    }
};

判断一个整数的字符串表示是否是回文串

思路

(循环) $O(1)$

我们可以借鉴Reverse Integer题目的做法，一个正整数的字符串表示是回文串，当且仅当它的逆序和它本身相等。
但如果直接这么做，会存在整数溢出的问题，比如1111111119的逆序是9111111111(大于INT_MAX)。
所以我们要对其改进：我们只需先算出后一半的逆序值，再判断是否和前一半相等即可。

时间复杂度分析：int型整数在十进制表示下最多有10位，对于每一位的计算是常数级的，因此总时间复杂度是 $O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || x && x % 10 == 0) return false;
        int s = 0;
        while (s <= x)
        {
            s = s * 10 + x % 10;
            if (s == x || s == x / 10) return true; // 分别处理整数长度是奇数或者偶数的情况
            x /= 10;
        }
        return false;
    }
};

介绍一个求最长回文串的时间复杂度很低(O(n))的算法：Manacher

二叉树中节点的最大距离

把二叉树看成一个图，父子节点之间的连线看成是双向的，定义“距离”为两个节点之间的边数。例如下图中最大距离为红线的条数为6.

思路

定义：过以节点x作为根节点的子树中，节点间的最大距离为Dis(x)。

上图，左图中Dis(根节点)最大，右图中Dis(根节点->left)最大。从上边可以看出每个节点都可能成为最大距离根节点的潜质。

因此可以求出每个Dis(节点)，从中得出最大值即为整个二叉树的根节点最大值。

在求过点x的最大距离时，最大距离的两个点有可能出现在三种情况下

  1. 左子树
  2. 右子树
  3. 过节点x

经分析得出以下特点

  1. 以上三种情况最终必定一叶子结束
  2. 在第三种情况下必然是左子树高度与右子树高度之和（只有这样，才可能取得最大值）

经过以上分析即可得出递推式

Dis(x) = max(Dis(x->left), Dis(x->right), height(x->left)+height(x->right))

代码

1
2
3
4
5
6
7
8
9
10
11
int treeDistance(BiTree root)
{
    if(root == NULL)
        return 0;
    else if(root->left == NULL && root->right == NULL)
        return 0;
    int dis = max(height(root->left) + height(root->right), treeDistance(root->left), treeDistance(root->right));
    if(maxDis < dis)
        maxDis = dis;
    return dis;
}

这里用了一个技巧：maxDis是个全局变量，递归一次根节点会遍历到每个节点，在这期间于maxDis比较，从而得出了最大值，而不需要额外的空间。

相同子集和分割

一个数组，分为两个子数组，使得它们的和相等

思路

实际上就是求是否存在子数组，使得子数组的和等于整个数组和的1/2。考虑用动规，看成是0-1背包问题的一种变形，dp[i][j]表示考虑前i个数字，是否存在子数组和为j。转移方程为

$dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]$

（即不选第$i$个数字或者选第$i$个数字）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool canPartition(vector<int> nums){
    int sum=0;
    for(auto num:nums){
        sum+=num;
    }
    if(sum%2!=0){
        return false;
    }
    vector<bool> dp(0,sum/2+1);  //dp[i]表示是否可以找出若干个数使其总和为i
    dp[0]=1;
    for(int i=0;i<nums.size();i++){
        for(int j=sum/2;j>=nums[i];j--){
            dp[j]|=dp[j-nums[i]];
        }
    }
    return dp[sum/2];
}
//这里需要特别注意的是，第二个for循环一定要从target遍历到nums[i]，而不能反过来，想想为什么呢？因为如果我们从nums[i]遍历到target的话，假如nums[i]=1的话，那么[1, target]中所有的dp值都是true，因为dp[0]是true，dp[1]或上dp[0]，为true，dp[2]会或上dp[1]，为true，依此类推，完全使我们的dp数组失效了
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多