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;
}
};