facebook onsite

siren01 发表于 2015-4-3 07:39
谢谢，想了一下，你的代码可行，赞

求第一题O(n)的代码，貌似用hashmap能做

sonicgu 发表于 2015-4-3 08:43
求第一题O(n)的代码，貌似用hashmap能做

yuxrose回家贴

sonicgu 发表于 2015-4-3 08:43
求第一题O(n)的代码，貌似用hashmap能做

//给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做，“第二题用三个stack，一个维护后续遍历，一个维护每个节点为根的字数和，另一个维护你要的结果”

求代码看看

siren01 发表于 2015-4-3 08:53
//给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做，“第二题用三个stac ...

第二题 可以用 arraylist加 hashmap做

siren01 发表于 2015-4-3 05:09
赞，小板凳搬好了

map的key是字母，value是最新的index, 一边扫一边update index, cooldown就是k.
有大神能想想O(1)怎么做吗？

public static int scheduler_map(String s){
                Map<Character, Integer> hashMap = new HashMap<Character, Integer>();
                int total = 0;
                int i = 0;
                int cooldown = 2;
                while(i < s.length()){
                        if(!hashMap.containsKey(s.charAt(i)) || (total - hashMap.get(s.charAt(i)) >= cooldown + 1)){
                                hashMap.put(s.charAt(i), total);
                                i++;
                        }
                        total++;
                }
                return total;
        }

补充内容 (2015-4-3 10:28):
测试case
Tasks: AABABCD
Cooldown Time: 2
  A__AB_ABCD
Output: 10

tracywade 发表于 2015-4-3 10:16
第二题 可以用 arraylist加 hashmap做

求楼主上代码，小板凳搬好了

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

哈哈，赞一个，不错的代码

补充内容 (2015-4-3 10:58):
往回扫k个字母，看是否有出现，是，则等着，否，则可以执行，代码差不多，只不过这里用hashmap判断的代码要改为k次往前扫

补充内容 (2015-4-3 11:10):
试了一下，貌似行不通，还是要用东西记录上一个出现的，毕竟处理的时间是相对时间

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

这个办法很赞！不过最后不是sorted list，还是visit的order，所以是不是还得再sort一下？

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

what if task 顺序不用一致

siren01 发表于 2015-4-3 10:46
哈哈，赞一个，不错的代码

补充内容 (2015-4-3 10:58):

用deque可以实现O(K)space, 等价于O(1).
用一个长度为K的deque，每次检查的时候就数queue里面有没有出现过字符，也是O(K)的复杂度。
然后循环移除front