讨论/技术交流/🐱 第 15 场夜喵双周赛/
🐱 第 15 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

2 分 - 有序数组中出现次数超过25%的元素
4 分 - 删除被覆盖区间
5 分 - 字母组合迭代器
7 分 - 下降路径最小和 II

共 9 个回复

5126. 有序数组中出现次数超过25%的元素

首先,题目保证数组中仅有一个数字出现超过 25%,所以有很多奇怪的情况可以不用考虑了。
最直接的思路就是暴力统计每一个数字出现了多少次,然后输出满足要求的那一个。

  • 一种方法是使用 map 来实现这件事,就是 O(nlogn)O(n log n) 的复杂度。
  • 因为题目中保证数字有序排列(即相同的数字一定在一起),所以你可以线性地做到相同的事情。方法就是使用一个 cur 变量统计当前扫描到了哪一个数字, cnt 变量表示 cur 这个数字遇到了多少次。
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int cur = arr[0], cnt = 1;
        if (cnt * 4 > n) return cur;
        for (int i = 1; i < n; i++){
            if (arr[i] != cur) cur = arr[i], cnt = 0;
            ++cnt;
            if (cnt * 4 > n) return cur;
        }
        return 0;
    }
};

5127. 删除被覆盖区间

因为数据范围非常小,区间的数量仅有 10001000 个,所以暴力的使用 O(n2)O(n ^ 2) 的复杂度就可以通过这道题目。
具体做法就是,顺次枚举区间 [a,b)[a, b),然后检查给定的其他所有区间 [c,d)[c, d),是否存在 [a,b)[c,d)[a, b) \in [c, d),不存在则给答案计数器加一。

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int ans = 0;
        for (int i = 0; i < n; i++){
            bool flag = true;
            for (int j = 0; j < n && flag; j++){
                if (i == j) continue;
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) flag = false;
            }
            if (flag) ++ans;
        }
        return ans;
    }
};

5123. 字母排列迭代器

题目就是按顺序生成 nn 个字母中选择 combinationLengthcombinationLength 的所有子序列。
方法也非常直白,常见于小学奥数课本,初中、高中数学课本,大学组合数学中。
我们将字符串的外衣去掉,将字符串看作 1,2,3,,n1, 2, 3, \cdots, n,那么第一个排列数组一定是 1,2,3,,combinationLength1, 2, 3, \cdots, combinationLength,最后一个排列数组一定是 ncombinationLength+1,ncombinationLength+2,,nn - combinationLength + 1, n - combinationLength + 2, \cdots, n
生成下一个字符串的方法也很简单,从后往前扫描当前的数组,判断位置是否可以增加 11(增加后不超过最后一个排列这个位置上的值),如果找不到可以增大的数字,说明已经生成完毕,否则将此位置增加 11, 然后这个位置之后的所有位置升序递增 11

class CombinationIterator {
public:
    int cur[20], lim[20], len;
    string ch;
    bool nxt;
    CombinationIterator(string characters, int combinationLength) {
        int n = characters.size();
        ch = characters;
        len = combinationLength;
        nxt = true;
        for (int i = 0; i < len; i++) cur[i] = i, lim [i] = n - len + i;
    }
    
    string next() {
        string ret = "";
        for (int i = 0; i < len; i++) ret += ch[cur[i]];
        
        int j = len - 1;
        while(j >= 0 && cur[j] == lim[j]) --j;
        if (j == -1) nxt = false; else{
            ++cur[j];
            for (int i = j + 1; i < len; i++) cur[i] = cur[i - 1] + 1;
        }
        
        return ret;
    }
    
    bool hasNext() {
        return nxt;
    }
};

5129. 下降路径最小和 II

简单的一个动态规划,令 dp[i][j]dp[i][j] 表示当前路径走到了第 ii 行第 jj 个位置的最小权值和。(讨论中坐标均从 11 开始 ,矩阵 arrarrnnmm 列)
边界情况就是 dp[0][i]=0,i[1,n]dp[0][i] = 0, i \in [1, n],即未出发还在第 00 行的某个位置,权值和为 00
转移就是对于第 i 行第 j 个位置,我们可以从第 i1i - 1 行第 kk 个位置移动过来,满足 kj,k[1,m]k \neq j , k \in [1, m]。对于所有的 dp[i1][k]dp[i - 1][k] 找一个最小的转移到当前位置就可以了,即 dp[i][j]=minkj,k[1,m]dp[i1][k]+arr[i][j]dp[i][j] = \mathop{min}\limits_{k\neq j, k \in [1, m]}{dp[i-1][k] + arr[i][j]}
最终答案就是在第 nn 行的所有情况中找一个最小的。

int dp[250][250];

class Solution {
public:    
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        memset(dp[0], 0, sizeof(dp[0]));
        
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                dp[i][j] = 4000000;
                for (int k = 1; k <= m; k++){
                    if (j == k) continue;
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + arr[i - 1][j - 1]);
                }
            }
        }
        
        int ans = 4000000;
        for (int i = 1; i <= m; i++) ans = min(ans, dp[n][i]);
        
        return ans;
    }
};
11

拿了一次国服第一(以及世界服第一)很开心!
请大家继续支持力扣平台呀!

7

第一题:

求出数量超过25%的那个数,统计即可,至于怎么统计,见仁见智,用平衡树的,用哈希表的,用桶的,等等

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        map<int, int> count;
        for (auto a: arr) {
            count[a]++;
        }
        for (auto it = count.begin();it != count.end();it++) {
            if (it->second * 4 > arr.size()) {
                return it->first;
            }
        }
        return -1;
    }
};

第二题:

这数据范围,才1000个,o(n2)o(n^2)的暴力检测妥妥就能过

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        vector<bool> flag(intervals.size(), true);
        int n = intervals.size();
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (i == j || !flag[j]) {
                    continue;
                }
                if (intervals[j][0] <= intervals[i][0] && intervals[j][1] >= intervals[i][1]) {
                    flag[i] = false;
                    break;
                }
            }
            if (flag[i]) {
                ret++;
            }
        }
        return ret;
    }
};

第三题:

python有这个题的生成函数,详情请百度“itertools.combinations”

另:

知道前一个组合,如何求后一个组合?

例子:给定字母abcd,前一个组合是abc,下一个组合?

从组合的最后一个字母开始寻找,c有下一个字母d,所以将c换成d,返回下一个组合abd

d没有下一个字母,往前寻找,b有下一个字母c,所以将b换成c,最后一个字母赋值为c的下一个字母d,返回下一个组合acd

d没有下一个字母,往前寻找,c有下一个字母d,但是换成d后,最后一个字母没有字母赋值,所以继续往前寻找,a的下一个字母是b,所以a换成b,后面两个字母依次赋值为c和d,返回下一个组合bcd

按照这种方法,b虽然有下个字母c,但换成c后,最后一个字母没有字母可以赋值,所以bcd没有下一个组合

class CombinationIterator {
public:
    string res;
    vector<int> index;
    string allc;
    
    CombinationIterator(string characters, int combinationLength) {
        allc = characters;
        res = characters.substr(0, combinationLength);
        index = vector<int>(combinationLength, 0);
        for (int i = 0;i < index.size();i++) {
            index[i] = i;
        }
    }
    
    string next() {
        if (res == "") {
            return "";
        }
        string ret = string(res);
        int i = index.size() - 1;
        while (i >= 0) {
            index[i]++;
            if (index[i] + index.size() < allc.size() + i + 1) {
                res[i] = allc[index[i]];
                break;
            } else {
                i--;
            }
        }
        if (i < 0) {
            res = "";
        } else {
            i++;
            while (i < index.size()) {
                index[i] = index[i - 1] + 1;
                res[i] = allc[index[i]];
                i++;
            }
        }
        return ret;
    }
    
    bool hasNext() {
        return res != "";
    }
};

第四题:

动态规划,令dp[i][j]dp[i][j]为arr前i行中,并且第i行第j列这个元素位于下降路径的最后一个节点的最小路径,
则有转移方程,dp[i][j]=min(dp[i1][k])+arr[i][j],k!=jdp[i][j]=min(dp[i - 1][k])+arr[i][j], k != j

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        vector<vector<int>> dp(arr.size(), vector<int>(arr[0].size(), 0));
        for (int j = 0;j < arr[0].size();j++) {
            dp[0][j] = arr[0][j];
        }
        for (int i = 1;i < arr.size();i++) {
            for (int j = 0;j < arr[0].size();j++) {
                int min = -1;
                for (int k = 0;k < arr[0].size();k++) {
                    if (j == k) {
                        continue;
                    }
                    if (min == -1 || dp[i - 1][k] < dp[i - 1][min]) {
                        min = k;
                    }
                }
                dp[i][j] = dp[i - 1][min] + arr[i][j];
            }
        }
        int min = -1;
        for (int j = 0;j < arr[0].size();j++) {
            if (min == -1 || dp[arr.size() - 1][j] < dp[arr.size() - 1][min]) {
                min = j;
            }
        }
        return dp[arr.size() - 1][min];
    }
};
8

5126. 有序数组中出现次数超过25%的元素

出现次数超过 25% 就返回,直接按照题意来:

某个数的出现次数总次数25%\frac{某个数的出现次数}{总次数} \geq 25\%

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        cnt = len(arr)
        cc = dict(collections.Counter(arr))
        for k, v in cc.items():
            if v > cnt / 4:
                return k

5127. 删除被覆盖区间

如果区间被覆盖就替换,由于就 1000 个区间,那么就 O(n^2) 暴力出结果就可以了。

class Solution:
    def removeCoveredIntervals(self, iii: List[List[int]]) -> int:
        n, t = len(iii), iii
        ans = 0
        for i in range(n):
            ok = 1
            for j in range(n):
                if i == j:
                    continue    
                if t[i][0] >= t[j][0] and t[i][1] <= t[j][1]:
                    ok = 0
            if ok == 1:
                ans += 1        
        return ans        

5123. 字母组合迭代器

这题抖了个小机灵。由于才 15 个数字,所以先计算了一下到底最多有多少种可能结果。

C157=6435C_{15}^{7} = 6435

所以最大排列情况就这么多。因为字符串是有序的,所以我们先暴力出来所有指定数目的子集合,然后 sort 一下,记录下下标,在调用的时候输出即可。

class CombinationIterator:
    
    def sol(self, items):

        if len(items) == 0:
            return [[]]

        subsets = []
        first_elt, rest_list = items[0], items[1:]

        for partial_sebset in self.sol(rest_list):
            subsets.append(partial_sebset)
            next_subset = partial_sebset[:] +[first_elt]
            subsets.append(next_subset)
        return subsets

    def __init__(self, characters: str, ll: int):
        self.isFirst = True
        self.cnt = 0
        cc = [c for c in characters]
        sols = self.sol(cc)
        self.res = []
        for s in sols:
            if len(s) == ll:
                self.res.append("".join(s[::-1]))
        self.res = sorted(self.res)       

    def next(self) -> str:
        self.cnt += 1
        return self.res[self.cnt - 1]
        

    def hasNext(self) -> bool:
        return self.cnt < len(self.res)


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

5129. 下降路径最小和 II

应该是我见过最简单的第四题之一了。由于不能同一列,所以在第三次循环的时候判一下列数就好。定义 dp[i][j] 代表到达第 i 行第 j 列时候的最小下降路径和。所以状态转移方程:

dp(i,j)=min(dp(i,j),dp(i1,k))      (kj)dp(i, j) = min(dp(i, j), dp(i - 1, k)) \ \ \ \ \ \ (k \neq j)

另外,这题卡语言!! Python 相同的代码会 TLE,C++ 1A。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int dp[204][204];
        for (int i = 0; i < arr.size(); ++ i) {
            dp[0][i] = arr[0][i];
        }
        int result = 200 * 99;
        for (int i = 1; i < arr.size(); ++ i) {
            for (int j = 0; j < arr.size(); ++ j) {
                dp[i][j] = 200 * 99;
                for (int k = 0; k < arr.size(); ++ k) {
                    if (k == j) continue;
                    dp[i][j] = min(arr[i][j] + dp[i - 1][k], dp[i][j]);
                }
                if (i == arr.size() - 1) {
                    result = min(result, dp[i][j]);
                }
            }
        }
        return result;
    }
};


最后,如果大家对移动端和刷算法题感兴趣,可以微信关注我的技术公众号。

image.png

5

答题

有序数组中出现次数超过25%的元素

因为是非递减的 有序 整数数组,所以从前往后挨着数,超过25%的返回就对了。

int findSpecialInteger(vector<int>& arr) 
{
	int cnt = 0;
	int pre = INT_MAX;
	for (auto n : arr)
	{
		if (pre == n)
		{
			cnt++;
			continue;
		}
		if (cnt > arr.size() / 4) break;
		pre = n;
        cnt = 1;
    }
	return pre;
}

删除被覆盖区间

将区间按照左小右大的方式排序,这样就可以保证如果有需要删除的子区间,一定会在母区间的后面。
然后每一个区间只需要跟它前面的区间比较,如果需要删除记个数。

int removeCoveredIntervals(vector<vector<int>>& intervals) 
{
	sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b)
		{
			if (a[0] == b[0])
			{
				return b[1] < a[1];
			}
			return (a[0] < b[0]);
		});

	int cnt = 0;
	for (size_t i = 1; i < intervals.size(); i++)
	{
		for (size_t j = 0; j < i; j++)
		{
			if (intervals[i][0] >= intervals[j][0]
				&& intervals[i][1] <= intervals[j][1])
			{
				cnt++;
				break;
			}
		}
	}
	return intervals.size() - cnt;
}

字母排列迭代器

这题最重要的是阅读理解。
举个例子:

输入:abcde,3
所有的输出:
abc, abd, abe,
acd, ace,
ade,

bcd, bce,
bde,

cde

  1. next()
    11. 从后往前对要返回的字符串strNext的字符判断,是否在源数据characters中后面还有字符
    12. 如果有,就把这个字母换了之后就可以返回了
    13. 如果最后一位的字符已经是最后的字符了,那么倒数第二位的字符就可以往后换一个字符,并且最后的字符是其之后的字符

    abe --> acd

    1. 按照这个规则不断往前推,推到第0位字符更新时,更新后如果整个长度不够,就说明没有后续的组合了
  2. hasNext()
    21. 提前计算并保存下一个strNext,调用next()时,使用临时变量保存,再更新
    22. 判断strNext是否为空就行了

  3. 使用unordered_map<char, size_t> um;记录字符和索引的对应关系

class CombinationIterator 
{
public:
    CombinationIterator(string characters, int combinationLength) 
        : chs(characters), len(combinationLength)
    {
        for (size_t i = 0; i < chs.size(); i++)
        {
            um[chs[i]] = i;
        }
		for (size_t i = 0; i < len; i++)
		{
			strNext.push_back(chs[i]);
		}
    }

    string next()
    {
        string ret = strNext;
        for (size_t i = strNext.size() - 1; i < strNext.size(); i--)
        {
            auto di = um[strNext[i]] + 1;
            if (di + len - i - 1 < chs.size())
            {
                strNext[i] = chs[di];
                while ((++i) < strNext.size())
                {
					strNext[i] = chs[++di];
                }
                return ret;
            }
        }
		strNext = "";
		return ret;
    }

    bool hasNext() 
    {
        return strNext != "";
	}

private:
    string chs;
	string strNext;
    int len;
    unordered_map<char, size_t> um;
};

下降路径最小和 II

动态规划。

如果决定使用第i行j列的数值,那么需要i - 1行中除了自己这列之外最小的值与自己相加。
即 arr[i][j] + min(arr[i - 1][all], 除去arr[i - 1][j])

所以每行寻找第一最小值和第二最小值。
把最小值的列下一行的值加上第二最小值,其他列的下一行都加上第一最小值。

直接在原数组上改了。
最后返回最后一行的最小值。

int minFallingPathSum(vector<vector<int>>& arr) 
{
	for (size_t i = 0; i < arr.size() - 1; i++)
	{
		size_t min1 = arr[i][0] < arr[i][1] ? 0 : 1;
		size_t min2 = arr[i][0] < arr[i][1] ? 1 : 0;
		for (size_t j = 2; j < arr[0].size(); j++)
		{
			if (arr[i][min1] > arr[i][j])
			{
				min2 = min1;
				min1 = j;
			}
			else if (arr[i][min2] > arr[i][j])
			{
				min2 = j;
			}
		}
		for (size_t j = 0; j < arr[0].size(); j++)
		{
			if (j == min1)
			{
				arr[i + 1][j] += arr[i][min2];
			}
			else
			{
				arr[i + 1][j] += arr[i][min1];
			}
		}
	}

	int ans = INT_MAX;
	for (size_t j = 0; j < arr[0].size(); j++)
	{
		ans = min(ans, arr[arr.size() - 1][j]);
	}
	return ans;
}

致谢

纪念第一次明明可以4道全做完,却审题不清,静不下心,结果只提交了2题。
虽然是题简单,但也算进步吧。

感谢观看,希望大家坚持并进步!

2

这周的题是我参加周赛以来,感觉最简单的一次,第一名写完都不到10分钟,足以见得这次的难度。。。

Rank

  • 31/791。

5126. 有序数组中出现次数超过25%的元素

  • 题意:给你一个非递减的有序整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。请你找到并返回这个整数。
  • 数据范围:
    • 1<=arr.length<=1041 <= arr.length <= 10^4
    • 0<=arr[i]<=1050 <= arr[i] <= 10^5
  • 思路:开一个长度为1e5的数组,扫描一遍,统计每个数出现的次数,然后从0遍历到1e5,如果某个数出现次数大于数组总长度除以4,就直接输出这个数。
  • 复杂度:O(arr.length)O(arr.length)
  • 代码:
class Solution {
public:
    int cnt[100010];
    int findSpecialInteger(vector<int>& arr) {
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<arr.size(); i++){
            cnt[arr[i]]++;
        }
        int ans = -1;
        for(int i=0; i<100010; i++){
            if(cnt[i]*4>arr.size()){
                ans = i;
                break;
            }
        }
        return ans;
    }
};

5127. 删除被覆盖区间

  • 题意:给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。只有当 c <= ab <= d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。在完成所有删除操作后,请你返回列表中剩余区间的数目。
  • 数据范围:
    • 1<=intervals.length<=10001 <= intervals.length <= 1000
    • 0<=intervals[i][0]<intervals[i][1]<=1050 <= intervals[i][0] < intervals[i][1] <= 10^5
    • 对于所有的 i!=jintervals[i]!=intervals[j]i != j:intervals[i] != intervals[j]
  • 思路:数据范围才1000,直接for循环暴力标记即可。
  • 复杂度:O(n^2)
  • 代码:
class Solution {
public:
    struct node{
        int l,r;
        node(){}
        node(int l_, int r_):l(l_),r(r_){}
    }a[1010];
    bool vis[1010];
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        for(int i=0; i<n; i++){
            a[i].l=intervals[i][0];
            a[i].r=intervals[i][1];
        }
        memset(vis, false, sizeof(vis));
        for(int i=0; i<n; i++){
            if(vis[i]) continue;
            for(int j=0; j<n; j++){
                if(j==i) continue;
                if(a[j].l<=a[i].l&&a[j].r>=a[i].r){
                    vis[i]=true;
                    break;
                }
            }
        }
        int ans=0;
        for(int i=0; i<n; i++){
            if(!vis[i]) ans++;
        }
        return ans;
    }
};

5123. 字母排列迭代器

  • 题意:请你设计一个迭代器类,包括以下内容:

    • 一个构造函数,输入参数包括:一个 有序且字符唯一 的字符串 characterscharacters(该字符串只包含小写英文字母)和一个数字 combinationLengthcombinationLength
    • 函数 next()next() ,按 字典序 返回长度为 combinationLengthcombinationLength 的下一个字母排列。
    • 函数 hasNext()hasNext() ,只有存在长度为combinationLengthcombinationLength 的下一个字母排列时,才返回 TrueTrue;否则,返回FalseFalse
  • 数据范围:

    • 1<=combinationLength<=characters.length<=151 <= combinationLength <= characters.length <= 15
    • 每组测试数据最多包含10410^4次函数调用。
    • 题目保证每次调用函数nextnext时都存在下一个字母排列。
  • 思路:这个题本质就是从n个数中取k个数,但是需要满足不降原则,直接使用回溯法搜索一下就可以了,注意搜索的起点就行。我们在搜索的时候可以把所有字符串都存入到一个vector<string>ans里面,后续就直接回答就可以了。

  • 复杂度:C(n,k),代表组合数。

  • 代码:

class CombinationIterator {
public:
    vector <string> ans;
    int n, k;
    bool vis[20];
    char re[20];
    char a[20];
    void dfs(int step,int start)
    {
        if(step==k)
        {
            string t="";
            for(int i=0;i<k;i++)
            {
                t+=re[i];
            }
            ans.push_back(t);
            return;
        }
        for(int i=start;i<n;i++) 
        {
            if(vis[i]==1)
                continue;
            vis[i]=1;
            re[step]=a[i];
            dfs(step+1,i+1);
            vis[i]=0;
        }
        return;
    }

    CombinationIterator(string characters, int combinationLength) {
        n = characters.size();
        k = combinationLength;
        ans.clear();
        memset(vis, false, sizeof(vis));
        for(int i=0; i<n; i++){
            a[i]=characters[i];
        }
        dfs(0, 0);
        reverse(ans.begin(), ans.end());
    }

    string next() {
        string t = ans[ans.size()-1];
        ans.pop_back();
        return t;
    }

    bool hasNext() {
        if(ans.size()) return true;
        else return false;
    }
};

5129. 下降路径最小和 II

  • 题意:给你一个整数方阵arr ,定义「非零偏移下降路径」为:从arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。请你返回非零偏移下降路径数字和的最小值。
  • 数据范围:
    • 1<=arr.length==arr[i].length<=2001 <= arr.length == arr[i].length <= 200
    • 99<=arr[i][j]<=99-99 <= arr[i][j] <= 99
  • 思路:简单DP,设dp[i][j]dp[i][j]表示选择第ii行第jj个数的时候获得的 非零偏移下降路径数字和的最小值,那么转移就很明显了。dp[i][j]=min(dp[i][j],dp[i1][k]+arr[i][j])dp[i][j]=min(dp[i][j], dp[i-1][k]+arr[i][j]),其中kk要和jj不相等。注意一下边界条件就可以了。
  • 复杂度:O(arr.lengtharr[0].length2)O(arr.length*arr[0].length^2)
  • 代码:
class Solution {
public:
    int dp[210][210];
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size();
        int m = arr[0].size();
        memset(dp, 0x3f, sizeof(dp));
        for(int i=0; i<m; i++){
            dp[0][i]=arr[0][i];
        }
        for(int i=1; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<m; k++){
                    if(k==j) continue;
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+arr[i][j]);
                }
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0; i<m; i++){
            ans = min(ans, dp[n-1][i]);
        }
        return ans;
    }
};
1

纪念自己第一次完赛
应该是题目太简单了吧...
原谅我太激动了。。。因为我之前的比赛顶多过两题。。。

5

第三题题意不够明晰,

ab,ac下面怎么直接就是bc,而不是ba呢?


确定是翻译的问题,题意是考虑组合再按字典序排列。

abc的组合有三个,{a,b},{b,c},{a,c},

每个都排成字典序,再比较就是ab,ac,bc.

解答时用数字更清楚。

3