分类 LeetCode 下的文章

二叉树展开为链表

问题描述

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

例如，给定二叉树

   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);
    }
};

填充每个节点的下一个右侧节点指针/填充每个节点的下一个右侧节点指针 II

问题描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL

示例：

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

思路

  • 将二叉树按层存储到 vector<Node*> res中，我用的是深搜。详情可以见 https://www.irene.ink/archives/77/
  • 然后，除每层的最后一个节点外，让每个节点res[i][j]的next指向res[i][j+1],最后一个节点res[i][res[i].size()-1]的next指向nullptr；
  • 最后，返回根节点root即可。

题解

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    vector<vector<Node *>> res;
    Node *connect(Node *root) {
        if(root== nullptr)
            return root;
        dfs(root,0);
        for(int i=0;i<res.size();i++){
            for(int j=0;j<res[i].size()-1;j++){
                res[i][j]->next=res[i][j+1];
            }
            res[i][res[i].size()-1]->next= nullptr;
        }
        return root;
    }
    void dfs(Node *node,int dep){
        if(node== nullptr) return;
        if(dep+1>res.size()) res.push_back(vector<Node *>{});
        res[dep].push_back(node);
        if(node->left!= nullptr) dfs(node->left,dep+1);
        if(node->right!= nullptr) dfs(node->right,dep+1);
    }
};

第N高的薪水

问题描述

编写一个 SQL 查询，获取 Employee 表中第 n 高的薪水（Salary）。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

例如上述 Employee 表，n = 2 时，应返回第二高的薪水 200。如果不存在第 n 高的薪水，那么查询应返回 null。

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nth-highest-salary

思路

求第N个薪水的分页思想

  • 首先先将数据去重：SELECT DISTINCT Salary FROM Employee
  • 再将是数据按薪水降序排除：SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC
  • 分页的思想是一页一条数据，第二高的薪水则在第二页：SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1, 1
  • 第N高的薪水则在第N页:SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT N-1, 1
  • 考虑到极端情况：没有第二薪水则为空，使用ifnull判断：SELECT IFNULL( (SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT N-1, 1),null) AS SecondHighestSalary

作者：li-qiu-xin-yi
链接：https://leetcode-cn.com/problems/two-sum/solution/qiu-di-nge-xin-shui-de-fen-ye-si-xiang-by-li-qiu-x/

题解

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  DECLARE P INT;
  SET P = N-1;
  RETURN (  
    SELECT
    IFNULL(
    (    SELECT DISTINCT
            Salary
        FROM
            Employee
        ORDER BY
            Salary DESC
        LIMIT P,1),
        NULL
    ) AS getNthHighestSalary
      
  );
END

连续出现的数字

问题描述

编写一个 SQL 查询，查找所有至少连续出现三次的数字。

+----+-----+
| Id | Num |
+----+-----+
| 1  |  1  |
| 2  |  1  |
| 3  |  1  |
| 4  |  2  |
| 5  |  1  |
| 6  |  2  |
| 7  |  2  |
+----+-----+

例如，给定上面的 Logs 表， 1 是唯一连续出现至少三次的数字。

| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

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

题解

SELECT DISTINCT
    l1.Num AS ConsecutiveNums
FROM
    Logs l1,
    Logs l2,
    Logs l3
WHERE
    l1.Id = l2.Id - 1
    AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num
    AND l2.Num = l3.Num

注意

DISTINCT必须加上，否则会返回重复元素。
distinct.png

有效的数独

问题描述

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

有效的数独.png

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:
输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

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

思路

  • vector<vector<int>> rows(9, vector<int>(9, 0)); 每行的数字1-9未出现过
  • vector<vector<int>> cols(9, vector<int>(9, 0)); 每列的数字1-9未出现过
  • vector<vector<int>> cell(9, vector<int>(9, 0)); 每个3x3 宫格内数字1-9未出现过
    在遍历的过程中，i行的数字num（char）第一次出现时，将rows[i]中第num-'1'+1列的值即rowsi置为1，如果在i行第二次出现即rowsi==1，则不是有效的数独，返回false;
    其他两种，同理。

其中非常有意思的一点是，将9*9的宫格转化为9个3*3的宫格时，每个3*3的宫格占cell中的一行，在遍历i、j时，用(i/3)*3+j/3的值即可计算出board[i][j]在第几个宫格。

宫格转换.png

题解

class Solution {
public:
    bool isValidSudoku(vector<vector<char>> &board) {
        vector<vector<int>> rows(9, vector<int>(9, 0));
        vector<vector<int>> cols(9, vector<int>(9, 0));
        vector<vector<int>> cell(9, vector<int>(9, 0));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int e = board[i][j] - '1';
                if (rows[i][e] == 0) rows[i][e] = 1;
                else return false;
                if (cols[j][e] == 0) cols[j][e] = 1;
                else return false;
                if(cell[(i/3)*3+j/3][e]==0) cell[(i/3)*3+j/3][e]=1;
                else return false;
            }
        }
        return true;
    }
};
  1. 1
  2. ...
  3. 4
  4. 5
  5. 6
  6. 7
  7. 8
  8. 9
  9. 10
  10. ...
  11. 28