@Author：Runsen

求职季在即，技巧千万条，硬实力才是关键，听说今年疫情大环境不好，更要好好准备才行。于是Runsen在牛客网，Leetcode，九章算法，不断地寻找面试真题，共计100题，包括Python基础，算法，数据库，SQL，Linux。

大四刷题拼offer系列，不拼不行啊。我先刷下牛客网的Python的题目和知识点，适当的记录下自己做
错的题目。然后刷Java面试题。

41、查找最晚入职员工的所有信息

这个题目的是入门的水平，就是目前所有的数据里员工入职的日期都不是同一天（sqlite里面的注释为–，在mysql中为comment）

CREATE TABLE `employees` (
`emp_no` int(11) NOT NULL,  -- '员工编号'
`birth_date` date NOT NULL,
`first_name` varchar(14) NOT NULL,
`last_name` varchar(16) NOT NULL,
`gender` char(1) NOT NULL,
`hire_date` date NOT NULL,
PRIMARY KEY (`emp_no`));

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

其实就是有一个员工表，查找最晚入职员工的所有信息。

很简单直接降序：select * from employees order by hire_date desc limit 1

还有一种方法激素使用子查询，针对的是最后一天的时间有多个员工信息：select * from employees where hire_date = (select max(hire_date) from employees);

42、查找入职员工时间排名倒数第三的员工所有信息

这个题目和上面变了，现在寻找倒数第三。那么就使用limit+offset 。offset 就是区间长度的意思，可以是一个数，也可以是一个区间，记得是从0开始，和Python列表完全一样。

下面举几个limit+offset 的示例。

以下的两种方式均表示取2,3,4三条条数据。
1.select* from test LIMIT 1,3;
当limit后面跟两个参数的时候，第一个数表示要跳过的数量，后一位表示要取的数量。

2.select * from test LIMIT 3 OFFSET 1;(在mysql 5以后支持这种写法)
当 limit和offset组合使用的时候，limit后面只能有一个参数，表示要取的的数量,offset表示要跳过的数量 。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

查找入职员工时间排名倒数第三的员工所有信息的SQl代码：select * from employees order by hire_date desc limit 1 offset 2

43、Leetcode175. 组合两个表

表1: Person
+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| PersonId | int |
| FirstName   | varchar |
| LastName | varchar |
+-------------+---------+
PersonId 是上表主键

表2: Address

+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| AddressId   | int |
| PersonId | int |
| City | varchar |
| State | varchar |
+-------------+---------+
AddressId 是上表主键
编写一个 SQL 查询，满足条件：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息：

FirstName, LastName, City, State


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

在Leetcode这题有一个要求：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息。其实这就是左连接。

select FirstName,LastName,City,State from Person left join Address on Person.PersonId = Address.PersonId

44、Leetcode176 第二高的薪水

编写一个 SQL 查询，获取 Employee 表中第二高的薪水（Salary） 。
+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100 |
| 2  | 200 |
| 3  | 300 |
+----+--------+
例如上述 Employee 表，SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 null。

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200 |
+---------------------+


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

首先考虑选取最高工资的， 然后再选取次高， 其中用到了嵌套

SELECT max(Salary) AS SecondHighestSalary FROM Employee WHERE Salary < (SELECT MAX(Salary) FROM Employee);

  

 

  
1
 

用order BY 排序，再LIMIT output，输出更加快。

SELECT max(Salary) AS SecondHighestSalary FROM Employee WHERE Salary < (SELECT Salary
FROM Employee ORDER BY Salary DESC LIMIT 1);

  

 

  
1
  
2
 

最好的方法就是使用ifnull + limit + offset

ifnull(expression,value)

• 当expression获得数据为空的时候，返回value，有点类似python的 dict.get(x，value)的形式，即当一个查询没有对应的值的时候，返回一个默认值，这个默认值可以自定义

limit x offset y

• 跳过y条记录，返回x条记录

order by xx

• 这个就是按照xx字段排序，后面可以用desc/asc指定是降序还是升序

• 那么，综合以上，就是要按照Salary字段排序且按降序排序，并跳过排序结果的第一条，再返回一条

• 因为是跳过了降序排序结果的第一条，再返回一条，那么返回的就是第二高的记录

• 并用ifnull函数控制查询结果为空的时候的返回结果

select ifnull((select distinct Salary from Employee order by Salary desc limit 1 offset 1),null) as SecondHighestSalary

45、Leetcode 177. 第N高的薪水

编写一个 SQL 查询，获取 Employee 表中第 n 高的薪水（Salary）。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100 |
| 2  | 200 |
| 3  | 300 |
+----+--------+
例如上述 Employee 表，n = 2 时，应返回第二高的薪水 200。如果不存在第 n 高的薪水，那么查询应返回 null。

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200 |
+------------------------+


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

代码逻辑基本和上一题的一样，就是多了一个判断的条件。

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  if N<0 then RETURN (select min(Salary) from Employee);
  else set N = N-1; RETURN ( # Write your MySQL query statement below. select ifnull((select distinct Salary from Employee order by Salary desc limit N,1),null) as NthHighestSalay );
  end if;
END

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

46、将二维数组合并成一维数组

extend这个需要和append区别开来。extend将二维数组合并成一维数组，很多人不知道的。

lst = [[1,2,3],[4,5,6],[7,8,9]]
ll=[]
for l in lst: # ll+=l ll.extend(l)
print(ll)

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

在这里提供内置的方法chain

from itertools import chain
list(chain.from_iterable(lst))

  

 

  
1
  
2
 

47、将字典的values进行排序

将列表alist=[{'name':'a','age':25},{'name':'b','age':30},{'name':'c','age':20}]，按照age的值从大到小排列。

alist=[{'name':'a','age':25},{'name':'b','age':30},{'name':'c','age':20}]
blist=sorted(alist,key=lambda x:x['age'],reverse=True)
print(blist)
# [{'name': 'b', 'age': 30}, {'name': 'a', 'age': 25}, {'name': 'c', 'age': 20}]

  

 

  
1
  
2
  
3
  
4
 

48、两个元组或者列表合并成字典

写代码：如何由tuple1=('a','b','c','d','e')，和tuple2=(1,2,3,4,5)得到res={'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}。

tuple1=('a','b','c','d','e')
tuple2=(1,2,3,4,5)
res=dict(zip(tuple1,tuple2))
print(res)
# {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  

 

  
1
  
2
  
3
  
4
  
5
 

49、字符串的排列组合

面试中常见到：输入一个字符串，输出该字符串的字符的所有组合。如输入'abc',输出["abc","acb","bac","bca","cab","cba"].

字符串的排列组合 II其实本身就是一个回溯算法的一个例子。

def permutation(s): if len(s) == 1: return [s] res = [] for i, x in enumerate(s): n = s[:i] + s[i+1:] for y in permutation(n): res.append(x+y) return list(set(res))
print(permutation('abc'))

# ['bca', 'abc', 'acb', 'cba', 'cab', 'bac']

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

下面是Python中itertools内置的做法，一行代码就可以搞定

import itertools
print(list(set([''.join(x) for x in list(itertools.permutations(list('abc')))])))

# ['bca', 'abc', 'acb', 'cba', 'cab', 'bac']

  

 

  
1
  
2
  
3
  
4
 

补充下：对于组合，有两个自带的方法：itertools.combinations和 itertools.combinations_with_replacement，其中前者不放回抽取，后者为放回抽取。

In [15]: print(list(set([''.join(x) for x in list(itertools.combinations_with_replacement('abcd',3))])))
['acd', 'abc', 'aaa', 'bbb', 'acc', 'aac', 'cdd', 'bbc', 'abd', 'ccd', 'add', 'bdd', 'bcd', 'aad', 'ddd', 'bcc', 'aab', 'bbd', 'abb', 'ccc']

In [16]: print(list(set([''.join(x) for x in list(itertools.combinations('abcd',3))])))
['acd', 'bcd', 'abc', 'abd']

  

 

  
1
  
2
  
3
  
4
  
5
 

上面的题目其实是Leetcode上第46题全排列的。

50、数组的排列组合 II

上面一题是全排列的，这题是Leetcode的第78题子集问题。

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

如果直接用Python内置的itertools，代码非常简单。

import itertools

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): # 不放回抽取 for tmp in itertools.combinations(nums, i): res.append(tmp) return res

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

这题更多的考察的是回溯算法，原理是一条路黑到底。

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [[]] for i in nums: res = res + [[i] + num for num in res] return res

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

51、寻找完数

一个数如果恰好等于它的因子之和，这个数就称为‘完数’，比如6=1+2+3，下面编程找出10000以内的所有的完数。

wanshu=[]
for i in range(1,10001): s=0 for j in range(1,i//2+1): if i % j ==0: s+=j else: if i==s: wanshu.append(i)
print(wanshu)
# [6, 28, 496, 8128]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

52、压缩字符串

把a='aaabbcccdddde'这种形式的字符串，压缩成a3b2c3d4e1这种形式。’

a='aaabbcccdddde'
aa=''
for i in sorted(list(set(a)),key=a.index): aa=aa+i+str(a.count(i))
print(aa)
# a3b2c3d4e1

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

53、腾讯校招压缩算法

这是腾讯2020校招后端的算法题：题目链接

题目：小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入例子1:
HG[3|B[2|CA]]F

输出例子1:
HGBCACABCACABCACAF

例子说明1:
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

思路是使用遍历，但就是找到]的index，就是break，同时储存前面的[的index，和|的index，这样就不断地进行递归解码，直到一个中括号都没有。

def decode(s): i = 0 x, y, z = -1, -1, -1 while i < len(s): if s[i] == '[': x = i elif s[i] == '|': y = i elif s[i] == ']': z = i break i += 1 if x != -1 and y != -1 and z != -1: times = int(s[x + 1:y])  # 次数 sub = s[y + 1:z]  # 子串 decode_str = s[:x] + times * sub + s[z + 1:]  # 解码 return decode(decode_str)  # 递归解码 return s  # 如果一个中括号都没有，说明没有需要解码的部分


if __name__ == '__main__': s = input() print(decode(s))


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

54、数位之积

数位之积这题是vivo的校招题，题目链接

题目是这样的：现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 … …）之乘积等于n，若不存在则输出 -1。

输入
36
输出
49
# 36=4*9

  

 

  
1
  
2
  
3
  
4
  
5
 

对于小于10的数n，输出1n。
对于大于10的数，需要分解为若干个个位数之积，数字的个数尽可能少。这个数字可以分解为以9，8，…，2的因子之积。然后从小到大输出即可。

class Solution: def solution(self, n): # write code here if n < 10: return 10+ n else: result, nums = 0, 1 for i in range(9, 1, -1): while n % i == 0: result = result + i * nums n /= i nums *= 10 if n != 1: return -1 else: return result

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

55、数位重排

数位重排：题目链接

输入包括t+1行,第一行包括一个整数t (1 ≤ t ≤ 10),

接下来t行,每行一个整数x (1 ≤ x ≤ 10^6)

输出描述:
对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".

'''
输入
2
14  
1035
输出
Impossible #41 不是14的倍数
Possible #3015是1035的倍数
'''

import itertools
t = int(input())
# 题目要求使用x的原始数字重排，即重排后的位数等于x的位数，即只需判断x的2到9倍中的数是否存在由x重排得到的数
def f(s): x = itertools.permutations(s) for n in x: for k in range(2,10): a = "".join(list(n)) if int(a) == (k*int(s)): return "Possible" return "Impossible"
i = 0
while i < t: s = input() print(f(s)) i = i + 1

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

56、标准二分法

二分查找算法是在面试题中出现的频率很高的，特别是二分法的四个变种问题。二分查找算法的条件需要有序的，所以只要题目中出现有序的数组八成就是二分，或者先是一个无序，然后通过快排再进行二分。

下面是一个标准的二分算法。

'''
@Author： Runsen
标准的二分查找
'''

a = [1, 2,4, 5, 8,10,11,16]
def bsearch(a,value): low = 0 high = len(a) -1 while low <= high: mid = (low + high) // 2 if a[mid] == value: return mid elif a[mid] < value: low = mid + 1 else: high = mid -1

if __name__ == '__main__': print(bsearch(a,10)) # 5 print(bsearch(a,11)) # 6 print(bsearch(a,16)) # 7 print(bsearch(a,1)) # 0


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

57、二分变形：第一个等于定值的

求第一个等于定指的 有重复值。比如nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)

注意点：while low <= high: 需要 <=

mid = low + ((high - low) >> 1)最好用位运算，比//2好，防止泄露

• 小了：说明要往右移动：low = mid + 1
• 大了：说明要往左移动：high = mid - 1

时刻要注意：端点的情况

def f1(nums,target): '''求第一个等于定值的 ''' low = 0 high = len(nums) - 1 # 这里需要 <= while low <= high: # 这里需要注意： 就是使用((high - low) >> 1)需要双扩号 mid = low + ((high - low) >> 1) if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid - 1 else: if mid == 0 or nums[mid-1] != target: return mid else: high = mid -1 return -1 print(f1(nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)) # 6

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

58、二分变形：最后一个等于定值的

def f2(nums,target): '''求最后一个等于定值的''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + ((higt- low) >>1 ) if nums[mid] > target: higt = mid - 1 elif nums[mid] < target: low = mid +1 else: if mid == (len(nums) -1) or nums[mid] != nums[mid+1]: return mid else: low = mid +1 return  -1


print(f2(nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)) # 7


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

59、二分变形：第一个大于等于值，不一定存在定值

def f3(nums,target): '''求第一个大于等于值''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + ((higt - low) >> 1) if target <= nums[mid]: if (nums[mid-1] < target) or (mid == 0): return  mid else: higt = mid -1 else: low = mid + 1 return -1


print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=3)) # 2
print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=9))# 5


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

60、二分变形：最后一个小于等于定值，不一定存在定值

def f4(nums,target): '''求最后一个小于等于值''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + (( higt -low ) >> 1) if nums[mid] <= target: if (mid == len(nums) -1) or (nums[mid + 1] > target): return mid else: low = mid +1 else: higt = mid -1 return  -1


if __name__ == '__main__': print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=10))  #5 print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=3))  #1 print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=7))  #3

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

注：上面二分的变种是看王争算法专栏总结套路的。

如果你想跟博主建立亲密关系，可以关注博主，或者关注博主公众号“Python之王”，了解一个非本科程序员是如何成长的。
博主ID：润森（weixin_44510615），希望大家点赞、评论、收藏

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/108655357