一亩三分地
// "static void main" must be defined in a public class.
class Cell{
int val;
int freq;
public Cell(int val, int freq){
this.val = val;
this.freq = freq;
}
}
public class Main {
public static void main(String[] args) {
int[][] input = new int[][]{{1, 4, -2}, {-2, 3, 4}, {3, 1, 3}};
int[][] ans = new int[][]{{3, 3, 4}, {3, 4, 1}, {1, -2, -2}};
sortMatrixByOcuurrences(input);
}
public static int[][] sortMatrixByOcuurrences(int[][] matrix){
int m = matrix.length, n = matrix[0].length;
HashMap<Integer, Integer> count = new HashMap<>();
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
count.put(matrix[i][j], count.getOrDefault(matrix[i][j], 0) + 1);
}
}
List<Cell> cells = new ArrayList<>();
for(int i : count.keySet()){
cells.add(new Cell(i, count.get(i)));
}
Collections.sort(cells, new Comparator<Cell>(){
public int compare(Cell c1, Cell c2){
if(c1.freq == c2.freq){
return c1.val - c2.val;
}
return c1.freq - c2.freq;
}
});
int idx = 0;
int[][] ans = new int[m][n];
for(int k = n-1; k >= 0; k--){
int i = m-1;
int j = k;
while(j <= n-1){
ans[i--][j++] = cells.get(idx).val;
cells.get(idx).freq--;
if(cells.get(idx).freq == 0) idx++;
}
}
for(int k = m - 2; k >= 0; k--){
int i = k;
int j = 0;
while(i >= 0){
ans[i--][j++] = cells.get(idx).val;
cells.get(idx).freq--;
if(cells.get(idx).freq == 0) idx++;
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
System.out.print(ans[i][j] + " ");
}
System.out.println(" ");
}
return ans;
}
}
Max Arithmetic Length
思路：先找到a里面所有相邻数字difference的gcd，对于这个gcd的所有factor，当成diff，一个一个试一试，看看能不能用这个diff形成等差数列
Time Complexity : O(nlogn) + O(gcd) + O(gcd*O(a+b))
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
int[] a1 = new int[]{0, 4, 8, 16};
int[] b1 = new int[]{0, 2, 6,12, 14,20};
int[] a2 = new int[]{5, 7, 13, 14};
int[] b2 = new int[]{9, 11, 15};
int[] ans1 = new int[]{0, 4, 8, 12, 16, 20};
System.out.println("The Max Arithmetic Length : "+ maxArithmeticLength(a1, b1));
}
public static int maxArithmeticLength(int[] a, int[] b){
//find the gcd of number differences in a
int gcd = a[1] - a[0];//2<= a.length <= 1000
for(int i = 2; i < a.length; i++){
gcd = findGCD(a[i] - a[i-1], gcd);
}
//find all the possible differences
List<Integer> diffs = findFactors(gcd);
Set<Integer> set_b = new HashSet<>();
for(int n : b){
set_b.add(n);
}
//get the max length by trying all the possible differences
int max = -1;
for(int diff : diffs){
max = Math.max(max, canBeArithmetic(a, set_b, diff));
}
return max;
}
//method that return the max length if can make array a an arithmetic progression with the given difference, else return -1;
private static int canBeArithmetic(int[] a, Set<Integer> b, int diff){
//System.out.println( "diff " + diff);
int idx = 0;
int target = a[0];
int len = 0;
while(idx < a.length){
if(a[idx] != target && !b.contains(target)){
return -1;
}
while(idx < a.length && a[idx] == target){
idx++;
target += diff;
len++;
}
while(b.contains(target)){
len++;
target += diff;
}
}
return len;
}
private static int findGCD(int A, int B){
if(A < B) return findGCD(B, A);
if(B == 0) return A;
return findGCD(B, A % B);
}
private static List<Integer> findFactors(int n){
List<Integer> ans = new ArrayList<>();
for(int i = 1; i <= Math.sqrt(n);i++){
if(n % i == 0){
ans.add(i);
if(i * i != n){
ans.add(n / i);
}
}
}
return ans;
}
}
Modify a bit at a given position
Given an integer number n, set its kth bit to 0
(assume from right to left and k index starts from 1)
Example：For n = 37 and k = 3
37 = 100101 -> 100001 = 33
public class Main {
public static void main(String[] args) {
System.out.print(modifyK(37, 3));//
}
public static int modifyK(int n, int k){
k = k-1;
int mask = 1 << k;
return (n & ~mask) | ((0 << k) & mask);
}
}
Beautiful Array
A beautiful array conrains an element occurs once, another one that occurs twice, another thrice, and so on up to some positive integer n > 3. Given an array arr as an input, your task is to find the array of the minimal possible length that can be appended to arr to make it beautiful.
Input : [1,1,1,1, 2, 2]
output: [3,3,3,4]
解释：[1, 1, 1, 1, 3, 3, 3, 2, 2, 4]
Lintcode/Leetcode
Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Input:s = "aaabb", k = 3
Output: 3
public class Solution {
public int longestSubstring(String s, int k) {
return longestSubstring(s.toCharArray(), k, 0, s.length());
}
private int longestSubstring(char[] ss, int k, int left, int right){
//base case
if(left >= right) return 0;
//recursion
int[] count = new int[26];
for(int i = left; i < right; i++){
count[ss[i] - 'a']++;
}
for(int mid = left; mid < right; mid++){
if(count[ss[mid] - 'a'] >= k){
continue;
}
int midNext = mid + 1;
while(midNext < right && count[ss[midNext] - 'a'] < k){
midNext++;
}
return Math.max(longestSubstring(ss, k, left, mid), longestSubstring(ss, k, midNext, right));
}
return right - left;
}
}
Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int n : nums){
map.put(n, map.getOrDefault(n, 0) + 1);
}
//buckets的index是frequency，value是element of nums
List[] buckets = new ArrayList[nums.length+1];
for(int n : map.keySet()){
int count = map.get(n);
if(buckets[count] == null){
buckets[count] = new ArrayList<>();
}
buckets[count].add(n);
}
List<Integer> ans = new ArrayList<>();
for(int i = buckets.length - 1; i > 0 && ans.size() < k; i--){
if(buckets[i] != null) ans.addAll(buckets[i]);
}
return ans;
}
}
Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> ans = new ArrayList<>();
//coner case 1
if(nums == null || nums.length == 0) return ans;
//corner case 2
if(nums.length == 1){
ans.add(nums[0] + "");
return ans;
}
//general cases
int i = 0;
while(i < nums.length){
int start = nums[i];
while(i + 1 < nums.length && nums[i] + 1 == nums[i+1]){
i++;
}
if(nums[i] == start){
ans.add(nums[i] + "");
}else{
ans.add(start + "->" + nums[i]);
}
i++;
}
return ans;
}
}
// ans = ["0", "2->4", "6","8->9"]
// nums = [0,2,3,4,6,8,9]
// ^
// start = 8
Number of Islands
Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent. Find the number of islands.
- DFS
public class Solution {
/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
public int numIslands(boolean[][] grid) {
//corner cases
if(grid == null || grid.length == 0) return 0;
//dfs
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int count = 0;
for(int y = 0; y < m; y++){
for(int x = 0; x < n; x++){
if(grid[y][x] && !visited[y][x]) {
count++;
dfs(y, x, visited, grid);
}
}
}
return count;
}
private void dfs(int y, int x, boolean[][] visited, boolean[][] grid){
//out of bound
if(y < 0 || y >= grid.length || x < 0 || x >= grid[0].length){
return;
}
//not an island or visited
if(visited[y][x] || !grid[y][x]) {
return;
}
visited[y][x] = true;
dfs(y+1, x, visited, grid);
dfs(y, x+1, visited, grid);
dfs(y-1, x, visited, grid);
dfs(y, x-1, visited, grid);
}
}
- BFS
public class Solution {
/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
public int numIslands(boolean[][] grid) {
//corner cases
if(grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int count = 0;
for(int y = 0; y < m; y++){
for(int x = 0; x < n; x++){
if(grid[y][x] && !visited[y][x]) {
count++;
bfs(y, x, visited, grid, directions);
}
}
}
return count;
}
private void bfs(int y, int x, boolean[][] visited, boolean[][] grid, int[][] directions){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{y, x});
visited[y][x] = true;
while(!queue.isEmpty()){
int size = queue.size();
while(size > 0){
int[] curr = queue.remove();
for(int[] d : directions){
int ty = curr[0] + d[0];
int tx = curr[1] + d[1];
if(is_valid(ty, tx, visited, grid)){
visited[ty][tx] = true;
queue.add(new int[]{ty, tx});
}
}
size--;
}
}
}
private boolean is_valid(int y, int x, boolean[][] visited, boolean[][] grid){
//out of bound
if(y < 0 || y >= grid.length || x < 0 || x >= grid[0].length){
return false;
}
//visited or a sea
if(visited[y][x] || !grid[y][x]){
return false;
}
return true;
}
}
Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
public class Solution {
/**
* @param root: the root of binary tree
* @return: the length of the longest consecutive sequence path
*/
public int longestConsecutive(TreeNode root) {
int[] ans = new int[1];
dfs(root, 0, root.val, ans);
return ans[0];
}
private void dfs(TreeNode root, int length, int target, int[] ans) {
if (root == null) {
return;
}
if (root.val == target) {
length++;
} else {
length = 1;
}
ans[0] = Math.max(ans[0], length);
dfs(root.left, length, root.val + 1, ans);
dfs(root.right, length, root.val + 1, ans);
Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, output sequence in dictionary order. Transformation rule such that: 1. Only one letter can be changed at a time 2. Each intermediate word must exist in the dictionary
Input：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
Output：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation：
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
public class Solution {
public List<List<String>> findLadders(String start, String end,
Set<String> dict) {
List<List<String>> ans = new ArrayList<List<String>>();
Map<String, List<String>> map = new HashMap<String, List<String>>();
Map<String, Integer> distance = new HashMap<String, Integer>();
dict.add(start);
dict.add(end);
// 1)先bfs从end到start找到所有dict里的单词到end的距离，存在distance里
//同时生成map：每一个单词可以扩展成dict里什么单词
bfs(map, distance, end, start, dict);
List<String> path = new ArrayList<String>();
// 2) dfs从start到end找到all shortest transformation sequence(s)
dfs(ans, path, start, end, distance, map);
return ans;
}
void dfs(List<List<String>> ans, List<String> path, String crt,
String end, Map<String, Integer> distance,
Map<String, List<String>> map) {
path.add(crt);
if (crt.equals(end)) {
ans.add(new ArrayList<String>(path));
} else {
for (String next : map.get(crt)) {
if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) {
dfs(ans, path, next, end, distance, map);
}
}
}
path.remove(path.size() - 1);
}
void bfs(Map<String, List<String>> map, Map<String, Integer> distance,
String start, String end, Set<String> dict) {
Queue<String> q = new LinkedList<String>();
q.offer(start);
distance.put(start, 0);
for (String s : dict) {
map.put(s, new ArrayList<String>());
}
while (!q.isEmpty()) {
String crt = q.poll();
List<String> nextList = expand(crt, dict);
for (String next : nextList) {
map.get(next).add(crt);
if (!distance.containsKey(next)) {
distance.put(next, distance.get(crt) + 1);
q.offer(next);
}
}
}
}
List<String> expand(String crt, Set<String> dict) {
List<String> expansion = new ArrayList<String>();
for (int i = 0; i < crt.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch != crt.charAt(i)) {
String expanded = crt.substring(0, i) + ch
+ crt.substring(i + 1);
if (dict.contains(expanded)) {
expansion.add(expanded);
}
}
}
}
return expansion;
}
}
Sliding Window Maximum
Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
Input: [1,2,7,7,8], 3
Output: [7,7,8]
class Node {
int pos;
int val;
public Node(int pos, int val) {
this.pos = pos;
this.val = val;
}
}
public class Solution {
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
Comparator<Node> comparator = new Comparator<Node>() {
public int compare(Node left, Node right) {
if (right.val == left.val) {
return left.pos - right.pos;
}
return right.val - left.val;
}
};
TreeSet<Node> set = new TreeSet<>(comparator);
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
Node node = new Node(i, nums[i]);
set.add(node);
if (set.size() > k) {
Node last = new Node(i - k, nums[i - k]);
set.remove(last);
}
if (set.size() == k) {
result.add(set.first().val);
}
}
return result;
}
};
Expression Add Operators
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Input: "123", 6
Output: ["1*2*3","1+2+3"]
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
dfs(num, target, 0, "", 0, 0, ans);
return ans;
}
//idx是我们evaluate到第几位数字了
private void dfs(String num, int target, int idx, String path, long curr, long prev, List<String> ans){
if(idx == num.length()){
if(curr == target){
ans.add(path);
}
return;
}
for(int i = idx; i < num.length(); i++){
long x = Long.parseLong(num.substring(idx, i+1));
if(idx == 0){
dfs(num, target, i+1, path + x, x, x, ans);
}else{
dfs(num, target, i+1, path + "*" + x, curr - prev + prev*x, prev*x, ans);
dfs(num, target, i+1, path + "+" + x, curr + x, x, ans);
dfs(num, target, i+1, path + "-" + x, curr - x, -x, ans);
}
if(x == 0) break;
}
}
}
Alien Dictionary
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Time Complexity: O(C), Let C be the total length of all the words in the input list, added together.
Input：["wrt","wrf","er","ett","rftt"]
Output："wertf"
public class Solution {
/**
* @param words: a list of words
* @return: a string which is correct order
*/
public String alienOrder(String[] words) {
//topological sort + BFS
Map<Character, List<Character>> graph = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
if(!build_graph(graph, indegree, words)){
return "";
}
return bfs(graph, indegree);
}
//return false if we can't build a graph
private boolean build_graph(Map<Character, List<Character>> graph, Map<Character, Integer> indegree, String[] words){
for(String word : words){
for(char c: word.toCharArray()){
graph.put(c, new ArrayList<>());
indegree.put(c, 0);
}
}
for(int i = 0; i < words.length-1; i++){
String word1 = words[i];
String word2 = words[i+1];
if(word1.length() > word2.length() && word1.startsWith(word2)){
return false;
}
for(int j = 0; j < Math.min(word1.length(), word2.length()); j++){
char c1 = word1.charAt(j);
char c2 = word2.charAt(j);
if(c1 != c2) {
graph.get(c1).add(c2);
indegree.put(c2, indegree.get(c2) + 1);
break;
}
}
}
return true;
}
private String bfs(Map<Character, List<Character>> graph, Map<Character, Integer> indegree){
StringBuilder sb = new StringBuilder();
PriorityQueue<Character> pq = new PriorityQueue<>();
for(char c : indegree.keySet()){
if(indegree.get(c).equals(0)){
pq.add(c);
}
}
while(pq.size() > 0){
char curr = pq.poll();
sb.append(curr);
for(char next : graph.get(curr)){
indegree.put(next, indegree.get(next)-1);
if(indegree.get(next).equals(0)){
pq.add(next);
}
}
}
if(sb.length() < indegree.size()){
return "";
}
return sb.toString();
}
}
Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
- A single node tree is a BST
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
// write your code here
return helper(root, null, null);
}
private boolean helper(TreeNode root, Integer min, Integer max){
if(root == null) return true;
if((min != null && root.val <= min) || (max != null && root.val >= max)) return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
}
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
public RandomListNode copyRandomList(RandomListNode head) {
// write your code here
//corner case
if(head == null) return null;
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode dummy = new RandomListNode(0) ;
RandomListNode pre = dummy;
while(head != null){
if(!map.containsKey(head)){
map.put(head, new RandomListNode(head.label));
}
RandomListNode newNode = map.get(head);
pre.next = newNode;
if(head.random != null){
if(!map.containsKey(head.random)){
map.put(head.random, new RandomListNode(head.random.label));
}
newNode.random = map.get(head.random);
}
head = head.next;
pre = newNode;
}
return dummy.next;
}
}
Word Search
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
board =[['A','B','C','E'],``['S','F','C','S'],`` ['A','D','E','E']]
Given word = "ABCCED", returntrue.
Given word = "ABCB", return false.
Time Complexity : Time Complexity: O(N⋅3^L) where N is the number of cells in the board and L is the length of the word to be matched.
class Solution {
public boolean exist(char[][] board, String word) {
char[] w = word.toCharArray();
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(dfs(board, i, j, w, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, char[] w, int idx){
if(idx == w.length) return true;
//out of bound
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length){
return false;
}
if(board[i][j] != w[idx]) return false;
board[i][j] ^= 256;//mark as visited
boolean exist = dfs(board, i+1, j, w, idx+1)
|| dfs(board, i-1, j, w, idx+1)
|| dfs(board, i, j+1, w, idx+1)
|| dfs(board, i, j-1, w, idx+1);
board[i][j] ^= 256;
return exist;
}
}
Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
public class Solution {
//从右往左找突然降下来的点是因为这样他的后面才有比他大的可以换的
//如果从右往左一直变大，那任意一个点右边的数都小于它，那就找不到比他大的数来交换
public void nextPermutation(int[] nums) {
//corner cases
if(nums == null || nums.length == 0) return;
int n = nums.length;
int i = n - 2;
//从右往左看，我们想找到突然降下来的那个点
while(i >= 0 && nums[i] >= nums[i+1]) {
i--;
}
if(i >= 0){
int j = n - 1;
while(nums[j] <= nums[i]){
j--;
}
swap(nums, i, j);
}
reverse(nums, i+1, n-1);
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void reverse(int[] nums, int i ,int j){
while(i < j) swap(nums, i++, j--);
}
}
// 6 2 1 5 4 3 0
//这里，5 4 3 0， 任意一个数字的右边都小于自己，所以和右边的数字交换不能使这个数变大
//当我们遇到1的时候， 1 5 4 3 0，把1和 5 4 3 交换，都会产生大的数，因为我们要找的是next permutation，所以，我要找最小的大于1的数
//也就是3， swap 1 3， 我们得到 6 2 3 5 4 1 0，然后再把原来1位置的右边全部reverse
//得到 6 2 3 0 1 4 5，这就是next permutation
Simplify Path
Given an absolute path for a file (Unix-style), simplify it. In a UNIX-style file system, a period .refers to the current directory. Furthermore, a double period .. moves the directory up a level. The result must always begin with /, and there must be only a single / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the result must be the shortest string representing the absolute path.
Input: "/a/./../../c/"
Output:"/c"
public class Solution {
/**
* @param path: the original path
* @return: the simplified path
*/
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
for(String s : path.split("/")){
if(s.equals("..")){
if(!stack.isEmpty()){
stack.pop();//返回上一级
}
}else if(!s.isEmpty() && !s.equals(".")) {
stack.push(s);
}
}
String ans = "";
while(!stack.isEmpty()){
ans = "/"+stack.pop()+ans;
}
return ans.isEmpty()? "/" : ans;
}
}
Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
//corner cases
List<Integer> ans = new ArrayList<>();
if(root == null) return ans;
//general case
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode curr = queue.remove();
if(i == 0){
ans.add(curr.val);
}
if(curr.right != null) queue.add(curr.right);
if(curr.left != null) queue.add(curr.left);
}
}
return ans;
}
}
Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: the minimum number of conference rooms required
*/
public int minMeetingRooms(List<Interval> intervals) {
int max_time = 0;
for(Interval i : intervals){
max_time = Math.max(i.end, max_time);
}
int[] prefix = new int[max_time+1];
for(Interval i : intervals){
prefix[i.start]++;
prefix[i.end]--;
}
int ans = prefix[0];
for(int i = 1; i < max_time; i++){
prefix[i] += prefix[i-1];
ans = Math.max(ans, prefix[i]);
}
return ans;
}
}
Task Scheduler
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks.
Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B.
public class Solution {
public int leastInterval(char[] tasks, int n) {
if(tasks == null || tasks.length == 0){
return 0;
}
int[] counts = new int[26];
for(char c : tasks){
counts[c - 'A']++;
}
int max_freq = 0;
for(int count : counts){
max_freq = Math.max(count, max_freq);
}
//get how many tasks have the frequency with the maximum
int p = 0;
for(int count : counts){
p += count == max_freq? 1 : 0;
}
int ans = (max_freq - 1)*(n+1) + p;
return Math.max(ans, tasks.length);
}
}
Reorganize String
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.
Input: S = "aab"
Output: "aba"
class Solution {
public String reorganizeString(String S) {
int n = S.length();
int[] counts = new int[26];
//Encoded counts[i] = 100*count + i
for(char c : S.toCharArray()){
counts[c - 'a'] += 100;
}
for(int i = 0; i < 26; i++){
counts[i] += i;
}
Arrays.sort(counts);
int idx = 1;//fill from odd idx
char[] ans = new char[n];
for(int code : counts){
int count = code / 100;
char character = (char)(code % 100 + 'a');
if(count > (n+1)/2) return "";
for(int i = 0; i < count; i++){
if(idx >= n) idx = 0;//now fill even idx
ans[idx] = character;
idx += 2;
}
}
return new String(ans);
}
}
Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.
Input: [4, 14, 2]
Output: 6
Explanation:
4 is 0100
14 is 1110
2 is 0010
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Time Complexity : O(32n) = O(n)
public class Solution {
public int totalHammingDistance(int[] nums) {
//从bits右边开始，count ones on each bits
//total number of hamming distance += #ones * #zeros
int ans = 0;
for(int i = 0; i < 32; i++){
int ones = 0;
for(int n : nums){
ones += (n >> i) & 1;
}
//zeros * ones
ans += (nums.length - ones) * ones;
}
return ans;
}
}
All Nodes Distance K in Binary Tree
We are given a binary tree (with root node root), a target node, and an integer value K. Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.
Input:
{3,5,1,6,2,0,8,#,#,7,4}
5
2
Output: [7,4,1]
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: the root of the tree
* @param target: the target
* @param K: the given K
* @return: All Nodes Distance K in Binary Tree
*/
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
HashMap<Integer, List<Integer>> graph = new HashMap<>();
buildGraph(root, graph);
for(int n : graph.get(target.val)){
System.out.println(n);
}
List<Integer> ans = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.add(target.val);
visited.add(target.val);
int distance = 0;
while(!q.isEmpty()){
int size = q.size();
while(size > 0){
int curr = q.remove();
if(distance == K){
ans.add(curr);
}
for(int next : graph.get(curr)){
if(visited.contains(next)) continue;
q.add(next);
visited.add(next);
}
size--;
}
distance++;
}
return ans;
}
private void buildGraph(TreeNode root, HashMap<Integer, List<Integer>> graph){
if(root == null) return;
graph.putIfAbsent(root.val, new ArrayList<>());
if(root.left != null) {
buildGraph(root.left, graph);
graph.get(root.val).add(root.left.val);
graph.get(root.left.val).add(root.val);
}
if(root.right != null) {
buildGraph(root.right, graph);
graph.get(root.val).add(root.right.val);
graph.get(root.right.val).add(root.val);
}
}
}
Range Sum of BST - easy
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive). The binary search tree is guaranteed to have unique values.
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: the root node
* @param L: an integer
* @param R: an integer
* @return: the sum
*/
public int rangeSumBST(TreeNode root, int L, int R) {
int[] sum = new int[1];
dfs(root, sum, L, R);
return sum[0];
}
private void dfs(TreeNode root, int[] sum, int L ,int R){
if(root == null) return;
if(root.val >= L && root.val <= R){
sum[0] += root.val;
}
if(root.val > L){
dfs(root.left, sum, L, R);
}
if(root.val < R){
dfs(root.right, sum, L, R);
}
}
}
Nested List Weight Sum -easy
Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Input: the list [[1,1],2,[1,1]],
Output: 10.
Explanation:
four 1's at depth 2, one 2 at depth 1, 4 * 1 * 2 + 1 * 2 * 1 = 10
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer,
* // rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds,
* // if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds,
* // if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class Solution {
public int depthSum(List<NestedInteger> nestedList) {
return helper(nestedList, 0);
}
private int helper(List<NestedInteger> nestedList, int depth){
int sum = 0;
for(NestedInteger curr : nestedList){
if(curr.isInteger()){
sum += curr.getInteger() * (depth+1);
}else{
sum += helper(curr.getList(), depth+1);
}
}
return sum;
}
}
Add Binary -easy
Given two binary strings, return their sum (also a binary string).
Input:
a = "11", b = "1"
Output:
"100"
public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i1 = a.length() - 1;
int i2 = b.length() - 1;
int carry = 0;
while(i1 >= 0 || i2 >= 0){
int d1 = i1 >= 0 ? (a.charAt(i1--) - '0') : 0;
int d2 = i2 >= 0 ? (b.charAt(i2--) - '0') : 0;
sb.append((d1 + d2 + carry) % 2);
carry = (d1 + d2 + carry) / 2;
}
if(carry != 0) sb.append(carry);
return sb.reverse().toString();
}
}
Palindromic Substrings -easy
Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
- extend
O(N^2)
class Solution {
public int countSubstrings(String s) {
if(s == null || s.length() == 0) return 0;
int count = 0;
for(int center = 0; center < s.length(); center++){
count += extend(s, center, center);//odd
count += extend(s, center, center+1);//even
}
return count;
}
private int extend(String s, int left, int right){
int count = 0;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
count++;
left--;
right++;
}
return count;
}
}
- DP
O(N^2)
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int count = 0;
int[][] dp = new int[n][n];
for(int j = 0; j < n; j++){
for(int i = 0; i <= j; i++){
dp[i][j] = (s.charAt(i) == s.charAt(j) && (j - i + 1 <= 3 || dp[i+1][j-1] == 1)) ? 1 : 0;
count += dp[i][j];
}
}
return count;
}
}
Monotonic Array -easy
An array is monotonic if it is either monotone increasing or monotone decreasing. An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j]. Return true if and only if the given array A is monotonic
public class Solution {
public boolean isMonotonic(int[] A) {
boolean inc = true;
boolean dec = true;
for(int i = 1; i < A.length; i++){
inc = inc && A[i-1] <= A[i];
dec = dec && A[i-1] >= A[i];
}
return inc || dec;
}
}
Search a 2D Matrix II -easy
Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- Integers in each column are sorted from up to bottom.
- No duplicate integers in each row or column.
Input:
[[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10] ]
target =3
Output: 2
public class Solution {
public int searchMatrix(int[][] matrix, int target) {
//corner cases
int m = matrix.length;
if(m == 0) return 0;
int n = matrix[0].length;
if(n == 0) return 0;
//general cases;
int ans = 0;
int y = m-1, x = 0;
while(y >= 0 && x < n){
if(matrix[y][x] == target){
ans++;
y--;
x++;
}else if(matrix[y][x] < target){
x++;
}else{
y--;
}
}
return ans;
}
}
Find Peak Element -easy
There is an integer array which has the following features: The numbers in adjacent positions are different. A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peak if: A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.
public class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
// write your code here
int left = 0, right = A.length - 1;
while(left + 1 < right){
int med = left + (right - left) / 2;
if(A[med] > A[med + 1]){
right = med;
}else{
left = med;
}
}
if(A[left] > A[left+1]) return left;
return right;
}
}
Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. Node.val can be negative.
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer
*/
public int maxPathSum(TreeNode root) {
// write your code here
if(root == null) return 0;
int[] path_sum = new int[1];
path_sum[0] = Integer.MIN_VALUE;
dfs(root, path_sum);
return path_sum[0];
}
//返回单边最长path的同时，更新path_summ
private int dfs(TreeNode root, int[] path_sum){
if(root == null) return 0;
int left_single_path = dfs(root.left, path_sum);
int right_single_path = dfs(root.right, path_sum);
//path_sum可以是双边的，path不能为空，所以不能为零
//这里为什么不用比较right_single_path + root.val，left_single_path + root.val的原因是
//如果右子树的值小于零，会导致我们加上后path sum变小，那么一开始，右子树的值return的时候就会被0取代（就像最后一行代码）
path_sum[0] = Math.max(path_sum[0], left_single_path + right_single_path + root.val);
//chain是单边的，可以为0，代表不取
return Math.max(Math.max(left_single_path , right_single_path) + root.val, 0);
}
}
First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer. We have an array which contains only positive numbers in a range from [1, n], and the problem is to find a first missing positive in O(n) time and O(1)space
Input: [3,4,-1,1]
Output: 2
class Solution {
public int firstMissingPositive(int[] nums) {
//[1, 2, 3, ... -2, > N, -1]
//we want to partition the array in place, where the left part has the all the positive integers at its own index, and the right part has all the numbers we don't wnat like -1, -2 or number > N
int left = 0, right = nums.length;
int n = nums.length;
while(left != right){
int val = nums[left];
//positive number at the right index
if(val == left+1){
left++;
//all the numbers we don't want
}else if(val <= 0 || val > n || nums[val - 1] == val){
swap(nums, left, --right);
//positive number at wrong position
}else{
swap(nums, left, val - 1);
}
}
return left+1;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
One Edit Distance
Given two strings S and T, determine if they are both one edit distance apart.
One edit distance means doing one of these operation:
- insert one character in any position of S
- delete one character in S
- change one character in S to other character
Example 1:
Input: s = "aDb", t = "adb"
Output:true
Example 2:
Input: s = "ab", t = "ab"
Output: false
public class Solution {
public boolean isOneEditDistance(String s, String t) {
int m = s.length();
int n = t.length();
if(Math.abs(m-n) > 1){
return false;
}
if(m > n){
return isOneEditDistance(t, s);
}
for(int i = 0; i < m; i++){
if(s.charAt(i) != t.charAt(i)){
if(m == n){
return s.substring(i+1).equals(t.substring(i+1));
}
return s.substring(i).equals(t.substring(i+1));
}
}
return m != n; //s = "ab", t = "ab"
}
}
Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Input: n = 2, prerequisites = [[1,0]]
Output: true
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//corner cases
if(prerequisites == null || prerequisites.length == 0) return true;
//build graph
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph.add(new ArrayList<>());
}
for(int[] p : prerequisites){
graph.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
//BFS: Topological sort
int taken = 0;
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0){
queue.add(i);
}
}
while(!queue.isEmpty()){
int u = queue.remove();
taken++;
for(int v : graph.get(u)){
indegree[v]--;
if(indegree[v] == 0){
queue.add(v);
}
}
}
return taken == numCourses;
}
}
Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2^31 - 1.
Example
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
public class Solution {
static String[] lessThan20 = new String[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
static String[] lessThan100 = new String[]{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if(num == 0){
return "Zero";
}
return helper(num);
}
private String helper(int num){
StringBuilder sb = new StringBuilder();
if(num < 20){
sb.append(lessThan20[num]);
}else if(num < 100){
sb.append(lessThan100[num / 10])
.append(" ")
.append(helper(num % 10));
}else if(num < 1000){
sb.append(helper(num / 100))
.append(" Hundred ")
.append(helper(num % 100));
}else if(num < 1000000){
sb.append(helper(num / 1000))
.append(" Thousand ")
.append(helper(num % 1000));
}else if(num < 1000000000){
sb.append(helper(num / 1000000))
.append(" Million ")
.append(helper(num % 1000000));
}else{
sb.append(helper(num / 1000000000))
.append(" Billion ")
.append(helper(num % 1000000000));
}
return sb.toString().trim();
}
}
Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Input: [1,2,3,4]
Output: [24,12,8,6]
public class Solution{
public int[] productExceptSelf(int[] nums){
int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;
//from left to right, ans[i] = product of elements [0,i-1]
//ans[3]等于前三个elements product nums[0] nums[1] nums[2]
for(int i = 1; i < n; i++){
ans[i] = ans[i-1] * nums[i-1];
}
int right_product = 1;
for(int i = n-1; i >= 0; i--){
ans[i] *= right_product;
right_product *= nums[i];
}
return ans;
}
}
Minimum Add to Make Parentheses Valid
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid. Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Input: "()))(("
Output: 4
public class Solution {
public int minAddToMakeValid(String S) {
int left = 0; //number left parentheses to add
int right = 0;//number right parentheses to add
for(char c : S.toCharArray()){
//如果当前遇到了右括号，但是我们需要的右括号为0，left++
if(c == ')' && right == 0){
left++;
}else{
right += c == '('? 1 : -1;
}
}
return left + right;
}
}
Valid Number
Validate if a given string can be interpreted as a decimal number. It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:
- Numbers 0-9
- Exponent - "e"
- Positive/negative sign - "+"/"-"
- Decimal point - "."
Of course, the context of these characters also matters in the input.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
public class Solution {
public boolean isNumber(String s) {
s = s.trim().toLowerCase();
boolean eSeen = false;
boolean dotSeen = false;
boolean numberSeen = false;
for(int i = 0; i < s.length(); i++){
int c = s.charAt(i);
if(c >= '0' && c<= '9'){
numberSeen = true;
}else if(c == '.'){
if(dotSeen || eSeen){
return false;
}
dotSeen = true;
}else if(c == 'e'){
if(eSeen || !numberSeen){
return false;
}
numberSeen = false;
eSeen = true;
}else if(c == '-' || c == '+'){
if(i != 0 && s.charAt(i-1) != 'e'){
return false;
}
}else{
return false;
}
}
return numberSeen;
}
}
Is Graph Bipartite?
Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B. The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
public class Solution {
public boolean isBipartite(int[][] graph) {
if(graph == null || graph.length == 0){
return true;
}
int n = graph.length;
int[] colors = new int[n];//0 : not visited, 1 : red, -1 : blue
for(int i = 0; i < n; i++){
if(colors[i] == 0 && !dfs(graph,colors, i, 1)){
return false;
}
}
return true;
}
private boolean dfs(int[][] graph, int[] colors, int curr, int color){
if(colors[curr] != 0){
return colors[curr] == color;
}
colors[curr] = color;
for(int next : graph[curr]){
if(!dfs(graph, colors, next, -color)){
return false;
}
}
return true;
}
}
Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
- Priority Queue
Time:O(NlogK)where k is the number of linked lists, n is the total number of nodes in two lists.
Space :O(N)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//O(NlogK)
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
ListNode dummy = new ListNode();
PriorityQueue<ListNode> minheap = new PriorityQueue<>(new Comparator<ListNode>(){
public int compare(ListNode n1, ListNode n2){
return n1.val - n2.val;
}
});
for(ListNode node : lists){
if(node != null) minheap.offer(node);
}
ListNode curr = dummy;
while(minheap.size() > 0){
ListNode min = minheap.poll();
curr.next = min;
if(min.next != null){
minheap.add(min.next);
}
curr = curr.next;
}
return dummy.next;
}
}
- Merge with Divide And Conquer
Time:O(NlogK)where k is the number of linked lists, n is the total number of nodes in two lists.
Space :O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mergeK(lists, 0, lists.length-1);
}
private ListNode mergeK(ListNode[] lists, int left, int right){
if(left > right) return null;
if(left == right) return lists[left];
if(left + 1 == right) return mergeTwo(lists[left], lists[right]);
int mid = left + (right - left) / 2;
ListNode l1 = mergeK(lists, left, mid);
ListNode l2 = mergeK(lists, mid+1, right);
return mergeTwo(l1, l2);
}
private ListNode mergeTwo(ListNode l1,ListNode l2){
ListNode dummy=new ListNode(0);
ListNode curr = dummy;
while(l1!=null || l2!=null){
int val1 = (l1==null)? Integer.MAX_VALUE:l1.val;
int val2 = (l2==null)? Integer.MAX_VALUE:l2.val;
if(val1 < val2){
curr.next=l1;
l1=l1.next;
}else{
curr.next=l2;
l2=l2.next;
}
curr = curr.next;
}
return dummy.next;
}
}
Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add an integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.
class MedianFinder {
//top
PriorityQueue<Integer> maxHeap;//smaller elements
//bottom
PriorityQueue<Integer> minHeap;//larger elements
public MedianFinder() {
this.minHeap = new PriorityQueue<>();
this.maxHeap = new PriorityQueue<>(Collections.reverseOrder());
}
//O(logn)
public void addNum(int num) {
if(maxHeap.isEmpty() || num <= maxHeap.peek()){
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
balance();
}
// O(1)
public double findMedian() {
if(minHeap.size() == maxHeap.size()){
return (double)(minHeap.peek() + maxHeap.peek()) / 2;
}
return (double) maxHeap.peek();
}
//O(logn)
//maxHeap.size = minHeap.size() || minHeap.size() + 1
private void balance(){
while(maxHeap.size() > minHeap.size() + 1){
minHeap.offer(maxHeap.poll());
}
while(minHeap.size() > maxHeap.size()){
maxHeap.offer(minHeap.poll());
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
