填充每个节点的下一个右侧节点指针/填充每个节点的下一个右侧节点指针 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必须加上，否则会返回重复元素。

有效的数独

问题描述

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

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

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

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

示例 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]在第几个宫格。

题解

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

组合总和 II

问题描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

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

思路

本题分为两步

简单的回溯算法
对未完全剪枝的ret进行去重。

去重的方法有两种，效率都比较低

• sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end())
• set<vector<int>> sets(ret.begin(), ret.end());ret=vector<vector<int>>(sets.begin(),sets.end())

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    int n;

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        n = candidates.size();
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, 0, target);
        sort(ret.begin(), ret.end());
        ret.erase(unique(ret.begin(), ret.end()), ret.end());
        return ret;
    }

    void dfs(vector<int> vec, int sum, int location, int target) {
        if (sum >= target || location == n) {
            if (sum == target) {
                ret.push_back(tmp);
            }
            return;
        }
        for (int i = location; i < n; i++) {
            tmp.push_back(vec[i]);
            sum += vec[i];
            dfs(vec, sum, i + 1, target);
            sum = sum - vec[i];
            tmp.pop_back();
        }
    }
};