image-20210829114205849

5854. 学生分数的最小差值

排序之后 遍历一遍每个大小为k的区间， 然后计算下就好

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int ans = nums[nums.size()-1] - nums[0];
        for(int i=k-1; i<nums.size(); i++) {
            ans = min(ans, nums[i]-nums[i-k+1]);
        }
        
        return ans;
    }
};

5855. 找出数组中的第 K 大整数

还是排序， 注意字符串比较和整数不同，需要补上前导0. 最后别忘了把前导0去掉。

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:
    string kthLargestNumber(vector<string>& nums, int k) {
        
        int mx = 1;
        for(auto a: nums) {
            mx = max(mx, int(a.size()));
        }
        
        for(int i=0; i<nums.size(); i++) {
            string &a = nums[i];
            while(a.size() < mx) {
                a = "0" + a;
            }
        }
        
        sort(nums.begin(), nums.end());
        
        string ans = nums[nums.size()-k];
        
        int p = 0;
        for(p=0; p<ans.size() && ans[p]=='0'; p++) {
            
        }
        
        ans = ans.substr(p, ans.size()-p);
        
        return (ans.empty()?"0":ans);
    }
};

5856. 完成任务的最少工作时间段

经典状压dp

dp[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
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size();
        
        vector<int> dp(1<<n), cost(1<<n);
        
        int t = 1<<n;
        for(int i=1, sum; i < t; i++) {
            dp[i] = 100000000;
            
            sum = 0;
            for(int j=0; j<n; j++) {
                if(i>>j&1) {
                    sum += tasks[j];
                }
            }
            cost[i] = sum;
        }
        

        dp[0] = cost[0] = 0;
        for(int i=1; i < t; i++) {
            for(int j=i; j; j = (j-1)&i) {
                if(cost[j] <= sessionTime) {
                    dp[i] = min(dp[i], 
                                dp[i^j] + 1);
                }
            }
        }
        
        return dp[t-1];
        
    }
};

5857. 不同的好子序列数目

类似940. 不同的子序列 II， 针对0特殊处理下就好了。

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
class Solution {
public:
    static const int MOD = 1e9+7;
    
    int numberOfUniqueGoodSubsequences(string s) {
        int n = s.length();
        
        int ans = 0;
        for(auto c: s) {
            if (c == '0') {
                ans = 1;
            }
        }
        
        vector<int> dp(n+1);
        vector<int> last(2, -1);
        
        dp[0] = 1;
        for(int i=0; i<n; i++) {
            int x = s[i] - '0';
            if(x == 1) {
                dp[i+1] = dp[i] * 2 % MOD;
                if (last[x] >= 0) {
                    dp[i+1] = (dp[i+1] - dp[last[x]]+MOD) % MOD;
                }
            } else { // if(x == 0)
                dp[i+1] = (dp[i]*2-1) %MOD;
                if (last[x] >= 0) {
                    dp[i+1] = (dp[i+1] - dp[last[x]] + 1+MOD) % MOD;
                }
            }
            last[x] = i;
        }
        
        return (dp[n]+ans-1)%MOD;
    }
};