LeetCode

LeetCode 并发 题目 1114 按序打印 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 交替打印FooBar 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 打印零与奇偶数 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 生成 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(); } };

LeetCode 树（2） 题目 3. 二叉搜索树 95 不同的二叉搜索树 II 生成由 1 … n 为节点所组成的二叉搜索树。 为了构造以 i 为根节点的二叉搜索树，我们需要先构造以 1 … i - 1 为左子树的所有二叉搜索树与以 i + 1 … n 为右子树的所有二叉搜索树，再将这些子树排列组合得到以 i 为根节点的所有二叉搜索树。 class Solution { public: vector<TreeNode *> generateTrees(int n) { if (n == 0) return {}; return Generate(1, n); } vector<TreeNode *> Generate(int m, int n) { vector<TreeNode *> nodes; if (m == n) nodes.push_back(new TreeNode(n)); if (m > n) nodes.push_back(nullptr); if (m >= n) return nodes; for (int i = m; i <= n; ++i) { vector<TreeNode *> left = Generate(m, i - 1); vector<TreeNode *> right = Generate(i + 1, n); for (auto &l:left) for (auto &r:right) { TreeNode *node = new TreeNode(i); node->left = l, node->right = r; nodes.push_back(node); } } return nodes; } }; 98 验证二叉搜索树 因为二叉搜索树的中序遍历结果是一个有序数组，所以一种方法是将中序遍历的结果保存下来进行判断，也可以根据二叉搜索树的定义判断子节点和根节点的大小关系。 ...

LeetCode 树（1） 题目 1. 树的遍历 144 二叉树的前序遍历 前序遍历一个二叉树。 前序遍历是按照根节点，左子节点，右子节点的顺序来遍历一个二叉树，有递归和迭代两种方法。对于迭代方法，先将节点加入结果数组，然后用一个栈保存右，左子节点，依次访问，重复此过程。 class Solution { vector<int> res; public: vector<int> preorderTraversal(TreeNode *root) { res = vector<int>(); Preorder(root); return res; } void Preorder(TreeNode *root) { if (!root) return; res.push_back(root->val); Preorder(root->left); Preorder(root->right); } }; class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> res; if (!root) return res; stack<TreeNode *> pre; pre.push(root); while (!pre.empty()) { TreeNode *node = pre.top(); pre.pop(); res.push_back(node->val); if (node->right) pre.push(node->right); if (node->left) pre.push(node->left); } return res; } }; 589 N叉树的前序遍历 前序遍历一个 N 叉树。 ...

LeetCode 链表（2） 题目 4. 双指针 19 删除链表的倒数第N个节点 删除链表的倒数第 n 个节点。 在链表中不易直接取到倒数第 n 个位置，所以用两个指针 prev 和 tail，tail 先往前走 n 步，然后两个指针一起往前走直到 tail 没有后继指针，此时 prev 的后继指针就是倒数第 n 个位置，删除其即可。注意如果要删除的指针是头指针的话要单独处理。 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *prev = head, *tail = head; for (int i = 0; i < n; ++i) tail = tail->next; if (!tail) { head = head->next; delete prev; return head; } while (tail->next) tail = tail->next, prev = prev->next; ListNode *next = prev->next; prev->next = next->next; delete next; return head; } }; 61 旋转链表 给一个链表，将其每个节点向右移动 k 个位置。 ...

LeetCode 链表（1） 题目 1. 常规题 2 两数相加 给两个链表分别代表两个正数的逆序表示，计算两个链表之和。 依次按位进行相加。 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 合并两个有序链表 合并两个有序链表。 ...