脸书onsite

steveguang 发表于 2016-10-22 22:54
楼主可以讲下第一题第四题怎么做的吗？

第一题就是利扣原题呀，不用dp的话，我说的是backtracking/DFS的做法，感觉这个follow up纯粹是小哥没准备别的题了硬加上的
第四题我的暴力解就挺直接的，用dp的话我后来想了想，可以记录到每个位置的走法数（初始状态只有数字1有1种），然后每走一步，根据前一步的位置更新下一步位置的走法数，步数走完以后，把所有位置的走法数加起来就可以了

yzlwjs 发表于 2016-10-24 01:30
第一题就是利扣原题呀，不用dp的话，我说的是backtracking/DFS的做法，感觉这个follow up纯粹是小哥没准 ...

楼主走日字是什么意思？矩形对角线吗？有什么限制没有

steveguang 发表于 2016-10-24 04:06
楼主走日字是什么意思？矩形对角线吗？有什么限制没有

就是中国象棋里面的马走日，横2步纵1步，或者横1步纵2步

居然看出来群主了

这个多少种可能走法，比如1开始走两步，最后1-6-1，1-6-7，1-8-1，1-8-3 应该是有1，7，3三个Positions. 结果是3吗？如果不是那就有问题了，那就应该是2^steps种不同路径了（即使最后到一样的点）   链接: https://instant.1point3acres.com/thread/195066 来源: 一亩三分地 (Instant 真垃圾！）

dowhatyoufear 发表于 2016-10-25 00:42
这个多少种可能走法，比如1开始走两步，最后1-6-1，1-6-7，1-8-1，1-8-3 应该是有1，7，3三个Positions. 结 ...

我也是这么觉得的。。。

dowhatyoufear 发表于 2016-10-25 00:42
这个多少种可能走法，比如1开始走两步，最后1-6-1，1-6-7，1-8-1，1-8-3 应该是有1，7，3三个Positions. 结 ...

是后者，看有多少种不同路径（即使最后到一样的点）。 另外应该是有O（m^steps）种不同路径，有些点出发到下一步的走法不一定是2种, 比如4->（3, 9, 0）

yzlwjs 发表于 2016-10-25 12:22
是后者，看有多少种不同路径（即使最后到一样的点）。 另外应该是有O（m^steps）种不同路径，有些点出发 ...

谢谢楼主～BFS或者DFS没觉得有什么不好的。恭喜楼主拿到Offer。

想请教一下楼主第三问的followup怎么做的?能写一段代码看看吗，十分感谢

试写了一下code，先统计了frequency of tasks然后用maxHeap做的，楼主能帮忙看看是这样么，感觉还有可以优化的地方，谢谢~
public static String taskSchedule(String str, int k) {
        StringBuilder rearranged = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : str.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }

        Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
                return entry2.getValue() - entry1.getValue();
            }
        });
        maxHeap.addAll(map.entrySet());

        while (!maxHeap.isEmpty()) {
            int i = 0;
            ArrayList<Map.Entry<Character, Integer>> temp = new ArrayList<>();
            while (i <= k && !maxHeap.isEmpty()) {
                Map.Entry<Character, Integer> curr = maxHeap.poll();
                rearranged.append(curr.getKey());
                curr.setValue(curr.getValue() - 1);
                temp.add(curr);
                i++;
            }
            for (Map.Entry<Character, Integer> e : temp) {
                if (e.getValue() > 0) {
                    maxHeap.offer(e);
                }
            }
        }
        return rearranged.toString();
    }