[leetcode]第二十八部分(181-187)

181. Employees Earning More Than Their Managers

问题难度: ♣

问题描述

Employee表中存储着所有雇员的信息(包括经理). 每个雇员都有一个工号id, 最后一列为其经理的id:

+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+

给定Employee表, 写一个SQL查询语句找出那些工资比他们经理高的员工们. 在上面的表中, 只有Joe的工资比他的经理高.

+----------+
| Employee |
+----------+
| Joe      |
+----------+

解题思路

这道题是一个考察SQL的题目. 需要考虑到自连接:

  • 第一步: 将员工的工资和经理的工资放在同一行, 需要自己join一下: select e.salary, (select salary from Employee m where e.ManagerId = m.Id) as m.salary from Employee e, (由于两个表名字相同, 需要使用到mysql中的别名)
  • 第二步: 筛选出员工工资比经理高的员工: select e_name as Employee from (select e.name as e_name, e.salary as e_salary, (select salary from Employee m where e.ManagerId = m.Id) as m_salary from Employee e) as f where f.e_salary > f.m_salary

代码

# Write your MySQL query statement below
select e_name as Employee from (select e.name as e_name, e.salary as e_salary, (select salary from Employee m where e.ManagerId = m.Id)  as m_salary from Employee e) as f where f.e_salary > f.m_salary

182. Duplicate Emails

问题难度: ♣

问题描述

写一个SQL查询出一个名为Person的表中的所有重复邮件.

+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+

例如, 针对上面的表, 应该返回下面的结果:

+---------+
| Email   |
+---------+
| a@b.com |
+---------+

注意: 所有邮件都是小写.

解题思路

直接使用havinggroup by相结合.

代码

# Write your MySQL query statement below
select Email from Person group by Email having count(Email) > 1

183. Customers Who Never Order

问题难度: ♣

问题描述

假设一个网站包含两个表, CustomersOrders表, 写一个SQL查询找到所有从未订购过东西的客户.

Customers表:

+----+-------+
| Id | Name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+

Orders表:

+----+------------+
| Id | CustomerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+

基于上面的示例, 返回以下数据:

+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+

解题思路

可以使用到mysql中的not in, 但是很显然, 时间复杂度比较高.

在这里, 也可以使用Left JOIN来进行解决.

代码

# Write your MySQL query statement below
select Name as Customers from Customers where Id not in (select distinct(CustomerId) from Orders)
# Write your MySQL query statement below
select Name as Customers from Customers left join (select CustomerId from Orders) as ods on Customers.Id = ods.CustomerId where ods.CustomerId is NULL;

184. Department Highest Salary

问题难度: ♣ ♣ ♣

问题描述

Employee表中存储着所有员工的信息. 每个员工有一个ID和工资, 还有一列为部门id.

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

Department表存储着公司所有部门的信息.

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

写一个SQL查询语句找到每个部门中工资最高的员工及对应的工资.

针对上面的示例, MaxIT部门最高的工资, 而HenrySales部门最高的工资.

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+

解题思路

首先, 在Department表中找到每个部门最高的工资(使用group bymax)
select Employee.DepartmentId, Employee.Name, Employee.Salary from Employee, (select DepartmentId, max(Salary) as max_salary from Employee group by DepartmentId) as e where e.DepartmentId = Employee.DepartmentId and e.max_salary=Salary;

再将该表与Departmentjoin一下:
select d.Name as Department, e.Name as Employee, e.max_salary as Salary from Department d inner join(...) as e on e.DepartmentId = d.Name

代码

# Write your MySQL query statement below
select d.Name as Department, e.Name as Employee, e.Salary from Department d inner join(select Employee.DepartmentId, Employee.Name, Employee.Salary from Employee, (select DepartmentId, max(Salary) as max_salary from Employee group by DepartmentId) as e where e.DepartmentId = Employee.DepartmentId and e.max_salary=Salary) as e on e.DepartmentId = d.Id;

185. Department Top Three Salaries

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

Employee表存储着所有员工的信息. 每个员工都有一个id和对应的工资以及部门id.

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
+----+-------+--------+--------------+

Department表存储着公司所有部门的信息.

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

写一个SQL语句找到上表中每个部门前三高公司的员工, 我们的SQL语句应该返回下列行:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

解题思路

首先考虑结合使用sort以及limit, 找到每个部门top 3工资的员工, 解决过程如下:

  • 基于DepartmentIdSalary进行排序
  • 然后对相同部门的员工工资进行排序(特别注意: 如果工资相等, 那么排序应该也要相等)
  • 取出排序在前三的员工的信息
  • 将部门信息join起来

代码

# Write your MySQL query statement below
SELECT d.Name AS Department, e.Name AS Employee, e.Salary
FROM(
SELECT t.Name,
CASE
WHEN t.DepartmentId = @preDep THEN 
    CASE
    WHEN t.Salary = @preSal THEN @rank
    ELSE @rank := @rank + 1
    END
ELSE @rank := 1
END
AS rank,
@preDep := t.DepartmentId AS depId,
@preSal := t.Salary AS Salary
FROM
(SELECT * FROM Employee ORDER BY DepartmentId, Salary DESC) AS t, 
(SELECT @rank := 0, @preDep := -1, @preSal := -1) INIT
) AS e JOIN Department as d ON e.depId = d.Id WHERE e.rank <=3;

186. Reverse Words in a String II

问题难度: ♣ ♣ ♣

问题描述

给定一个输入字符串, 逐个单词逐个单词翻转字符串.

示例

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

注意
– 一个单词的定义为: 一个非空字符串的序列
– 输入字符串前后不包含空字符串
– 单词之间一般用""分隔

延伸: 尝试在O(1)的空间复杂度内就地解决这个问题.

解题思路

和之前第158题的想法类似, 甚至比之前更简单, 因为不用考虑多余的空格问题. 首先将整个字符串旋转, 再将逐个单词进行旋转.

代码

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: a list of 1 length strings (List[str])
        :rtype: nothing
        """
        def reverse(s, i, j):
            # 将s从i到j的元素进行对调
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        reverse(s, 0, len(s)-1)
        # 然后遍历, 找到每个单词的起始位置和终止位置
        start_idx, end_idx = 0, 0
        for i in range(1, len(s)):
            while i < len(s) and s[i] != " ":
                i += 1
            end_idx = i - 1
            reverse(s, start_idx, end_idx)
            start_idx = i + 1
sl = Solution()
s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
sl.reverseWords(s)
print(s)
['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']

187. Repeated DNA Sequences

问题难度: ♣ ♣ ♣

问题描述

所有的DNA都是由简写为A,C,G,T的核苷酸序列构成, 例如: "ACGAATTCCG",在研究DNA的时候, 识别DNA中的重复序列有时候是非常有用的.

写一个函数找到所有出现在一个DNA分子中超过一次的10个字符长度的序列(子串).

示例

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

解题思路

最直接的方式: 维护一个10字符的字符窗口, 首先判断返回列表中是否已经包含了该字符串, 如果不包含, 那么直接向后开始找是否有相同的字符串即可; 如果包含, 则直接跳过.

好的, 那么问题转变为了: 怎么判断某个字符串中是否有相同的字符串.

  • 先试用一用python中自带的in函数. 有点吃惊, 居然AC了, 很显然, 这种方法的时间复杂度应该有O(n^3)

然后参考了下网上的代码, 再讲一种比较简单的思路:

由于字符串只可能由4中字符构成, 四种字符的二进制表示为;

A: 0100 0001
C: 0100 0011
G: 0100 0111
T: 0101 0100

可以发现, 最后三位能够标识不同的字符, 然后这里要求的是10个字符, 因此需要3*10=32位来标识这10个字符, 换算成十六进制大概是8位, 为了提取出后30位, 我们还需要使用一个mask, 0x7ffffff用这个mask可以取出后27位, 再向左平移3位即可. 算法的基本思想: 第一次取出前10个字符之后, 将其存在哈希表中; 之后向左移动3位, 再将当前字符的最后3为存储到后面, 查找新字符串在哈希表中出现的次数, 如果正好出现过1次, 则将次数设置为1, 并且将其加入到返回列表中. (PPPS... 这样的做法存储进去可以比较节省内存.)

代码

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ret_list = []
        char_size = 10
        for i in range(len(s) - char_size):
            cur_str = s[i: i + char_size]
            if cur_str not in ret_list and cur_str in s[i+1:]:
                ret_list.append(cur_str)
        return ret_list


    def findRepeatedDnaSequencesBit(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) <= 10:
            return []
        mask = 0x7ffffff
        cur = 0
        str_dict = dict()
        ret_list = list()
        for i in range(9):
            cur = (cur << 3) | (ord(s[i]) & 7)
        for i in range(9, len(s)):
            cur = ((cur & mask) << 3) |  (ord(s[i]) & 7)
            if cur in str_dict:
                cnt = str_dict[cur]
                if cnt == 1:
                    ret_list.append(s[i-9:i+1])
                str_dict[cur] += 1
            else:
                str_dict[cur] = 1
        return ret_list
sl = Solution()
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
print(sl.findRepeatedDnaSequences(s))
print(sl.findRepeatedDnaSequencesBit(s))
s = "AAAAAAAAAAAA"
print(sl.findRepeatedDnaSequences(s))
print(sl.findRepeatedDnaSequencesBit(s))
['AAAAACCCCC', 'CCCCCAAAAA']
['AAAAACCCCC', 'CCCCCAAAAA']
['AAAAAAAAAA']
['AAAAAAAAAA']
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注