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