45.日常算法

1.第二高的薪水

题目来源

Employee 表：
+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+
id 是这个表的主键。
表的每一行包含员工的工资信息。

查询并返回 Employee 表中第二高的 不同 薪水 。如果不存在第二高的薪水，查询应该返回 null(Pandas 则返回 None) 。查询结果如下例所示。

示例 1：

输入：
Employee 表：
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
输出：
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

# Write your MySQL query statement below
select (
    select distinct # 去重
        salary 
    from 
        Employee 
    order by salary desc # 降序排序
    limit 1, 1 # 筛选
) as SecondHighestSalary # 重命名

1.格雷编码

题目来源

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）第一个整数是 0一个整数在序列中出现 不超过一次每对 相邻 整数的二进制表示 恰好一位不同 ，且第一个 和 最后一个 整数的二进制表示 恰好一位不同给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

• 00 和 01 有一位不同
• 01 和 11 有一位不同
• 11 和 10 有一位不同
• 10 和 00 有一位不同
  [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
• 00 和 10 有一位不同
• 10 和 11 有一位不同
• 11 和 01 有一位不同
• 01 和 00 有一位不同

方法一：模拟

class Solution {
public:
    vector<int> grayCode(int n) {
        int c = (int)pow(2, n);
        int hash[70000] = {0};
        int k = 0;
        vector<int> ret;
        ret.push_back(0);
        hash[0] = 1;
        for (int i = 1; i < c; ++i){
            for (int j = 0; j < 32; ++j){
                int val = (1 <<j) ^ k;
                if (hash[val] != 1){
                    hash[val] = 1;
                    ret.push_back(val);
                    k = val;
                    break;
                }
            }
        }
        return ret;
    }
};

方法二：数学推导

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret(1 << n, 0);
        for (int i = 1; i < (1 << n); ++i){
            ret[i] = i ^ (i >> 1);
        }
        return ret;
    }
};