成功人士從不刷Leetcode（2）

提示：一堆石子，每次拿1～3個，自己先拿，兩個人輪流拿，誰先拿到最後一個誰就算贏。其中一種必勝的策略是，對方拿n個，自己就拿4-n個——因此如果保證自己贏，必須要保證自己拿掉石頭，使剩下的石頭數量n滿足：n%4==0——也就是開始的時候，石頭數量必須不是4的倍數。

class Solution {npublic:n bool canWinNim(int n) {n return (n%4 != 0);n }nn};n

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；

c. 如果num!=pow(2,p)，則取prev=countBits(pow(2,p))；，然後再prev添加從pow(2,p)~num。

class Solution {npublic:ntvector<int> countBits(int num) {nttif (num == 0) return (vector<int>(1, 0));nttif (num == 1) {ntttvector<int>p = { 0,1 };ntttreturn p;ntt}nttint p = floor(log(num) / log(2));nttvector<int> prev;nttif (pow(2,p) == num) prev = countBits(pow(2, p - 1));nttelse prev = countBits(pow(2, p));nttint j = 1;nttint prev_size = prev.size();nttwhile (j <= num - prev_size + 1) prev.push_back(prev[j++] + 1);nttif (pow(2, p) == num) {ntttprev.back() = 1;ntt}nttreturn prev;nt}nn};n

220. Contains Duplicate III(https://leetcode.com/problems/contains-duplicate-iii/)

提示：遍曆數組中每一個數（N），並同時維護一個set，使得set中存儲有第i個元素中前k個元素，每次用set找出和第i個元素相差小於t的元素（logN），如果存在則返回true。

class Solution {npublic:n bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {n set<int> buf;n for (int i=0;i<nums.size();i++){n if (i > k) buf.erase(nums[i-k-1]);n auto low = buf.lower_bound(nums[i] - t);n if (low != buf.end() && abs(*low - nums[i]) <= t) return true;n buf.insert(nums[i]);n }n return false;n }nn};n

346. Moving Average from Data Stream(https://leetcode.com/problems/moving-average-from-data-stream/)

送分題。

class MovingAverage {npublic:n list<int> buf;n int sz;n double sum;n /** Initialize your data structure here. */n MovingAverage(int size) {n sz = size;n sum = 0;n }n n double next(int val) {n sum += val;n buf.push_back(val);n if (buf.size() > sz) {n sum -= buf.front();n buf.pop_front();n }n return sum / buf.size();n }nn};n

344. Reverse String（https://leetcode.com/problems/reverse-string/）

送分題。

class Solution {npublic:n string reverseString(string s) {n int p1=0,p2=s.size()-1;n while (p1<p2) swap(s[p1++],s[p2--]);n return s;n }nn};n

359. Logger Rate Limiter(https://leetcode.com/problems/logger-rate-limiter/)

提示：送分題。

class Logger {npublic:n /** Initialize your data structure here. */n map<string,int> ht;n Logger() {n n }n n /** Returns true if the message should be printed in the given timestamp, otherwise returns false.n If this method returns false, the message will not be printed.n The timestamp is in seconds granularity. */n bool shouldPrintMessage(int timestamp, string message) {n if (ht[message] > timestamp) return false;n ht[message]=timestamp+10;n return true;n }n};nn/**n * Your Logger object will be instantiated and called as such:n * Logger obj = new Logger();n * bool param_1 = obj.shouldPrintMessage(timestamp,message);nn */n

339. Nested List Weight Sum(https://leetcode.com/problems/nested-list-weight-sum/)

提示：送分題。

class Solution {npublic:n int calsum(vector<NestedInteger> &n, int level){n int sum = 0;n for (int i=0;i<n.size();i++){n if (n[i].isInteger()) sum += n[i].getInteger() * level;n else sum += calsum(n[i].getList(), level+1);n }n return sum;n }n int depthSum(vector<NestedInteger>& nestedList) {n return calsum (nestedList, 1);n }nn};n

266. Palindrome Permutation(https://leetcode.com/problems/palindrome-permutation/)

提示：送分題。

class Solution {npublic:n bool canPermutePalindrome(string s) {n vector<int> cnt(128,0);n for (auto i:s) cnt[i]++;n int oddmark = 0;n for (int i=0;i<128;i++) {n if (cnt[i]%2 && oddmark == 0) oddmark++;n else if (cnt[i]%2 && oddmark) return false;n }n return true;n }nn};n

136. Single Number(https://leetcode.com/problems/single-number/)

提示：送分題。

class Solution {npublic:n int singleNumber(vector<int>& nums) {n int single = 0;n for (auto i:nums) single ^= i;n return single;n }nn};n

提示：送分題。

class Solution {npublic:n vector<string> generatePossibleNextMoves(string s) {n vector<string> ret;n if (s.size()<2) return ret;n for (int i=0;i<s.size()-1;i++){n if (s[i]==+ && s[i+1]==+) {n string s1 = s;n s1[i] = -;n s1[i+1] = -;n ret.push_back(s1);n }n }n return ret;n }nn};n