7/6, LinkedIn 面经
这题本身不难,但是有一个常见错误:
在 dfs 中直接 root = null 是无法删除 root 的.
因为对于 object, java 是 pass by value, 传递过去的是 object reference.
在这个帖子中举例:
换句话讲,dfs 中作为参数的 TreeNode root 是一个新建的 reference,默认指向的是原参数 root 的同一个位置。因此我们可以对它指向的 object 进行各种操作.
但是当我们更改这个 reference 指向时,我们只是改了函数自己的那个 copy 所指向的 object,而对原始参数指向的东西没有任何改变。
于是这题如果试图在 dfs 中用 root = null 删除节点,实际上我们不会删除任何节点,只会更改在自己这层 call 中, root 指向的节点而已。因此我们之前可以用其他 method call 在 dfs 中对各种 list, set, map 和 collection 里面的值进行修改,但是改 method call 里面的 reference 并不会对原 object 造成任何影响。
对于两个人 A 与 B, 有如下可能:
knows(A, B)
A --> B ( A knows B )
A 一定不是明星
A <-- B ( B knows A)
B 一定不是明星
A ... B ( 互相不认识 )
B 一定不是明星
因为给定条件“所有人都认识明星,而明星不认识任何人”,对于任意一对 A 和 B,我们仅仅做一次 knows 比较就可以排除掉一个人,我们就可以存一个 ptr 依次扫描整个数组。
当最后只剩下一个可能性的时候,我们依然有必要检查一下,因为我们不确定这个 cur 是不是认识数组里的其他人,或者是不是其他人都认识 cur. 因此再一次循环进行判断 + 记录认识 cur 的人数就可以了。
老题了,前缀积数组的应用。
Word Search II 之后留下了后遗症,看到这种问题也想用记忆化搜索加快速度。
不过这题的 subproblem 不太一样。 因为当最开始的 n 真的等于质数时,我们返回 empty list; 但是如果这是个 dfs 嵌套的 method call,我们却要把这个质数加到 list 里。 换句话说,同样 size / interval 的 subproblem, 返回的结果却要依情况而定,这是违反了记忆化搜索和动态规划性质的。
简单说就是,这题的 subproblem 之间,不具有 optimal substructure.
dfs(12) 并不等于 2 + dfs(6) 和 3 + dfs(4) 与 4 + dfs(3) ..
于是我们仔细观察 sample output 中,n = 32 的正解,重新排列顺序之后得到:
n = 32
[16,2]
[8, 4]
[8, 2, 2]
[4, 4, 2]
[4, 2, 2, 2]
[2, 2, 2, 2, 2]
我们可以发现把解按照递减顺序排列之后,这是一个类似 combination 的问题,因为:
每一个解是若干个元素的组合,解与解之间大小不等
同一组解之间,元素的选取有单调性 (去重)
具体实现上,为了保证不盲目把初始 n 加到结果中,第一层 dfs 里传进去的 prev 是 n - 1.
这题的 dfs 里 base case 还不太一样,我们做的是试图直接把 n 加进去作为一个解,同时要注意不能直接 return ,否则后面的解就都看不到了。
真正的 return ,是在对于 n 来讲从大到小连 i = 2 都尝试过作为 factor 之后自然结束搜索。
我想了半天怎么用 KMP 做这题复杂度比较低,看到 tag 里有 hashtable 就直接用 hashmap 套用了一下,然后不但 AC 了还在运行速度上超过了 76% 的人。。。这题的用意到底是什么。。。
唯一需要注意的是对于出现超过 2 次的 str 不要重复添加,因此 hashmap 里留一个 count ,根据 count 行事。
去地里看了一圈,这题更有意思的解法是利用 DNA 只有四种字母的性质去做 encode / decode.
因为字母只有四种可能,我们可以用 2 bits 表示任意字母;同时因为 sequence 长度为 10,所以我们只需要 20 bits 就可以 Uniquely represent 一个 sequence,即自己实现无 collision 的 hashing. 简便起见,一个 32-bit int 就够了。
encode 时,对于每一个给定的 substring,遍历每个字母,然后根据字母决定其数字,给最后两位赋值之后 << 2.
decode 时,每次把当前数字除以 4 看余数,根据余数决定字母,而后 >> 2.
这样对于每一个 string / int ,其 encode / decode 都是唯一的。
空间占用为 2^20 = 1048576 个 int = 4.194304 MB ,代表可能的 hash 值数量。
轻松愉快,一次 AC.
Last updated