谷歌新鲜昂赛面经

匿名者 发表于 2022-2-2 23:07
楼主，能问一问coding 3的数字仅限于1-9吗?

我目前的大概想法是backtracking，但是我没太想明白memo的是 ...

我的思路和你差不多，有几点细微不同的，或者说想clarify的是：
1. 每一个dfs的step，我们都需要尝试两种可能（凑三张，凑顺子），而不是otherwise的关系对吧。
2. 凑三张的时候，不是count > 3, 而是count >= 3。然后count取余和减3其实一样。
3. 你说的index其实就是牌的value对吧，就是1到9的值。
4. 这个其实无所谓，但还是想问问：拿掉pair后，dfs时间复杂度，2^10, 如果按树来看，怎么知道是10层呢。比如开头1111，一个分支是取3个1走，一个分支取一个1和后面的23。但是如果取一个1，下一个dfs step还是在1的位置上，因为没用完。我的计算可能更worst case，按memo里面的counts的可能个数，每个value最多5种count（0～4），所以是5^9，当然实际没这么多因为不是每种count都能出现。