voidqsort(vector<int> &vec, int s, int e){ if (s >= e) return; int pv = vec[s]; int l = s, r = e; for (int i = s + 1, left = e - s; left > 0; left--) { if (vec[i] < pv) { vec[l++] = vec[i++]; } else { swap(vec[i], vec[r--]); } } assert(l == r); vec[l] = pv; qsort(vec, s, l - 1); qsort(vec, l + 1, e); }
intmain(int argc, char **argv){ srand(time(NULL)); vector<int> vec(500000); for (int i = 0; i < vec.size(); i++) vec[i] = random(); vector<int> s = vec;
\(s\) is the first index in the subarray of \(vec\), \(e\) is the last index in the subarray of \(vec\). \(vec[s:e]\) denotes the whole subarray, inclusive. At the start of the for loop:
\(i\) denotes the index of the element to be compared with the pivot
\(left\) denotes the number of remaining elements to be compared
\(l\) denotes the minimum position to put the element which is smaller than the pivot
\(r\) denotes the maximum position to put the element which is greater than or equal to the pivot
We say there are \(x\) elements \(<\) pivot, then there are supposed to be \(e - s - x\) elements \(>=\) pivot. After the for loop terminates, \(l\) will be \(s + x\), and \(y\) will be \(e - (e - s - x) = s + x\) too, so \(l = r\). The elements on the left side of \(l \ or\ r\) are all \(<\) pivot, and the elements of the right side of \(l \ or \ r\) are all \(>=\) pivot, then we put the pivot on the position \(l \ or \ r\). Then all the elements on the left side of the pivot will be smaller than the pivot, and all the elements on the right side of the pivot will be greater than or equal to the pivot. Thus, the partition is correct.
Correctness of recursion
Proof by induction. Suppose that \(P(n)\) is a predicate defined on \(n \in [1, \infty)\) meaning the \(Quick Sort\) is correct on a given array sized \(n\). If we can show that: 1. \(P(1)\) is true 2. (\(\forall k < n \ P(k)) \implies P(n)\)
Then \(P(n)\) is true for all integers \(n >= 1\). \(P(1)\) is obviously true.
To use quicksort to sort an array of size đ, we partition it into three pieces: the first đ subarray, the pivot (which will be in its correct place), and the remaining subarray of size đâđâ1. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.
We show this is correct by strong induction: since the first subarray has đ<đ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has đâđâ1<đ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.1
voidinit(int n, int m){ this->n = n; this->m = m; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { c[i][j] = 0; } } }
voidadd(int x, int y, int v){ for (int i = x; i <= n; i += lowbit(i)) { for (int j = y; j <= m; j += lowbit(j)) { c[i][j] += v; } } }
intget(int x, int y){ int s = 0; for (int i = x; i > 0; i -= lowbit(i)) { for (int j = y; j > 0; j -= lowbit(j)) { s += c[i][j]; } } return s; } } bit;
bool star[N][N];
intmain(int argc, char **argv){ int n; while (scanf("%d", &n) != EOF) { int m = 1001; bit.init(m, m); for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { star[i][j] = false; } } for (int i = 0; i < n; i++) { char op[2]; scanf("%s", op); if (op[0] == 'B') { int x, y; scanf("%d%d", &x, &y); x++, y++; if (!star[x][y]) { star[x][y] = true; bit.add(x, y, 1); } } elseif (op[0] == 'D') { int x, y; scanf("%d%d", &x, &y); x++, y++; if (star[x][y]) { star[x][y] = false; bit.add(x, y, -1); } } else { int x1, x2, y1, y2; scanf("%d%d%d%d", &x1, &x2, &y1, &y2); if (x1 > x2) { swap(x1, x2); } if (y1 > y2) { swap(y1, y2); } x1++, x2++, y1++, y2++; int res = bit.get(x2, y2) - bit.get(x1 - 1, y2) - bit.get(x2, y1 - 1) + bit.get(x1 - 1, y1 - 1); printf("%d\n", res); } } } return0; }
If we can find two subtrees of root such that both of them has target, then root is the LCA of p and q. If there is exactly one subtree of root having target and root itself has target, then root is the LCA of p and q too.
classSolution { public: intnumTrees(int n){ // We consider the position of node n in the tree first. // Because all nodes on the tree except for node n is less than node, // if node n has children, that must be its left child. // Node n can have a parent if the value of its parent is less than its. // So we separate the n - 1 nodes into 2 parts, the first part is considered to be the parent part of node n, // and the second part is considered to be the left child part of node n. // We traverse every possible separation, for each separation we add the multiplication of the number of the combination // of the two parts to the answer of node n. vector<int> dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - 1 - j]; } } return dp[n]; } };
classSolution { public: intsearch(vector<int>& nums, int target){ int l = 0, r = nums.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) { // target on the left side and mid on the right side if (target > nums[r] && nums[mid] < nums[l]) r = mid - 1; else l = mid + 1; } else { // target on the right side and mid on the left side if (target < nums[l] && nums[mid] > nums[r]) l = mid + 1; else r = mid - 1; } } return-1; } };
Some details of this implementation borrow from sonyflake. Here using 8 bits to represent time in units of 500ms, 4 bits to represent sequence, 4 bits to represent machine. As a result:
The lifetime is \(2^8 \times 500ms = 128s\)
It can work in \(2^4 = 16\) distributed machines
It can generate \(2^4 = 16\) IDs per \(500ms\) at most in a single thread
machineID int64 startTick int64// ticks of the start time of IDFlake from UNIX epoch elapsedTick int64// elapsed ticks from start tick sequence int64 }
defmain(): whileTrue: res = requests.get('http://127.0.0.1:8080/get_id').json() print res if res.get('error'): break
if __name__ == '__main__': main()
Run
server:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
[GIN-debug] [WARNING] Creating an Engine instance with the Logger and Recovery middleware already attached.
[GIN-debug] [WARNING] Running in "debug" mode. Switch to "release" mode in production. - using env: export GIN_MODE=release - using code: gin.SetMode(gin.ReleaseMode)
[GIN-debug] Listening and serving HTTP on :8080 [2020-04-01 16:11:05] INFO slept for 285.71300000ms [2020-04-01 16:11:06] INFO slept for 446.46500000ms [2020-04-01 16:11:06] INFO slept for 450.56500000ms [2020-04-01 16:11:07] INFO slept for 449.93100000ms ...... [2020-04-01 16:13:08] INFO slept for 449.52100000ms [2020-04-01 16:13:09] INFO slept for 441.43400000ms [2020-04-01 16:13:09] INFO slept for 434.80600000ms [2020-04-01 16:13:10] INFO slept for 445.62500000ms [2020-04-01 16:13:10] INFO slept for 444.83400000ms [2020-04-01 16:13:11] INFO slept for 437.82700000ms [2020-04-01 16:13:11] WARN getID error: over the time limit
for i := int64(1); i <= num; { if bucket.TakeAvailable(1) == 1 { time.Sleep(timeNeed) i++ if i%1000 == 0 { now := time.Now() logger.Infof("rate: %.3f", 1000/now.Sub(lastTime).Seconds()) lastTime = now } } }
A Go map type looks like this: map[KeyType]ValueType where KeyType may be any type that is comparable (more on this later), and ValueType may be any type at all, including another map!
Key types
As mentioned earlier, map keys may be of any type that is comparable. The language spec defines this precisely, but in short, comparable types are boolean, numeric, string, pointer, channel, and interface types, and structs or arrays that contain only those types. Notably absent from the list are slices, maps, and functions; these types cannot be compared using ==, and may not be used as map keys.