LeetCode第432场周赛 （前3题|多语言）
比赛链接：第432场周赛
文章目录
- 3417. 跳过交替单元格的之字形遍历
- 思路
- 代码
- C++
- Java
- Python
- 3418. 机器人可以获得的最大金币数
- 思路
- 代码
- C++
- Java
- Python
- 3419. 图的最大边权的最小值
- 思路
- 代码
- C++
- Java
- Python
- 总结
3417. 跳过交替单元格的之字形遍历
思路
没啥好说的就是模拟
按照题目要求，S形遍历数组，然后从[0][0]开始，每隔一个元素就记录一下。（以i为行遍历，j为列遍历）那么就可以得知，当i为偶数时，j就是从前往后，反之从后往前。然后我们再用一个数flag来判断遍历的该元素是否是要记录的元素。
代码
C++
class Solution {
public:
vector<int> zigzagTraversal(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<int> ret;
int num = 0;
for(int i = 0;i<n;++i){
if(i%2 == 0){
for(int j = 0;j<m;++j){
if(num%2==0){
ret.push_back(grid[i][j]);
}
num++;
}
}else{
for(int j = m-1;j>=0;--j){
if(num%2==0){
ret.push_back(grid[i][j]);
}
num++;
}
}
}
return ret;
}
};
Java
class Solution {
public List<Integer> zigzagTraversal(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
List<Integer> ret = new ArrayList<>();
int flag = 0;
for(int i = 0;i<n;++i){
if(i%2 == 0){
for(int j = 0;j<m;++j){
if(flag%2==0){
ret.add(grid[i][j]);
}else{
;
}
flag++;
}
}else{
for(int j = m-1;j>=0;--j){
if(flag%2==0){
ret.add(grid[i][j]);
}else{
;
}
flag++;
}
}
}
return ret;
}
}
Python
class Solution:
def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
ret=[]
flag = 0
for i in range(0,len(grid)):
if i%2==0:
for j in range(0,len(grid[0])):
if flag%2==0:
ret.append(grid[i][j])
else:
pass
flag+=1
else:
for j in range(len(grid[0])-1,-1,-1):
if flag%2==0:
ret.append(grid[i][j])
else:
pass
flag+=1
return ret
3418. 机器人可以获得的最大金币数
思路
通过查看题目我们可以发现，如果去掉感化这一个限制条件，那么这题不就是非常典型的动态规划了吗？我们只要创建一个二维数组就可以轻松解决了。
可是现在多了一个感化的选项，如果我们只用一个二维数组肯定是无法解决问题的，二维数组能表达的信息只有到当前位置获得的最大金币数，但是没有限制。
现在我们定义一个三维数组dp[i][j][k]表示到达(i,j)位置时，已经感化k个强盗的最大金币数
状态转移：
如果不感化强盗：dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-1][k])+coins[i][j]
如果感化强盗：dp[i][j][k] = max(dp[i-1][j][k-1],dp[i][j-1][k-1])+0
初始状态：
dp[0][0][0] = coins[0][0],如果coins[0][0]<0。那么感化dp[0][0][1] = 0
代码
C++
class Solution {
public:
int maximumAmount(vector<vector<int>>& coins) {
int n = coins.size(), m = coins[0].size();
// 定义 dp 数组，dp[i][j][k] 表示到 (i, j) 位置感化了 k 个强盗的最大金币数
vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(3, INT_MIN)));
// 初始化 dp[0][0] 的状态
dp[0][0][0] = coins[0][0];
if (coins[0][0] < 0) dp[0][0][1] = 0; // 如果起点有强盗，感化后金币为 0
// 填充 DP 表
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < 3; ++k) { // k 表示已感化强盗的数量
if (dp[i][j][k] == INT_MIN) continue; // 无效状态跳过
// 向下移动
if (i + 1 < n) {
// 不感化
dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + coins[i + 1][j]);
// 感化
if (coins[i + 1][j] < 0 && k + 1 < 3) {
dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + 0);
}
}
// 向右移动
if (j + 1 < m) {
// 不感化
dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k] + coins[i][j + 1]);
// 感化
if (coins[i][j + 1] < 0 && k + 1 < 3) {
dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + 0);
}
}
}
}
}
// 返回到达终点时的最大金币数（考虑感化 0, 1, 2 个强盗的情况）
return max({dp[n - 1][m - 1][0], dp[n - 1][m - 1][1], dp[n - 1][m - 1][2]});
}
};
Java
class Solution {
public int maximumAmount(int[][] coins) {
int n = coins.length;
int m = coins[0].length;
int dp[][][] = new int[n][m][3];
for(int i = 0;i<n;++i){
for(int j = 0;j<m;++j){
for(int k = 0;k<3;++k){
dp[i][j][k] = -0x3f3f3f3f;
}
}
}
dp[0][0][0] = coins[0][0];
if(coins[0][0]<0){
dp[0][0][1] = 0;
}
for(int i = 0;i<n;++i){
for(int j = 0;j<m;++j){
for(int k = 0;k<3;++k){
if(dp[i][j][k] == -0x3f3f3f3f){
continue;
}
if(i+1<n){
dp[i+1][j][k] = Math.max(dp[i+1][j][k],dp[i][j][k]+coins[i+1][j]);
if(coins[i+1][j]<0&&k<2){
dp[i+1][j][k+1] = Math.max(dp[i+1][j][k+1],dp[i][j][k]);
}
}
if(j+1<m){
dp[i][j+1][k] = Math.max(dp[i][j+1][k],dp[i][j][k]+coins[i][j+1]);
if(coins[i][j+1]<0&&k<2){
dp[i][j+1][k+1] = Math.max(dp[i][j+1][k+1],dp[i][j][k]);
}
}
}
}
}
return Math.max(Math.max(dp[n-1][m-1][0],dp[n-1][m-1][1]),dp[n-1][m-1][2]);
}
}
Python
class Solution:
def maximumAmount(self, coins: List[List[int]]) -> int:
n,m = len(coins),len(coins[0])
dp = [[[-float('inf')]*3 for _ in range(m)] for _ in range(n)]
dp[0][0][0] = coins[0][0]
if coins[0][0] < 0:
dp[0][0][1] = 0
for i in range(n):
for j in range(m):
for k in range(3):
if dp[i][j][k] == -float('inf'):
continue
#下移
if i+1<n:
dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]+coins[i+1][j])
if(coins[i+1][j]<0 and k<2):
dp[i+1][j][k+1] = max(dp[i+1][j][k+1],dp[i][j][k]+0)
# 右移
if j+1<m:
dp[i][j+1][k] = max(dp[i][j+1][k],dp[i][j][k]+coins[i][j+1])
if(coins[i][j+1]<0 and k<2):
dp[i][j+1][k+1] = max(dp[i][j+1][k+1],dp[i][j][k]+0)
return max(dp[i][j])
3419. 图的最大边权的最小值
本题思路来自：TsReaper
思路
题目有3个要求。
我们先看要求1：所有的节点都可以到达节点0，那么也就意味着0节点可以到达所有点，那么所有点最大有threshold的出度的限制，也反过来变成，所有点最大有threshold的入度。
了解完上面我们能发现，第3点条件好像不是很重要啊。当我们从0开始遍历，就会形成一个树，树的有向边从从父节点指向子节点。因为树上每个节点最多只有一个父节点，所以每个节点最多只有一个入度，一定满足条件3.
那么剩下的就是条件2了，看到让最大边权尽可能小（最大值最小）我们可以想到二分算法。因此我们可以使用二分算法，二分的判断判断条件就是检查是否能从0节点到达所有节点。
笔者使用的BFS遍历图。
代码
C++
class Solution {
public:
int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
auto check = [&](int lim){
vector<vector<int>> arr(n);
vector<bool> vis(n,false);
for(auto&edge:edges){
if(edge[2]<=lim){
arr[edge[1]].push_back(edge[0]);
}
}
queue<int> q;
q.push(0);
vis[0] = true;
while(!q.empty()){
int tmp = q.front();
q.pop();
for(int x:arr[tmp]){
if(vis[x]==false){
q.push(x);
vis[x] = true;
}
}
}
for(bool x:vis){
if(x == false){
return false;
}
}
return true;
};
int low = 0,high = 0;
for(auto&edge:edges){
high = max(high,edge[2]);
}
if(check(high)==false){
return -1;
}
while(low<high){
int mid = (low+high)>>1;
if(check(mid)){
high = mid;
}else{
low = mid+1;
}
}
return high;
}
};
Java
class Solution {
public int minMaxWeight(int n, int[][] edges, int threshold) {
int low = 0,high = 0;
for(int[] edge : edges){
high = Math.max(high,edge[2]);
}
if(check(n,edges,high) == false){
return -1;
}
while(low<high){
int mid = (low+high)>>1;
if(check(n,edges,mid)){
high = mid;
}else{
low = mid+1;
}
}
return high;
}
public boolean check(int n,int[][] edges,int lim){
List<List<Integer>> e = new ArrayList<>();
for(int i = 0;i<n;++i){
e.add(new ArrayList<>());
}
boolean[] vis = new boolean[n];
for(int[] edge : edges){
if(edge[2]<=lim){
e.get(edge[1]).add(edge[0]);
}
}
Queue<Integer> q = new LinkedList<>();
q.add(0);
vis[0] = true;
while(!q.isEmpty()){
int tmp = q.remove();
for(int x : e.get(tmp)){
if(vis[x] == false){
vis[x] = true;
q.add(x);
}
}
}
for(boolean x : vis){
if(x == false){
return false;
}
}
return true;
}
}
Python
from queue import Queue
class Solution:
def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
def check(lim: int):
e = [[] for _ in range(n)]
for edge in edges:
if(edge[2]<=lim):
e[edge[1]].append(edge[0])
vis = [False]*n
q = Queue()
q.put(0)
vis[0] = True
while(not q.empty()):
tmp = q.get()
for x in e[tmp]:
if vis[x] == False:
vis[x] = True
q.put(x)
for x in vis:
if x == False:
return False
return True
low,high = 0,0
for edge in edges:
high = max(high,edge[2])
if check(high) == False:
return -1
while low<high:
mid = (low+high)>>1
if check(mid):
high = mid
else:
low = mid+1
return high
总结
好久没打力扣的周赛了，以后的力扣的周赛，我尽量都参加吧。
本系列主要记录我的刷题历程