成功人士从不刷Leetcode（2） - 知乎书馆 - 知乎专栏
提示：一堆石子，每次拿1～3个，自己先拿，两个人轮流拿，谁先拿到最后一个谁就算赢。其中一种必胜的策略是，对方拿n个，自己就拿4-n个——因此如果保证自己赢，必须要保证自己拿掉石头，使剩下的石头数量n满足：n%4==0——也就是开始的时候，石头数量必须不是4的倍数。
class Solution { public: bool canWinNim(int n) { return (n%4 != 0); } }; 338. Counting Bits（https://leetcode.com/problems/counting-bits/）
提示：如果每个数，则总共需要时间是O(nlog(n))的时间。按照提示，提供一个O(n)的解法。如果已知1~2^N的bits结果为[a1,a2,..., a2^N-1,a2^N]，那么从2^N+1~2^(N+1)的bits数量分别为[a1+1, a2+1, ..., (a2^N-1)+1, 1]，即后2^N个数中，前N-1为从1~2^N-1的bits数量+1，而最后一个为1。一个recursive的详细方法是：
a. 判断num的最大2次幂int p = floor(log(num) / log(2));
b. 如果num==pow(2,p)，即num是2的整数次幂，则取prev=countBits(pow(2,p-1));，然后在prev后添加num/2~num，并把最后一位数换成1；
Read full article from 成功人士从不刷Leetcode（2） - 知乎书馆 - 知乎专栏
No comments:
Post a Comment