Re: [閒聊] 每日leetcode
https://leetcode.com/problems/robot-collisions/
2751. Robot Collisions
給你三個長度一樣的陣列positions, healths, directions，分別表示機器人的座標、
生命、行走方向，機器人同時開始行走，如果不同方向的機器人碰到了，分成兩情況：
1.其中一個機器人生命較高，生命較低的機器人hp變0，生命較高的機器人生命減一
2.機器人生命一樣，兩個hp一起變0
返回剩餘hp大於0的機器人生命值陣列，並且按照原始輸入的順序。
Example:
https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.png
Input: positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
Output: [14]
Explanation: There are 2 collisions in this example. Firstly, robot 1 and
robot 2 will collide, and since both have the same health, they will be
removed from the line. Next, robot 3 and robot 4 will collide and since robot
4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 =
14. Only robot 3 remains, so we return [14].
思路：
1.首先，因為positions不是一定照順序，所以我們先把他排序，從左到右處理。
2.使用一個stack儲存往右的機器人編號，如果下次遇到往左的機器人就一直相撞
直到其中一個方向的機器人生命為0。
3.遍歷healths陣列，按照順序把生命大於0的值存起來就好。
java code:
----------------------------------------------------------------
class Solution {
public List<Integer> survivedRobotsHealths(int[] positions, int[]
healths, String directions) {
int n = positions.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = i;
}
Arrays.sort(order, (a, b) -> positions[a] - positions[b]);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int a = order[i];
if (directions.charAt(a) == 'R') {
stack.add(a);
continue;
}
while (!stack.isEmpty() && healths[a] != 0) {
int b = stack.peekLast();
if (healths[a] == healths[b]) {
stack.pollLast();
healths[a] = 0;
healths[b] = 0;
} else if (healths[a] > healths[b]) {
stack.pollLast();
healths[a]--;
healths[b] = 0;
} else {
healths[a] = 0;
healths[b]--;
}
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (healths[i] != 0) {
res.add(healths[i]);
}
}
return res;
}
}
----------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720839425.A.9BB.html
※ 編輯: Rushia (122.100.73.13 臺灣), 07/13/2024 10:57:43
→
07/13 10:57,
1年前
, 1F
07/13 10:57, 1F
→
07/13 11:00,
1年前
, 2F
07/13 11:00, 2F
推
07/13 11:13,
1年前
, 3F
07/13 11:13, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 484 之 1552 篇)：