换座位

问题描述

小美是一所中学的信息科技老师，她有一张 seat 座位表，平时用来储存学生名字和与他们相对应的座位 id。

其中纵列的 id 是连续递增的

小美想改变相邻俩学生的座位。

你能不能帮她写一个 SQL query 来输出小美想要的结果呢？

示例：

+---------+---------+
|    id   | student |
+---------+---------+
|    1    | Abbot   |
|    2    | Doris   |
|    3    | Emerson |
|    4    | Green   |
|    5    | Jeames  |
+---------+---------+

假如数据输入的是上表，则输出结果如下：

+---------+---------+
|    id   | student |
+---------+---------+
|    1    | Doris   |
|    2    | Abbot   |
|    3    | Green   |
|    4    | Emerson |
|    5    | Jeames  |
+---------+---------+

注意：
如果学生人数是奇数，则不需要改变最后一个同学的座位。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/exchange-seats

思路

• 调换id
• 根据id进行升序排序

题解

SELECT (CASE 
            WHEN MOD(id,2) = 1 AND id = (SELECT COUNT(*) FROM seat) THEN id
            WHEN MOD(id,2) = 1 THEN id+1
            ElSE id-1
        END) AS id, student
FROM seat
ORDER BY id;

交替打印FooBar

问题描述

我们提供一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

请设计修改程序，以确保 "foobar" 被输出 n 次。

示例 1:
输入: n = 1
输出: "foobar"
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2:
输入: n = 2
输出: "foobarfoobar"
解释: "foobar" 将被输出两次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-foobar-alternately

题解

class FooBar {
private:
    int n;
    pthread_mutex_t one = PTHREAD_MUTEX_INITIALIZER;
    pthread_mutex_t two = PTHREAD_MUTEX_INITIALIZER;
public:
    FooBar(int n) {
        this->n = n;
        pthread_mutex_lock(&two);
    }

    void foo(function<void()> printFoo) {

        for (int i = 0; i < n; i++) {

            // printFoo() outputs "foo". Do not change or remove this line.
            pthread_mutex_lock(&one);
            printFoo();
            pthread_mutex_unlock(&two);
        }
    }

    void bar(function<void()> printBar) {

        for (int i = 0; i < n; i++) {

            // printBar() outputs "bar". Do not change or remove this line.
            pthread_mutex_lock(&two);
            printBar();
            pthread_mutex_unlock(&one);
        }
    }
};

路径总和 II

问题描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii

思路

深搜

• 当节点是叶子节点时，就不用向下继续搜索了。
• 非叶子节点，左右子树都遍历完以后，就将其从vector中弹出。

详细实现可以在题解中查看，很容易理解的。

题解

class Solution {
public:
    vector<int> vec;
    vector<vector<int>> ret;

    void dfs(TreeNode *node, int sum, int target) {
        if (node->left == nullptr && node->right== nullptr) {
            vec.push_back(node->val);
            sum+=node->val;
            if (sum== target) {
                ret.push_back(vec);
            }
            vec.pop_back();
            return;
        }
        vec.push_back(node->val);
        if(node->left!= nullptr)dfs(node->left, sum + node->val, target);
        if(node->right!= nullptr) dfs(node->right, sum + node->val, target);
        vec.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode *root, int sum) {
        if (root != nullptr) {
            dfs(root, 0, sum);
        }
        return ret;
    }
};

排序链表

问题描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list

思路

• 遍历链表，将链表存在一个int类型的vector中。
• 对链表进行排序。
• 根据vector重新建立一个链表。

题解

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        if(vec.size()==0)
            return nullptr;
        sort(vec.begin(),vec.end());
        ListNode *q = nullptr;
        ListNode *ret;
        for (int i = 0; i < vec.size(); i++) {
            if (q == nullptr) {
                q = new ListNode(vec[i]);
                ret=q;

            } else {
                q->next = new ListNode(vec[i]);
                q = q->next;
            }
        }
        return ret;
    }
};

二叉树展开为链表

问题描述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

   1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

思路

题目描述中是将二叉树展开为链表，但是函数返回值是void，所以题目真实的要求应该是将一个二叉树按中序遍历的顺序展开为一个只有右子树的二叉树。

• 将二叉树按照中序遍历的顺序存储到一个vector<TreeNode*>中。
• TreeNode *p=root,即从root所在的节点开始，其左子树为nullptr，右子树为vec[i]（注意i是从1开始的），然后，p=p->right

题解

class Solution {
public:
    vector<TreeNode*> vec;
    void flatten(TreeNode* root) {
        TreeNode *p=root;
        dfs(root);
        for(int i=1;i<vec.size();i++){
            p->left= nullptr;
            p->right=vec[i];
            p=p->right;
        }
   }
   void dfs(TreeNode *node){
        if(node== nullptr) return;
        vec.push_back(node);
        dfs(node->left);
        dfs(node->right);
    }
};