本文共 11723 字，大约阅读时间需要 39 分钟。

@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`));

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

很简单直接降序：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表示要跳过的数量 。

查找入职员工时间排名倒数第三的员工所有信息的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

在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                 |+---------------------+

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

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

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

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

最好的方法就是使用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                    |+------------------------+

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

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INTBEGIN  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

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)

在这里提供内置的方法chain

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

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

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}

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']

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

import itertoolsprint(list(set([''.join(x) for x in list(itertools.permutations(list('abc')))])))# ['bca', 'abc', 'acb', 'cba', 'cab', 'bac']

补充下：对于组合，有两个自带的方法：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']

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

50、数组的排列组合 II

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

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

示例:

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

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

import itertoolsclass 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

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

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

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]

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

53、腾讯校招压缩算法

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

题目：小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的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

思路是使用遍历，但就是找到]的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))

54、数位之积

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

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

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

对于小于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

55、数位重排

数位重排：

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

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

输出描述:

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

'''输入214  1035输出Impossible #41 不是14的倍数Possible #3015是1035的倍数'''import itertoolst = 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 = 0while i < t:    s = input()    print(f(s))    i = i + 1

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 -1if __name__ == '__main__':    print(bsearch(a,10)) # 5    print(bsearch(a,11)) # 6    print(bsearch(a,16)) # 7    print(bsearch(a,1)) # 0

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

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  -1print(f2(nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)) # 7

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 -1print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=3)) # 2print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=9))# 5

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  -1if __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

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

如果你想跟博主建立亲密关系，可以关注博主，或者关注博主公众号“Python之王”，了解一个非本科程序员是如何成长的。

博主ID：润森（weixin_44510615），希望大家点赞、评论、收藏

转载地址：https://maoli.blog.csdn.net/article/details/108655357 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！