OA2025-12-19
UB coding hello interview
Problem
- [‼️] Leetcode 269. Alien Dictionary
class Solution { public String alienOrder(String[] words) { Set<Integer>[] graph = new HashSet[26]; Arrays.setAll(graph, _ -> new HashSet<>()); int[] indegree = new int[26]; boolean[] present = new boolean[26]; // 1) 统计出现过的字符 for (String w : words) { for (int i = 0; i < w.length(); i++) { present[w.charAt(i) - 'a'] = true; } } // 2) 只比较相邻单词，构建有向边 for (int i = 0; i < words.length - 1; i++) { String l = words[i]; String r = words[i + 1]; int minLen = Math.min(l.length(), r.length()); boolean foundDiff = false; for (int k = 0; k < minLen; k++) { if (l.charAt(k) != r.charAt(k)) { int x = l.charAt(k) - 'a'; int y = r.charAt(k) - 'a'; // 只在第一次加这条边时才增加入度（避免重复计数） if (graph[x].add(y)) { indegree[y]++; } foundDiff = true; break; } } // 前缀非法：比如 "abc" 在 "ab" 前面 if (!foundDiff && l.length() > r.length()) return ""; } // 3) 拓扑排序（只处理出现过的字符） Deque<Integer> queue = new ArrayDeque<>(); int total = 0; for (int i = 0; i < 26; i++) { if (present[i]) { total++; if (indegree[i] == 0) queue.offerLast(i); } } StringBuilder sb = new StringBuilder(); while (!queue.isEmpty()) { int cur = queue.pollFirst(); sb.append((char) (cur + 'a')); for (int nxt : graph[cur]) { if (--indegree[nxt] == 0) { queue.offerLast(nxt); } } } // 没有输出完所有出现过的字符 => 有环/不合法 return sb.length() == total ? sb.toString() : ""; } }
- [‼️] Leetcode 247. Strobogrammatic Number II
class Solution { private static final char[][] PAIRS = { {'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'} }; public List<String> findStrobogrammatic(int n) { return build(n, n); } private List<String> build(int n, int totalLen) { if (n == 0) return List.of(""); if (n == 1) return List.of("0", "1", "8"); List<String> res = new ArrayList<>(); for (String mid : build(n - 2, totalLen)) { for (char[] p : PAIRS) { // 最外层不能用 0 if (n == totalLen && p[0] == '0') continue; res.add(p[0] + mid + p[1]); } } return res; } }
- [‼️] Leetcode 384. Shuffle an Array
public int[] shuffle() { int[] res = nums.clone(); Random rd = new Random(); for (int i = res.length - 1; i > 0; i--) { int j = rd.nextInt(i + 1); int tmp = res[i]; res[i] = res[j]; res[j] = tmp; } return res; }
- [‼️] Leetcode 305. Number of Islands II
class Solution { int[] father; int size; public void build(int m, int n) { father = new int[m * n]; for (int i = 0; i < m * n; i++) { father[i] = i; } size = 0; } public int find(int x) { int root = x; while (root != father[root]) { root = father[root]; } while (x != father[x]) { int tmp = father[x]; father[x] = root; x = tmp; } return root; } public void union(int x, int y) { int fx = find(x); int fy = find(y); if (fx != fy) { father[fx] = father[fy]; size--; } } public List<Integer> numIslands2(int m, int n, int[][] positions) { int[][] map = new int[m][n]; build(m, n); int[] xes = new int[] {0, 0, -1, 1}; int[] yes = new int[] {-1, 1, 0, 0}; List<Integer> ans = new ArrayList<>(); for (int[] point : positions) { int x = point[0]; int y = point[1]; if (map[x][y] == 1) { ans.add(size); continue; } map[x][y] = 1; size++; for (int i = 0; i < 4; i++) { int nx = x + xes[i]; int ny = y + yes[i]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == 1) { int a = x * n + y; int b = nx * n + ny; union(a, b); } } ans.add(size); } return ans; } }
- [‼️] Leetcode 2402. Meeting Rooms III 用两个heap存free和busy
class Solution { public int mostBooked(int n, int[][] meetings) { int[] cnt = new int[n]; PriorityQueue<Integer> freeRoom = new PriorityQueue<>(); for (int i = 0; i < n; i++) { freeRoom.offer(i); } PriorityQueue<long[]> busyRoom = new PriorityQueue<>((long[] o1, long[] o2) -> { if (o1[1] == o2[1]) { return Long.compare(o1[0], o2[0]); } return Long.compare(o1[1], o2[1]); }); Arrays.sort(meetings, (o1, o2) -> o1[0] - o2[0]); for (int i = 0; i < meetings.length; i++) { int[] cur = meetings[i]; int start = cur[0]; int end = cur[1]; while (!busyRoom.isEmpty() && (int) busyRoom.peek()[1] <= start) { int room = (int) busyRoom.poll()[0]; freeRoom.offer(room); } if (!freeRoom.isEmpty()) { int room = freeRoom.poll(); busyRoom.offer(new long[] {room, end}); cnt[room]++; } else { long[] top = busyRoom.poll(); // 最早结束 int room = (int) top[0]; long newEnd = top[1] + (end - start); busyRoom.offer(new long[]{room, newEnd}); cnt[room]++; } } // int ans = 0; int mx = 0; for (int i = 0; i < n; i++) { mx = Math.max(mx, cnt[i]); } for (int i = 0; i < n; i++) { if (cnt[i] == mx) return i; } return -1; } }
- [‼️] Leetcode 815. Bus Routes 对bus和route同时记录visit
class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { List<Integer>[] stopToRoutes = new ArrayList[1000000]; Arrays.setAll(stopToRoutes, _ -> new ArrayList<>()); for (int i = 0; i < routes.length; i++) { for (int j = 0; j < routes[i].length; j++) { stopToRoutes[routes[i][j]].add(i); } } Deque<int[]> queue = new ArrayDeque<>(); boolean[] visit = new boolean[1000000]; queue.offerLast(new int[] {source, 0}); visit[source] = true; while (!queue.isEmpty()) { int[] cur = queue.pollFirst(); if (cur[0] == target) { return cur[1]; } for (int route : stopToRoutes[cur[0]]) { if (routes[route] == null) continue; for (int stop : routes[route]) { if (visit[stop]) continue; visit[stop] = true; queue.offerLast(new int[] {stop, cur[1] + 1}); } routes[route] = null; } } return -1; } }
- [‼️] Leetcode 427. Construct Quad Tree 二维前缀和求面积
class Solution { int[][] pre; public void build(int[][] grid) { int n = grid.length; pre = new int[n + 1][n + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + grid[i][j]; } } } public Node construct(int[][] grid) { build(grid); int n = grid.length; return buildTree(0, 0, n - 1, n - 1); } public Node buildTree(int a, int b, int c, int d) { // 暴力搜索 // if (rowStart > rowEnd || colStart > colEnd) { // return null; // } // boolean isLeaf = true; // int val = grid[rowStart][colStart]; // for (int i = rowStart; i <= rowEnd; i++) { // for (int j = colStart; j <= colEnd; j++) { // if (grid[i][j] != val) { // isLeaf = false; // break; // } // } // } // if (isLeaf) { // return new Node(val == 1, true, null, null, null, null); // } int area = pre[c + 1][d + 1] - pre[a][d + 1] - pre[c + 1][b] + pre[a][b]; int len = c - a + 1; if (area == 0 || area == len * len) { return new Node(area == len * len, true); } Node root = new Node(); root.isLeaf = false; int midRow = (a + c) / 2; int midCol = (b + d) / 2; root.topLeft = buildTree(a, b, midRow, midCol); root.topRight = buildTree(a, midCol + 1, midRow, d); root.bottomLeft = buildTree(midRow + 1, b, c, midCol); root.bottomRight = buildTree(midRow + 1, midCol + 1, c, d); return root; } }
- [‼️] Leetcode 564. Find the Closest Palindrome
class Solution { private long minD = Long.MAX_VALUE; private long ans; public String nearestPalindromic(String n) { long num = Long.parseLong(n); int m = n.length(); // num 的十进制长度 update((long) Math.pow(10, m - 1) - 1, num); // 十进制长为 m-1 的最大回文数 update((long) Math.pow(10, m) + 1, num); // 十进制长为 m+1 的最小回文数 int left = Integer.parseInt(n.substring(0, (m + 1) / 2)); // 枚举十进制长为 m 的邻近回文数 for (int l = left - 1; l <= left + 1; l++) { long pal = l; for (int x = m % 2 > 0 ? l / 10 : l; x > 0; x /= 10) { pal = pal * 10 + (x % 10); } update(pal, num); } return Long.toString(ans); } private void update(long pal, long num) { long d = Math.abs(pal - num); if (d > 0 && (d < minD || d == minD && pal < ans)) { minD = d; ans = pal; } } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/3855597/zhi-xu-kao-lu-5-ge-shu-zi-pythonjavacgo-3td25/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- [⚠️] Leetcode 5. Longest Palindromic Substring
- [⚠️] Leetcode 1244. Design A Leaderboard TreeMap store score cnt
- [⚠️ 复习] Leetcode 648. Replace Words Trie Tree
- [⚠️] Leetcode 79. Word Search
- [✅] Design an in-memory database to handle transactions
- [ ] Package Installation Order
- [ ] Leetcode 127. Word Ladder
- [ ] Leetcode 749. Contain Virus
- [✅] Leetcode 588. Design In-Memory File System Trie Tree
class TrieNode { Map<String, String> files; Map<String, TrieNode> directory; TrieNode() { files = new HashMap<>(); directory = new HashMap<>(); } } class FileSystem { TrieNode root; public FileSystem() { root = new TrieNode(); } public List<String> ls(String path) { TrieNode cur = root; String[] paths = path.split("/"); for (int i = 1; i < paths.length - 1; i++) { if (!cur.directory.containsKey(paths[i])) { cur.directory.put(paths[i], new TrieNode()); } cur = cur.directory.get(paths[i]); } List<String> ans = new ArrayList<>(); if (paths.length != 0) { String last = paths[paths.length - 1]; if (cur.files.containsKey(last)) { ans.add(last); return ans; } else { cur = cur.directory.get(paths[paths.length - 1]); } } for (String str : cur.files.keySet()) { ans.add(str); } for (String str : cur.directory.keySet()) { ans.add(str); } Collections.sort(ans); return ans; } public void mkdir(String path) { TrieNode cur = root; String[] paths = path.split("/"); for (int i = 1; i < paths.length; i++) { if (!cur.directory.containsKey(paths[i])) { cur.directory.put(paths[i], new TrieNode()); } cur = cur.directory.get(paths[i]); } } public void addContentToFile(String filePath, String content) { TrieNode cur = root; String[] paths = filePath.split("/"); for (int i = 1; i < paths.length - 1; i++) { if (!cur.directory.containsKey(paths[i])) { cur.directory.put(paths[i], new TrieNode()); } cur = cur.directory.get(paths[i]); } String fileName = paths[paths.length - 1]; if (!cur.files.containsKey(fileName)) { cur.files.put(fileName, content); } else { String curContent = cur.files.get(fileName); cur.files.put(fileName, curContent + content); } } public String readContentFromFile(String filePath) { TrieNode cur = root; String[] paths = filePath.split("/"); for (int i = 1; i < paths.length - 1; i++) { if (!cur.directory.containsKey(paths[i])) { cur.directory.put(paths[i], new TrieNode()); } cur = cur.directory.get(paths[i]); } String fileName = paths[paths.length - 1]; if (!cur.files.containsKey(fileName)) { return ""; } else { return cur.files.get(fileName); } } }