Leetcode 815：公交路线

题目

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

• 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

1
2
3

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 

示例 2：

1
2

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

提示：

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 10^5
• routes[i] 中的所有值 互不相同
• sum(routes[i].length) <= 10^5
• 0 <= routes[i][j] < 10^6
• 0 <= source, target < 10^6

题解

开始看到题面第一想法当然是建图，每个route连完全图， 问题就转化为source到target的单源最短距离，使用堆优化的Dijstra算法，可以在$O((|V|+|E|)log|V|)$内找到最优解；

但是很快就想到不对劲，总点数最大10w，当点数很大而且接近稠密图时复杂度基本会爆炸，但是有一个特例，当点数很多但是只有两三个route时，直觉上遍历几遍就出来了（因为route内部是完全图），这个复杂度不符合我们的预期；

此时我已经放弃单源最短路径，已经转而想其他的搜索算法了，最终无果；

本质上还是疏于训练的原因，之前在tarjan算法中，我们对于强联通分量直接做缩点，这里也是一样，因为bus可以在route内无代价移动，我们将每个route内完全图缩成一个点，保留缩点以外的边，只需要找到source和target可能在的route中最短距离；

为此我们对每个站点site：int，维护一个R：unordered_map<int, vector<int>> ,记录站点site在哪些完全图route里，优化建图，对每个route(这样的route最多500个)，使用Dijstra算法（甚至不用优化），维护一个队列，对可能的三角形松弛，最后比较可能的答案返回；

甚至优化建图后求全局最短路径使用Floyd算法都是可以过的

车站总数为$N$,route总数为n, 建图复杂度为$O(Nn)$,最短路复杂度为$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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# include <vector>
# include <iostream>
# include <unordered_map>
# include <climits>
# include <queue>
using namespace std;

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target) return 0;
        int n = routes.size();
        unordered_map<int, vector<int>> R;
        vector<vector<int>> edge(n, vector<int>(n));
        for(int i = 0; i < n; i++){
            for(int site : routes[i]){
                for(int j: R[site]){
                    edge[j][i]=edge[i][j]=1;
                }
                R[site].push_back(i);
            }
        }   
        queue<int> q;
        vector<int> dis(n, -1);
        for(int direct: R[source]){
            dis[direct] = 1;
            q.push(direct);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v = 0; v < n; v++){
                if(edge[u][v] && dis[v] == -1){
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        int ans = INT_MAX;
        for(int t: R[target]){
            if(dis[t]!= -1){
                ans = min(ans, dis[t]);
            }
        }
        return ans == INT_MAX? -1 : ans;  
        
    }
};

int main(){
    vector<vector<int>> routes1 = {{1,2,7},{3,6,7}};
    int source1 = 1;
    int target1 = 6;
    cout << Solution().numBusesToDestination(routes1, source1, target1) << endl; // Output: 2

    vector<vector<int>> routes2 = {{7,12},{4,5,15},{6},{15,19},{9,12,13}};
    int source2 = 15;
    int target2 = 12;
    cout << Solution().numBusesToDestination(routes2, source2, target2) << endl; // Output: -1

    return 0;
}

题目

Leetcode 410

此题非常自然的想法就是动态规划，但是用C++一交，只能打败20%的人，说明时间内存双双爆炸，查看题解后，竟然还有一种神奇的二分做法（虽然之前暑假集训见过，但是仍然很巧妙）；

又是被每日一题杀烂的一天

动态规划

先来看看暴力的动态规划：

维护数组$f(n,k)$，代表数组$n$个数分成$k$组的最佳方案；

注意到分组的无后效性，即存在对于某一个边界下标$x$,$nums$分成$k$组可以看成$nums[0:x]$分成$k-1$组以及$nums[x:]$单独构成一组，但是这里$x$要满足$k-1\le x$，前面的分组情况不会影响后一组的元素之和；

我们贪心地确定分割的最后一个下标（称为凤尾），对于枚举凤尾的所有可能情况，找到最佳的凤尾，极小化分割数组和最大值，从后向前确定凤尾，最终整个分割的情况被确定；

若$x$是凤尾的一个备选值，而假如凤尾前的分割最佳情况已经确定，分割数组和最大值为$max( splitArray(nums[0:x],k-1),\sum_{i=x}^{n-1}nums[i])$,现遍历$x$,不断更新$splitArray(nums,k)$使得保持为最小状态，也就找到了动态规划方程：
$$
f(n,k)=\begin{cases}
\infty & n<k \
min_{x<n}{f(x,k-1),\sum_{i=x}^{n-1}nums[i]}& n\ge k
\end{cases}
$$
贴下暴力做法的代码：

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 f[1005][55];
    int inf=1000000007;
    int splitArray(vector<int>& nums, int k) {
        memset(f,0,sizeof(f));
        int n= nums.size();
        for(int K=0;K<=k;++K){
            for(int N=0;N<=n;++N){
                if(K==0||N<K) f[N][K]=inf;
                else if(K==1){
                    f[N][K]=(N==1)?nums[N-1]:f[N-1][K]+nums[N-1];
                }
                else{
                    int best=inf;
                    int sum=0;
                    f[N][K]=inf;
                    for(int x=N-1;x>=0;--x){
                        sum+=nums[x];
                        if(best>max(f[x][K-1],sum)){
                            best=max(f[x][K-1],sum);
                        }
                    }
                    f[N][K]=best;
                }
            }
        }
        return f[n][k];
    }
};

三重循环表明时间复杂度为$O(n^2k)$

二分查找可能答案

再来介绍下社区里一个漂亮的二分做法；

称一组$k$段数组的分割使得所有子数组元素和不大于$x$的分割为$x-$完美分割；

请注意，$x-$完美分割不一定是题目要求的理想状态，因为有可能等号取不到，所有子数组元素和都严格小于$x$;

• 假如分割数组最大值的极小化结果是一个明确的答案$ans$,$ans$的一个平凡下界为$max(nums)$,平凡上界为$sum(nums)$；

  • 很明显，对于$x\ge ans$,一定存在$x-$完美分割(它就是题目中想象的，能够达到$ans$的那个分割)，同时注意$ans$的最小性，对于$x<ans$,一定不存在$x-$完美分割，我们发现了其中的等价关系；

• 我们缩小这个上下界，当前为$[l,r]$，二分区间验证$mid=(l+r)//2$是上界还是下界；

  • 准确来说，是不断尝试用$mid$缩小$r$；
  • 如果发现存在$mid-$完美分割，说明$mid$是一个比$r$更优的上界；
  • 如果不存在$mid-$完美分割，说明$mid<ans$,改进下界为$mid+1$;

• 我们构造一种贪心的分割策略：保证当前子数组元素和不超过$mid$，也即往当前组加入新数，如果即将超过了就开一个新组（分割原来的旧组），新数加入到新组中；

  这样的贪心策略保证在每个子数组和不超过$mid$的前提下，划分的组数$cnt$最少；

  • 如果我们发现$cnt\le k$,基于贪心策略$G$我们很容易的能给出$mid-$完美分割的策略：打散比较长的子数组，使得$cnt$增加到$k$,（这一般是很容易做到的，除非每个子数组只有一个数，但这往往说明上下界要重合了）

  • 反之若$cnt> k$，连贪心的策略都无能为力，说明$mid-$完美分割是不可能的：

    因为$mid-$完美分割也在每个子数组元素和不超过$mid$的前提下，由$cnt$的最小性,$cnt\le k$,矛盾；

  • $cnt$最小性证明：如果存在一种分割策略$F$，划分了$cnt’$个子数组，$cnt’<cnt$那么在$F$中一定存在一个子数组包含$G$中的一个子数组未来的我一定能看懂吧，由贪心性质，这组元素和要超过$mid$,这与$F$也是满足前提的策略矛盾

• 若$mid-$完美分割存在，说明我们贪心地分割数组，保证每个子数组和不超过$mid$，也即往当前组加入新数，如果即将超过了就开一个新组，新数加入到新组中，这样的贪心策略能保证分割数组在每个子数组和不超过$mid$的前提下，划分的组数最少；

• 就这样，区间越来越小，由离散介值原理，达到$ans=l=r$时，一定有个数组元素和能取等（否则就会继续缩小）；

贴代码：

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

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        l = max(nums)
        r = sum(nums)
        while(l<r):
            mid = (l + r)//2
            if(self.check(nums, k, mid)):
                r = mid
            else:
                l = mid + 1
        return l
        
    def check(self, nums: List[int], k: int, val: int) ->bool:
        cnt, tmp = 1, 0
        for num in nums:
            if tmp + num<=val:
                tmp += num
            else:
                cnt +=1
                tmp = num
        return cnt<=k

给出这个算法的证明还算比较自然，但是如何能敏锐地注意到应该使用二分搜索答案（条件最大值地极小化），如何注意到一系列的等价关系确实值得好好记录xia’lai

题目

leetcode3261

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的

子字符串

的数量。

示例 1：

**输入：**s = “0001111”, k = 2, queries = [[0,6]]

输出：[26]

解释：

对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。

示例 2：

**输入：**s = “010101”, k = 1, queries = [[0,5],[1,4],[2,3]]

输出：[15,9,3]

解释：

s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

提示：

• 1 <= s.length <= 105
• s[i] 是 '0' 或 '1'
• 1 <= k <= s.length
• 1 <= queries.length <= 105
• queries[i] == [li, ri]
• 0 <= li <= ri < s.length
• 所有查询互不相同

题解

对于每一个查询$q=[l,r]$,我们希望于经过某种预处理后，实现$O(1)$回答查询，我们用区间$[l,r]$替代其叙述的子串$s[l\dots r]$；

规定某种布尔变量$\delta$，记录区间$[l,r]$是否为$k$约束的
$$
\delta(u,v)=\begin{cases}
1&\text{[l,r]是k约束的；}\
0&\text{Otherwise.}
\end{cases}
$$
观察任意一个区间,应该具有如下先验性质：

• 若区间是$k$约束的，那么其子区间也应该是$k$约束的；
• 若区间不是$k$约束，那么其超区间也不应该是$k$约束的；

回忆关联规则挖掘中的频繁项集，似乎也具有这样的先验性质；

考察某种$k$约束的区间$[i,j]$,他应该具有极大性质的区间，类似于极大频繁项集在Apriori算法的作用：

• 对于固定的右端点$j$，若$[i,j]$不是$k$约束的，左移端点$i$，可能变为$k$约束的（因为$[j,j]$被认为一定是$k$约束的，$\forall k$）;找到这种极大区间$[f(j),j]$：

  可建立映射$f:0\le f(j)\le j$,其中$[0,j],\cdots,[f(j)-1, j]$不是$k$约束的，$[f(j),j],\cdots,[j,j]$是$k$约束的;

• 对于固定的左端点$i$，若$[i,j]$是$k$约束的，右移端点$j$，可能变为不是$k$约束的（因为越界的区间$[i,n]$不认为是$k$约束的），找到这种极大区间$[i,g(i)]$：

  建立映射$g:i<g(i)\le n$,其中$[i,i],\cdots,[i,g(i)-1]$是$k$约束的，$[i,g(i)],\cdots,[i,n]$不是$k$约束的；

注意，这样的映射建立的本质原因是因为不可能存在两个数满足对应性质；

左移端点的同时应该维护一个区间长度的前缀和$\rm{prefix}$
$$
{\rm prefix}(j+1)=\sum_{t=0}^r \sum_{u=f(t)}^t 1=\sum_{t=0}^j (t-f(t)+1)
$$
[对于查询$[l,r]$,查询的答案是
$$
\begin{aligned}
\sum_{(u,v)\sube [l,r]} \delta(u,v)
&=\sum_{v=l}^r \sum_{u=l}^v \delta(u,v)\
&=\sum_{v=l}^{g(i)-1}\sum_{u=l}^v 1 + \sum_{v=g(i)}^r \sum_{u=f(v)}^v 1\
&=\frac{(g(i)-i)(g(i)-i+1)}{2} + {\rm prefix}(r+1)-{\rm prefix}(g(i))
\end{aligned}
$$
更新映射数组$f,g$，其具有某种单调性，可以采用滑动窗口更新；

AC代码

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:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> count(2, 0);
        vector<int> g(n, n);
        vector<long long> prefix(n + 1, 0);
        int i = 0;
        for (int j = 0; j < n; ++j) {
            count[s[j] - '0']++;
            while (count[0] > k && count[1] > k) {
                count[s[i] - '0']--;
                g[i] = j;
                i++;
            }
            prefix[j + 1] = prefix[j] + j - i + 1;
        }

        vector<long long> res;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            int i = min(g[l], r + 1);
            long long part1 = 1LL * (i - l + 1) * (i - l) / 2;
            long long part2 = prefix[r + 1] - prefix[i];
            res.push_back(part1 + part2);
        }
        return res;
    }
};

题目

Leetcode 2865

1
2
3
4
5
6

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山脉数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

1
2
3
4
5
6

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。

1
2
3
4
5
6
7

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。

这道题应该在集训的时候见过，依稀记得用单调栈应该能做到$O(N$​​);奈何学的不扎实怎么想都降不下来，只能先交个暴力枚举的方法，在这里认认真真做个笔记；

注意观察，山脉数组由左侧的非递减序列和右侧的非递增序列组成；

对于每个下标i,设山脉数组中[0,i]中非递减序列元素和最大值为prefix[i]，[i,n-1]中非递增序列元素和最大值为suffix[i]，遍历i作为峰顶，最大值即为 max⁡(prefix[i]+suffix[i]−maxHeights[i])

• heights[i]=maxHeights[i]

  放开对两侧的限制，才能使得prefix[i]和suffix[i]尽可能大；

• 对于左侧的prefix[i]的求法：

  我们保持单调栈中元素是增的，也就是说：

  • maxHeights依次入栈，若栈为空直接进入；
  • 在maxHeights[i]入栈之前，将所有大于它的栈顶全部弹出；
  • 弹出后假设栈顶为maxHeights[j] j<i，我们可以利用已经求好的prefix[j]和j左侧的取值关系，得到prefix[i]=prefix[j]+(i-j)*maxHeights[i],因为在[j+1,i-1]中的值最多取到maxHeights[i]

• 对于右侧的suffix[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
29
30
31
32
33
34

long long maximumSumOfHeights(vector<int>& maxHeights) {
        std::stack<int> s,t;
        long long sum = 0;
        int n = maxHeights.size();
        vector<long long> prefix(n);
        vector<long long> suffix(n);
        for(int i=0;i<n;i++){
            if(s.empty()){
                s.push(i);
                prefix[i] = maxHeights[i];
                continue;
            }
            while(!s.empty()&&maxHeights[s.top()]>maxHeights[i]) s.pop();
            if(s.empty()) prefix[i] = (i+1)*1LL*maxHeights[i];
            else prefix[i] = (i-s.top())*1LL*maxHeights[i] + prefix[s.top()];
            s.push(i);
        }
        for(int i=n-1;i>=0;i--){
            if(t.empty()){
                t.push(i);
                suffix[i] = maxHeights[i];
                continue;
            }
            while(!t.empty()&&maxHeights[t.top()]>maxHeights[i]) t.pop();
            if(t.empty()) suffix[i]=(n-i)*1LL*maxHeights[i];
            else suffix[i] = (t.top() - i)*1LL*maxHeights[i] + suffix[t.top()];
            t.push(i);
        }
        for(int i=0;i<n;i++){
            if(sum<prefix[i]+suffix[i]-maxHeights[i]) 
                sum = prefix[i]+suffix[i]-maxHeights[i];
        }
        return sum;
    }

很不应该的一道题，之前的算法学的一点也不扎实，也可能是太久没看算法了（一学期），得回炉重造了；

题目：

leetcode 2859

1
2
3
4
5
6
7
8
9
10

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示是： 
0 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002 
下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

1
2
3
4
5
6
7
8
9

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示是： 
0 = 002
1 = 012
2 = 102
3 = 112
只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。

也没什么花算法，对每个下标验证是否是否是k置位的加起来即可；

用位运算a&(a-1)可以去掉a最低位的1，用位运算a&(-a)可以找到最低位的1，换句话说，a&(a-1)==a-a&(-a);

利用这个可以交一份看起来比较简洁的代码：

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

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        sum = 0
        for i in range(len(nums)):
            sum += nums[i] if self.getIndex(i,k) else 0
        return sum 

    def getIndex(self, n:int, k:int):
        cnt = 0
        while n:
            n = n&(n-1)
            cnt +=1
        return cnt==k

不过还有高手，既然用的是python，自然是要成为调库高手的：

1
2
3

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        return sum([x for i, x in enumerate(nums) if i.bit_count() == k])

顺便总结一下python库中int的内置函数：

题目

Leetcode 2788

先来看看原始解答：

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

class Solution:
    def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
        ans = []
        for word in words:
            self.splitWordUnit(word, separator, ans)
        return ans
    def splitWordUnit(self, word: str, separator: str, ans: List[str]):
        tmp = ""
        for ch in word:
            if ch != separator:
                tmp += ch
            elif tmp != '':
                ans.append(tmp)
                tmp = ''
        if tmp != '':
            ans.append(tmp)

下面我们用列表解析和字符串的join和split方法优化我们的题解：

join方法

在Python中，join() 是用于将列表或其他可迭代对象的元素连接成一个字符串的方法。它是一个字符串方法，可以在一个分隔符字符串的帮助下将元素连接起来。

join() 方法的语法如下：

1

字符串分隔符.join(可迭代对象)

其中，字符串分隔符 是一个用于将元素连接起来的字符串，而可迭代对象 是一个包含要连接的元素的列表、元组等。请注意，可迭代对象中的元素必须都是字符串类型。

1
2
3

my_list = ['Hello', 'World', 'Python']
result = '-'.join(my_list)
print(result)

1

Hello-World-Python

split方法

在Python中，split() 是用于将字符串分割成子字符串的方法。它可以根据指定的分隔符将一个字符串分割成多个部分，并返回一个包含所有子字符串的列表。

split() 方法的语法如下：

1

字符串.split(分隔符, 最大分割次数)

其中，字符串 是要分割的字符串，分隔符 是用于确定分割位置的字符串，最大分割次数 是可选参数，用于指定最大的分割次数。如果未指定最大分割次数，则会将字符串全部分割。

1
2
3

my_string = "Hello-World-Python"
result = my_string.split('-')
print(result)

1

['Hello', 'World', 'Python']

1
2
3

my_string = "apple,banana,orange,grape"
result = my_string.split(',', 2)
print(result)

1

['apple', 'banana', 'orange,grape']

列表解析

列表解析是一种简洁且强大的方式，用于根据现有列表创建新的列表。它是 Python 提供的一种快速生成列表的方法。

列表解析的基本语法如下：

1

[表达式 for 变量 in 可迭代对象 if 条件]

其中，表达式 是对变量的处理方法，变量 是用于遍历可迭代对象的变量名，可迭代对象 是需要遍历的列表、元组、字符串等，条件 是一个可选项，用于筛选出满足条件的元素。

1
2
3

numbers = [1, 2, 3, 4, 5]
squared_numbers = [x**2 for x in numbers]
print(squared_numbers)

1

[1, 4, 9, 16, 25]

1
2
3

numbers = [1, 2, 3, 4, 5]
even_numbers = [x for x in numbers if x % 2 == 0]
print(even_numbers)

1

[2, 4]

请注意，添加条件是不能带有else的。

列表解析还可以嵌套使用，用于处理多维数据。这使得可以更加灵活地生成复杂的数据结构。

总之，列表解析是一种简洁而强大的方式，用于根据现有列表以及一些条件创建新的列表。它是 Python 中优雅而高效的一种编程技巧。

题解

最终的题解可以用一行解决：

1
2
3

class Solution:
    def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
        return [x for x in separator.join(words).split(separator) if x != '']<u></u>

题目

[Leetcode 1547](1547. 切棍子的最小成本 - 力扣（LeetCode）)

1
2
3
4
5
6

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：

第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

1
2
3

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。

题解

明显能想到， 尽管随着cuts顺序变化，但是最终剩余的原子棍子都是固定的，因此应该考察一个逆向问题，合并这些短棍子具有某种代价，现找到一种方案使得代价最小化；

第len个阶段，我们合并len个棍子，可以看到，每个阶段的短棍子的合并付出的代价和前一阶段由哪些棍子已经被合并有关，这应该是一个**区间DP问题**；

• 分阶段合并小区间具有某种代价
• 代价和前面的阶段有关

随手排序，发现cuts数组天然维护一个前缀和的形式：

以样例n = 7, cuts = [1,3,4,5]来说，最终分的短棍子长度只可能是1,2,1,1,2，那么其前缀和为0,1,3,4,5,7,我们每一阶段合并棍子的代价应该是某个长棍子的长度，也就是某个区间和,我们重新在cuts的头部插入0,尾部插入n;

假设cuts原始长度为m, 原子棍子的索引从1开始，一共有m+1个原子棍子，插入0,n后cuts长度为m+1;

在第len个阶段，合并索引在[i,j]中的棍子代价为cuts[j]-cuts[i-1]，这里j-i+1=len,他应该和上某个阶段区间合并有关，转移方程如下：
$$
f[i][j]= {\min}\limits_{i\le k< j} {f[i][k]+f[k+1][j]+cuts[j]-cuts[i-1]}
$$
时间复杂度为$O(m^3)$;

AC代码

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:
    int minCost(int n, vector<int>& cuts) {
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();
        vector<int> c;
        c.push_back(0);
        for(int i=0;i<m;i++) c.push_back(cuts[i]);
        c.push_back(n);

        int f[105][105]={0};
        for(int i=1;i<=m+1;i++){
            for(int j=i+1;j<=m+1;j++) {
                f[i][j]=INT_MAX;
            }
        }
        for(int len=2;len<=m+1; len++) {
            for(int i=1;i<=m-len+2;i++){
                int j=i+len-1;
                for(int k=i;k<j;k++) {
                    f[i][j]=min(f[i][k]+f[k+1][j]+c[j]-c[i-1], f[i][j]);
                }
            }
        }
        return f[1][m+1];
    }
};

题目

Leetcode 10

动态规划

$$
dp[i][j]=\begin{cases}
dp[i-1][j-1]&match(s[i],p[j]),p[j]\neq*\
false& unmatch(s[i],p[j]),p[j]\neq*\
dp[i][j-2]or dp[i-1][j]&p[j]=, match(s[i],p[j-1])\
dp[i][j-2] &p[j]=, unmatch(s[i],p[j-1])
\end{cases}
$$

群

若称$G$为一个群，如果非空集合$G$定义了二元运算「$\cdot$」,满足：

• 结合律：$\forall a,b,c\in G, ( a· b) · c = a·( b· c) $;
• 存在幺元：$\exist e\in G, e· a = a· e = a;$
• 存在逆元：$a^{-1} · a = a· a^{- 1} = e$​;

Abel群

进一步，若称$G$为Abel群，如果$G$还满足交换律,否则为非交换群；

• 交换律：$\forall a,b\in G, a· b = b· a $

将$G$中的运算记作「$+$」,有如下性质：

• 存在零；
• 存在负元素；

显然，全体整数$\mathbb Z$对于加法构成交换群；

阶

称$G$为有限群，如果群$G$包含元素个数有限，元素个数称为群$G$的阶；

称$a$为有限阶元素，如果存在正整数$k$满足$a^k=e$，将$k$定义为$a$的阶；

若不存在这样的$k$​，则为无限阶元素；

称群$G$为周期群，如果其每一个元素都是有限阶元素；

Property

对于如果$a$ 是群$G$ 的一个$k$ 阶元素, $e$ 是$G$ 的单位元素

• $a^l=e,k|l$;
• $a^l = a^m,k|l-m$;
• 若$a$是无限阶元素，对于$a^l = a^m$,必有$k=m$;

置换群

设$M$是一个非空集合，$M$到自身的双射的全体对于复合运算构成群，称作$M$的全置换群$S(M)$；

若$|M|=n$,则$S(M)$称为$n$级对称群；

$S(M)$中的元素称作$M$的一个置换$\sigma$；

• $|S(M)|=n!$;

简便起见，$M={1,2,\cdots,n},i_1,i_2,\cdots ,i_t\in M$,称置换$\sigma$是一个长度为$t$的轮换，如果：
$$
\sigma(i_1)=i_2,\sigma(i_2)=i_3,\cdots,\sigma(i_t)=i_1
$$
对于不是$i_1,i_2,\cdots ,i_t$的其他元素$i$而言，均有$\sigma(i)=i$;

长度为2的轮换又称为对换；

对于不相交的轮换$\tau,\sigma$，满足交换律$\tau\sigma=\sigma\tau$

Theorem

对称群$S_n$中任意不等于幺元的元素都可以唯一分解为不相交的轮换的乘积；

proof:考虑取$i_1$使得$\sigma(i_1)\neq i_1$,存在最小的$t$使得$\sigma^t(i_1)=i_1$,记$I={i_1,\sigma(i_1),..,\sigma^{t-1}(i_1)}$;

取轮换$\tau$为$\sigma$限制在$I$;考虑$[n]/I$的元素，若在$\sigma$下不动，则说明$\sigma$是单个轮换；

否则取$[n]/I$的发生变动的元素$i_2\neq i_1$,重复分解即可；

Corollary

1. 任意置换可以分解为对换的乘积;
2. 任意给定的置换分解为对换乘积时出现的对换个数奇偶性不变；

子群，陪集

对于群$G$的非空子集$H$，称$H$为$G$的子群，若$H$在$G$的运算下构成群；

• 记作$H\le G$

定义$G$的子集$H,K$的子集的积
$$
HK={hk|h\in H,k\in K}
$$

Theorem

设$G$是群，$H\subseteq G,H\neq\varnothing$;下三个命题等价；

• $H\le G$
• $H^2 \sube {H}, H^{-1}\sube H$;
• $HH^{-1}\sube H$

事实上，若$H\le G$,则$H^2=H,H^{-1}=H$

• ${e}$为$G$的平凡子群；
• 若干子群的交仍为子群；

生成子群

对群$G$，$M\sube G$,称由$M$生成的子群$$为所有包含$M$的子群的交；

• $={e,a_1…a_n|a_i\in M\cup M^{-1},n=1,2…}$

代数系统

运算

一般地，对于非空集合$A_1,A_2,…,A_n,A$,$n$元运算是指映射$f:A_1\times A_2\times…\times A_n\to A$;

运算的封闭性：对于$A_1\times A_2\times…\times A_n$到$A$的$n$元运算中，对集合$A$的任意两个元素运算后的结果仍属于$A$

代数系统

对非空集合$A$，$*_i$是定义在$A$上的$k_i$元封闭代数运算$(1\le i\le m)$;

定义代数系统为$<A,*_1,…,*_m>$;

对于同类型的代数系统当且仅当所有运算的目数相同；

称$<B,*_1,…,*_m>$是$<A,*_1,…,*_m>$的子代数，如果

• $B\sube A,B\neq \varnothing$
• $_1,…,_B$是$B$上的封闭运算；

二元运算律

结合律

对于二元代数系统$<A,>$,如果$\forall a,b,c\in A$有$(ab)c=a(bc)$,称$$在$A$上满足结合律；

交换律

对于二元代数系统$<A,>$,如果$\forall a,b\in A$有$ab=ba$,称$$在$A$上满足交换律；

消去律

对于二元代数系统$<A,*>,a\in A$

• 对$\forall x,y\in A$,若$ax=ay\iff x=y$,那么称$a$为左可消去元；
• 对$\forall x,y\in A$,若$xa=ya\iff x=y$,那么称$a$为右可消去元；
• 称$a$是可消去元，如果$a$既是左可消去的又是右可消去的；
• 若$A$中所有的元素都是可消去元，称$*$满足消去律；

幂等律

对于二元代数系统$<A,>,a\in A$，若$aa=a$，称$a$是$A$关于$*$的一个幂等元；

若$A$中每一个元素都是幂等的，称$*$满足幂等律；

分配律

对于代数系统$<A,*,\circ>$;对$\forall a,b,c\in A$

• 称$$对$\circ$左分配，如果$a(b\circ c)=(a\circ b)\circ(a\circ c)$
• 称$*$对$\circ$右分配，如果$(b\circ c)*a=(b\circ a)\circ(c\circ a)$
• 称$*$对$\circ$满足分配律，如果既满足左分配律又满足右分配律；

吸收律

对代数系统$<A,*,\circ>$,如果对$\forall x,y\in A$有

• $x*(x\circ y)=x$
• $x\circ(x*y)=x$

称$*$和$\circ$满足吸收律；

特殊元素

幺元

对于二元代数系统$<A,*>$

• 若存在$e_l\in A$,对$\forall a\in A$,有$e_la=a$,称$e_l$为运算$$的左幺元；
• 若存在$e_r\in A$,对$\forall a\in A$,有$ae_r=a$,称$e_r$为运算$$的右幺元；
• 幺元既是左幺元，又是右幺元；

零元

对于二元代数系统$<A,*>$

• 若存在$e_l\in A$,对$\forall a\in A$,有$e_la=e_l$,称$e_l$为运算$$的左零元；
• 若存在$e_r\in A$,对$\forall a\in A$,有$ae_r=e_r$,称$e_r$为运算$$的右零元；
• 零元既是左零元，又是右零元；

逆元

对于存在幺元$e$的代数系统$<a,*>$,对于$\forall a\in A$

• 若$\exist b\in A$,使得$b*a=e$,称$a$左可逆，$b$是$a$的一个左逆元，记作$a_l^{-1}$
• 若$\exist b\in A$,使得$a*b=e$,称$a$右可逆，$b$是$a$的一个右逆元，记作$a_r^{-1}$
• 逆元既是左逆元，又是右逆元；

关系代数系统

对于关系集$\mathscr R$,额外定义如下运算(除开常规的交，并，差)

1. 笛卡尔积
   $$
   R \times S = {<t_r,t_s>|t_r\in R \wedge t_s\in S}
   $$

2. 选择运算
   $$
   \sigma_F(R)={t|t\in R,F(R)=true}
   $$

3. 投影运算
   $$
   \Pi_A(R)={ t[A]|t\in R}, A \subseteq R
   $$