LeetCode

LeetCode: Concurrency Originally published in Chinese on 2019-07-22; this English edition preserves the original scope and technical context. Title 1114 Print in order C++ mutex class Foo { mutex lock1, lock2; public: Foo() { lock1.lock(); lock2.lock(); } void first(function<void()> printFirst) { printFirst(); lock1.unlock(); } void second(function<void()> printSecond) { lock1.lock(); printSecond(); lock1.unlock(); lock2.unlock(); } void third(function<void()> printThird) { lock2.lock(); printThird(); lock2.unlock(); } }; C++ condition_variable class Foo { int i; mutex mut; condition_variable con_var1, con_var2; public: Foo() : i(1) { } void first(function<void()> printFirst) { unique_lock<mutex> lock(mut); printFirst(); ++i; con_var1.notify_one(); } void second(function<void()> printSecond) { unique_lock<mutex> lock(mut); con_var1.wait(lock, [this]() { return i == 2; }); printSecond(); ++i; con_var2.notify_one(); } void third(function<void()> printThird) { unique_lock<mutex> lock(mut); con_var2.wait(lock, [this]() { return i == 3; }); printThird(); } }; C++ atomic class Foo { atomic_int i; public: Foo() : i(1) { } void first(function<void()> printFirst) { printFirst(); ++i; } void second(function<void()> printSecond) { while (i != 2) {} printSecond(); ++i; } void third(function<void()> printThird) { while (i != 3) {} printThird(); i = 1; } }; C++ promise class Foo { promise<void> pro1, pro2; public: Foo() { } void first(function<void()> printFirst) { printFirst(); pro1.set_value(); } void second(function<void()> printSecond) { pro1.get_future().wait(); printSecond(); pro2.set_value(); } void third(function<void()> printThird) { pro2.get_future().wait(); printThird(); } }; 1115 Print FooBar alternately C++ mutex class FooBar { private: int n; mutex mut1, mut2; public: FooBar(int n) { this->n = n; mut2.lock(); } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { mut1.lock(); printFoo(); mut2.unlock(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { mut2.lock(); printBar(); mut1.unlock(); } } }; C++ condition_variable class FooBar { private: int m, n; mutex mut; condition_variable con_var1, con_var2; public: FooBar(int n) : n(n), m(0) { } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { unique_lock<mutex> lock(mut); con_var1.wait(lock, [&]() { return m == 0; }); printFoo(); ++m; con_var2.notify_one(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { unique_lock<mutex> lock(mut); con_var2.wait(lock, [&]() { return m == 1; }); printBar(); m = 0; con_var1.notify_one(); } } }; C++ atomic class FooBar { private: int n; atomic_int m; public: FooBar(int n) : n(n), m(0) { } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { while (m != 0) {} printFoo(); m = 1; } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { while (m != 1) {} printBar(); m = 0; } } }; C++ promise class FooBar { private: int n; vector<promise<void>> pros1, pros2; public: FooBar(int n) : n(n) { for (int i = 0; i < n; ++i) { pros1.push_back(promise<void>()); pros2.push_back(promise<void>()); } } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { if (i != 0) pros1[i - 1].get_future().wait(); printFoo(); pros2[i].set_value(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { pros2[i].get_future().wait(); printBar(); pros1[i].set_value(); } } }; 1116 Print zero and odd and even numbers C++ mutex class ZeroEvenOdd { private: int m, n; mutex mut_zero, mut_odd, mut_even; public: ZeroEvenOdd(int n) { this->m = 1; this->n = n; mut_odd.lock(); mut_even.lock(); } void zero(function<void(int)> printNumber) { for (int i = 0; i < n; ++i) { mut_zero.lock(); printNumber(0); if (this->m % 2 == 1) mut_odd.unlock(); else mut_even.unlock(); } } void even(function<void(int)> printNumber) { for (int i = 0; i < n / 2; ++i) { mut_even.lock(); printNumber(this->m); ++this->m; mut_zero.unlock(); } } void odd(function<void(int)> printNumber) { for (int i = 0; i < (n + 1) / 2; ++i) { mut_odd.lock(); printNumber(this->m); ++this->m; mut_zero.unlock(); } } }; 1117 H2O generation C++ condition variable class H2O { int m = 1; mutex mut; condition_variable con_var; public: void hydrogen(function<void()> releaseHydrogen) { unique_lock<mutex> lock(mut); con_var.wait(lock, [&]() { return m % 3 != 0; }); ++m; releaseHydrogen(); con_var.notify_all(); } void oxygen(function<void()> releaseOxygen) { unique_lock<mutex> lock(mut); con_var.wait(lock, [&]() { return m % 3 == 0; }); ++m; releaseOxygen(); con_var.notify_all(); } }; Original references Reference 1

LeetCode: Trees (2) Originally published in Chinese on 2019-07-18; this English edition preserves the original scope and technical context. Title 3. Binary search tree 95 different binary search trees II Generate a binary search tree consisting of 1…n nodes. In order to construct a binary search tree with i as the root node, we need to first construct all binary search trees with 1 … i - 1 as the left subtree and all binary search trees with i + 1 … n as the right subtree, and then arrange and combine these subtrees to obtain all binary search trees with i as the root node. ...

LeetCode: Trees (1) Originally published in Chinese on 2019-07-13; this English edition preserves the original scope and technical context. Title 1. Tree traversal 144 Preorder traversal of binary trees Preorder traversal of a binary tree. Preorder traversal traverses a binary tree in the order of the root node, left child node, and right child node. There are two methods: recursive and iterative. For the iterative method, first add the node to the result array, then use a stack to save the right and left child nodes, access them in sequence, and repeat the process. ...

LeetCode: Linked Lists (2) Originally published in Chinese on 2019-07-09; this English edition preserves the original scope and technical context. Title 4. Double pointer 19 Delete the penultimate N node of the linked list Delete the nth node from the last in the linked list. It is not easy to directly access the nth position from the bottom in the linked list, so two pointers prev and tail are used. The tail goes forward n steps first, and then the two pointers go forward together until tail has no successor pointer. At this time, the successor pointer of prev is the nth position from the bottom, just delete it. Note that if the pointer to be deleted is the head pointer, it must be processed separately. ...

LeetCode: Linked Lists (1) Originally published in Chinese on 2019-07-04; this English edition preserves the original scope and technical context. Title 1. General questions 2 Add two numbers Given two linked lists respectively representing the reverse order of two positive numbers, calculate the sum of the two linked lists. Add them bit by bit. class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { int acc = 0, val = 0; auto head = l1, tail = l1; while (l1 && l2) { val = l1->val + l2->val + acc; acc = val / 10; l1->val = val % 10; if (!l1->next) l1->next = l2->next, l2->next = nullptr; tail = l1; l1 = l1->next, l2 = l2->next; } while (l1) { val = l1->val + acc; acc = val / 10; l1->val = val % 10; tail = l1; l1 = l1->next; } if (acc) tail->next = new ListNode(1); return head; } }; 21 Merge two ordered linked lists Merge two sorted linked lists. ...