226周赛好题分享

本场周赛依旧只a了两题,发现题不难,只是自己思维和处理细节的能力有点差。。。

5665. 从相邻元素对还原数组

这个题有个很重要的辅助条件,就是,关系数组的长度比数组长度小1,将数组看场一个图,数组中相邻的点存在边,那么度为0的点,就是数组的头或者尾,所以我们只要找到数组的头或者尾巴,就可以使用dfs恢复数组了,我们需要把边的关系进行保存

class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
n = len(adjacentPairs)
res = [0] * (n+1)
mp = {}
for a , b in adjacentPairs:
mp[a] = mp.get(a,0)+1
mp[b] = mp.get(b,0)+1
hh = []
for k ,v in mp.items():
if v == 1:
hh.append(k)
res[0] = hh[0]
res[-1] = hh[1]
c = collections.defaultdict(list)
for a ,b in adjacentPairs:
c[a].append(b)
c[b].append(a)
used = set()
used.add(res[0])
def dfs(cur,pos):
data = c[cur]
for d in data:
if d not in used:
res[pos] = d
used.add(d)
pos += 1
dfs(d,pos)
dfs(res[0],1)
return res

5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗?

这题没啥好说的前缀和,但是条件的处理太过于细节。够吃和不够吃的边界需要想的很清楚,我们事先算出,在这一天之前(包括这一天)可以吃到的最多最少的糖果,然后看前t种糖果的数量的关系。

class Solution {
public:
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int n = candiesCount.size();
vector<long long> sum(n + 1);
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + candiesCount[i];
}

vector<bool> ret;
for (auto &i : queries) {
long long max = (long long)(i[1]+1) * i[2]; // 算上今天能吃到最多的
long long min = i[1] + 1; // 算上今天 能吃的最少的
//最多的吃法,可以吃完前t种 有剩余 可以用来吃第t种
//最少的吃法,保证前t种(包括t)还有的吃
if (max > sum[i[0]] && min <= sum[i[0] + 1]) ret.push_back(true);
else ret.push_back(false);
}

return ret;
}
};

5666. 回文串分割 IV

这个题是一个原题,直接代码复用改个参数就好。原题在:1278. 分割回文串 III

class Solution {
public:
bool checkPartitioning(string s) {
return palindromePartition( s, 3) == 0;
}
int cost(string& s, int l, int r) {
int ret = 0;
for (int i = l, j = r; i < j; ++i, --j) {
if (s[i] != s[j]) {
++ret;
}
}
return ret;
}

int palindromePartition(string& s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n));
for (int span = 2; span <= n; ++span) {
for (int i = 0; i <= n - span; ++i) {
int j = i + span - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
}
}

vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(k, i); ++j) {
if (j == 1) {
f[i][j] = cost[0][i - 1];
}
else {
for (int i0 = j - 1; i0 < i; ++i0) {
f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0][i - 1]);
}
}
}
}

return f[n][k];
}

};

标准题解:

const int maxn = 2010;
bool dp[maxn][maxn];

class Solution {
public:
bool checkPartitioning(string s) {
memset(dp, 0, sizeof(dp));
int n = s.length();
for(int i = 0; i < n; i++){
dp[i][i] = 1;
if(i < n - 1){
if(s[i]==s[i+1])dp[i][i+1] = 1;
}
}
for(int L = 3; L <= n; L++){
for(int i = 0; i + L - 1 < n; i++){
int j = i + L - 1;
if(s[i]==s[j] && dp[i+1][j-1]){
dp[i][j] = 1;
}
}
}
for(int s = 1; s <= n - 2; s++)
for(int e = s; e <= n - 2; e++)
if(dp[0][s-1]&&dp[s][e]&&dp[e+1][n-1])
return true;
return false;
}
};