Stack
735. Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
陨石撞击，用栈模拟，关键是分析出来有几种情况。最后栈的情况一定是 - - - + + +。分析清楚栈顶元素的正负和当前元素的正负就能作出题。
public int[] asteroidCollision(int[] asteroids) {
// [- - - + + +]
if (asteroids == null) return new int[0];
Stack<Integer> stack = new Stack<>();
for (int num : asteroids) {
// peek element is +, num is -
while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -num) {
stack.pop();
}
// peek is negative,
if (stack.isEmpty() || num > 0 || stack.peek() < 0) {
stack.push(num);
}
if (num < 0 && stack.peek() == -num) {
stack.pop();
}
// skip
}
int[] res = new int[stack.size()];
int j = stack.size() - 1;
while (!stack.isEmpty()) {
res[j--] = stack.pop();
}
return res;
}
341. Flatten Nested List Iterator
In design
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
227. Basic Calculator II
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
用stack保存扫过的每一个数，遇到乘法pop出来，算过后再push回去。
这么做会带来一个问题：如何处理最后一个数，如何初始化lastopreator。
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
// 存每个数
Stack<Integer> stack = new Stack<>();
String temp = "";
// 初始化为+没想到，也是为了算最后一个数
char last_operator = '+';
// how to calculate the last number;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
temp = temp + c;
}
if (c != ' ' && !Character.isDigit(c) || i == s.length() - 1) {
int val = Integer.parseInt(temp);
temp = ""; // clear
if (last_operator == '+') {
stack.push(val);
} else if (last_operator == '-') {
stack.push(-val)''
} else if (last_operator == '*') {
stack.push(stack.pop() * val);
} else {
stack.push(stack.pop() / val);
}
last_operator = c;
}
}
int res = 0;
for (!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
Proprity Queue
// 从大到小排序
Comparator<Task> comparator = (t1, t2) -> t2.count - t1.count;
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
if (o1.val<o2.val)
return -1;
else if (o1.val==o2.val)
return 0;
else
return 1;
}
});
295. Find Median from Data Stream
[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 a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
用两个heap去做，一个最大堆（存数组中小的那部分）一个最小堆（存数组中大的那部分），两个堆里元素的数量最多相差1。进来元素先加入最小堆，再把最小值pop出来加入最大堆。这时候如果最大堆的元素个数多于最小堆，就pop出最大值加入最小堆。想到一分为二的处理数组。
class MedianFinder {
/** initialize your data structure here. */
PriorityQueue<Integer> max; // a max heap storing smaller half
PriorityQueue<Integer> min; // a min head storing larger half
public MedianFinder() {
min = new PriorityQueue<>();
max = new PriorityQueue<>(Collections.reverseOrder());
}
public void addNum(int num) {
min.offer(num);
max.offer(min.poll());
// shift to maintain the size difference no more than 1
if (max.size() > min.size()) {
min.offer(max.poll());
}
}
public double findMedian() {
if (min.size() == max.size()) {
return (max.peek() + min.peek()) / 2.0;
} else {
return min.peek();
}
}
}
621. Task Scheduler
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.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
算个数和给出真正的顺序是有差别的，不必纠结于先A还是先B，开始想复杂了。实际上每个坑有n+1个元素，从频率高到低从pq里poll出来填进坑里，如果pq里没任务了但计数器还没到n+1，就说明需要加idle。tempList的task如果freq大于1，再丢回pq
public class Solution {
public int leastInterval(char[] tasks, int n) {
// construct a priority queue
Comparator<Task> comparator = (t1, t2) -> t2.count - t1.count;
PriorityQueue<Task> queue = new PriorityQueue<>(tasks.length, comparator);
int[] temp = new int[26];
for (char c : tasks) {
temp[c - 'A'] += 1;
}
for (int i = 0; i < temp.length; i++) {
if (temp[i] > 0) {
Task task = new Task((char)(i + 'A'), temp[i]);
queue.add(task);
}
}
int res = 0;
while (!queue.isEmpty()) {
int k = n + 1;
List<Task> tempList = new ArrayList<>();
while (k > 0 && !queue.isEmpty()) {
Task t = queue.poll();
t.count = t.count - 1;
k--;
res++;
}
// copy
for (Task t1 : tempList) {
if (t1.count > 0)
queue.add(t1);
}
if (queue.isEmpty()) {
break;
}
res += k;
}
return res;
}
}
class Task {
char name;
int count;
public Task(char name, int count) {
this.name = name;
this.count = count;
}
}
Deque
272. Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
BST自然想到中序遍历，中序递归方便。根据题意需要维护一个size固定的数据结构，当新进来的值比数据结构里的值更满足条件时，removeFirst，所以想到用deque。(peekFirst, removeFirst)
注意的是linkedlist声明不能用范型。
注意else里的return，如果当前值都不能加入deque里，那么后面的值差的更多，更不能加入deque
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
// traverse the tree in in-order recursively
LinkedList<Integer> res = new LinkedList<>();
helper(root, target, k, res);
return res;
}
public void helper(TreeNode root, double target, int k, LinkedList<Integer> res) {
if (root == null) {
return;
}
helper(root.left, target, k, res);
// check the size of res
if (res.size() == k) {
if (Math.abs(root.val - target) < Math.abs(target - res.peekFirst())) {
res.removeFirst();
}
else {
return;
}
}
res.add(root.val);
helper(root.right, target, k, res);
}
}
239. Sliding Window Maximum
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Therefore, return the max sliding window as [3,3,5,5,6,7].
Find max value of each sliding window
用双端队列，LinkedList实现
队列里存index，不存值，
每进来一个新值，1）看是不是要poll出最老的元素 2）进来的新值如果比之前的值大，pollLast，poll到deque为空或者碰到比它大的值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0) {
return nums;
}
int[] result = new int[n - k + 1];
LinkedList<Integer> dq = new LinkedList<>();
for (int i = 0; i < n; i++) {
// peek, poll针对队头（最早进入的元素）
if (!dq.isEmpty() && dq.peek() < i - k + 1) {
dq.poll();
}
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offer(i);
if (i - k + 1 >= 0) {
result[i - k + 1] = nums[dq.peek()];
}
}
return result;
}
}
TreeMap
Treemap是有序的hashmap，基于red black tree实现，根据key排序。
get，put，containsKey是long(n)
- Entry
TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() - Key
firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()
floorKey(k1)是找比k1小于等于的里面最大的key
