题目列表
一、交换后字典序最小的字符串
这题读懂题目要求就行，关键在于字典序的理解，由于只能交换一次，肯定是优先改变靠前的字符顺序，才能让字典序变得最小，代码如下
class Solution {
public:
string getSmallestString(string s) {
int n = s.size();
for(int i = 1; i < n; i++){
if(s[i]%2 == s[i-1]%2 && s[i] < s[i-1]){
swap(s[i], s[i-1]);
return s;
}
}
return s;
}
};二、从链表中移除在数组中出现的结点
考察链表的增删查改，基本数据结构，没啥可说的，代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
ListNode *newhead = nullptr, *tail = nullptr, *cur = head;
unordered_set<int> st(nums.begin(), nums.end());
while(cur) {
if(st.count(cur->val) == 0) {
if(newhead == nullptr) {
newhead = tail = cur;
} else {
tail = tail->next = cur;
}
}
cur = cur->next;
}
if(tail) tail->next = nullptr;
return newhead;
}
};三、切蛋糕的最小总开销 I & II
这题其实很适合用分治来写，一块蛋糕切一次，分成两块蛋糕，在分别对这两个蛋糕进行切分，很标准将一个问题划分成两个更小规模的重复子问题，代码如下
class Solution {
public:
int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
int a = horizontalCut.size(), b = verticalCut.size();
int memo[a+1][a+1][b+1][b+1];
memset(memo,-1,sizeof(memo));
function<int(int,int,int,int)>dfs=[&](int up,int down,int left,int right)->int{
if(up == down && left == right) return 0;
if(memo[up][down][left][right]!=-1) return memo[up][down][left][right];
int res = INT_MAX;
for(int i = up; i < down; i++){ // 枚举切割哪一行
res = min(res, dfs(up,i,left,right) + dfs(i+1,down,left,right) + horizontalCut[i]);
}
for(int i = left; i < right; i++){ // 枚举切割哪一列
res = min(res, dfs(up,down,left,i) + dfs(up,down,i+1,right) + verticalCut[i]);
}
return memo[up][down][left][right] = res;
};
return dfs(0,a,0,b);
}
};但是数据范围增大之后，这样做就会超时，这里我们就需要去考虑贪心了。
如何贪心？我们模拟一下切蛋糕的过程，能得出下面几个结论：
- 1、无论如何切，切的次数总是相同的，因为每次切都只会增加一个独立的蛋糕，一开始只有一块，分出的块数固定为m*n，故一共要切m*n - 1刀
- 2、切的顺序不同，总能被化简为，每次切都是将某一行/某一列全部切完才算结束的情况，如下图
- 3、每次横切一刀之后，下次的竖切次数就会+1，同理每次竖切一刀之后，下次的横切次数就会+1，因为横切之后，原本一块蛋糕就成了两块蛋糕，故竖切一刀也就变成了两刀，竖切同理，如下图
- 4、由3可知：竖切不会影响竖切，横切也不会影响横切，所以我们只要考虑竖切和横切哪个先就行
代码如下
class Solution {
public:
long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
long long ans = 0;
ranges::sort(horizontalCut);
ranges::sort(verticalCut);
int h = 1, v = 1;
int i = horizontalCut.size()-1, j = verticalCut.size()-1;
while(i>=0 || j>=0) {
if(i < 0){
int y = verticalCut[j];
ans += 1LL*v*y;
j--;
}else if(j < 0){
int x = horizontalCut[i];
ans += 1LL*h*x;
i--;
}else{
int x = horizontalCut[i];
int y = verticalCut[j];
if(x > y){
ans += 1LL*x*h;
v++, i--;
}else{
ans += 1LL*v*y;
h++, j--;
}
}
}
return ans;
}
};
