@yuluodi
OK. You mean the line that you commented right? There's a difference between 'i' and 'i'. The first one is called postfix operation, and the second one is prefix operation. Prefix operation takes effect immediately, even when the variable is used in the same line. However, Postfix operation takes effect after the variable used if they are in the same line.
Let's see an example:
int a = 1;
int b = a;
then a = 0, b = 0 because prefix '' takes effect immediately.
In contrast:
int x = 1;
int y = x;
then x = 0, y = 1 because 'x' was used, and post '' takes effect after it was used.
The problem in your code is that the subtraction doesn't take place. Each time we pop a node from the queue, we should subtract all its adjacent node's indegree by 1. However, if you write like this, the subtraction will only take place when the indegree equals 1. If you use prefix operation and put it in the if condition, the indegree will decrease 1 in each iteration.
Forget to @you at first...
Irving_cl
@Irving_cl
Posts made by Irving_cl

RE: C++ 28ms solution, using topological sort

RE: C++ 28ms solution, using topological sort
OK. You mean the line that you commented right? There's a difference between 'i' and 'i'. The first one is called postfix operation, and the second one is prefix operation. Prefix operation takes effect immediately, even when the variable is used in the same line. However, Postfix operation takes effect after the variable used if they are in the same line.
Let's see an example:
int a = 1;
int b = a;
then a = 0, b = 0 because prefix '' takes effect immediately.
In contrast:
int x = 1;
int y = x;
then x = 0, y = 1 because 'x' was used, and post '' takes effect after it was used.
The problem in your code is that the subtraction doesn't take place. Each time we pop a node from the queue, we should subtract all its adjacent node's indegree by 1. However, if you write like this, the subtraction will only take place when the indegree equals 1. If you use prefix operation and put it in the if condition, the indegree will decrease 1 in each iteration. 
RE: Simple C++ DP solution
@ravi007 dp[i] represents the number of structurally unique trees of i nodes. For example, we have four nodes now, and we have already known the number of trees of 0, 1, 2, 3 nodes(we have already calculated dp[0], dp[1], dp[2], dp[3]). Then how do we get the dp[4]? We can first take 1 node out, and let's call it 'root', then we have 3 nodes left. After that, we can create a new unique structurally unique tree by putting a tree 0nodetree on left side of 'root' and putting a 3nodetree on right side of it. And how many ways are there for us to do this? The answer is dp[0] * dp[3]. For the same reason, we can put 1nodetree on the left and 2nodetree on the right, 2nodetree on the left and 1nodetree on the right, 3nodetree on the left and 0nodetree on the right. That's all.
Thus dp[4] = d[0] * dp[3] + dp[1] * d[2] + dp[2] * dp[1] + dp[3] * dp[0].
I hope I've made myself understood :) 
RE: C++ O(N^2) solution, 56ms
@LHearen Thank you for your advice~

C++ solution using binary search, easy to understand
int binary_search(vector<Interval>& intervals, int target) { if (intervals.empty()) return 1; int low = 0, high = intervals.size()  1; while (low < high) { int mid = (low + high) >> 1; if (target > intervals[mid].start) { low = mid + 1; } else { high = mid; } } return intervals[low].start <= target ? low : low  1; } vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { vector<Interval> ret; int i1 = binary_search(intervals, newInterval.start), i2 = binary_search(intervals, newInterval.end); int c = ((i1 == 1  newInterval.start > intervals[i1].end) ? 0 : 1) + ((i2 == 1  newInterval.end > intervals[i2].end) ? 0 : 2); for (int i = 0; i <= i1; i++) { ret.push_back(intervals[i]); } switch (c) { case 0: ret.push_back(newInterval); break; case 1: ret.back().end = newInterval.end; break; case 2: ret.emplace(ret.end(), newInterval.start, intervals[i2].end); break; case 3: ret.back().end = intervals[i2].end; break; } for (int i = i2 + 1; i < intervals.size(); i++) { ret.push_back(intervals[i]); } return ret; }

0ms c++ norecursive solution
The idea is same as most posts. The good thing is that we don't need to calculate log10(n) in each iteration here and it's nonrecursive.
int countDigitOne(int n) { if (n < 0) return 0; int a[10] = { 0 }, b[10] = { 1 }; for (int i = 1; i < 10; i++) { b[i] = b[i  1] * 10; a[i] = a[i  1] * 10 + b[i  1]; } string nStr = to_string(n); int ans = 0; for (int i = 0, size = nStr.size(); i < size; i++) { int digit = nStr[i]  '0'; if (digit > 1) { ans += a[size  i  1] * digit + b[size  i  1]; } else if (digit == 1) { ans += a[size  i  1] + 1; if (i != size  1) ans += stoi(nStr.substr(i + 1)); } } return ans; }

C++ O(N^2) solution, 56ms
vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.empty()) return vector<int>(); sort(nums.begin(), nums.end()); vector<pair<int, int>> dp(nums.size(), make_pair(1, 1)); int globalLargest = 1, globalLargestIdx = 0; for (int i = 1; i < nums.size(); i++) { int largest = 1, parentIdx = 1; for (int j = i  1; j >  1; j) { if (nums[i] % nums[j] == 0) { if (dp[j].first + 1 > largest) { parentIdx = j; largest = dp[j].first + 1; } } } dp[i].first = largest; dp[i].second = parentIdx; if (largest > globalLargest) { globalLargestIdx = i; globalLargest = largest; } } vector<int> ret; for (int idx = globalLargestIdx; idx != 1; idx = dp[idx].second) { ret.push_back(nums[idx]); } return ret; }

C++ 0ms solution, using binary search
Since we know the input is an integer, the largest square root is 46340. The time complexity is O(lg(46340)). lg(46340) = 16.
bool isPerfectSquare(int num) { if (num < 0) return false; int low = 0, high = 46340; while (low < high) { int mid = low + (high  low) / 2; int square = mid * mid; if (square < num) { low = mid + 1; } else { high = mid; } } return low * low == num; }