229周赛&&46双周赛好题分享

双周赛是在国际服打的,A了三题,第四题对我而言有点难。周赛没打,之后补了一下题,不难,前两题送分,后两题是两个区间dp,第三题用python的lru_cache也能过,但是用dp的话状态方程不太好想(对我而言),反倒是第四题的很好想。

1765. 地图中的最高点

这个题蛮有意思,刚开始没想到用多源bfs,想的是一个点一个点去试着加,结果T了,很明显就是从水开始BFS,每一层可以+1,知道走完所有,典型的多源头BFS。

class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m , n = len(isWater) , len(isWater[0])
for i in range(m):
for j in range(n):
isWater[i][j] = isWater[i][j] ^ 1
direct = [(-1,0),(1,0),(0,-1),(0,1)]

queue = []
visit = set()
for i in range(m):
for j in range(n):
if isWater[i][j] == 0:
queue.append((i,j))
visit.add((i,j))
hh = 1
while len(queue) > 0:
sz = len(queue)
for _ in range(sz):
i , j = queue[0]
queue.pop(0)
for k in range(4):
x = i + direct[k][0]
y = j + direct[k][1]
if x>=0 and x < m and y >= 0 and y < n and (x,y) not in visit:
queue.append((x,y))
visit.add((x,y))
isWater[x][y] = hh
hh += 1
return isWater

1766. 互质树

这个题对我来说,一下不太好想思路,思路大概是题中给了提醒,值的范围不超过50,所以我们每次对这颗树中相同的数字统一处理,就是从根进行dfs,在互质的时候,记录上一个节点即可。

const int M = 1e5 + 10;
vector<int> adj[M];
bool coprime[55][55];
int ans[M];
class Solution {
public:
void dfs(int x, int fa, int cur, int prev, vector<int>& nums){ // x:当前节点编号,prev:上个节点的编号
if (nums[x] == cur) ans[x] = prev; // 找到值为i的的节点
if (coprime[nums[x]][cur]) prev = x; // 和cur互质 记录上一个
for (int v: adj[x]){
if (v == fa) continue;
dfs(v, x, cur, prev, nums);
}
}
vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
for(int i = 1;i <= 50;i++){
for(int j = 1;j <= 50;j++){
coprime[i][j] = (gcd(i,j)==1);
}
}
for (int i = 0; i < n; i++) adj[i].clear(), ans[i] = -1;
for(auto e : edges){
int a = e[0] , b = e[1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 1;i <= 50;i++) dfs(0, -1, i, -1, nums);
vector<int> ret;
for (int i = 0; i < n; i++) ret.push_back(ans[i]);
return ret;
}
};

1770. 执行乘法运算的最大分数

这个题用python写,backtrack来做很简单,然后使用lru_cache可以降低一下复杂度,就能过,代码如下:

class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
m , n = len(nums) , len(multipliers)
@lru_cache(None)
def dfs(i,j,cur):
if i > j or cur >= n:
return 0
a = dfs(i+1,j,cur+1) + nums[i]* multipliers[cur]
b = dfs(i,j-1,cur+1) + nums[j] * multipliers[cur]
return max(a,b)
res = dfs(0,m-1,0)
dfs.cache_clear()#niu
return res

但是这个题更优的做法是使用dp

状态:$dp[i][j]$ 表示,左侧去掉i个,右侧去掉j个可以得到的最大值,那么最终的结果一定是$i+j=m$ 中所有$dp[i][j]$的最大值

转移:$dp[i][j] = max(dp[i][j],dp[i-1][j] + nums[i] *mul[l-1]) $

$dp[i][j] = max(dp[i-1][j],dp[i][j]) + nums[i] *mul[l-1] $

其中$l$表示的是区间的长度,也就是去掉的总长度,要保证$i+j=l$

class Solution {
public:
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int m = multipliers.size() , n = nums.size();
vector<vector<int>> dp (m+1,vector<int>(m+1,INT_MIN));
dp[0][0] = 0; //左边取i个 右边取j个
for(int l = 1; l <= m;l++){ // 长度
for(int i = 0;i <= l;i++){
int j = l-i;
if(i > 0) dp[i][j] = max(dp[i][j],dp[i-1][j] + nums[i-1]*multipliers[l-1]);
if(j > 0) dp[i][j] = max(dp[i][j],dp[i][j-1] + nums[n-j] *multipliers[l-1] );
}
}
int ans = -1e9;
for (int i = 0; i <= m; ++i) {
ans = max(ans, dp[i][m - i]);
}
return ans;

}
};

1771. 由子序列构造的最长回文串的长度

这个题比上一个题的dp要好想一些,但是前提要想到先将字符串进行拼接,拼接之后就是516. 最长回文子序列 的裸题,但是因为会问串不能出现在单一的字符串中,所以在更新结果的时候,需要判断端点是否在同一个字符串上:

最长回文子序列的dp

状态:$dp[i][j]$表示字符串i,j的最长子序列的长度

转移:$dp[i][j] = dp[i+1][j-1]+2$ if s[i]==s[j]

else

$dp[i][j] = max(dp[i+1][j],dp[i][j-1])$

const int maxn = 2000+5;
int dp[maxn][maxn];
class Solution {
public:
int longestPalindrome(string word1, string word2) {
string word = word1 + word2;
int n1 = word1.size(), n2 = word2.size();
memset(dp,0,sizeof dp);
int ans = 0;
for(int i = 0;i < word.size();i++) dp[i][i] = 1;
for(int i = word.size()-1;i >=0;i--){
for(int j =i+1; j<word.size();j++){
if(word[i] == word[j]){
dp[i][j] = dp[i+1][j-1]+2;
if(i < n1 && j >= n1) ans = max(ans,dp[i][j]);
}
else
dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
return ans;
}
};