2020-06-07 | 编程

leetcode1

NO177. 第N高的薪水
题目：编写一个 SQL 查询，获取 Employee 表中第 n 高的薪水（Salary）。

code：

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN 
    SET N=N-1;
    RETURN (select distinct Salary from Employee order by Salary desc limit N,1);
END

题解：limit的操作。目前对于截取第几个的操作有limit 2,1和limit 2 offset 1这两种。

1
2
3

select * from t limit 2 offset 1；代表是从第1条后面数据开始取出2条数据，即读取第2,3条

select * from t limit 2,1；代表跳过前两条数据取出1条数据，即读取第3条数据

NO178.分数排名
题目：编写一个 SQL 查询来实现分数排名。

code:

select a.Score,
    (select count(distinct Score) from Scores b where a.Score<=b.Score) as rank
from Scores a 
order by a.Score desc

题解：相当于统计b表中有多少个大于a表的元素。

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

code:

select distinct a.Num as ConsecutiveNums from 
Logs a 
left outer join Logs b on a.Id=b.Id-1
left outer join Logs c on b.Id=c.Id-1
where a.Num=b.Num and a.Num=c.Num

题解：三表join，Id差值为1，Num值相等。

NO184.部门工资最高的员工
题目：编写一个 SQL 查询，找出每个部门工资最高的员工。例如，根据上述给定的表格，Max 在 IT 部门有最高工资，Henry 在 Sales 部门有最高工资。

code

select d.Name as Department,b.Name as Employee,c.max_salary as Salary from 
Employee b 
inner join (select DepartmentId,max(Salary) as max_salary from Employee a group by 1 ) c on b.DepartmentId=c.DepartmentId and b.Salary=c.max_salary
inner  join Department d on b.DepartmentId = d.Id

题解：inner join 操作

NO185.部门工资前三高的所有员工
题目：

code:

select distinct e.Name as Department,d.Name as Employee,c.Salary from 
(select a.DepartmentId,a.Salary,
    (select count(distinct b.Salary) from Employee b 
    where b.Salary>=a.Salary and a.DepartmentId=b.DepartmentId) as rank
from Employee a 
order by a.DepartmentId,a.Salary desc) c
inner join Employee d on c.DepartmentId = d.DepartmentId and c.Salary=d.Salary
inner join Department e on c.DepartmentId = e.Id 
where c.rank<=3
order by e.Name asc,c.Salary desc

上面这个方法有点复杂了，比较耗时。

SELECT
    d.Name AS 'Department', e1.Name AS 'Employee', e1.Salary
FROM
    Employee e1
        JOIN
    Department d ON e1.DepartmentId = d.Id
WHERE
    3 > (SELECT
            COUNT(DISTINCT e2.Salary)
        FROM
            Employee e2
        WHERE
            e2.Salary > e1.Salary
                AND e1.DepartmentId = e2.DepartmentId
        )

面试题03.数组中重复的数字
题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

code:

#字典
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        d = {}
        for key in nums:
            d[key] = d.get(key,0)+1
        for key in d:
            if d[key]>=2:
                return key
                break
            else:
                pass

code:

#遍历用set
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        s = set()
        for items in nums:
            ll = len(s)
            s.add(items)
            if ll == len(s):
                return items
                break
            else:
                continue

面试题04.二维数组中的查找
题目：在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

code:

选对方向。

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        left = len(matrix)
        right = len(matrix[0])
        i, j = left - 1, 0 
        while i >= 0 and j < right :
            if matrix[i][j] > target:
                i = i - 1
            elif matrix[i][j] < target:
                j = j + 1 
            else:
                return True
        return False

面试题05.替换空格
题目：请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

code:

1
2
3

class Solution:
    def replaceSpace(self, s: str) -> str:
        return '%20'.join(s.split(' '))

面试题6.从头到位打印链表
题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

code:

1
2
3

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

面试题11.旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

code:

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        i, j = 0, len(numbers) - 1 
        while i < j:
            m = (i + j) // 2 
            if numbers[m] > numbers[j]:
                i = m + 1 
            elif numbers[m] < numbers[j]:
                j = m
            else:
                j = j - 1 
        return numbers[i]

面试题48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

核心思想：从左往右移动，如果最右边那个已经在字典中，则左侧开始+1.

code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right, res = 0, 0, 0
        length = len(s)
        windows = {}
        while right < length:
            c = s[right]
            if c not in windows:
                windows[c] = 1 
            else:
                windows[c] += 1
            right += 1 
            while c in windows and windows[c]>1:
                c2 = s[left]
                windows[c2] = windows[c2] - 1
                left += 1  
            res = max(res,right-left)
        return res