leetcode刷题笔记

发表于 更新于
一些在leetcode刷题的笔记

哈希表

题目一

哈希题目1

这题gpt告诉我分类到哈希表里，遂创建这个一级标题。
主要思路放代码注释里了，值得一提的是看到我建的哈希表最多存在26个元素，于是让gpt给我改了一版数组版本，时间超过了96%，空间超过了48%。

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
func maxPointsInsideSquare(points [][]int, s string) int {
	// 正方形的中心在(0,0),所以点的实际含义可以变成max(abs(x),abs(y))
	// map(label,distance)也就是label不重复的情况下最大distance时的len(map)
	mp := make(map[byte]int,26)
	// 遍历一次更新mp,表示某个字符距离原点的最近距离
	// lebel不重复要求如果出现了mp中出现过的点,需要不包含这个点,也就是还要维护一个上界
	upperBound := int(^uint(0) >> 1)
	res := 0
	// 求出map和上界
	for i,point := range points {
		label := s[i]
		value,isExist := mp[label]
		dis := max(abs(point[0]),abs(point[1]))
		if isExist {
			// 已经存在的点要看谁变成mp内,谁变成上界
			if dis > value {
				upperBound = min(upperBound,dis)
			} else {
				upperBound = min(upperBound,value)
				mp[label] = dis
			}
		} else {
			mp[label] = dis
		}
	}
	// map中小于上界的点都符合标准
	for _,value := range mp {
		if value < upperBound {
			res++
		}
	}
	return res
}
func abs(a int) int {
	if a >= 0 {
		return a
	}else{
		return -a
	}
}

题目二

哈希题目2

根据题意不难推断出，比如对于实例2来说，【“leetcoleet”，k=2】可以看成["le","et","co","le","et"]其中"le"和"et"重复了最多次$$m=2$$次，所以如果要最少操作次数将word变成k周期字符串，那么最好让重复的s为"le"或者"et"，总共能分隔出n=5个，所以至少的操作数为n-m=3次
综上：求出能分割成几个字串
$$n=len(word)/k$$

填哈希表mp[subString]Count，答案为

$$n/k-max(count)$$

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func minimumOperationsToMakeKPeriodic(word string, k int) int {
	mp := make(map[string]int)
	n := len(word)
	res,m := 0,0
	// 分割字符串
	// 统计频率
	for i:=0; i<n; i+=k{
		mp[word[i:i+k]]++
	}
	// 计算res
	for _,count := range mp{
		m = max(m,count)
	}
	res = n/k - m
	return res
}

滑动窗口题目

题目一

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。

解题：双指针滑动窗口
令m=n/4，假设有一个区间已经选定了待替换的子串，如果外部存在某一个字母的个数大于m，那无论选定区间内部的字符串如何改变，都没有办法使得每一个字母都有m个。其逆否命题是如果要使得每个字母都有m个，那外部得每个字母个数都要小于等于m。
所以解题思路为：首先计算每个字母个数（数组存储），再额外写一个判断当前字符串是否处于平衡状态的函数。而由于需要计算最小的子串，我们用【left,rght】来表示滑动窗口，窗口内部的字母要对应再数组的数值减去1，这样数组表示的就是窗口外部的字母个数了。

函数主体框架为：
①如果当前滑动窗口内的子串不满足外部每个字母个数都小于等于m时，right向右移动，扩大窗口，再判断。
②当目前滑动窗口内的子串满足外部每个字母个数小于等于m时，由于题目要求的时最小的字串长度，所以令left++，再判断。

每次出现了一次满足条件的窗口时都要判断一次此时的子串是否为最短的。
使用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
43
44
45
46
47
48
#define Min(a,b) (a)>(b)?(b):(a)
int sw(char c){
	switch c:
		case 'Q':return 0;
		case 'W':return 1;
		case 'E':return 2;
		case 'R':return 3;
		default: return -1;
	return -1;
}
int judge(int* num, int n_4){
	int i;
	for(i = 0; i < 4; i++){
		if(num[i]>n_4){
			return false;
		}
	}
	return true;
}

int balancedString(char * s){
	int num[4]={0};
	int i,j,len=strlen(s);
	int ans,n_4;
	n_4=n/4;
	ans=len;
	//i和j是滑动窗口的左右去间端点
	for(i = 0; i < len; i++){
		num[sw(s[i])]++;
	}
	
	//下面是滑动窗口的核心了
	for(i = 0, j = 0; i < len ;i++){
		while(j < len && !judge(num,n_4)){
			//此时是固定了左窗口，活动右窗口
			num[sw(s[j])]--;
			j++;
		}
		//跳出循环有两种，一种是窗口已经到了字符串尾巴了，另一种是找到了一个窗口可以满足
		if(!judge(num,n_4)){
			break;
			//到底了都没能平衡，后面也就不用看了
		}
		ans=Min(ans,j-i);//j在前面++过，所以不需要+1，实际窗口去间为左闭右开
		num[sw(s[i])]++;//下一步要缩小左窗口，所以需要把此时的s[i]对应字母加入到外部
	}
	return ans;
}

题目二

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

题目一是维护最小窗口，而题目二是维护最大窗口。
分析：当某一时刻找到了最大的窗口，此时窗口内部乘积严格小于k，再将右端点右移一个元素，将不满足条件，那么此时假设窗口为【left,right】。可以知道，此时满足题目要求的连续子数组有：【left,right】,【left+1,right】……【right,right】。即为：right-left+1。
所以我们需要不断维护最大滑动窗口，满足条件时right右移，考虑到只左移一次left不一定能够使窗口再次满足要求，于是使用两个while循环。
代码如下：

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
bool judge(int mul,int k){
    if(mul < k){
        return true;
    }else{
        return false;
    }
}
int numSubarrayProductLessThanK(int* nums, int numsSize, int k){
    int count=0;
    int left,right,mul=1;
    if(k<=1){
        return 0;
    }
    left=0,right=0;
    while(right<numsSize){
        mul *= nums[right];
        while(mul>=k&&left<=right){
            mul/=nums[left];
            left++;
        }
        count += right-left+1;
        right++;
    }
    return count;
}

题目三

滑动窗口题目三

思路：对于queries里存的区间[left,right]，可以考虑维护最大滑动窗口以求解出以right为右端点的最大区间[temp,right]，那么如果left>=temp，就说明是满足题意的，这个返回true，否则返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isArraySpecial(nums []int, queries [][]int) []bool {
	res := make([]bool,len(queries))
	temp := make([]int,len(nums))
	temp[0] = 0
	for i:=1; i < len(nums); i++{
		if nums[i-1] % 2 != nums[i] % 2{
			temp[i] = temp[i-1]
		}else{
			temp[i]=i
		}
	}
	for i,query := range queries{
		if query[0] >= temp[query[1]] {
			res[i] = true
		}else{
			res[i] = false
		}
	}
	return res
}

题目四

滑动窗口题目四

维护一个最大窗口，满足条件是窗口内部的T或F不超过k个，返回最大窗口值，所以需要滑动两次，一次看T的最大，一次看F的最大，取更大的返回。

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
func maxConsecutiveAnswers(answerKey string, k int) int {
	// 滑动窗口，求包含T或F个数不超过k的最大窗口
	return max(window(answerKey,k,'T'),window(answerKey,k,'F'))
}
func max(i,j int) int {
	if i>j{
		return i
	}
	return j
}
func window(answerKey string, k int, ch byte) int {
	// 滑动窗口left和right指针，count表示个数，要让他不超过k
	left,count,maxlen := 0,0,0
	for right:=0; right<len(answerKey); right++ {
		if answerKey[right] != ch {
			count++
		}
		for count > k {
			if answerKey[left] != ch{
				count--
			}
			left++
		}
		maxlen = max(maxlen,right-left+1)
	}
	return maxlen
}

贪心算法

题目一

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
花园里总共有 n + 1 个水龙头，分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为[i -  ranges[i], i + ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

贪心题目一

题目分析：
每个点的最优解的集合即可。
具体算法：从0开始向右走，每次走到最远处，再从此时的最远处开始判断，走向下一个能走到的最远处，直到无路可走返回【-1】或走完全程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)>(b)?(b):(a)
int minTaps(int n, int* ranges, int rangesSize){
   int x=0,i=0,max=0;
   while(i<n){
      for(int j=0;j<n+1;j++){
          if(ranges[j]+j>i&&j-ranges[j]<=i) 
	          max=Max(max,ranges[j]+j);
      }
      if(max==0) return -1;
      x++;
      i=max;
      max=0;
   }
   return x;
}

题目二

贪心题目二

有点过于简单导致不是很想放上来，但是是第一个自己写的双百就还是放了。由于最近在学go，拿go写的，不过相同的代码转成c++就没有100%了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func getSmallestString(s string, k int) string {
    result := []byte(s)
    n := len(s)
    for i := 0; i < n && k > 0; i++ {
        forwardDist := int(s[i] - 'a')
        backwardDist := int('z' - s[i] + 1)
        //前两个分支好像还能再优化，但是时间空间双百了就不改了
        if forwardDist <= backwardDist && forwardDist <= k {
            result[i] = 'a'
            k -= forwardDist
        } else if backwardDist < forwardDist&& backwardDist <= k {
            result[i] = 'a'
            k -= backwardDist
        } else {
            // 变不成'a'了就返回字典序最小的，向'a'方向移动
            result[i] = byte(int(s[i]) - k)
            k = 0
            break;
        }
    }
    return string(result)
}

双百的截图

双百截图

题目三

贪心题目三

非常简单的贪心，这也能是中等题啊，不过完全不知道哪里有优化的空间，时间复杂度和空间复杂度都不好看（过了就行）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func minRectanglesToCoverPoints(points [][]int, w int) int {
    /*
        矩形的底部在x轴上，宽度一定要小于w，高度没有限制
        那其实二维的就可以压缩成一维的？只看横坐标，矩形越宽肯定越好覆盖，所以就宽都为w是最好的
        如果x0处有一个点，那么无论如果这里得有一个矩形，就让这里的x为第一个矩形的左半拉即可
    */
    //先将二维数组按照第一列大小排序，一遍过
    res := 1
    sort.Slice(points,func(i,j int) bool{
        return points[i][0] <= points[j][0]
    })
    last_x := points[0][0]
    for _,point := range points {
        if last_x + w < point[0] {
            res += 1
            last_x = point[0]
        }
    }
    return res
}

题目四

感觉更像是模拟，用到了贪心思想，那还是归类到这里来吧。

贪心题目四

贪心，从大到小排序，取最大的cnt个数求和
如果是偶数直接返回
如果是奇数：
1.删除最小奇数后加上最大偶数
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func maxmiumScore(cards []int, cnt int) int {
    sort.Slice(cards, func(i,j int) bool {
        return cards[i]>cards[j]
    })
    sum := 0
    // 找前cnt大范围内的最小值的下标
    minEven := -1
    minOdd := -1
    for i := 0; i < cnt; i++{
        sum += cards[i]
        if cards[i] % 2 == 1{
            //奇数
            if minOdd == -1 || cards[i] < cards[minOdd] {
                minOdd = i
            }
        }else {
            // 偶数
            if minEven == -1 || cards[i] < cards[minEven] {
                minEven = i
            }
        }
    }
    if sum % 2 == 0 {
        return sum
    }
    minOutEven := -1
    minOutOdd := -1
    for i := cnt; i < len(cards); i++ {
        if cards[i] % 2 == 1 && minOutOdd == -1{
            //奇数
            minOutOdd = i
        } else if cards[i] % 2 == 0 && minOutEven == -1 {
            minOutEven = i
        }
    }
    maxSum := 0
    // 尝试用cnt中的最小奇数替换为非cnt中的最小偶数
    if minOdd != -1 && minOutEven != -1 {
        maxSum = sum - cards[minOdd] + cards[minOutEven]
    }
    // 尝试用cnt中的最小偶数替换为非cnt中的最小奇数
    if minEven != -1 && minOutOdd != -1 {
        maxSum = max(maxSum, sum - cards[minEven] + cards[minOutOdd])
    }
    return maxSum
}

题目五

贪心题目五

差值越大的越优先考虑，去耗费相对小的地方，双百。

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
func twoCitySchedCost(costs [][]int) int {
    // 贪心，两地都能去的前提下，差值越大的人越改去数值小的地方
    ans := 0
    n := len(costs)/2
    cntA,cntB := 0,0
    sort.Slice(costs, func(i,j int) bool {
        return abs(costs[i][0]-costs[i][1])>abs(costs[j][0]-costs[j][1])
    })
    for _,cost := range costs{
        if cntA < n && cost[0] < cost[1]{
            ans += cost[0]
            cntA++
            continue
        }
        if cntB < n && cost[1] < cost[0]{
            ans += cost[1]
            cntB++
            continue
        }
        if cntA == n{
            ans += cost[1]
            continue
        }
        ans += cost[0]
    }
    return ans
}
func abs(a int) int {
    if a >= 0{
        return a
    }
    return -a
}

动态规划

关注状态和转移，为了得到规划出的最优内容，可以通过转移的时候记录来源，算出结果后通过回溯求出最优的内容。

题目一

(leetcode1140题)
许多堆石子排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

分析：题目说了爱丽丝和鲍勃都发挥了最佳水平，所以实际上要做的是计算出再每个i时候，不同的m能够使得此时能拿到的最大石子数为多少。

创建一个数组dp[i][j]，表示当此时已经拿走了i堆石子之后，M=j时的最大结果。这个结果不针对爱丽丝或鲍勃，只是该情况下可拿走的最大可能。所以最后结果变为求dp[0][1]。
而存在这样一个递推方程：

$$dp[i][j]=max(dp[i][j],sum-dp[i+x][max(m,x)])$$

sum表示从i开始的后缀和

$$dp[i+x][max(m,x)]$$

表示的是当此次拿走了x堆时，下一个人取石子的最大可能。
那么解题可以这样：
从最后一堆开始向前遍历，每次记录此时的sum，先遍历m，当m*2>=n时们就代表着此时可以将剩下所有的石子全部拿完，则此时的sum就是dp[i][j]。如果不满足上面那个条件，就说明此时x可以有多个选择，我们要从中选出最优解。那么直接for循环遍历，套上上面的递推公式即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define max(a,b) (a)>(b)?(a):(b)
int stoneGameII(int* piles, int n){
    int i,x,m,dp[110][110]={0},sum=0;
    for(i=n-1;i>=0;i--){
        sum+=piles[i];
        //i为某个值的时候，对m的取值遍历
        for(m=1;m<50;m++){
            if(i+m*2>=n){
                //能全部取完
                dp[i][m]=sum;
                continue;
            }
            for(x=1;x<=m*2;x++){
                dp[i][m]=max(dp[i][m],sum-dp[i+x][max(x,m)]);
            }
        }
    }
    return dp[0][1];
}

题目二

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

解题笔记：
由于每次只能向右和向下移动，并且要求当走到右下角的时候累计和最大，返回最大值。
典型动态规划问题，创建数组dp[i][j]表示当走到位置i,j的时候，最大的礼物价值。
假设[i][j]位置的礼物权值为x，则

$$dp[i][j]=x+max(dp[i-1][j],dp[i][j-1])$$

第一行第一列额外分别处理。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define max(a,b) (a)>(b)?(a):(b)
int maxValue(int** grid, int gridSize, int* gridColSize){
    int m = gridSize, n = gridColSize[0];
    for(int j = 1;j<n;j++){
        grid[0][j] += grid[0][j-1];
    }
    for(int i = 1; i < m; i++){
        grid[i][0]+=grid[i-1][0];
        for(int j = 1; j < n; j++){
            grid[i][j] += max(grid[i-1][j],grid[i][j-1]); 
        }
    }
    return grid[m-1][n-1];
}

题目三

矩阵链乘法问题
给定一个n个矩阵的序列⟨A1,A2,A3…An⟩，我们要计算他们的乘积：A1A2A3…An，由于矩阵乘法满足结合律，加括号不会影响结果，但是不同的加括号方法，算法复杂度有很大的差别。考虑三个矩阵，规模为$$10100,1005,550$$，
如果按照$$((A_1A_2)A_3)$$的次序，需要运算$$101005+10550=7500$$一共7500次；
如果按照$$(A_1(A_2A_3))$$的次序，需要运算$$100550+10100*50=75000$$，一共75000次。
乘法运算次数相差10倍。
动态规划：
们可以将问题划分为两个子问题，$$<A_i,A_{(i+1)},A_{(i+2)}…A_{(j)}>$$的最有括号方案可以划分为$$<A_i,A_{(i+1)},A_{(i+2)}…A_{(k)}>$$和$$<A_{(k+1)},A_{(k+2)},A_{(k+3)}…A_{(j)}>$$的最有括号化方案。
令m[i][j]表示从$$⟨A_i….A_j⟩$$的最小值
当i = j时，m[i,j]=0
当i < j时，假设在矩阵链⟨Ai,Ai+1,Ai+2…Aj⟩分割点位置为$$A_k$$和$$A_{k+1}$$之间m[i,j]等于前后两部分也就是m[i,k]和m[k+1,j]的和，然后还要加上最后两者相乘的运算次数，假如Ai的大小为$$p_{i−1}×p_i$$,则子矩阵链m[i,k]乘积后的矩阵大小为$$p_{i−1}×p_k$$, m[k+1,j]乘积后的大小为$$p_k×p_j$$，最后一次乘法运算次数为$$p_{i-1}p_kp_j$$

可以得出：
$$m[i,j]=0,(i=j)$$
$$m[i,j]=min{m[i,k]+m[k+1,j]+p_{i−1}p_kp_j},i<j，i≤k≤j−1$$

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Matrix_Chain_Order(int p[],int n)
{
   int i,j,L,k,q;
   for (i=1;i<=n;i++)      //先对单个矩阵的链，求解，即所有m[i][i] =0;
   {
     m[i][i]=0;          
   }
   for(L=2;L<=n;L++)     //从两个矩阵链的长度开始，逐次增加矩阵链的长度
       for(i=1;i<=n-L+1;i++)  //在给定p[]中的矩阵链中，对所有种长度为L的情况计算
       {
           j = i+L-1;
           m[i][j] = -1;
           for(k=i;k<=j-1;k++)   //遍历所有可能的划分点k，计算出最优的划分方案
           {
             q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//计算划分的代价
             if ( q < m[i][j] || m[i][j] == -1)  
             {
                m[i][j] = q;     //最优的代价q保存在m[i][j]中
                s[i][j] = k;     //最优的划分位置k保存在s[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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        //计算两个结果，一个是不删除元素时的结果，一个是删除时的结果
        int res = arr[0];
        //不删除的用滑动窗口
        int left = 0;
        int currentMax = arr[0];
        for(int right = 1; right < arr.size(); right++){
            if(currentMax < 0){
                currentMax = arr[right];
                left = right;
            }else{
                currentMax += arr[right];
            }
            res = max(res, currentMax);
        }
        //删除的枚举每个数组元素，计算之前元素的后缀和以及之后元素的前缀和的最大，这两者的和就是删除该元素的最大
        int n = arr.size();
        vector<int> leftMaxSuffix(n);
        leftMaxSuffix[0] = arr[0];
        currentMax = arr[0];
        for (int i = 1; i < n; ++i) {
            currentMax = max(arr[i], currentMax + arr[i]);
            leftMaxSuffix[i] = currentMax;
        }
        // 计算右侧最大前缀和
        vector<int> rightMaxPrefix(n);
        rightMaxPrefix[n-1] = arr[n-1];
        currentMax = arr[n-1];
        for (int i = n-2; i >= 0; --i) {
            currentMax = max(arr[i], currentMax + arr[i]);
            rightMaxPrefix[i] = currentMax;
        }
        // 计算删除一个元素后的最大子数组和
        for (int i = 1; i < n-1; ++i) {
            res = max(res, leftMaxSuffix[i-1] + rightMaxPrefix[i+1]);
        }
        return res;
    }
};

但是费劲巴拉写完后发现题解只有六行，笑嘻了。
题解用的是动态规划，因为原问题可以拆分成多个子问题，每个子问题是：求解以arr[i]结尾的最多删除一次的非空子数组的最大和。
让我们还是聚焦到状态和转移上面，我们维护一个变量dp[i][k]来表示以arr[i]结尾、删除k个数时候非空子数组的最大和。问题中只用考虑$$k=0&&k=1$$两种情况，这两种情况的转移方程为：
不删除比较简单：
$$dp[i][0]=max(dp[i-1][0],0)+arr[i]$$
删除一个是需要额外考虑一下，如果我需要删除的是末尾元素，那么相当于我此时得到的最大的值是以arr[i-1]结尾的、不删除任何一个元素的值，也就是dp[i-1][0],如果删除的不是arr[i-1]，那么说明已经删了别的元素，说明此时的求和应该是dp[i-1][1]+arr[i]，那么此时打的转移方程应该如下：
$$dp[i][1]=max(dp[i-1][1]+arr[i],dp[i-1][0])$$

状态：
当i=0是，不删除情况就是arr[0]，删除情况不合理，dp[0][1]不计入结果，所以：
$$dp[0][0]=arr[0];dp[0][1]=0$$
观察可知，dp[i][*]只和dp[i-1][*]有关，所以可以针对空间复杂度优化。
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int dp0 = arr[0], dp1 = 0, res = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            dp1 = max(dp0, dp1 + arr[i]);
            dp0 = max(dp0, 0) + arr[i];
            res = max(res, max(dp0, dp1));
        }
        return res;
    }
};

太牛了，什么人才能想出这个简洁的写法啊。

题目五

动态规划题目五

没写出来，题解说是数位dp，去查阅了资料。
特征：

  1. 要求统计满足一定条件的数的数量
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制
  4. 界很大（比如$$10^{18}$$），暴力枚举验证会超时
    基本思想是把区间数字拆分成数位，逐位确定。可以通过记忆化搜索的方式实现，也可以通过迭代地推的方式实现。

    状态和转移

    令dp[k]表示二进制长度为k时，不存在连续的1数的个数。
    转移：
    对于第k位数，如果k=0，那么前k-1位可以是任意满足条件的数，有dp[k-1]种可能
    如果k=1，那么第k-1位必须是0，就回到上一种情况，也就是有dp[k-2]种可能
    所以转移方程是：$$dp[k]=dp[k-1]+dp[k-2]$$
    状态：
    只有一位的话0和1都可以，$$dp[1]=2$$
    只有两位的话00、01、10可以，$$dp[2]=3$$
    本题通过上述手段能得到k位二进制没有连续1的个数，但是还不够，需要判区分出哪些数在[0,n]范围内，所以还需要想办法区分。
  • curBit 是当前位，prevBit 是前一位。
  • 如果 curBit 为1，表示可以使用之前计算的 dp[i]，加到结果中。
  • 如果出现连续的两个1，则终止计算，因为后续的数不会符合要求。
  • 如果遍历结束且没有出现连续的1，说明 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
    27
    28
    29
    30
    func findIntegers(n int) int {
    	// 计算当数值为k位时，不存在连续的1数的个数dp[k]
    	L := 0
    	for temp := n; temp > 0; temp >>= 1 {
    		L++
    	}
    	dp := make([]int,L+1)
    	dp[0] = 1
    	dp[1] = 2
    	for i := 2; i <= L; i++ {
    		dp[i] = dp[i-1] + dp[i-2]
    	}
    	// 用于判断当前位是否有连续的 1
    	prevBit := 0
    	result := 0
    	// 遍历每一位
    	for i := L - 1; i >= 0; i-- {
    		// 从最高位开始
    		curBit := (n >> i) & 1
    		if curBit == 1 {
    			result += dp[i]
    			if prevBit == 1 {
    				return result
    			}
    		}
    		prevBit = curBit
    	}
    	// 如果上面循环结束了也合法，那么需要最终加上自己
    	return result + 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
29
30
31
32
33
34
35
func minimumDeleteSum(s1 string, s2 string) int {
/**
    思路上：
    状态：
    dp[i][j]表示s1的前i个字符和s2的前j个字符的最大公共子序列长度
    dp[0][j]=dp[i][0]=0
    转移：
    如果s1[i]==s2[j]，那么dp[i][j]=dp[i-1][j-1]+1
    如果s1[i]!=s2[j]，那么dp[i][j]=max(dp[i][j-1], dp[i-1][j])
    删除的字符的和=总和-剩余的和
    实际上直接让dp[i][j]表示剩余的和，方便计算
**/
    n,m := len(s1), len(s2)
    total := 0
    for _,c := range s1 {
        total += int(c)
    }
    for _,c := range s2 {
        total += int(c)
    }
    dp := make([][] int, n+1)
    for i := range dp {
        dp[i] = make([] int, m+1)
    }
    for i,x := range s1 {
        for j,y := range s2{
            if x == y{
                dp[i+1][j+1] = dp[i][j] + int(x)
            } else {
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            }
        }
    }
    return total-2*dp[n][m]
}

数学部分

快速幂

快速幂

上来就暴力看看能不能力大砖飞（包不行的）

1
2
3
4
5
6
7
8
9
10
11
func getGoodIndices(variables [][]int, target int) []int {
	res := []int{}
	for i,v := range variables {
		a := int(math.Pow(float64(v[0]), float64(v[1])))
		b := int(math.Pow(float64(a), float64(v[2])))
		if b%v[3] == target {
			res = append(res,i)
		}
	}
	return res
}  

考虑用这两条数学公式：

$$\begin{aligned}
(a*b)\quad mod \quad c = (a\quad mod\quad c) * (b \quad mod \quad c)\quad mod \quad c\quad(1)
\end{aligned}$$

$$\begin{aligned}
(a^{b})\quad mod \quad c=(a\quad mod \quad c)^{b}\quad mod \quad c \quad (2)
\end{aligned}$$

在上面的暴力里面进行简单优化发现还是不行，对于比如[[528,818,733,438]]的数据就会判错，高次幂取余的运算可以结合上面的两条公式定义一个pow函数（python是内置了pow能接受base,exp,mod三个参数表示(base^exp)%mod的结果），也就是不求出幂的结果，尽量能求出模的结果就求出模的结果。
快速幂的原理举例是：

$$\begin{aligned}
3^{13} \quad =\quad 3^{(1101)_2}\quad =\quad 3^8 \quad * \quad3^4\quad*\quad3
\end{aligned}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func fastPow(base,exp,mod int) int {
	res := 1
	//先用公式（2）对base求余
	base = base % mod
	//快速幂的退出条件是exp=0
	for exp > 0 {
		if exp%2 == 1 {
			// 也就是指数为1的地方，这里是公式（1）
			result = (result * base) % mod
			}
		base = (base * base) % mod
		exp /= 2
	}
	return res
}

关于快速幂的说明可以在这里查看学习。

回溯

题目一

回溯1

抽象成为数&集合，每个数都会进入到一个集合当中，需要最后每个集合的总和相等，也就是$$target=\sum_{i=0}^{i=len-1}nums[i]÷k$$
递推：

从数的角度看，每个数可以选择进入某个集合，进入该集合后，这个集合的总和不超过$$target$$，同时能满足后续能变为target。
所以考虑：
①存储一个int类型数组，代表桶内的总和
②如果bucket[i]放不下这个数，就剪枝到bucket[i+1]
③放入的操作为bucket[i]+nums[index]
④判断下一个数能否满足条件

回溯：

某个节点不满足的回溯方法就是恢复该节点桶的值，回溯的操作是bucket[i]-=nums[index]

剪枝：

不难看出，先放入大的数显然会减少后续枝的数量，所以需要先对原数组进行倒序排序
如果bucket[i+1]==bucket[i]，那么bucket[i+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
29
30
31
32
33
34
35
36
37
38
39
40
41
func canPartitionKSubsets(nums []int, k int) bool {
	// sum(nums)/k就是求和需要求的结果
	sum := 0
	for _,num := range nums{
		sum += num
	}
	target := sum / k
	sort.Slice(nums,func(i,j int)bool{
		return nums[i]>nums[j]
	})
	bucket := make([]int, k)
	return backtrack(nums,0,bucket,target)
}
func backtrack(nums []int, index int, bucket []int,target int) bool{
	// 结束条件是所有桶都放满了，都放满开始判断是否符合条件
	// 不用判断，能放进去已经说明了该桶满足条件
	if index == len(nums) {
		return true
	}
	// 从nums[index]开始遍历
	for i:=0; i<len(bucket); i++{
		if i > 0 && bucket[i] == bucket[i-1] {
			continue
		}
		if bucket[i]+nums[index]>target {
			// 放不进去就剪枝
			continue
		}
		// 能放进去就放进去
		bucket[i] += nums[index]
		// 判断下一个数
		if backtrack(nums,index+1,bucket,target) {
			return true
		}
		// 下一个数不满足要从此处回溯
		bucket[i] -= nums[index]
	}
	// 当前nums[index]在上述遍历了所有桶后都不满足
	return false
}