1月刷题/Mockinterview接龙活动（缺米刷题的来）

我先来。
做了三道题
1307 Verbal Arithmetic Puzzle --> recursion with backtracking。 选择正确的recurssion方法很重要。需要灵活
903 Valid Permutations for DI Sequence。好难。想到了dp但是recursion部分想得有问题。最后看了答案才找到正确的转换方法
1637 Widest Vertical Area Between Two Points Containing No Points。不是很困难。nlogn和n的方法都能做。可是nlogn sort的方法竟然比n的快。有空需要优化一下代码。

---

本帖被14417335扣分。扣分情况：-5，理由：。
提醒：对于骂人、戾气、广告等行为，请勿对骂，请举报。

刷了四道：
Triples with Bitwise AND Equal To Zero --> 好楞的题，看了讨论里面的答案也都是接近～n^3 的方法。如果没有更好的解法的话，就觉得是题不好或者应该是medium。
Unique Paths III --> 标准的path search recursion。
Ways to Make a Fair Array --> 需要注意到只考虑挪除一个值的情况。而后就是通过cache避免sum的重复计算。
Where Will the Ball Fall --> 纯考察implementation能力，几乎没有算法部分。

加米必回加  做了几道DP：paint fence 需要定义两个DP数组
same means the number of ways if fence i has the same color with fence i - 1.
diff[i] means the number of ways for the fence i which has different color with fence i -1.
Initialization:
     same[0] = 0, diff[0] = k.
Induction rule:
     Case 1 : if paint i  same color with i - 1, [/i][i]i - 1 must be different from i - 2, then only use diff[i - 1] to computer same [/i][/i][i][i][i]                 same[i][i]= diff[i - 1]   [/i][/i]
[i][i]     Case 2: if paint i different color with i - 1, doesn't matter if color i - 1 same or different with i - 2, can use both[/i][/i]
[i][i]                there are (dp1[i - 1] + dp2[i - 1]) # of ways to paint previous i - 1, [/i][/i][i][i]for each choice, (k - 1) ways to paint current fence[/i][/i]
[i][i]                diff[i] [i]= (k - 1) * (same[i - 1] + diff[i - 1])[/i][/i][/i]
[/i][/i][/i]

楼主来信询问扣分的事情，我就再贴一遍：

每天相互加米的活动已经停止。详情还请看。

https://www.1point3acres.com/bbs ... age=293#pid13845323

欢迎每月总结性的回顾和总结。谢谢

楼主来信再次询问。还请看我上面的回复。