facebook onsite

yuxrose 发表于 2015-4-3 10:23
map的key是字母，value是最新的index, 一边扫一边update index, cooldown就是k.
有大神能想想O(1)怎么做 ...

既然K是常数了，那么你的方法用到的hashmap也可以理解为常数空间

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

各位觉得第一题是这个意思吗?

class FindSmallPath {
    public List<Integer> find(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }

        List<Integer> left = find(root.left);
        List<Integer> right = find(root.right);

        res.add(root.val);
        if(arraySmaller(left, right)) {
            res.addAll(left);
        } else {
            res.addAll(right);
        }
        Arrays.sort(res);
        return res;
    }

    private boolean arraySmaller(List<Integer> left, List<Integer> right) {
        int i = 0;
        int j = 0;
        while(i < left.size() && j < right.size()) {
            if(left.get(i) < right.get(j)) {
                return true;
            } else if(left.get(i) > right.get(j)) {
                return false;
            } else {
                i++;
                j++;
            }
        }
        return i == left.size();
    }
}

sonicgu 发表于 2015-4-3 05:47
献丑写个第二个吧, 水平有限，应该不是最好的解法
class TreeNode
{

这代码没有考虑树的值可能相同的情况啊

TreeNode dfs(TreeNode root) {}

sonicgu 发表于 2015-4-2 15:47
献丑写个第二个吧, 水平有限，应该不是最好的解法
class TreeNode
{

这个解法不对吧 考虑这个tree
     5
    /  \
   3   10
  / \   /
1  7 1
会return 5 10 1 但答案应该是5 3 1
而且每次addAll就是depth ^ 2 时间复杂度了 还不如把一条path上的数放一起sort呢 才depth * log(depth)

这个题好难啊

非常感谢 不过看不懂后面的内容