上岸算法LeetCode Weekly Contest 263解题报告
【 NO.1 检查句子中的数字是否递增】解题思路
签到题。
代码展示
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 < money) {
return false;
}
balance -= money;
balance += money;
return true;
}
public boolean deposit(int account, long money) {
account--;
if (account >= balance.length) {
return false;
}
balance += money;
return true;
}
public boolean withdraw(int account, long money) {
account--;
if (account >= balance.length || balance < money) {
return false;
}
balance -= 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;
}
}
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<Node> {
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<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (var e : edges) {
graph.get(e - 1).add(e - 1);
graph.get(e - 1).add(e - 1);
}
int result = 0; // 最终答案
int[][] min = new int; // min 最短路；min 次短路 (min 数组包含等待时间)
Arrays.fill(min, 0x3f3f3f3f);
Arrays.fill(min, 0x3f3f3f3f);
min = 0;
PriorityQueue<Node> heap = new PriorityQueue<>();
heap.add(new Node(0, 0));
while (!heap.isEmpty()) {
Node node = heap.poll();
if (min < node.min) {
continue;
}
for (int nxt : graph.get(node.idx)) {
int nxtMin = node.min + time;
nxtMin += waitRedLight(nxtMin, change);
if (nxtMin < min) {
int tmp = nxtMin;
nxtMin = min;
min = tmp;
heap.add(new Node(min, nxt));
}
if (nxtMin < min && min < nxtMin) {
if (nxt == n - 1) {
result = node.min + time;
}
min = nxtMin;
heap.add(new Node(min, nxt));
}
}
}
return result;
}
private int waitRedLight(int now, int change) {
if ((now / change) % 2 == 0) {
return 0;
}
return change - (now % change);
}
}
页:
[1]