such a genius
NathanNi
@NathanNi
Posts made by NathanNi

2 concise Java Solutions (O(n) and O(n2)) with using BST's feature (Not the old generic solution for Binary Tree)
Idea:
We are given a BST, so it is possible to reconstruct the tree by using PreOrder traverse array.Notice we have 1 requirement "The encoded string should be as compact as possible." So let us forget the generic BFS/DFS solution for Binary Tree (Adding "#" or "NULL" for empty node)
Serialize:
Very straightforward, simplify do a preorder traverse and append to String. Version 1: Two lines
public String serialize(TreeNode root) { if (root == null) return ""; return root.val + "," + serialize(root.left) + serialize(root.right); }
 Version 2: Use StringBuilder to save a little bit time.
public String serialize(TreeNode root) { if (root == null) return ""; StringBuilder sb = new StringBuilder(); sb.append(root.val).append(","); sb.append(serialize(root.left)); sb.append(serialize(root.right)); return sb.toString(); }
Deserialize
Since we have a preorder array. We always know the first element is the root.
So our strategy is to cut the array into different parts by appyling BST feature. Version 1: O(N2)
1.Passing start bound and end bound to helper function, which means to reconstruct tree in this scope (start ~ end).
2.Find the first element larger than current root, the first element index will be the middle cutting point. Which means all elements left to it need to be the root.left, all elements right after it need to be root.right. Recursively call the helper function.
public TreeNode deserialize(String data) { if (data == null  data.length() == 0) return null; String[] sArr = data.split(","); return helper(sArr, 0, sArr.length  1); } public TreeNode helper(String[] sArr, int start, int end) { if (start > end) return null; if (start == end) return new TreeNode(Integer.parseInt(sArr[start])); TreeNode node = new TreeNode(Integer.parseInt(sArr[start])); int mid = start + 1; while (mid <= end) { if (Integer.parseInt(sArr[mid]) > Integer.parseInt(sArr[start])) { break; } mid++; } node.left = helper(sArr, start + 1, mid  1); node.right = helper(sArr, mid, end); return node; }
 Version 2: O(N)
1.Similar id to @cccrrryyy 's solution: https://discuss.leetcode.com/topic/66495/usinglowerboundandupperboundtodeserializebst
2.Pass a min value (low bound) and a max value (high bound) to helper function.
3.I use int[] currIdx to simulate a static index variable, cuz I really don't like using a static/member/global variable.
public TreeNode deserialize(String data) { if (data == null  data.length() == 0) return null; String[] sArr = data.split(","); int[] currIdx = {0}; return helper(sArr, currIdx, Integer.MIN_VALUE, Integer.MAX_VALUE); } public TreeNode helper(String[] sArr, int[] currIdx, int min, int max) { if (currIdx[0] > sArr.length  1) return null; int curr = Integer.parseInt(sArr[currIdx[0]]); if (curr < min  curr > max) return null; TreeNode node = new TreeNode(curr); currIdx[0]++; node.left = helper(sArr, currIdx, min, curr); node.right = helper(sArr, currIdx, curr, max); return node; }

RE: Java SweepLine Solution O(nlogn)
@scheung Thank you, you are right. I modified my code to delete unused lines.

Java SweepLine Solution O(nlogn)
 wrapper class: Point
 value
 flag: 1 indicates start, 2 indicates end
 index: original pos in intervals array
 Comparable: sort by value ascending, end in front of start if they have same value.

Iterate intervals array and fill a points list, then sort it

Iterate points list, since the sequence will be "order by position, and end will come before start".
 whenever meet a end point, keep a list(prevIdxs) before next start, save original index of curr interval to the list.
 whenever meet a start point, this start point is the right interval to the intervals in the list (prevIdxs). Take out each index in it and update to result.
class Point implements Comparable<Point>{ int val; int flag; //1 start, 0 end int index; public Point(int val, int flag, int index) { this.val = val; this.flag = flag; this.index = index; } public int compareTo(Point o) { if (this.val == o.val) return this.flag  o.flag; //end in front of start return this.val  o.val; } } public int[] findRightInterval(Interval[] intervals) { if (intervals == null  intervals.length == 0) return new int[]{}; int[] res = new int[intervals.length]; Arrays.fill(res, 1); List<Point> points = new ArrayList<>(); for (int i = 0; i < intervals.length; i++) { points.add(new Point(intervals[i].start, 1, i)); points.add(new Point(intervals[i].end, 0, i)); } Collections.sort(points); List<Integer> prevIdxs = new ArrayList<>(); for (Point point: points) { if (point.flag == 1) { for (Integer prevIdx: prevIdxs) { res[prevIdx] = point.index; } prevIdxs = new ArrayList<>(); } else { prevIdxs.add(point.index); } } return res; }
 wrapper class: Point

Java O(nlogn) very easy solution
 Sort Intervals by end.
 Count valid intervals (nonoverlapping).
 Answer is len  count
public int eraseOverlapIntervals(Interval[] intervals) { if (intervals == null  intervals.length == 0) return 0; Arrays.sort(intervals, new Comparator<Interval>() { public int compare(Interval o1, Interval o2) { return o1.end  o2.end; } }); int count = 1; int last = 0; for (int i = 1; i < intervals.length; i++) { if (intervals[last].end <= intervals[i].start) { count++; last = i; } } return intervals.length  count; }

RE: Is this problem a joke?
Not sure if the question is joke, but your coding format is a joke.

RE: Very easy 1 pass Stack Solution in JAVA (NO STRING CONCAT)
@forestschao
Yeah, thank you, you bring out a good point.
Only for this case, we have the constraint in requirement so I didn't implement this.
"2. Each number will contain only one digit. " 
RE: Shortest/Concise JAVA O(n) Sliding Window Solution
@StefanPochmann hahah, you got my lazy point.

RE: Shortest/Concise JAVA O(n) Sliding Window Solution
You are right,
we can use int[128] instead of int[256].
I was thinking about extended ascii ( 0 ~ 256), but it doesn't apply to this problem.actually for this specific case, if we are given all lower case alphabets.
int[26] is enough.
Just do hash[c  'a'] every time. 
Concise/Easytounderstand Java 5ms solution with Explaination
Original idea comes from
http://bookshadow.com/weblog/2016/10/24/leetcodekthsmallestinlexicographicalorder/Actually this is a denary tree (each node has 10 children). Find the kth element is to do a k steps preorder traverse of the tree.
Initially, image you are at node 1 (variable: curr),
the goal is move (k  1) steps to the target node x. (substract steps from k after moving)
when k is down to 0, curr will be finally at node x, there you get the result.we don't really need to do a exact k steps preorder traverse of the denary tree, the idea is to calculate the steps between curr and curr + 1 (neighbor nodes in same level), in order to skip some unnecessary moves.
Main function
Firstly, calculate how many steps curr need to move to curr + 1.
if the steps <= k, we know we can move to curr + 1, and narrow down k to k  steps.

else if the steps > k, that means the curr + 1 is actually behind the target node x in the preorder path, we can't jump to curr + 1. What we have to do is to move forward only 1 step (curr * 10 is always next preorder node) and repeat the iteration.
calSteps function

how to calculate the steps between curr and curr + 1?
Here we come up a idea to calculate by level.
Let n1 = curr, n2 = curr + 1.
n2 is always the next right node beside n1's right most node (who shares the same ancestor "curr")
(refer to the pic, 2 is right next to 1, 20 is right next to 19, 200 is right next to 199). 
so, if n2 <= n, what means n1's right most node exists, we can simply add the number of nodes from n1 to n2 to steps.

else if n2 > n, what means n (the biggest node) is on the path between n1 to n2, add (n + 1  n1) to steps.

organize this flow to "steps += Math.min(n + 1, n2)  n1; n1 *= 10; n2 *= 10;"
Here is the code snippet:
public int findKthNumber(int n, int k) { int curr = 1; k = k  1; while (k > 0) { int steps = calSteps(n, curr, curr + 1); if (steps <= k) { curr += 1; k = steps; } else { curr *= 10; k = 1; } } return curr; } //use long in case of overflow public int calSteps(int n, long n1, long n2) { int steps = 0; while (n1 <= n) { steps += Math.min(n + 1, n2)  n1; n1 *= 10; n2 *= 10; } return steps; }
