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). 1 2 3 4 Example 1: Input: root = [1,2,2,3,4,4,3] Output: true 1 2 3 4 Example 2: Input: root = [1,2,2,null,3,null,3] Output: false Constraints: ...

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. 1 2 3 4 Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 1 2 3 4 Example 2: Input: root = [1,null,2] Output: 2 1 2 3 4 Example 3: Input: root = [] Output: 0 1 2 3 4 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. 1 2 3 4 Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true ...

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. 1 2 3 4 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]] 1 2 3 4 Example 2: Input: root = [1,2,3], targetSum = 5 Output: [] ...

![https://leetcode.com/problems/sort-characters-by-frequency/] Given a string, sort it in decreasing order based on the frequency of characters. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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. 1 2 3 4 5 6 7 8 9 Example 1: Input: S = "aab" Output: "aba" Example 2: Input: S = "aaab" Output: "" Note: ...

![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. 1 2 3 4 5 6 7 8 9 10 11 12 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 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. 1 2 3 4 5 6 7 8 9 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: ...