HDOJ-1058 Humble Numbers - 可笑痴狂 - 博客园


HDOJ-1058 Humble Numbers - 可笑痴狂 - 博客园
Problem Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.

Write a program to find and print the nth element in this sequence

Input
The input consists of one or more test cases. Each test case consists of one integer n with 1 <= n <= 5842. Input is terminated by a value of zero (0) for n.

Output
For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.

Sample Input
1 2 3 4 11 12 13 21 22 23 100 1000 5842 0

Sample Output
The 1st humble number is 1. The 2nd humble number is 2. The 3rd humble number is 3. The 4th humble number is 4. The 11th humble number is 12. The 12th humble number is 14. The 13th humble number is 15. The 21st humble number is 28. The 22nd humble number is 30. The 23rd humble number is 32. The 100th humble number is 450. The 1000th humble number is 385875. The 5842nd humble number is 2000000000.

只能含有素数因子2或3或5或7的数为Humble Numbers,
则可知:Humble Numbers的2倍或者3倍或者5倍或者7倍仍然是Humble Numbers,所以依次在当前找到的Humble Numbers中
依次*2;*3;*5;*7依次找最小的向后递推。
网上说这是经典的DP-----状态转移方程:
 ans(k) = min(ans(m)*2, ans(n)*3, ansF(p)*5, ans(q)*7)  (k > m,n,p,q)
特别的: m,n,p,q 只有在本项被选中后才移动
我感觉这题就是利用数组的滚动递推推出来的。。。。。
13 void init()
14 {
15     ans[1] = 1;
16     int m, n, p, q;
17     m = n = p = q = 1;
18     for(int i = 2; i <= 5842; ++i)  // 题目要求只能含有素数因子2或3或5或7,所以只能用Humble Numbers为基数去*2;*3;*5或*7
19     {
20         ans[i] = min(ans[m]*2, min(ans[n]*3, min(ans[p]*5, ans[q]*7)));
21         if(ans[i] == ans[m] * 2)    // 注意四个 if 是并列的,可能存在重叠的情况,此时都要相应的增加,否则结果会重复
22             ++m;
23         if(ans[i] == ans[n] * 3)
24             ++n;
25         if(ans[i] == ans[p] * 5)
26             ++p;
27         if(ans[i] == ans[q] * 7)
28             ++q;
29     }
30 }
31 
32 void output(int n) 
33 {
34     printf("The %d", n);
35     int last = n%100;
36     if(last==13 || last==12 || last==11)
37     {
38         printf("th humble number is %d.\n", ans[n]);
39         return ;
40     }
41     last = n%10;
42     if(last == 1)
43         printf("st");
44     else if(last == 2)
45         printf("nd");
46     else if(last == 3)
47         printf("rd");
48     else
49         printf("th");
50     printf(" humble number is %d.\n", ans[n]);
51 }
Read full article from HDOJ-1058 Humble Numbers - 可笑痴狂 - 博客园

Isotonic Regression | Algorithms Notes


Isotonic Regression | Algorithms Notes
Given a sequence A of n integers, design an algorithm to find an non-decreasing sequence B of n integers, such that \sum_{i=1}^n |A_i - B_i| is minimized.
http://stackoverflow.com/questions/28149331/given-a-sequence-a1-a2-an-find-an-array-b1-b2-bn-s
Given a sequence a[1], a[2], ..., a[n], find an array b[1] < b[2] < ... < b[n] such that |a[1]-b[1]| + |a[2]-b[2]| + ... + |a[n]-b[n]| is minimum.
I have already come up with some observations, but I still couldn't figure out any feasible solution.
it is given that n <= 10^6.
The problem is from BOI 2003, and is called Sequence.
Input
9 4 8 20 14 15 18
Output
6 7 8 13 14 15 18
Since the difference is 13.

Solution:
This problem can be solved by minimum cost flow. Here we use dynamic programming.
Let F(k, z) be the optimal objective value for the first k elements with B[k] = z. Then, we have a recurrence relation: F(k, z) = min F(k-1, x) + |zA[k]|. Thus, the problem becomes how to efficiently find the z minimizing F(k, z) for all fixed k. It can be showed that F(k, z) is a piecewise linear convex function in z and the minimizing value must be in A. Thus, the dynamic programming can be speed up by using slope optimization and find the solution in O(n lg n) time.

令 F(kz) 為前 k 個元素且  B[k] = 時的最佳解之值。當給定 k ,我們可得一遞回關係式:F(kz) = min F(k-1, x) + |z – A[k]|。因此問題就變成如何快速的找出最小化 F(kz) 的 z 值。我們可以證明 F(kz) 對於 z 是一個 piecewise linear convex 函數 ,而且可以最小化 的 z 值必定在 A 中。因此使用動態規劃加上斜率最佳化可以在O(n lg n)時間內找到答案。

http://stackoverflow.com/questions/10460861/finding-an-increasing-sequence-a-which-minimizes-sigmaabsaici
Read full article from Isotonic Regression | Algorithms Notes

LeetCode 272 - Closest Binary Search Tree Value II


http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree_8.html
LIKE CODING: LeetCode [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)?
Hint:

  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.
X. Use Queue to store candidates, the elements in the queue are already stored
还有一种解法是直接在中序遍历的过程中完成比较,当遍历到一个节点时,如果此时结果数组不到k个,我们直接将此节点值加入res中,如果该节点值和目标值的差值的绝对值小于res的首元素和目标值差值的绝对值,说明当前值更靠近目标值,则将首元素删除,末尾加上当前节点值,反之的话说明当前值比res中所有的值都更偏离目标值,由于中序遍历的特性,之后的值会更加的遍历,所以此时直接返回最终结果即可
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        inorder(root, target, k, res);
        return res;
    }
    void inorder(TreeNode *root, double target, int k, vector<int> &res) {
        if (!root) return;
        inorder(root->left, target, k, res);
        if (res.size() < k) res.push_back(root->val);
        else if (abs(root->val - target) < abs(res[0] - target)) {
            res.erase(res.begin());
            res.push_back(root->val);
        } else return;
        inorder(root->right, target, k, res);
    }
这道题本身并不难,实际上考到了in order traversal的写法,也考到了BST被in order traversal出来的会是non descending order这个特点。我一开始是全部把traverse过的节点再放到heap里面取离target最近的k个点。然而并不需要那样麻烦,完全可以在traverse的过程中就一边找到最近的k个点。 我们始终控制LinkedList的size在k. 当size等于k的时候,还需要加入节点时我们就检查该节点和first element in the list 哪个离target更近,取近的留下。关于为什么要getFirst()取跟最开始放进去的元素比较,我是认为因为前面那些元素因为res.size() < k, 所以会无脑放进去,但很有可能他们离target是很远的,所以我们要从first开始比较

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        LinkedList<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curt = root;
        while (curt != null){
            stack.push(curt);
            curt = curt.left;
        }
        while (!stack.isEmpty()){
            curt = stack.pop();
            if (res.size() == k){
                if (Math.abs(curt.val - target) >= Math.abs(res.getFirst() - target)){
                    break;
                } else {
                    res.removeFirst();
                }
            }
            res.add(curt.val);
            if (curt.right != null){
                curt = curt.right;
                while (curt != null){
                    stack.push(curt);
                    curt = curt.left;
                }
            }
        }
        return res;
    }
X. O(logn+k) Two stacks
还有一种O(logn)的方法, 利用两个栈来保存target的前驱和后继, 而且栈顶的元素保存的是距离target最近的前驱和后继, 这样就可以每次取到距离target最近的值. 这种时间复杂度可以达到O(logn).
http://likesky3.iteye.com/blog/2239868
中序遍历结果是将树中元素从小到大排列,逆式的中序遍历即先遍历右子树再访问根节点最后遍历左子树会得到树中元素从大到小排列的结果,因此可通过中序遍历获取最接近target节点的perdecessors,通过逆中序遍历获取最接近target节点的successors,然后merge perdecessors 和 successors 获取最接近target节点的 k个节点值。 
注意到在中序遍历时遇到比target 大的节点即停止,因为由BST的性质可知后面的元素均会比target 大,即所有target的predecessors均已找到,同理逆中序遍历时遇到不大于 target的节点即可停止递归。 
http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree_8.html
  1.     public List<Integer> closestKValues(TreeNode root, double target, int k) {  
  2.         List<Integer> result = new ArrayList<Integer>();  
  3.         LinkedList<Integer> stackPre = new LinkedList<Integer>();  
  4.         LinkedList<Integer> stackSucc = new LinkedList<Integer>();  
  5.         inorder(root, target, false, stackPre);  
  6.         inorder(root, target, true, stackSucc);  
  7.         while (k-- > 0) {  
  8.             if (stackPre.isEmpty()) {  
  9.                 result.add(stackSucc.pop());  
  10.             } else if (stackSucc.isEmpty()) {  
  11.                 result.add(stackPre.pop());  
  12.             } else if (Math.abs(stackPre.peek() - target) < Math.abs(stackSucc.peek() - target)) {  
  13.                 result.add(stackPre.pop());  
  14.             } else {  
  15.                 result.add(stackSucc.pop());  
  16.             }  
  17.         }  
  18.         return result;  
  19.     }  
  20.     public void inorder(TreeNode root, double target, boolean reverse, LinkedList<Integer> stack) {  
  21.         if (root == nullreturn;  
  22.         inorder(reverse ? root.right : root.left, target, reverse, stack);  
  23.         if ((reverse && root.val <= target) || (!reverse && root.val > target))  
  24.             return;  
  25.         stack.push(root.val);  
  26.         inorder(reverse ? root.left : root.right, target, reverse, stack);  
  27.     } 
http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree_8.html
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
         
        Stack<Integer> precedessor = new Stack<>();
        Stack<Integer> successor = new Stack<>();
         
        getPredecessor(root, target, precedessor);
        getSuccessor(root, target, successor);
         
        for (int i = 0; i < k; i++) {
            if (precedessor.isEmpty()) {
                result.add(successor.pop());
            } else if (successor.isEmpty()) {
                result.add(precedessor.pop());
            } else if (Math.abs((double) precedessor.peek() - target) < Math.abs((double) successor.peek() - target)) {
                result.add(precedessor.pop());
            } else {
                result.add(successor.pop());
            }
        }
         
        return result;
    }
     
    private void getPredecessor(TreeNode root, double target, Stack<Integer> precedessor) {
        if (root == null) {
            return;
        }
         
        getPredecessor(root.left, target, precedessor);
         
        if (root.val > target) {
            return;
        }
         
        precedessor.push(root.val);
         
        getPredecessor(root.right, target, precedessor);
    }
     
    private void getSuccessor(TreeNode root, double target, Stack<Integer> successor) {
        if (root == null) {
            return;
        }
         
        getSuccessor(root.right, target, successor);
         
        if (root.val <= target) {
            return;
        }
         
        successor.push(root.val);
         
        getSuccessor(root.left, target, successor);
    }

X.
https://leetcode.com/discuss/55486/java-two-stacks-iterative-solution
public List<Integer> closestKValues(TreeNode root, double target, int k) { Deque<TreeNode> bigger = new ArrayDeque<TreeNode>(); Deque<TreeNode> smaller = new ArrayDeque<TreeNode>(); TreeNode node = root; // log(n) while(node != null) { if(node.val > target) { bigger.push(node); node = node.left; } else { smaller.push(node); node = node.right; } } // k List<Integer> ret = new ArrayList<Integer>(); while(ret.size() < k) { if(bigger.isEmpty() || !smaller.isEmpty() && ((bigger.peek().val - target) > (target - smaller.peek().val))) { node = smaller.pop(); ret.add(node.val); // Get next smaller node = node.left; while(node != null) { smaller.push(node); node = node.right; } } else { node = bigger.pop(); ret.add(node.val); // get next bigger node = node.right; while(node != null) { bigger.push(node); node = node.left; } } } return ret; }
https://discuss.leetcode.com/topic/30597/java-5ms-iterative-following-hint-o-klogn-time-and-space
Following the hint, I use a predecessor stack and successor stack. I do a logn traversal to initialize them until I reach the null node. Then I use the getPredecessor and getSuccessor method to pop k closest nodes and update the stacks.
Time complexity is O(klogn), since k BST traversals are needed and each is bounded by O(logn) time. Note that it is not O(logn + k) which is the time complexity for k closest numbers in a linear array.
Space complexity is O(klogn), since each traversal brings O(logn) new nodes to the stack.

https://discuss.leetcode.com/topic/23151/o-logn-java-solution-with-two-stacks-following-hint/10
https://discuss.leetcode.com/topic/39192/java-o-logn-k-two-stacks-solution-w-improvement
My solution is inspired by following link. I gave all the credit to that post.
https://leetcode.com/discuss/55682/o-logn-java-solution-with-two-stacks-following-hint
However, I did some improvement, dealing with the case that target is a whole name like 12.0 and in the bst, there is also a node with int value of 12.
In the original post, the author put node 12 input both stacks and use if(!succ.isEmpty() && !pred.isEmpty() && succ.peek().val == pred.peek().val) {
getNextPredecessor(pred);
}
to get rid of the duplicate. My approach is to prevent the duplicate node being added into both stack in the first place. The predecessor stack only allows nodes strictly smaller than targetInt. So 12 is added only to successor stack.
2nd the double type target is rounded to nearest int targetInt and is used to compare. In original post.
if(root.val == target) is not a good idea to check if a double is equal to an int. Double has precision issue.
So I think it is better just to compare int with int by rounding target first.
The space complexity is O(logn + k) depending on if k is bigger or not. Runtime is also O(logn + k), as the initialization of stack takes O(logn), after that getting each next successor or predecessor takes O(1) most likely. Sometimes it takes more if you need to push left part into stack. but that can be accounted to logn. part..
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        int targetInt = (int) Math.round(target); // round target to the nearest int
        List<Integer> closestValues = new ArrayList<>();
        Stack<TreeNode> predecessors = new Stack<>();
        Stack<TreeNode> successors = new Stack<>();
        initializeSucc(successors, root, targetInt);
        initializePred(predecessors, root, targetInt);
        int pred, succ;
        while (k > 0) {
            if (successors.isEmpty()) {
                closestValues.add(getPredecessor(predecessors));
            } else if (predecessors.isEmpty()) {
                closestValues.add(getSuccessor(successors));
            } else {
                pred = predecessors.peek().val;
                succ = successors.peek().val;
                if (succ - target < target - pred) {
                    closestValues.add(getSuccessor(successors));
                } else {
                    closestValues.add(getPredecessor(predecessors));
                }
            }
            k--;
        }
        return closestValues;
    }
    // search from root, push all nodes >= target in stack 
    private void initializeSucc(Stack<TreeNode> successors, TreeNode root, int target) {
        while (root != null) {
            if (root.val > target) {
                successors.push(root);
                root = root.left;
            } else if (root.val < target) {
                root = root.right;
            } else {
                successors.push(root);
                break; // if targetInt is found, stop as its right child will be pushed into stack next time
            }
        }
    }
    // push nodes that are strictly less than targetInt
    private void initializePred(Stack<TreeNode> predecessors, TreeNode root, int target) {
        while (root != null) {
            if (root.val < target) {
                predecessors.push(root);
                root = root.right;
            } else {
                root = root.left;
            }
        }
    }
    private int getPredecessor(Stack<TreeNode> predecessors) {
        TreeNode nextPred = predecessors.pop();
        TreeNode root = nextPred.left;
        while (root != null) {
            predecessors.push(root);
            root = root.right;
        }
        return nextPred.val;
    }
    
    
    private int getSuccessor(Stack<TreeNode> successors) {
        TreeNode nextSucc = successors.pop();
        TreeNode root = nextSucc.right;
        while (root != null) {
            successors.push(root);
            root = root.left;
        }
        return nextSucc.val;
    }
X. Use Deque
http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree_8.html
Brute-force solution:
The straight-forward solution would be to use a heap. We just treat the BST just as a usual array and do a in-order traverse. Then we compare the current element with the minimum element in the heap, the same as top k problem.

http://www.cnblogs.com/yrbbest/p/5031304.html
我们可以使用in-order的原理,从最左边的元素开始,维护一个Deque或者doubly linked list,将这个元素的值从后端加入到Deque中,然后继续遍历下一个元素。当Deque的大小为k时, 比较当前元素和队首元素与target的差来尝试更新deque。循环结束条件是队首元素与target的差更小或者遍历完全部元素。这样的话时间复杂度是O(n), 空间复杂度应该是O(k)。
Time Complexity - O(n), Space Complexity - O(k)
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        LinkedList<Integer> res = new LinkedList<>();
        inOrder(root, target, k, res);
        return res;
    }
    
    private void inOrder(TreeNode root, double target, int k, LinkedList<Integer> res) {
        if(root == null) {
            return;
        }
        inOrder(root.left, target, k, res);
        if(res.size() == k) {
            if(Math.abs(res.get(0) - target) >= Math.abs(root.val - target)) {
                res.removeFirst();
                res.add(root.val);
            } else {
                return;
            }
        } else {
            res.add(root.val);
        }
        inOrder(root.right, target, k, res);
    }
https://segmentfault.com/a/1190000003797291
二叉搜索树的中序遍历就是顺序输出二叉搜索树,所以我们只要中序遍历二叉搜索树,同时维护一个大小为K的队列,前K个数直接加入队列,之后每来一个新的数(较大的数),如果该数和目标的差,相比于队头的数离目标的差来说,更小,则将队头拿出来,将新数加入队列。如果该数的差更大,则直接退出并返回这个队列,因为后面的数更大,差值也只会更大。
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Queue<Integer> klist = new LinkedList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        // 迭代中序遍历二叉搜索树的代码
        while(root != null){
            stk.push(root);
            root = root.left;
        }
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            // 维护一个大小为k的队列
            // 队列不到k时直接加入
            if(klist.size() < k){
                klist.offer(curr.val);
            } else {
            // 队列到k时,判断下新的数是否更近,更近就加入队列并去掉队头
                int first = klist.peek();
                if(Math.abs(first - target) > Math.abs(curr.val - target)){
                    klist.poll();
                    klist.offer(curr.val);
                } else {
                // 如果不是更近则直接退出,后面的数只会更大
                    break;
                }
            }
            // 中序遍历的代码
            if(curr.right != null){
                curr = curr.right;
                while(curr != null){
                    stk.push(curr);
                    curr = curr.left;
                }
            }
        }
        // 强制转换成List,是用LinkedList实现的所以可以转换
        return (List<Integer>)klist;
    }
X. O(n) https://discuss.leetcode.com/topic/30081/java-in-order-traversal-1ms-solution
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        closestKValuesHelper(list, root, target, k);
        return list;
    }
    
    /**
     * @return <code>true</code> if result is already found.
     */
    private boolean closestKValuesHelper(LinkedList<Integer> list, TreeNode root, double target, int k) {
        if (root == null) {
            return false;
        }
        
        if (closestKValuesHelper(list, root.left, target, k)) {
            return true;
        }
        
        if (list.size() == k) {
            if (Math.abs(list.getFirst() - target) < Math.abs(root.val - target)) {
                return true;
            } else {
                list.removeFirst();
            }
        }
        
        list.addLast(root.val);
        return closestKValuesHelper(list, root.right, target, k);
    }

X. Using Heap/PriorityQueue
在来看一种利用最大堆来解题的方法,堆里保存的一个差值diff和节点值的pair,我们中序遍历二叉树(也可以用其他遍历方法),然后对于每个节点值都计算一下和目标值之差的绝对值,由于最大堆的性质,diff大的自动拍到最前面,我们维护k个pair,如果超过了k个,就把堆前面大的pair删掉,最后留下的k个pair,我们将pair中的节点值取出存入res中返回即可

Brute-force solution:
The straight-forward solution would be to use a heap. We just treat the BST just as a usual array and do a in-order traverse. Then we compare the current element with the minimum element in the heap, the same as top k problem.
The time complexity would be O(k + (n - k) logk). 
Space complexity is O(k).

private PriorityQueue<Integer> minPQ;
private int count = 0;
public List<Integer> closestKValues(TreeNode root, double target, int k) {
    minPQ = new PriorityQueue<Integer>(k);
    List<Integer> result = new ArrayList<Integer>();
   
    inorderTraverse(root, target, k);
   
    // Dump the pq into result list
    for (Integer elem : minPQ) {
        result.add(elem);
    }
   
    return result;
}

private void inorderTraverse(TreeNode root, double target, int k) {
    if (root == null) {
        return;
    }
   
    inorderTraverse(root.left, target, k);
   
    if (count < k) {
        minPQ.offer(root.val);
    } else {
        if (Math.abs((double) root.val - target) < Math.abs((double) minPQ.peek() - target)) {
            minPQ.poll();
            minPQ.offer(root.val);
        }
    }
    count++;
   
    inorderTraverse(root.right, target, k);
}
http://blog.csdn.net/xudli/article/details/48752907
prefix traverse. 同时维护一个大小为k的 max heap. 注意根据bst的性质,在diff 大于 maxHeap时, 可以只遍历一边的子树. 
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Double> maxHeap = new PriorityQueue<Double>(k, new Comparator<Double>() { 
            @Override
            public int compare(Double x, Double y) {
                return (int)(y-x);
            }
        });
        Set<Integer> set = new HashSet<Integer>();
        
        rec(root, target, k, maxHeap, set);
        
        return new ArrayList<Integer>(set);
    }
    
    private void rec(TreeNode root, double target, int k, PriorityQueue<Double> maxHeap, Set<Integer> set) {
        if(root==null) return;
        double diff = Math.abs(root.val-target);
        if(maxHeap.size()<k) {
            maxHeap.offer(diff);
            set.add(root.val);
        } else if( diff < maxHeap.peek() ) {
            double x = maxHeap.poll();
            if(! set.remove((int)(target+x))) set.remove((int)(target-x));
            maxHeap.offer(diff);
            set.add(root.val);
        } else {
            if(root.val > target) rec(root.left, target, k, maxHeap,set);
            else rec(root.right, target, k, maxHeap, set);
            return;
        }
        rec(root.left, target, k, maxHeap, set);
        rec(root.right, target, k, maxHeap, set);
    }

http://www.cnblogs.com/jcliBlogger/p/4771342.html
http://blog.csdn.net/xudli/article/details/48752907
There is a very simple idea to keep a max heap of size k and elements in the heap are sorted by their absolute difference from target. For the max heap, we will simply use the default priority_queue. Then we simply traverse the tree and push all its nodes to the heap while maintaining the size of heap not larger than k.
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        priority_queue<pair<double, int>> que;
        dfs(root, target, k, que);
        vector<int> ret;
        while(!que.empty()){
            ret.push_back(que.top().second);
            que.pop();
        }
        return ret;
    }
    void dfs(TreeNode* root, double target, int k, priority_queue<pair<double, int>> &que){
        if(!root) return;
        que.push(pair<double, int>(abs(target-root->val), root->val));
        if(que.size()>k) que.pop();
        dfs(root->left, target, k, que);
        dfs(root->right, target, k, que);
    }
http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree_8.html
The straight-forward solution would be to use a heap. We just treat the BST just as a usual array and do a in-order traverse. Then we compare the current element with the minimum element in the heap, the same as top k problem.
    private PriorityQueue<Integer> minPQ;
    private int count = 0;
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        minPQ = new PriorityQueue<Integer>(k);
        List<Integer> result = new ArrayList<Integer>();
         
        inorderTraverse(root, target, k);
         
        // Dump the pq into result list
        for (Integer elem : minPQ) {
            result.add(elem);
        }
         
        return result;
    }
     
    private void inorderTraverse(TreeNode root, double target, int k) {
        if (root == null) {
            return;
        }
         
        inorderTraverse(root.left, target, k);
         
        if (count < k) {
            minPQ.offer(root.val);
        } else {
            if (Math.abs((double) root.val - target) < Math.abs((double) minPQ.peek() - target)) {
                minPQ.poll();
                minPQ.offer(root.val);
            }
        }
        count++;
         
        inorderTraverse(root.right, target, k);
    }
X. A time linear solution:
https://www.cnblogs.com/lightwindy/p/d.html
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
         
        Stack<Integer> precedessor = new Stack<>();
        Stack<Integer> successor = new Stack<>();
         
        getPredecessor(root, target, precedessor);
        getSuccessor(root, target, successor);
         
        for (int i = 0; i < k; i++) {
            if (precedessor.isEmpty()) {
                result.add(successor.pop());
            } else if (successor.isEmpty()) {
                result.add(precedessor.pop());
            } else if (Math.abs((double) precedessor.peek() - target) < Math.abs((double) successor.peek() - target)) {
                result.add(precedessor.pop());
            } else {
                result.add(successor.pop());
            }
        }
         
        return result;
    }
     
    private void getPredecessor(TreeNode root, double target, Stack<Integer> precedessor) {
        if (root == null) {
            return;
        }
         
        getPredecessor(root.left, target, precedessor);
         
        if (root.val > target) {
            return;
        }
         
        precedessor.push(root.val);
         
        getPredecessor(root.right, target, precedessor);
    }
     
    private void getSuccessor(TreeNode root, double target, Stack<Integer> successor) {
        if (root == null) {
            return;
        }
         
        getSuccessor(root.right, target, successor);
         
        if (root.val <= target) {
            return;
        }
         
        successor.push(root.val);
         
        getSuccessor(root.left, target, successor);
    }
Your time linear solution is unnecessarily complicated. You are using O(N) space with those two stacks.
A simple solution with same time and space complexity of O(N) is:
1. Store InOrder traversal of the BST in an array. O(N) space and time
2. Find the element closest to target in the inorder array.(can be implemented in O(logn) using binary search variation or just traverse the array in O(N).
3. From the closest value in the array move left or right depending on which is closer similarly to what you have done with those two stacks. O(K)

https://discuss.leetcode.com/topic/22940/ac-clean-java-solution-using-two-stacks
The idea is to compare the predecessors and successors of the closest node to the target, we can use two stacks to track the predecessors and successors, then like what we do in merge sort, we compare and pick the closest one to the target and put it to the result list.
As we know, inorder traversal gives us sorted predecessors, whereas reverse-inorder traversal gives us sorted successors.
We can use iterative inorder traversal rather than recursion, but to keep the code clean, here is the recursion version.
public List<Integer> closestKValues(TreeNode root, double target, int k) {
  List<Integer> res = new ArrayList<>();

  Stack<Integer> s1 = new Stack<>(); // predecessors
  Stack<Integer> s2 = new Stack<>(); // successors

  inorder(root, target, false, s1);
  inorder(root, target, true, s2);
  
  while (k-- > 0) {
    if (s1.isEmpty())
      res.add(s2.pop());
    else if (s2.isEmpty())
      res.add(s1.pop());
    else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target))
      res.add(s1.pop());
    else
      res.add(s2.pop());
  }
  
  return res;
}

// inorder traversal
void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
  if (root == null) return;

  inorder(reverse ? root.right : root.left, target, reverse, stack);
  // early terminate, no need to traverse the whole tree
  if ((reverse && root.val <= target) || (!reverse && root.val > target)) return;
  // track the value of current node
  stack.push(root.val);
  inorder(reverse ? root.left : root.right, target, reverse, stack);
}
下面的这种方法用了两个栈,pre和suc,其中pre存小于目标值的数,suc存大于目标值的数,开始初始化pre和suc的时候,要分别将最接近目标值的稍小值和稍大值压入pre和suc,然后我们循环k次,每次比较pre和suc的栈顶元素,看谁更接近目标值,将其存入结果res中,然后更新取出元素的栈,依次类推直至取完k个数返回即可
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        stack<TreeNode*> pre, suc;
        while (root) {
            if (root->val <= target) {
                pre.push(root);
                root = root->right;
            } else {
                suc.push(root);
                root = root->left;
            }
        }
        while (k-- > 0) {
            if (suc.empty() || !pre.empty() && target - pre.top()->val < suc.top()->val - target) {
                res.push_back(pre.top()->val);
                getPredecessor(pre);
            } else {
                res.push_back(suc.top()->val);
                getSuccessor(suc);
            }
        }
        return res;
    }
    void getPredecessor(stack<TreeNode*> &pre) {
        TreeNode *t = pre.top(); pre.pop();
        if (t->left) {
            pre.push(t->left);
            while (pre.top()->right) pre.push(pre.top()->right);
        }
    }
    void getSuccessor(stack<TreeNode*> &suc) {
        TreeNode *t = suc.top(); suc.pop();
        if (t->right) {
            suc.push(t->right);
            while (suc.top()->left) suc.push(suc.top()->left);
        }
    }

https://github.com/kamyu104/LeetCode/blob/master/Python/closest-binary-search-tree-value-ii.py
https://leetcode.com/discuss/oj/closest-binary-search-tree-value-ii
X. https://www.cnblogs.com/grandyang/p/5247398.html
那道题只让我们找出离目标值最近的一个节点值,而这道题让我们找出离目标值最近的k个节点值,难度瞬间增加了不少,我最先想到的方法是用中序遍历将所有节点值存入到一个一维数组中,由于二分搜索树的性质,这个一维数组是有序的,然后我们再在有序数组中需要和目标值最近的k个值就简单的多
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res, v;
        inorder(root, v);
        int idx = 0;
        double diff = numeric_limits<double>::max();
        for (int i = 0; i < v.size(); ++i) {
            if (diff >= abs(target - v[i])) {
                diff = abs(target - v[i]);
                idx = i;
            }
        }
        int left = idx - 1, right = idx + 1;
        for (int i = 0; i < k; ++i) {
            res.push_back(v[idx]);
            if (left >= 0 && right < v.size()) {
                if (abs(v[left] - target) > abs(v[right] - target)) {
                    idx = right;
                    ++right;
                } else {
                    idx = left;
                    --left;
                }
            } else if (left >= 0) {
                idx = left;
                --left;
            } else if (right < v.size()) {
                idx = right;
                ++right;
            }
        }
        return res;
    }
    void inorder(TreeNode *root, vector<int> &v) {
        if (!root) return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    }

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts