OA2025-12-19
UB coding final list
UB coding
Problem
- [⚠️] Leetcode 5. Longest Palindromic Substring
- [✅] Leetcode 14. Longest Common Prefix
- [✅] Leetcode 53. Maximum Subarray DP
- [‼️] Leetcode 79. Word Search DFS
- [ ] Leetcode 127. Word Ladder
- [✅] Leetcode 146. LRU Cache double linked list + MAP
- [✅] Leetcode 200. Number of Islands
- [✅] Leetcode 204. Count Primes
- [✅] Leetcode 207. Course Schedule
- [‼️] Leetcode 212. Word Search II Trie + DFS
- [‼️] Leetcode 214. Shortest Palindrome manacher / KMP
- [‼️] Leetcode 230. Kth Smallest Element in a BST 中序遍历
- [✅] Leetcode 239. Sliding Window Maximum 单调队列
- [‼️] Leetcode 247. Strobogrammatic Number II
- [✅] Leetcode 253. Meeting Rooms II 时间排序+heap
- [‼️] Leetcode 269. Alien Dictionary
class Solution { public String alienOrder(String[] words) { List<Integer>[] graph = new ArrayList[26]; Arrays.setAll(graph, _ -> new ArrayList<>()); int n = words.length; int[] indegree = new int[26]; Set<Integer> met = new HashSet<>(); // ***** 提前把所有的字符加入集合，别在后边处理了, 也可以用boolean array来 for (String w : words) { for (char c : w.toCharArray()) { met.add(c - 'a'); } } for (int i = 0; i < n - 1; i++) { String cur = words[i]; String next = words[i + 1]; int minLen = Math.min(cur.length(), next.length()); boolean find = false; for (int j = 0; j < minLen; j++) { int from = cur.charAt(j) - 'a'; int to = next.charAt(j) - 'a'; if (cur.charAt(j) != next.charAt(j)) { find = true; indegree[to]++; graph[from].add(to); // ********* 终止 break; } } if (!find && cur.length() > next.length()) return ""; } Deque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < 26; i++) { if (indegree[i] == 0 && met.contains(i)) { queue.offerLast(i); } } StringBuilder sb = new StringBuilder(); while (!queue.isEmpty()) { int cur = queue.pollFirst(); sb.append((char) (cur + 'a')); for (int next : graph[cur]) { if (--indegree[next] == 0) { queue.offerLast(next); } } } if (sb.length() != met.size()) return ""; return sb.toString(); } }