FB 电话面经

tm1234 发表于 2020-5-5 23:34
请问lz第一题先reverse在print面试官说这样做可以吗？

可以 zszszszs

rsm 发表于 2020-5-5 20:19
没明白。
请问如何对presum array进行binary search得到range值的上下边界？这个上下边界应该是在所有元 ...

不好意思说掉了，需要一个inorder array 和presum array。inorder array 搜index，presum直接擦sum

aprilcooper 发表于 2020-5-7 00:01
请注意看，是达到log(n)

算presum 不要O(n)?

aprilcooper 发表于 2020/05/07 00:03:26
不好意思说掉了，需要一个inorder array 和presum array。inorder array 搜index...

这个树是BST吗？如果不是，那得先sorted 吧，才能用二分查找？

徐小桃 发表于 2020-5-6 20:33
算presum 不要O(n)?

preprocess 一次就行了，rangesum作为API反复调用logn

aprilcooper 发表于 2020-5-8 13:14
preprocess 一次就行了，rangesum作为API反复调用logn

哦哦是这个意思

aprilcooper 发表于 2020/05/06 05:43:22
我觉得linkedlist那题要做到O(1) space O(n) time 还挺难的了啊。
range sum 那题...

O(1) space 就是不能Recursion了呗

aprilcooper 发表于 2020/05/06 05:43:22
我觉得linkedlist那题要做到O(1) space O(n) time 还挺难的了啊。
range sum 那题...

Preprocessing 不算复杂度是吗

楼主，请问 presum 是个数组吧 ？  怎么知道数组的长度？  因为开辟数组和binary search的时候都得知道这个长度是多少？ 面试官有说吗？

**PreProcessing**
PreProcess: Run time O(n) Space: O(n)
Find Range Sum Multiple Time: Run Time :O(logN)
```
class Solution {
    int sum = 0;
    List<Integer> prefixSum = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public int rangeSumBST(TreeNode root, int L, int R) {
        inOrder(root, L, R);
        int left = findIndex(L);
        int right = findIndex(R);
        int lowerBound = left == 0 ? 0 :prefixSum.get(left-1);
        return prefixSum.get(right) - lowerBound;
    }
   
    int findIndex(int L){
        int left = 0;
        int right = list.size();
        while(left<right){
            int mid = left + (right - left) /2 ;
            if(list.get(mid) == L) return mid;
            else if(list.get(mid)<L) left = mid +1;
            else right = mid;
        }
        return 0;
    }
    void inOrder(TreeNode root, int L, int R){
        if(root == null) return;
        
        inOrder(root.left, L, R);
        
        sum+=root.val;
        prefixSum.add(sum);
        list.add(root.val);
        
        inOrder(root.right, L, R);
    }
}
```