bb新鲜面经 哎。。

ld_xixi 发表于 2017-10-31 13:36
难道我没有理解你的题意？ 如果是string的话，这里val就是个字符串， 然后比较字符串第一个字符的ascii嘛 ...

不好意思 我有点脑抽， 对 string的话就是比较2个string的字符序，java的话就是用CompareTo，

ld_xixi 发表于 2017-10-31 13:34
validate BST,是LC的原题啊亲， LC98
        if(root == null) return true;
        TreeNode prev = ...

不好意思可能我没说明白，首先我知道这是lc原题呀，其次用stack的话也行，是另一种解法。 我一开始用我说的这种给解法是因为如果val是int类型的话，我感觉这种解法的代码更简洁，然后出follow up改成string的话，也不太好把整个代码删了重新换另一个解法，我就接着用这种解法了。 我的意思是，用stack的话，也得用compareTo（）去比较node的val值吧（如果是string类型）。 你说的“如果是string的话，这里val就是个字符串， 然后比较字符串第一个字符的ascii”，我有点没懂。。 比较string的话，不是用compareTo（）去比较嘛。。 很多字符串比如 “aaaaa”和“aaaab”前面都有很多位是相同的呀，怎么只通过比较第一次char的ascii来得知结果呢？ 可能是我蠢，不知道比较string还有你说的这种方法，你能用代码写出来我看看嘛 学习一下
然后面试的时候我的方法是这么写的，感觉比stack简洁一些。
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(Long.MIN_VALUE, Long.MAX_VALUE, root);
    }
    public boolean helper(long left, long right, TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.val <= left || root.val >= right) {
            return false;
        }
        return helper(left, root.val, root.left) && helper(root.val, right, root.right);
    }
}
以及改成string后：
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(null, null, root);
    }
    public boolean helper(String left, String right, TreeNode root) {
        if (root == null) {
            return true;
        }
        if (left != null && root.val.compareTo(left) < 0) {
            return false;
        }
        if (right != null && root.val.compareTo(right) > 0) {
            return false;
        }
        return helper(left, root.val, root.left) && helper(root.val, right, root.right);
    }
}

ld_xixi 发表于 2017-10-31 13:40
不好意思 我有点脑抽， 对 string的话就是比较2个string的字符序，java的话就是用CompareTo，

啊。。我发上一个回复之前 没看到你这条回复。。我也脑抽了。。

FF-Ti 发表于 2017-10-31 20:37
啊。。我发上一个回复之前 没看到你这条回复。。我也脑抽了。。

放心好了肯定能过， 安心等onsite吧，大晚上回帖子确实比较容易脑抽

什么叫初始边界用null，不是很明白，楼主可以解释一下么，还有是需要自己写main函数来跑么，最后问的bq又是什么？

ld_xixi 发表于 2017-11-1 00:37
放心好了肯定能过， 安心等onsite吧，大晚上回帖子确实比较容易脑抽

嗯嗯，借你吉言啦，希望有onsite

luyuzhuangdeyez 发表于 2017-11-1 01:33
什么叫初始边界用null，不是很明白，楼主可以解释一下么，还有是需要自己写main函数来跑么，最后问的bq又是 ...

你看我楼上贴的代码应该就能看懂啦。 bq问了 why bb， bb是干啥的，就这两个。

FF-Ti 发表于 2017-11-1 01:42
你看我楼上贴的代码应该就能看懂啦。 bq问了 why bb， bb是干啥的，就这两个。

噢噢好滴～validate BST我倒是刷过，就是这个需要自己写main函数来跑是么

luyuzhuangdeyez 发表于 2017-11-1 01:47
噢噢好滴～validate BST我倒是刷过，就是这个需要自己写main函数来跑是么

哦哦对的，main函数和test cases也是自己写

Stack直接用linked list实现就可以了啊...为什么第一个想到的是Queue...？Stack只需要知道last added element...

用ArrayList也可以理解。从硬件角度来说，如果queue的size接近于一个constant的话，memory alignment速度会比较快。