class Solution {
public:
bool checkPerfectNumber(int num) {
return num==6  num==28  num==496  num==8128  num==33550336;
}
};
shallpion
@shallpion
Posts made by shallpion

call me a cheater

C++ solution using binary search + Fenwick tree
This is obviously not a fast or short solution at all. But if you want to review the usage of Fenwick tree I wish this could be helpful. The basic idea is similar to LC315, but binary search is used to maintain another map so we know where to "count" the numbers. A detailed implementation of Fenwick tree is also given for the purpose of reviewing old knowledge...
class Fenwick { private: // tree is one unit shiftd from a virtual vector arr[] vector<long> tree; long lsb(long i) { return i & (i); } public: Fenwick(long size) { tree = vector<long>(size + 1, 0); } // the following function sums up arr[0..id] long sum(long id) { id++; long ret = 0; while(id > 0) { ret += tree[id]; id = lsb(id); } return ret; } // the following function increases arr[id] void add(long id, long val) { long n = tree.size(); id++; while(id < n) { tree[id] += val; id += lsb(id); } } }; class Solution { public: long reversePairs(vector<int>& nums) { vector<long> nums2; for(long i : nums) { nums2.push_back(2*i); } sort(nums2.begin(), nums2.end()); // order maps the original order to sorted order, it doesn't matter if duplicated is present unordered_map<long, long> order; // binary search result, notice that this is index<>index map unordered_map<long, long> biorder; long ret = 0; long n = nums.size(); for(long i = 0; i < n; ++i) { biorder[i] = lower_bound(nums2.begin(), nums2.end(), nums[i])  nums2.begin(); order[nums2[i]/2] = i; } Fenwick fw(n); for(long i = n1; i>=0; i) { ret += fw.sum(biorder[i]1); fw.add(order[nums[i]], 1); } return ret; } };

two pointers c++ solution
I feel like binary search route might be a little overkill...
class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { int heaterId = 0; int houseId = 0; int minR = 0; sort(houses.begin(), houses.end()); sort(heaters.begin(), heaters.end()); while(houseId < (int) houses.size()) { while(heaterId < (int) heaters.size()1 && houses[houseId] >= heaters[heaterId+1]) { heaterId++; } if(heaterId == (int) heaters.size()1) { minR = max(abs(houses[houseId]  heaters[heaterId]), minR); } else { minR = max( min(abs(houses[houseId]  heaters[heaterId]), abs(houses[houseId]  heaters[heaterId+1])), minR); } houseId++; } return minR; } };

dp solution in c++ with comments
I think the key to this problem is to use some bitwise operation to record what numbers have been used during the game to minimize the size of hash table as much as possible.
class Solution { public: bool canIWin(int maxChoosableInteger, int desiredTotal) { if(desiredTotal == 0) return true; if((maxChoosableInteger+1) * maxChoosableInteger / 2 < desiredTotal) return false; unordered_map<int, bool> dp; // a bit in record being equal to 1 means a number is available // for example if record is ..1000, it means number 3 has not been used, // for convenience we do not use the least significant digit. int record = 0; for(int i = 0; i < maxChoosableInteger+1; i++) { record = (record << 1) + 1; } return f(desiredTotal, record, dp); } bool f(int dt, int record, unordered_map<int, bool> &dp) { if(dp.count(record)) { return dp[record]; } // we know maxChoosableInteger wont be larger than 20 for(int i = 20; i > 0; i) { int bit = 1 << i; // if this number has not been used if(record & bit) { if(i >= dt) { dp[i] = true; return true; } // mark number i so it has been used and check whether the opponent // can win. Notice that due to the annoyance of [] operator // automatically inserting value into a set in c++, we should not // use dp[...] = f(..., dp) to avoid changing dp BEFORE the // function is called. bool t = f(dti, record^bit, dp); dp[record^bit] = t; if(t == false) { return true; } } } return false; } };

RE: Java Explained 1ms Solution
@tju_xu said in Java Explained 1ms Solution:
How about poorPigs(3, 2, 1), I think it should return 3.
In that case I think you cannot tell it at all. Since no matter how many pigs do you have they will only show signs of poison after 2 minutes which exceeds the time limit 1

RE: Java Explained 1ms Solution
I think it maybe a little bit easier to understand if you replace the
if(buckets == 1) return 0;
by simply
buckets;
and it should be the same result, as we can remove one bucket from the collection and test whether the remaining buckets have the poison or not.

RE: two pass O(n) solution by marking failed loop by zero
updated my solution to check for zeros in advance. Thanks for the correction!

two pass O(n) solution by marking failed loop by zero
hopefully this isn't too slow, haven't spent much time improving it. The basic idea is to detect a loop by maintaining a onestep and a twostep pointers, just like an old problem from leetcode. And each time a possible attempt failed we mark every index on the path by zero, since zero is guaranteed to fail. Since the problem asks only forward of backward solution we simply run it for positive indices and negative indices twice.
By the way, the problem states that the array has only pos and neg numbers, which is apparently a little inaccurate. The presence of zero though doesn't seem to cause much problem.
class Solution { public: bool circularArrayLoop(vector<int>& nums) { int n = nums.size(); // check for zero for(auto i : nums) if(i==0) return false; // forward: for(int i = 0; i < n; i++) { if(nums[i] <= 0  nums[i] == n) continue; int one = i; int two = i; int m = 2*n; while(m > 0) { int jump_one = (one + nums[one]) % n; if(nums[jump_one] <= 0  jump_one == one){ break; } one = jump_one; int jump_two = (two+nums[two]) % n; if(nums[jump_two] <= 0  jump_two == two) { break; } two = jump_two; jump_two = (two+nums[two]) % n; if(nums[jump_two] <= 0  jump_two == two) { break; } two = jump_two; if(one == two) return true; } // no forward for this chain one = i; while(nums[one] > 0) { int t = nums[one]; nums[one] = 0; one = (one + t) % n; } } // backward: for(int i = n1; i >= 0; i) { if(nums[i] >= 0  nums[i] == n) continue; int one = i; int two = i; int m = 2*n; while(m > 0) { int jump_one = ((one + nums[one]) % n + n) % n; if(nums[jump_one] >= 0  jump_one == one){ break; } one = jump_one; int jump_two = ((two+nums[two]) % n + n) % n; if(nums[jump_two] >= 0  jump_two == two) { break; } two = jump_two; jump_two = ((two+nums[two]) % n + n ) % n; if(nums[jump_two] >= 0  jump_two == two) { break; } two = jump_two; if(one == two) return true; } // no backward for this chain one = i; while(nums[one] < 0) { int t = nums[one]; nums[one] = 0; one = ((one + t) % n + n) % n; } } return false; } };

RE: WHF! I can not figured out why MLE for the simple test case
@zyoppy008 said in WHF! I can not figured out why MLE for the simple test case:
@husthyc
I know how hashmap works. It just might waste a lot unused space for mapping.
MLE in Leetcode I met before is always due to space larger than a given size.
So I never thought that it would MLE for this small test case.
I am wrong!As I said I really do not think it showed MLE due to this specific example. If you customize a test case as this one and run the code (do not submit), you can see it works perfectly. There must be a deeper reason why it went MLE, possibly due to earlier test cases. C++ hash map takes some overhead, of coz, so does java. But there are also many many problems for which C++ handled large data pretty well using hashing map. If a test case, so simple, can triger MLE for C++ I shall call for the removal of C++ from leetcode, that is nonsense.