Leetcode

!()[https://leetcode.com/problems/symmetric-tree/] Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: Input: root = [1,2,2,3,4,4,3] Output: true Example 2: Input: root = [1,2,2,null,3,null,3] Output: false Constraints: The number of nodes in the tree is in the range [1, 1000]. -100 <= Node.val <= 100 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } List<TreeNode> q = new ArrayList<>(); q.add(root.left); q.add(root.right); while (q.size() > 1) { TreeNode left = q.remove(0); TreeNode right = q.remove(0); if (left == null && left == right) { continue; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } q.add(left.left); q.add(right.right); q.add(left.right); q.add(right.left); } return true; } public boolean isSymmetricRecursive(TreeNode root) { if (root == null) { return true; } return isSymmetric(root.left, root.right); } boolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) { return true; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } return isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right); } }

104. Maximum Depth of Binary Tree Given the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 Example 3: Input: root = [] Output: 0 Example 4: Input: root = [0] Output: 1 Constraints: ...

112. Path Sum Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Example 3: Input: root = [1,2], targetSum = 0 Output: false Constraints: ...

113. Path Sum II Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Example 2: Input: root = [1,2,3], targetSum = 5 Output: [] Example 3: Input: root = [1,2], targetSum = 0 Output: [] Constraints: ...

![https://leetcode.com/problems/sort-characters-by-frequency/] Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: “bbaA” is also a valid answer, but “Aabb” is incorrect. Note that ‘A’ and ‘a’ are treated as two different characters. ...

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string. Example 1: Input: S = "aab" Output: "aba" Example 2: Input: S = "aaab" Output: "" Note: S will consist of lowercase letters and have length in range [1, 500]. class Solution { int n = 0; int[][] heap = new int[27][2]; // Queue<int[]> q = new PriorityQueue<int[]>((a, b) -> -Integer.compare(a[1], b[1])); public String reorganizeString(String S) { int[] freq = new int[26]; Arrays.fill(heap, new int[] {0, 0}); for (char c: S.toCharArray()) { freq[c - 'a']++; } for (int i = 0; i < freq.length; i++) { if (freq[i] != 0) { add(new int[]{i, freq[i]}); } } StringBuilder sb = new StringBuilder(); // while (!isEmpty()) { while (size() > 1) { int[] a = poll(); char aa = (char) ('a' + a[0]); int[] b = poll(); char bb = (char) ('a' + b[0]); char select; if (sb.length() == 0) { select = aa; a[1]--; } else if (sb.charAt(sb.length() - 1) == aa) { select = bb; b[1]--; } else { select = aa; a[1]--; } sb.append(select); if (a[1] != 0) { add(a); } if (b[1] != 0) { add(b); } } while (!isEmpty()) { // System.out.println(Arrays.deepToString(heap)); var a = poll(); char aa = (char) ('a' + a[0]); if (sb.length() > 0 && sb.charAt(sb.length() - 1) == aa) { sb.setLength(0); break; } else { a[1]--; sb.append(aa); if (a[1] != 0) { // System.out.println("add = " + Arrays.toString(a)); add(a); } } } return sb.toString(); } int[] poll() { // return q.poll(); int[] max = Arrays.copyOf(heap[1], 2); heap[1][0] = 0; heap[1][1] = 0; heap[1][0] = heap[n][0]; heap[1][1] = heap[n][1]; n--; heap[n + 1][0] = 0; heap[n + 1][1] = 0; sink(1); return max; } void add(int[] val) { // q.add(val); heap[++n] = Arrays.copyOf(val, 2); swim(n); } boolean isEmpty() { return size() == 0; } int size() { return n; // return q.size(); } // max heap parent > child; j > i // wrong j < i void swim(int i) { int j = i / 2; if (j > 0 && less(j, i)) { swap(i, j); swim(j); } } void swap(int i, int j) { int[] temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } void sink(int i) { int left = 2 * i; int right = 2 * i + 1; int largest = i; if (left < heap.length && less(largest, left)) { largest = left; } if (right < heap.length && less(largest, right)) { largest = right; } if (largest != i) { swap(i, largest); sink(largest); } } boolean less(int i, int j) { return heap[i][1] < heap[j][1]; } } Solution 2022-01-29 class Solution { public String reorganizeString(String s) { if (s.length() == 0) return ""; Queue<int[]> heap = buildQHeap(s); StringBuilder sb = new StringBuilder(); while (heap.size() > 0) { int[] first = heap.poll(); if (sb.length() == 0) { sb.append((char) ('a' + first[0])); first[1]--; if (first[1] != 0) { heap.add(first); } } else { int prev = sb.charAt(sb.length() - 1) - 'a'; if (prev != first[0]) { sb.append((char) ('a' + first[0])); first[1]--; if (first[1] != 0) { heap.add(first); } } else { if (heap.size() == 0) return ""; int[] second = heap.poll(); sb.append((char) ('a' + second[0])); second[1]--; if (second[1] != 0) { heap.add(second); } heap.add(first); } } } return sb.toString(); } Queue<int[]> buildHeap(String s) { int[] freq = new int[26]; for (char c: s.toCharArray()) { int index = (int)(c - 'a'); freq[index]++; } Queue<int[]> heap = new PriorityQueue <>((a, b) -> - a[1] + b[1]); for (int i = 0; i < 26; i++) { if (freq[i] > 0) { heap.add(new int[] {i, freq[i]}); } } return heap; } }

![https://leetcode.com/problems/find-the-town-judge/] In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. ...

![https://leetcode.com/problems/last-stone-weight/] We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.) ...

![https://leetcode.com/problems/kth-largest-element-in-an-array/] Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array's length. class Solution { public int findKthLargest(int[] nums, int k) { MinPQ pq = new MinPQ(k); for (int a: nums) { pq.add(a); } return pq.min(); } static class MinPQ { final int[] pq; int n = 0; MinPQ(int size) { this.pq = new int[size + 1]; } int min() { return pq[1]; } void add(int i) { if (n < pq.length - 1) { pq[++n] = i; swim(n); } else { if (i > pq[1]) { pq[1] = i; sink(1); } } } void sink(int i) { int left = 2 * i; int right = 2 * i + 1; int smallest = i; if (left < pq.length && pq[left] < pq[i]) { smallest = left; } if (right < pq.length && pq[right] < pq[smallest]) { smallest = right; } if (smallest != i) { swap(i, smallest); sink(smallest); } } void swim(int i) { int j = i / 2; if (j > 0 && pq[i] < pq[j]) { swap(i, j); swim(j); } } void swap(int i, int j) { int t = pq[i]; pq[i] = pq[j]; pq[j] = t; } } } Solution 2 class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; sort(nums, 0, n - 1); return nums[n - k]; } void sort(int[] nums, int lo, int hi) { if (lo >= hi) return; int j = partition(nums, lo, hi); sort(nums, lo, j - 1); sort(nums, j + 1, hi); } int partition(int[] nums, int lo, int hi) { int i = lo; int j = hi + 1; while (true) { while (nums[++i] < nums[lo]) { if (i == hi) break; } while (nums[lo] < nums[--j]) { if (j == lo) break; } if (i < j) { swap(nums, i, j); } else { break; } } swap(nums, lo, j); return j; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } Solution 3 class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); for (int value: nums) { pq.add(value); if (pq.size() == k + 1) { pq.poll(); } // System.out.println(pq); } return pq.peek(); } } Solution - Quick Select class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int lo = 0; int hi = n - 1; while (lo < hi) { int j = partition(nums, lo, hi); if (j < n - k) { lo = j + 1; } else if (n - k < j) { hi = j - 1; } else { return nums[n - k]; } } return nums[n - k]; } int partition(int[] nums, int lo, int hi) { int i = lo; int j = hi + 1; while (true) { while (nums[++i] < nums[lo]) { if (i == hi) break; } while (nums[lo] < nums[--j]) { if (j == lo) break; } if (i < j) { swap(nums, i, j); } else { break; } } swap(nums, lo, j); return j; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } Solution 2022-01-24 class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int lo = 0; int hi = n - 1; k = n - k; while (lo < hi) { int m = partition(nums, lo, hi); if (m > k) { hi = m - 1; } else if (m < k) { lo = m + 1; } else { return nums[m]; } } return nums[lo]; } int partition(int[] nums, int lo, int hi) { int swapIndex = lo; while (lo < hi) { while (lo < hi && nums[hi] >= nums[swapIndex]) { hi--; } while (lo < hi && nums[lo] <= nums[swapIndex]) { lo++; } swap(nums, lo, hi); } swap(nums, lo, swapIndex); return lo; } void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }

![https://leetcode.com/problems/top-k-frequent-elements/] Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique. You can return the answer in any order. class Solution { public int[] topKFrequent(int[] nums, int k) { List<Integer>[] buckets = new List[nums.length + 1]; Map<Integer, Integer> freq = new HashMap<>(); for (int num: nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } for (var entry: freq.entrySet()) { List<Integer> bucket = buckets[entry.getValue()]; if (bucket == null) { bucket = new ArrayList<>(); } bucket.add(entry.getKey()); buckets[entry.getValue()] = bucket; } int[] res = new int[k]; int j = 0; for (int i = buckets.length - 1; i >= 0 && j < k; i--) { if (buckets[i] != null) { for (Integer val : buckets[i]) { res[j++] = val; } } } return res; } public int[] topKFrequent2(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int num: nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue()); for (Map.Entry<Integer, Integer> entry: freq.entrySet()) { q.add(entry); if (q.size() > k) { q.poll(); } System.out.println(q); } int[] res = new int[q.size()]; int i = 0; for (var entry: q) { res[i++] = entry.getKey(); } return res; } }