推 JIWP: 大師 06/08 01:58
→ JIWP: 我好崇拜你 06/08 01:58
推 deatheo: 大師 06/08 01:59
https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars/
3170. Lexicographically Minimum String After Removing Stars
給你一個包含*的英文字串s，你要把所有的*刪除，並且每刪除一個*就要把該*左邊最小
字典序的任意一個字母也刪除。
思路:
貪婪，每次遇到*就把左邊最小的字元刪除(有多個就刪除最右邊的，因為結果要最小)，可
以用heap記錄左邊目前最小的是哪個字元還有他的索引在哪，把要刪掉的字元標記起來，
最後合併在一起就好。
Java Code:
-------------------------------------------
class Solution {
public String clearStars(String s) {
boolean[] deleted = new boolean[s.length()];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return b[1] - a[1];
});
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '*') {
deleted[i] = true;
int[] element = pq.poll();
deleted[element[1]] = true;
} else {
pq.offer(new int[]{s.charAt(i) - 'a', i});
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!deleted[i]) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
-------------------------------------------
--
https://i.imgur.com/gEScv9s.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.104.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749319046.A.FF7.html