Conquer on Tree (二叉树上的占领游戏) - 1point3acres

二叉树上的占领游戏
在一棵二叉树上玩一个游戏，对手先选择树上一个节点，现在该由你来选择一个点。然后同时开始，从选择的那个点开始，
向外扩张，只可以去占领其相邻的点(parent and children)，然后从占领的点再去扩张，依次类推，
但如果相邻的点已经被对方占了，就没法去占领了。谁最终占有的点最多谁获胜。

input是树root和对手选中的node,返回你是否能胜利

followup 如果你先选择点，你该选择哪个点能胜利？

比如下面这个树，如果你的对手选中了8，你选6就能胜利。而如果你选9，对手下一步可以由8扩张到6，对手就赢了。

1     2       3   4   5       6 7           8   9           10      11             12  13           14      15

https://www.1point3acres.com/bbs ... read&tid=488670

嗯，找到一个结点，使以该结点为根的新树的左右子树结点数目相等或者相差不大于1。那么先手选此结点必然不败；如果新树左右子树结点数目相等则先手胜，否则先手平。

不是一次。turn-based选。比如楼上的树，我选1，你选3。因为规则是必须从占领的点相邻的扩张。我占领的点是【1】。而3你又占着，所以我只能选2来扩张.

你选了某个点i，那么对方肯定选跟i相临的某个点。

所以对方就是选了以点i为root，权值和最大的一个subtree。

先选的一方肯定是不败的。

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=488670
https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/

红蓝小人占领二叉树 （频率 5）

两个人红蓝，在二叉树上，每个人可以从第一个选的点开始同时往相邻的点扩展占领点，已知red选了一个点，（规则大概是两点之间的可以共同占领，但红的children只能红的占）问蓝第一个点选哪里最后能占领的最多。输入root和红的点，输出蓝色选的node

请问这题可以有哪位好心的童鞋再解释一下题目的意思吗？“规则大概是两点之间的可以共同占领，但红的children只能红的占” 这里看不懂😔

例子：(N： 空node， r: 红色点，b蓝色点)

n

/ \

n n

n r n n

n n n n  n n n n

如果蓝色小人在红色小人上方作为起点，标红点node现在对于蓝色小人来说永远不可占领，其他节点两人可以轮流扩展占领

此处b选在蓝色节点处为最佳策略，蓝色小人堵住了红色小人向上扩展的机会

相关帖子

思路：

这个题关键在于明白规则：

即出了第一个点，其余的点放的时候都要连接到相同颜色的点， 所以红色选定后，就把树分为了三部分，如果蓝色选的是最大的一部分并且紧挨着红色第一个点，就有可能赢。 因为最大的一部分被蓝色堵住后， 红色都到不了了

选第一个点的的时候，要选一个三部分尽量均匀的，即 任何两部分都大于第三部分的，即红色先选并选第一个点的规则， 这个是follow up

参考代码

Provider: null

TreeNode {

int key;

TreeNode left;

TreeNode right;

public TreeNode(int key) {this.key = key;}

}

private TreeNode redParent = null;

private TreeNode red = null;

public TreeNode findNode(TreeNode root, TreeNode red) {

// sanity check

this.red = red;

int redL = countNode(red.left);

int redR = countNode(red.right);

int redParent = countNode(root);

int max = Math.max(redParent, Math.max(redL, redR));

if(max == redL) return red.left;

else if(max == redR) return red.right;

else return redParent;

}

private int countNode(TreeNode root) {

if(root.left == red || root.right == red) redParent = root;

if(root == null || root == red) return 0;

return countNode(root.left) + 1 + countNode(root.right);

}

骰子拼字

骰子拼字
字母骰子，六面字母有可能重复，给15个，input是长15的string，给出一个可行解使筛子的排列有可能组成这个15长度的单词。 

follow up是如果有可互换的字母怎么判断，比如W可看成M，Z可能看成N等等

https://www.1point3acres.com/bbs ... read&tid=488082

比如骰子 = [a, b], [c, c]

所以
"ab" [no]
"ac" [yes]
"bc" [yes]
"bb" [no]
"cc" [no]

差不多意思就是每个character从一个骰子上来, 怎么组合.

dfs吧, 没什么难度.

再加一个例子吧：

骰子 = [a, b], [c, c], [a, a]要求组成abc。则必须第一个骰子b，第二个c，第三个a。

这个问题，其实答到深搜就好了，但是更好的算法可以答匈牙利算法或者KM算法，但是估计不会让现场写的。。。

我觉得V应该就是骰子的数量或者word长度。

二向图一边是字母，另一边是骰子，如果字母在骰子里，就连一下。

补充内容 (2019-3-24 02:49):

二分图，不是二向图

现在都已经考二分图匹配这么难的题了吗.....

推箱子

推箱子
5. 一个洞穴里面很多格，每一格都是不同的高度，还有一堆object, 每个的高度不同，问这个洞穴最多可以放多少个object，往洞穴放object的话要注意是从洞口往里放，所以靠近洞口的格子的高度会限制后面的高度，因为object会被卡住。。. 每个格子只能放一个object，object不能叠加。


第三题：地里的面经题。有一个山洞，可以看作一维height数组。  另外有一堆箱子boxes， 要求将箱子从外面推到山洞里面，问最多能推多少箱子进山洞。楼主先解释了为什么要先将箱子高度排序，先推矮箱子，再推高箱子。同时山洞的每一个位置i都最多能容许min(heights[:i])的箱子通过。 根据这点建立一个allowedHeight数组，可以看出是单调不增的序列， 因此对每个箱子高度可以bisect寻找allowedHeight里面对应的position index.  讨论了时间复杂度 O(log(len(height))*len(boxes))。电脑写了code后和面试小哥讨论了几点可以优化的地方，最后小哥表示时间复杂度还可以优化，在提示下使用two pointer方法，让两个pointer分别指向最矮箱子的position和最小allowedHeight position, 依次比较二者的大小来分别递增两pointer。 时间复杂度可以变成O(len(height)+len(boxes))


我来描述一下吧：

假设山洞有三个格子，从左到右（也是从最深到洞口的顺序）的高度分别是: 5, 10, 6 【洞口】。见下图：

[Bash shell] 纯文本查看 复制代码

?

------       |      |------ |-----|      | |____________________ 洞口    高度5  高度10  高度6

那么可知最左的格子最多只能放5，中间的格子只能放6，因为6以上的箱子无法从洞口通过最右边的只有高度6的格子，也就不可能到中间。最右边的格子最多只能放6。因此箱子进洞有着单调性。另外格子里最多可以放一个箱子。

如果我有这些箱子：📦 10, 30, 6, 5, 8，7，那么在排序以后，我 应该 5 放最左，6放中间或者左边。有一个格子空着。7,8,10,30这些箱子不能放入。

https://www.1point3acres.com/bbs ... read&tid=511673

https://www.1point3acres.com/bbs ... read&tid=444025

洞O[n] 做递减数组

箱子排序, 挨个match.

最方便的公寓

最方便的寓所
一列street block，每个street block上都有POI （Point of Interests），比如学校，商店，诊所等等。也可能没有。

给定一个list of requirements, 比如[grocery，school]，找到距离所有requirement最近的apartment位置。

follow up是如果只有一些street block有apartment怎么办

https://www.1point3acres.com/bbs ... read&tid=504803

确认一下＂最远的定义＂是一个点到所有最近requirement的点的总和？一个点到所有requirement中最远的距离？
sum((distance to r) for r in requirements)
or
max((distance to r) for r in requirements)
我看另一个面经的例子好像是后者

神秘文件的例子，原帖找不到了：
假设一条街上有多个block，一个block上有多个建筑。求一条街上离几个最近的特定建筑的最远距离最短的block。例子： street = [[“store”, “school”, “museum”], [“hospital”, “restaurant”], [“school”, “restaurant”], [], [“museum”]], requirement = [“store”, “museum”, “restaurant”].
第一个block到最近store是0，到最近museum是0，到最近restaurant是1，所以它的max是1
第二个block到最近store是1，到最近museum是1，到最近restaurant是0，所以它的max是1
第三个block到最近store是2，到最近museum是2，到最近restaurant是0，所以它的max是2
第四个block到最近store是3，到最近museum是1，到最近restaurant是1，所以它的max是3
第五个block到最近store是4，到最近museum是0，到最近restaurant是2，所以它的max是4
所以返回的block是第一个和第二个。


题意有误解，这题有两种问法，一种是问距离和，一种是问到最远的一个的距离，距离和的话这个作法当然是不对的，如果只是到最远的requirement 的距离，500距离0和1000都是500，这例子就没问题

粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为O（nk），k为requires项数。

    * Input: 1. 给一条路，路上的不同位置有不同的设施，有多个设施在不同位置的情况, List<Set<String>>

    *        2. 给一个需求设施的set

    * Output： 希望给出一个位置，距离所有设施的距离最近的和

    *

    * Example:

    *   Road: {

    *           [bookstore, school],

    *           [grocery] ,

    *           [],

    *           [],

    *           [bookstore, library],

    *           []

    *           [grocery]

    *        }

    *   Requires: [bookstore, library, grocery]

    *   Output: the best place is 4, to bookstore and lib is 0, and grocery is 2, so in sum is 2.

    * */

 

    public int findBestLocationn(List<Set<String>> road, List<String> requires) {

        Map<String, List<Integer>> roadMap = createMap(road);

        int minSum = Integer.MAX_VALUE, index = 0;

        for (int i = 0; i < road.size(); i++) {

            int sum = 0;

            for (int j = 0; j < requires.size(); j++) {

                sum += getMinLen(roadMap, requires.get(j), i);

            }

            if (sum < minSum) {

                minSum = sum;

                index = i;

            }

        }

        return index;

    }

 

    private Map<String, List<Integer>> createMap(List<Set<String>> road) {

        Map<String, List<Integer>> roadMap = new HashMap<>();

        for (int i = 0; i < road.size(); i++) {

            for (String facility: road.get(i)) {

                List<Integer> list = roadMap.getOrDefault(facility, new ArrayList<>());

                list.add(i);

                roadMap.put(facility, list);

            }

        }

        return null;

    }

 

    private int getMinLen(Map<String, List<Integer>> roadMap, String require, int index) {

        List<Integer> list = roadMap.get(require);

        int minLen = Integer.MAX_VALUE;

        for (int pos: list) {

            minLen = Math.min(minLen, Math.abs(pos-index));

        }

        return minLen;

    }