$\large\color{orange}{比赛入口:}$$ \color{orange}{LeetCode346} $$ \large\color{orange}{周赛} $
两道easy,都挺简单!一道暴搜(DFS+回溯)能过;最后一题hard,写了一小时,没写出来!
$\large\color{green}{6439. 删除子串后的字符串最小长度}$
模拟,时间复杂度:$O(n^{2}) \Rightarrow 10^{4}$
class Solution {
public:
int minLength(string s) {
while(true){
int n = s.size();
string tmp = "";
for(int i = 0; i < n; i ++ ){
if(i + 1 < n){
string u = "";
u += s[i], u += s[i + 1];
if(u == "AB" || u == "CD") i ++ ;
else tmp += s[i];
}else tmp += s[i];
}
if(tmp == s) break;
s = tmp;
}
return s.size();
}
};
$\large\color{green}{6454. 字典序最小回文串}$
字符串操作,时间复杂度:$O(n) \Rightarrow 10^{3}$
class Solution {
public:
string makeSmallestPalindrome(string s) {
int n = s.size();
for(int i = 0; i < n / 2; i ++ ){
s[i] = min(s[i], s[n - 1 - i]);
s[n - 1 - i] = s[i];
}
return s;
}
};
$\large\color{orange}{6441. 求一个整数的惩罚数}$
DFS,时间复杂度:$O(2^{8} n) \Rightarrow 10^{5}$
class Solution {
public:
vector<int> tp;
int len;
bool flag;
void dfs(int index, int cur, int sum, int aim){
if(flag) return ;
if(index == len){
if(cur + sum == aim) flag = true;
return ;
}
dfs(index + 1, 0, sum + cur * 10 + tp[index], aim);
dfs(index + 1, cur * 10 + tp[index], sum, aim);
}
bool check(int x){
int t = x * x;
tp = vector<int>();
while(t){
tp.push_back(t % 10);
t /= 10;
}
reverse(tp.begin(), tp.end());
len = tp.size();
flag = false;
dfs(0, 0, 0, x);
return flag;
}
int punishmentNumber(int n) {
int sum = 0;
for(int i = 1; i <= n; i ++ ){
if(check(i)) sum += i * i;
}
return sum;
}
};
$\large\color{red}{6442. 修改图中的边权}$
dijkstra + 贪心,时间复杂度:$O(n^{4})) \Rightarrow 10^{7}$
class Solution {
public:
static const int N = 110, INF = 2 * 1E9;
int graph[N][N], dist[N];
bool st[N];
typedef pair<int, int> pii;
void dijkstra(int n, int source, int destination){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[source] = 0;
for(int i = 0; i < n; i ++ ){
int t = -1;
for(int j = 0; j < n; j ++ ){
if((t == -1 || dist[j] < dist[t]) && !st[j]) t = j;
}
st[t] = true;
for(int j = 0; j < n; j ++ ){
dist[j] = min(dist[j], dist[t] + graph[t][j]);
}
}
}
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
memset(graph, 0x3f, sizeof graph);
for(auto &edge : edges){
if(edge[2] > 0){
graph[edge[0]][edge[1]] = edge[2];
graph[edge[1]][edge[0]] = edge[2];
}
}
dijkstra(n, source, destination);
if(dist[destination] < target) return {};
else if(dist[destination] == target){
for(auto &edge : edges){
if(edge[2] < 0) edge[2] = 2e9;
}
return edges;
}
int len = edges.size();
int j = 0;
bool flag = false;
while(j < len){
auto edge = edges[j];
if(edge[2] < 0){
graph[edge[0]][edge[1]] = 1;
graph[edge[1]][edge[0]] = 1;
edges[j][2] = 1;
dijkstra(n, source, destination);
if(dist[destination] <= target){
edges[j][2] = target - dist[destination] + 1;
flag = true;
}
}
j ++ ;
if(flag) break;
}
if(!flag) return {};
while(j < len){
if(edges[j][2] < 0) edges[j][2] = 2e9;
j ++ ;
}
return edges;
}
};