Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間6月前 (2025/06/08 01:57)推噓2(2推 0噓 1→)

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