上岸算法LeetCode Weekly Contest 263解题报告 leetcode算法刷题

【 NO.1 检查句子中的数字是否递增】
解题思路
签到题。
【上岸算法LeetCode Weekly Contest 263解题报告】代码展示
class Solution {
public boolean areNumbersAscending(String s) {

var strList = s.split(" "); int last = -1; for (var str : strList) { try { int num = Integer.parseInt(str); if (num <= last) { return false; } last = num; } catch (NumberFormatException ignored) { } } return true;

}
}
【 NO.2 简易银行系统】
解题思路
约等于签到题。如果题目说明 “可能多个人同时操作” 还好一些，那就需要加锁了。
代码展示
class Bank {
long[] balance;
public Bank(long[] balance) {

this.balance = balance;

}
public boolean transfer(int account1, int account2, long money) {

account1--; account2--; if (account1 >= balance.length || account2 >= balance.length || balance[account1] < money) { return false; } balance[account1] -= money; balance[account2] += money; return true;

}
public boolean deposit(int account, long money) {

account--; if (account >= balance.length) { return false; } balance[account] += money; return true;

}
public boolean withdraw(int account, long money) {

account--; if (account >= balance.length || balance[account] < money) { return false; } balance[account] -= money; return true;

}
}
【 NO.3 统计按位或能得到最大值的子集数目】
解题思路
数据范围很小，枚举所有子集即可。
代码展示
class Solution {
public int countMaxOrSubsets(int[] nums) {

int max = 0; for (int num : nums) { max |= num; } int res = 0; for (int i = 1; i < (1 << nums.length); i++) { int or = 0; for (int j = 0; j < nums.length; j++) { if (((1 << j) & i) != 0) { or |= nums[j]; } } res += or == max ? 1 : 0; } return res;

}
}
【 NO.4 到达目的地的第二短时间】
解题思路
Dijkstra 求次短路即可。需要额外处理的就是红绿灯的转换，下述代码中，将等红灯的时间算做到达这个点的时间，比如从 A 走到点 B 后需要在点 B 等红灯 x 分钟，那么就相当于 A 到 B 的路径长为 time + x 分钟。
代码展示
class Solution {
static class Node implements Comparable {

int min; int idx; public Node(int min, int idx) { this.min = min; this.idx = idx; }@Override public int compareTo(Node o) { return min - o.min; }

}
public int secondMinimum(int n, int[][] edges, int time, int change) {

List> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (var e : edges) { graph.get(e[0] - 1).add(e[1] - 1); graph.get(e[1] - 1).add(e[0] - 1); }int result = 0; // 最终答案 int[][] min = new int[2][n]; // min[0] 最短路；min[1] 次短路 (min 数组包含等待时间) Arrays.fill(min[0], 0x3f3f3f3f); Arrays.fill(min[1], 0x3f3f3f3f); min[0][0] = 0; PriorityQueue heap = new PriorityQueue<>(); heap.add(new Node(0, 0)); while (!heap.isEmpty()) { Node node = heap.poll(); if (min[1][node.idx] < node.min) { continue; } for (int nxt : graph.get(node.idx)) { int nxtMin = node.min + time; nxtMin += waitRedLight(nxtMin, change); if (nxtMin < min[0][nxt]) { int tmp = nxtMin; nxtMin = min[0][nxt]; min[0][nxt] = tmp; heap.add(new Node(min[0][nxt], nxt)); } if (nxtMin < min[1][nxt] && min[0][nxt] < nxtMin) { if (nxt == n - 1) { result = node.min + time; } min[1][nxt] = nxtMin; heap.add(new Node(min[1][nxt], nxt)); } } } return result;

}
private int waitRedLight(int now, int change) {