王张开

Appearance

[TOC]

反转链表 ​

给你一个单链表的头节点head指针，请你反转链表，并返回反转后的链表。

例如：

python
# input
head = [1, 2, 3, 4, 5]

# output
[5, 4, 3, 2, 1]

判断环形链表 ​

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点，若环不存在，返回null。

请实现一个快速排序算法 ​

二维表.... ​

在一个4*6的二维表中，计算从左上角到右下角一共有多少种方式，每次移动只能向下或者向右移动一步

请在一个无需列表中，找到中位数 ​

青蛙题... ​

一只青蛙一次可以跳上1级台阶，也可以挑上2级台阶，请用代码代码实现跳上n级的台阶共有多少种跳法

遍历二叉树 ​

给定一个二叉树的根节点，请遍历整个二叉树。

# 例如：

			1
         /		\
        2		  3
        		/    \
        	   4 	   5
# output：1 2 3 4 5

最大公约数 ​

给你一个整数数组 nums，返回数组中最大数和最小数的最大公约数。

例如：

# input
nums = [2, 5, 6, 9, 10]

# output: 2

求n的x次方 ​

x的最大值为int 最大值 -1，如果n的x次结果y超过int最大值，需要返回y%（10^7+7）

数字拼接问题 ​

给一个非负整数列表，将列表中的元素组成一个最大数的字符串 ​

这个题也有其他问法，如：有n个非负整数，将其按照字符串拼接的方式拼接为一个整数，如何拼接可以使的得到的整数最大？

例：

python
[2, 10] --> 210
[3, 30, 34, 5, 9] --> 9534330
[32, 94, 128, 1286, 6, 71] --> 94716321286128

这种题也算是贪心算法的一个典型问题了，参考：

python
from functools import cmp_to_key


def my_cmp(x, y):
    """ 对比两个值返回对比结果 """
    if x + y < y + x:
        return 1
    elif x + y > y + x:
        return -1
    else:  # 相等
        return 0


def number_join(li):
    li = list(map(str, li))
    li.sort(key=cmp_to_key(my_cmp))
    return ''.join(li)


print(number_join([2, 10]))  # 210
print(number_join([3, 30, 34, 5, 9]))  # 9534330
print(number_join([32, 94, 128, 1286, 6, 71]))  # 94716321286128

参考：数字拼接问题

深度优先和广度优先搜索算法 ​

参考：https://www.jb51.net/article/149278.htm

广度优先搜索 ​

这里以遍历指定目录为例，我有这样的一个目录结构：

D:\tmp\web\root
│  file_a.txt
│  file_b.txt
│  file_c.txt
│  
├─dir_a
│  │  dir_a_file_a.txt
│  │  dir_a_file_b.txt
│  │  
│  └─dir_a_dir_a
│          dir_a_dir_a_file_a.txt
│          dir_a_dir_a_file_b.txt
│          
├─dir_b
│  └─dir_b_dir_a
│          dir_b_dir_a_file_a.txt
│          dir_b_dir_a_file_b.txt
│          
└─dir_c
        dir_c_file_a.txt
        dir_c_file_b.txt

广度优先搜索算法参考：

python
import os
import collections

def breadth_first(path):
    """
    以广度优先的方式遍历给定目录
    :param path:
    :return:
    """
    queue = collections.deque()  # 先进先出队列
    queue.append(path)  # 将
    while queue.__len__() > 0:
        # 从队列出来的是个目录名
        dir_path = queue.popleft()  # 右侧进，左侧出
        dir_path_list = os.listdir(dir_path)  # 拿到找个目录下所有的子目录或者子文件
        for item in dir_path_list:
            abs_path = os.path.join(dir_path, item)  # 获取绝对路径
            if os.path.isdir(abs_path):
                print(f'[{dir_path}] 下的 [{item}] 目录')
                queue.append(abs_path)
            else:
                print(f'[{dir_path}] 下的 [{item}] 文件')
        print()  # 为了好看，打印一个换行做隔断
breadth_first(r"D:\tmp\web\root")

"""
[D:\tmp\web\root] 下的 [dir_a] 目录
[D:\tmp\web\root] 下的 [dir_b] 目录
[D:\tmp\web\root] 下的 [dir_c] 目录
[D:\tmp\web\root] 下的 [file_a.txt] 文件
[D:\tmp\web\root] 下的 [file_b.txt] 文件
[D:\tmp\web\root] 下的 [file_c.txt] 文件

[D:\tmp\web\root\dir_a] 下的 [dir_a_dir_a] 目录
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_b.txt] 文件

[D:\tmp\web\root\dir_b] 下的 [dir_b_dir_a] 目录

[D:\tmp\web\root\dir_c] 下的 [dir_c_file_a.txt] 文件
[D:\tmp\web\root\dir_c] 下的 [dir_c_file_b.txt] 文件

[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_b.txt] 文件

[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_b.txt] 文件
"""

深度优先搜索 ​

深度优先，这里还是以遍历指定目录为例，采用的是递归和栈实现。

目录：

D:\tmp\web\root
│  file_a.txt
│  file_b.txt
│  file_c.txt
│  
├─dir_a
│  │  dir_a_file_a.txt
│  │  dir_a_file_b.txt
│  │  
│  └─dir_a_dir_a
│          dir_a_dir_a_file_a.txt
│          dir_a_dir_a_file_b.txt
│          
├─dir_b
│  └─dir_b_dir_a
│          dir_b_dir_a_file_a.txt
│          dir_b_dir_a_file_b.txt
│          
└─dir_c
        dir_c_file_a.txt
        dir_c_file_b.txt

栈实现

python
import os

def depth_first(root_path):
    """  深度优先搜索算法实现目录遍历 """
    stack = []
    stack.append(root_path)  # 首先将根目录入栈
    while len(stack) > 0:  # 栈为空时，表示遍历完毕
        dir_path = stack.pop()  # 抛出栈顶元素
        dir_path_list = os.listdir(dir_path)  # 拿到找个目录下所有的子目录或者子文件
        for item in dir_path_list:  # 遍历当前目录，如果item是目录，入栈，否则就直接打印
            abs_path = os.path.join(dir_path, item)
            if os.path.isdir(abs_path):
                print(f'[{dir_path}] 下的 [{item}] 目录')
                stack.append(abs_path)
            else:
                print(f'[{dir_path}] 下的 [{item}] 文件')
        print()

depth_first(r"D:\tmp\web\root")

"""
dir_a目录最先入栈，成了栈底元素，所以它最后遍历
[D:\tmp\web\root] 下的 [dir_a] 目录
[D:\tmp\web\root] 下的 [dir_b] 目录
[D:\tmp\web\root] 下的 [dir_c] 目录
[D:\tmp\web\root] 下的 [file_a.txt] 文件
[D:\tmp\web\root] 下的 [file_b.txt] 文件
[D:\tmp\web\root] 下的 [file_c.txt] 文件

[D:\tmp\web\root\dir_c] 下的 [dir_c_file_a.txt] 文件
[D:\tmp\web\root\dir_c] 下的 [dir_c_file_b.txt] 文件

[D:\tmp\web\root\dir_b] 下的 [dir_b_dir_a] 目录

[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_b.txt] 文件

[D:\tmp\web\root\dir_a] 下的 [dir_a_dir_a] 目录
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_b.txt] 文件

[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_b.txt] 文件
"""

递归

python
import os

def recursion(root_path):
    """ 递归遍历给定目录 """
    path_list = os.listdir(root_path)
    for item in path_list:
        abs_path = os.path.join(root_path, item)
        if os.path.isdir(abs_path):
            print(f'\n[{root_path}] 下的 [{item}] 目录\n')
            recursion(abs_path)
        else:
            print(f'[{root_path}] 下的 [{item}] 文件')

recursion(r"D:\tmp\web\root")
"""
[D:\tmp\web\root] 下的 [dir_a] 目录


[D:\tmp\web\root\dir_a] 下的 [dir_a_dir_a] 目录

[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a\dir_a_dir_a] 下的 [dir_a_dir_a_file_b.txt] 文件
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_a] 下的 [dir_a_file_b.txt] 文件

[D:\tmp\web\root] 下的 [dir_b] 目录


[D:\tmp\web\root\dir_b] 下的 [dir_b_dir_a] 目录

[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_a.txt] 文件
[D:\tmp\web\root\dir_b\dir_b_dir_a] 下的 [dir_b_dir_a_file_b.txt] 文件

[D:\tmp\web\root] 下的 [dir_c] 目录

[D:\tmp\web\root\dir_c] 下的 [dir_c_file_a.txt] 文件
[D:\tmp\web\root\dir_c] 下的 [dir_c_file_b.txt] 文件
[D:\tmp\web\root] 下的 [file_a.txt] 文件
[D:\tmp\web\root] 下的 [file_b.txt] 文件
[D:\tmp\web\root] 下的 [file_c.txt] 文件
"""

top k问题 ​

设计算法统计频数最高的ip ​

问题：

假设有个ip的日志文件，请设计一个算法统计频数最高的ip

如果是统计top k的呢？比如说是频率最高的top10

如何在Linux系统实现？

最长公共子序列 ​

编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串 ""

python
"""
示例 1:

输入: ["flower","flow","flight"]
输出: "fl"


示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。
"""

参考leetcode的答案：

python
class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        length = len(strs)
        if length == 1:
            return strs[0]
        result = strs[0]
        for index in range(1, length):
            if strs[index] == 0 or not result:
                return ""
            length_min = min(len(result), len(strs[index]))
            auxiliary = ""
            for index2 in range(length_min):
                if result[index2] == strs[index][index2]:
                    auxiliary = auxiliary + result[index2]
                else:
                    break
            result = auxiliary
        return result
print(Solution().longestCommonPrefix(["flower","flow","flight"])) # fl
print(Solution().longestCommonPrefix(["dog","racecar","car"])) # ""

什么是时间复杂度(2021/4/6) ​

Python中list.sort的时间复杂度？ ​

list.sort内部使用的是混合算法，我们称这种算法为timsort，它派生于归并排序(数据量大时)和插入排序(数据量小时)；是一种混合稳定的和自适应排序算法。

timsort的时间复杂度最好情况为O(n)，平均情况为O(nlogn)，最差情况为O(nlogn)；空间复杂度为O(n)。

更多参考：https://www.cnblogs.com/Neeo/articles/7835425.html#timsort

请用Python实现任意三种排序算法 ​

参考：https://www.cnblogs.com/Neeo/articles/7835425.html

给定一个二叉树的根节点root，返回它的中序遍历 ​

示例：

  • 输入：root = [1, null, 2, 3]
  • 输出： [1, 3, 2]

利用后进先出栈实现先进先出队列 ​

hash表有哪几种实现方案？ ​

B+tree和B-tree的区别？ ​

https://www.cnblogs.com/Neeo/articles/13602317.html#b树？b树？

给定一个列表，列表中的元素为int类型，请在O(n)的时间复杂度内找出列表中第一大和第二大的元素 ​

示例：

  • 输入：l = [5, 6, 9, 0, -1, 3]
  • 输出：9, 6

2. 给两个字符串s和t，判断t是否为s的重新排列的结果(2021/4/13) ​

示例：

  • s = "anagram", t = "nagaram", return True.
  • s = "rat", t = "car", return False.

答案参考：

python
# 法1 O(nlogn)  思路是对字符串每个字符排序，然后对比排序后的结果是否一致
def is_anagram(s, t):
    return sorted(list(s)) == sorted(list(t))

s, t = "anagram", "nagaram"
print(is_anagram(s, t))  # True
s, t = "rat", "car"
print(is_anagram(s, t))  # False

# 法2 O(n) 思路是判断两个字符串中每个字符的个数是否相等
def is_anagram(s, t):
    d1, d2 = {}, {}
    for ch in s:
        d1[ch] = d1.get(ch, 0) + 1
    for ch in t:
        d2[ch] = d2.get(ch, 0) + 1
    return d1 == d2

s, t = "anagram", "nagaram"
print(is_anagram(s, t))  # True
s, t = "rat", "car"
print(is_anagram(s, t))  # False

3. 给定一个m * n 的列表，查找一个是否存在，存在返回True，否则返回False(2021/4/13) ​

列表如下：

python
li = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

且列表具有如下特性：

  • 每一行的列表已经是有序的了。
  • 每一行第一个元素比上一行最后一个元素大。

参考：

python
li = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

# 法1，线性查找
def search_matrix(matrix, target):
    for line in matrix:
        if target in line:
            return True
    return False

print(search_matrix(li, 34))

# 法2， 利用二分查找，因为每一行列表都是有序的了

def search_matrix(matrix, target):
    h = len(matrix)
    if h == 0:  # 如果传来的列表是这样的： []
        return False
    w = len(matrix[0])
    if w == 0:  # 如果传来的列表是这样的： [[], [], []]
        return False
    left = 0
    right = w * h - 1
    while left <= right:
        mid = (left + right) // 2
        i = mid // w
        j = mid % w
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return False
print(search_matrix(li, 34))  # True
print(search_matrix(li, 88))  # False

给定一个列表和一个整数(2021/4/13) ​

给定一个列表和一个整数，设计算法找到两个数的下标，是两数之和等于给定的整数，且保证仅有一个结果。

例如，列表[1, 2, 5, 4]与给定整数3， 1 + 2 = 3，结果为(0, 1)，结果中的0和1分别表示两个数的下标。

示例1， 这个是O(n2)

python
li = [1, 2, 5, 4]
target = 3

def tow_sum(li, target):
    n = len(li)
    for i in range(n):
        for j in range(n):
            if i != j:  # 自己不能跟自己相加
                if li[i] + li[j] == target:
                    return [i, j]


print(tow_sum(li, target))  # [0, 1]

示例2，O(n2)，这个写法快一点。

python
li = [1, 2, 5, 4]
target = 3


def tow_sum(li, target):
    n = len(li)
    for i in range(n):
        # for j in range(i+1, n):  # 每次都跟它后面的数相加
        for j in range(i):  # 每次都跟它前面的数相加
            if li[i] + li[j] == target:
                return [i, j]


print(tow_sum(li, target))  # [0, 1]

示例3，O(nlogn)，这个更快，用上二分查找了，当然，这是有要求的，因为二分查找必须保证列表是有序的。

python
li = [1, 2, 5, 4]
target = 3


def binary_search(li, left, right, value):
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == value:
            return mid
        elif li[mid] > value:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None

def tow_sum(li, target):
    for i in range(len(li)):
        # 已知 a + b = target
        a = li[i]
        b = target - a
        if b >= a:  # 二分查找直接找从 li[i] 后面找即可
            j = binary_search(li, i + 1, len(li) - 1, b)
        else:
            j = binary_search(li, 0, i - 1, b)
        if j:  # 找到就结束循环
            break
    return [i, j]

print(tow_sum(li, target))  # [0, 1]

示例4，O(nlogn)，对于无序列表，要先排序再去二分查找。

python
li = [5, 2, 1, 4]
target = 3


def binary_search(li, left, right, value):
    while left <= right:
        mid = (left + right) // 2
        if li[mid][0] == value:
            return mid
        elif li[mid][0] > value:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None

def tow_sum(li, target):
    new_list = [[num, index] for index, num in enumerate(li)]
    new_list.sort(key=lambda x: x[0])
    for i in range(len(new_list)):
        # 已知 a + b = target
        a = new_list[i][0]
        b = target - a
        if b >= a:  # 二分查找直接找从 li[i] 后面找即可
            j = binary_search(new_list, i + 1, len(new_list) - 1, b)
        else:
            j = binary_search(new_list, 0, i - 1, b)
        if j:  # 找到就结束循环
            break
    return [new_list[i][1], new_list[j][1]]

print(tow_sum(li, target))  # [2, 1]

手写二分查找算法 ​

要重点掌握二分查找的流程。

python
def binary_search(li, value):
    """
    li: 待查找列表
    value: 待查找的值
    """
    left, right = 0, li.__len__() - 1  # right是列表长度减一
    while left <= right:  # 表示候选区有值
        mid = (left + right) // 2
        if li[mid] == value:  # 找到了结果，直接返回
            return mid
        elif li[mid] < value:  # value在mid和right之间
            left = mid + 1
        else:
            right = mid - 1
    else:
        return None

res = binary_search(list(range(100)), 28)
print(res)

pandas中有哪些不同类型的数据结构(2021/3/29) ​

代码实现列表排序，不允许使用内置函数或者方法(2021/3/29) ​

这个题，没啥好说的，就是考算法，你写个冒泡都行，参考：https://www.cnblogs.com/Neeo/articles/7835425.html

手写冒泡算法(2021/4/6) ​

python
import random

def bubble_sort(li):
    """ 冒泡排序"""
    for i in range(len(li) - 1):  # 从0开始的第i趟
        for j in range(len(li) - i - 1):  # 要循环的趟数
            exchange = False
            if li[j] > li[j + 1]:  # 后一个数比当前数大，就交换位置
                # if li[j] < li[j+1]:  # 降序排序， 大于是升序排序
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True  # 说明有交换，此时列表还需要进行排序
        # print('每一趟排序后的列表: ', li)
        if not exchange:  # 如果这一趟结束，没有发生交换，说明列表已经有序，可以结束算法了
            return


li = list(range(10))
random.shuffle(li)
print('before: ', li)
bubble_sort(li)
print('after: ', li)
"""
before:  [7, 5, 9, 2, 4, 6, 3, 1, 8, 0]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

5. 迷宫问题(2021/3/25) ​

如下maze是一个简易迷宫，1为墙，0为通路，玩家为 % 请写出一个方法，找出走出迷宫的路径，并将路径上的 0 设置为 # ，然后输出修改后的迷宫。

python
maze = [
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 0, 0, 0, 1],
    [1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
    [1, 0, "%", 0, 0, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

解题：

python
from collections import deque

maze = [
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 0, 0, 0, 1],
    [1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]


def print_r(path):
    current_node = path[-1]
    real_path = []
    while current_node[2] != -1:
        real_path.append(current_node[0:2])
        current_node = path[current_node[2]]
    real_path.append(current_node[0:2])  # 起点
    real_path.reverse()
    print('找到路径，展示如下: ')
    for node in real_path:
        print(node)
    return real_path


def maze_path_queue(x1, y1, x2, y2):
    """
    :param x1,y1:代表起点位置
    :param x2,y2:代表终点位置
    :return:
    """
    # 下个节点的四个方向
    direction_list = [
        lambda x, y: (x + 1, y),
        lambda x, y: (x - 1, y),
        lambda x, y: (x, y - 1),
        lambda x, y: (x, y + 1)
    ]

    tmp_path = []
    queue = deque()
    queue.append((x1, y1, -1))

    while len(queue) > 0:
        current_node = queue.popleft()
        tmp_path.append(current_node)
        if current_node[0] == x2 and current_node[1] == y2:
            return print_r(tmp_path)
        for direction in direction_list:
            nextNode = direction(current_node[0], current_node[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0], nextNode[1], len(tmp_path) - 1))
                maze[nextNode[0]][nextNode[1]] = 2
    else:
        print("没有出路")
        return False


for i in maze_path_queue(8, 2, 0, 6):
    maze[i[0]][i[1]] = "#"
print(maze)

"""
找到路径，展示如下:
(8, 2)
(8, 3)
(8, 4)
(7, 4)
(6, 4)
(5, 4)
(4, 4)
(4, 5)
(3, 5)
(2, 5)
(2, 6)
(1, 6)
(0, 6)
[
    [1, 1, 1, 1, 1, 1, '#', 1, 1, 1],
    [1, 2, 1, 1, 1, 1, '#', 1, 0, 1],
    [1, 2, 2, 2, 1, '#', '#', 1, 2, 1],
    [1, 2, 1, 2, 1, '#', 1, 2, 2, 1],
    [1, 2, 1, 2, '#', '#', 2, 2, 1, 1],
    [1, 0, 1, 1, '#', 1, 2, 1, 1, 1],
    [1, 1, 1, 1, '#', 1, 2, 2, 2, 1],
    [1, 1, 2, 1, '#', 1, 2, 1, 0, 1],
    [1, 2, '#', '#', '#', 1, 2, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
"""

6. 连锁挖矿(2021/3/25) ​

假如要在Minecraft(我的世界)里实现一种连锁挖矿功能，随机生成一个矩阵，0、1、2代表不同的方块类型。

请完善下方的destroy函数，将破坏的方块改为#，并输出修改后的矩阵。

连锁挖矿：破坏一个方块后，接连破坏所有邻接的相同方块。

示例：

python
import random
size = 8
blocks = [[0 for j in range(size)] for i in range(size)]
# 随机生成一个二维数组来表示矿物随机分布
for x in range(size):
    for y in range(size):
        blocks[x][y] = random.choice([0, 1, 2])

# 请完善这个destroy函数， 破坏的坐标 x,y | 存储方块类型的矩阵 lists
def destroy(x, y, lists):
    ...
    print(lists)

解题，这很明显，跟扫雷一样........

python
import random
from copy import deepcopy

size = 8
# 随机生成 8*8 矩阵
# lists = [[random.choice([0, 1, 2]) for j in range(size)] for i in range(size)]
lists = [
    # 0 1  2  3  4  5  6  7
    [0, 0, 1, 2, 0, 2, 0, 0],  # 0
    [1, 0, 1, 2, 1, 2, 0, 1],  # 1
    [1, 1, 2, 0, 0, 2, 1, 0],  # 2
    [1, 1, 0, 2, 0, 0, 0, 0],  # 3
    [2, 2, 0, 1, 0, 2, 1, 2],  # 4
    [0, 2, 0, 0, 2, 2, 2, 1],  # 5
    [0, 0, 1, 2, 2, 2, 0, 2],  # 6
    [0, 1, 1, 1, 2, 0, 0, 0]  # 7
]

"""
根据当前坐标，获取上下左右的坐标点，如坐标:(6, 5) x, y 那么，它的上下左右的坐标点:
    上:x-1,y;下:x+1,y;左:x,y-1;右:x,y+1
"""
direction_list = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1)
]

def destroy(x, y, lists, sign):
    """
    :param x: 顶级列表索引下表 符号
    :param y: 子列表中元素的下标
    :param x,y: 二维列表中的元素坐标
    :param lists: 二维数组
    :param sign: 符合条件的坐标替换为指定的字符样式
    :return: 返回修改后的二维列表
    """
    new_lists = deepcopy(lists)
    stack = []
    coordinate = new_lists[x][y]  # 指定坐标位置的元素
    new_lists[x][y] = sign  # 起点位置的坐标节点也需要替换
    print('坐标({}，{}): {}'.format(x, y, coordinate))
    stack.append((x, y))  # 起点坐标，也就是给定的坐标位置
    while len(stack) > 0:  # 当栈为空表示全部替换完毕
        current_node = stack[-1]  # 栈顶的坐标，也就是当前所在的坐标节点
        for direction in direction_list:  # 循环获取当前坐标的上下左右坐标点
            next_node = direction(current_node[0], current_node[1])  # 下一个坐标
            tmp_index = len(new_lists) - 1
            if 0 <= next_node[0] <= tmp_index and 0 <= next_node[1] <= tmp_index:  # 上下左右的坐标不允许超出列表的索引范围
                if new_lists[next_node[0]][next_node[1]] == coordinate:  # 下一个坐标需要替换的话
                    stack.append((next_node[0], next_node[1]))  # 将next node坐标点入栈，后续该坐标就会成为current node，在此基础上找上下左右节点
                    new_lists[next_node[0]][next_node[1]] = sign  # 将下一个坐标替换为指定字符
                    break  # 结束标记、入栈、替换任务
        else:  # 如果当前坐标节点的上下左右坐标点都不需要替换，就回退到上一个节点
            stack.pop()

    # 下面是为了方便观察结果做的打印操作
    print('原二维数组:\n', '\n'.join(str(i) for i in lists))
    print('修改后的二维数组:\n', '\n'.join(str(i) for i in new_lists))
    return new_lists


destroy(3, 4, lists, '🚩')
destroy(2, 2, lists, '🚩')
destroy(0, 0, lists, '🚩')
destroy(6, 5, lists, '🚩')
destroy(7, 0, lists, '🚩')

1000个数范围是[0, 999]， 有2个相同的数， 请设计算法找出来(2021/3/4) ​

这个题源自于leetcode-442.数组中重复的数据。

这个题的需求如果是找出一个重复的数，那用异或就可以了，是根据异或运算的性质可知， 当相同元素异或 时 ，其运算结果为 0，当相异元素异或时，其运算结果为非 0， 任何数与数字 。进行异或运算， 其运算结果为该数。

参考：https://blog.csdn.net/weixin_42813521/article/details/107649556

python
li = [3, 1, 2, 3]

def find_dup(li):
    if not li:
        return -1
    lens = len(li)
    result = 0
    i = 0
    while i < lens:
        print(result, li[i], result ^ li[i])
        result ^= li[i]
        i += 1
    return result
print(find_dup(li))
"""
0 3 3
3 1 2
2 2 0
0 3 3
3
"""

但很明显，题目需求有两个相同的数，用上面的异或法就不行了。

还可以用下面两种方式：

python
class Solution1(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tmp_dict = {}
        for i in nums:
            if i in tmp_dict:
                tmp_dict[i] = 1
            else:
                tmp_dict[i] = -1
        return [k for k in tmp_dict if tmp_dict[k] == 1]
    
class Solution2(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = []
        for i in nums:
            nums[abs(i) - 1] *= -1
            if nums[abs(i) - 1] > 0:
                result.append(abs(i))
        return result

上面两种都是摘自力扣。

第二种的思路是：借用index实现空间复杂度O（1），对数组中出现的每个数，把它们对应的 index * -1。比如 [4,3,2,7,8,2,3,1]，首先出现的是4，那我们就将对应的index也就是（4-1）上的值乘以-1。这样只出现一次的数字的index上的值一定为负数，如果我们乘完-1发现对应index上的值为正数，那么该数字出现了两次。

n个人(编号1~n)围成一圈从编号为1的开始报数，从1报数到m，报到m的人出来，下一个人继续重新从1开始报数， 编程求最后一个留下的人的编号(2021/3/4) ​

如n=3，m=4 第一次出队：1 第二次出队：3 最后留下：2

有26个字母a-z，找出所有字母的组合， a、b、c、ab、abc、a~z都是一个组合（顺序无关）(2021/3/4) ​

给出一个数字，输出它在excel中对应的表示形式(和excel无关，自行实现这个逻辑)(2021/4/7) ​

excel列命名规律：

A,B,C...Z,AA,AB,AC...AZ,BA,BB...BZ....ZZ,AAA,AAB....AAAZ,ABA....ZZZ,AAAA.....

示例1：

输入: 1
输出: A

示例2：

输入: 27
输出: AA

实现一个函数，根据标题序列生成相应的标题序号(2021/4/7) ​

输入参数是个列表，每个元素都是#为前缀的标题，保证层级结构的连续，然后返回解析好的列表。

# 输入： ["# A","## B","## C","### d","# e"]

# 输出: 
[
    ['1', 'A'],
    ['1.1', 'B'],
    ['1.2', 'C'],
    ['1.2.1', 'd'],
    ['2', 'e']
]

1、2、3、4、5 能组成多少个互不相同且无重复的三位数 ​

编程实现一个先进先出的队列类 ​

编程实现一个先进先出的队列类, 能指定初始化时的队列大小, 以及enqueue,dequeue,isempty, isfull四种方法

使用方法如下：

python
s = Queue(2) # 初始化一个大小为2的队列 
s.is_empty() # 初始化后, 队列为空, 返回True 
s.enqueue(1) # 将1加入队列 
s.enqueue(2) # 将2加入队列 
s.isfull() # 加入了两个元素, 队列已满, 返回True 
s.dequeue() # 移除一个元素, 返回1 
s.dequeue() # 移除一个元素, 返回2 
s.is_empty() # 队列已经为空, 返回True

列举熟悉的设计模式 ​

“设计模式有：工厂模式、抽象工厂模式、单例模式、建造者模式、原型模式、适配器模式、桥接模式、过滤器模式、组合模式、装饰器模式、外观模式、享元模式、代理模式、责任链模式、命令模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式等等。”

请用Python实现任意三种设计模式 ​

单例模式：

python
class Singleton(object):

	def __new__(cls, *args, **kwargs):
		if not hasattr(cls, '_instance'):
			cls._instance = super(Singleton, cls).__new__(cls)
		return cls._instance 
	
	def __init__(self, num):
		self.num = num

num1 = Singleton(10)
num2 = Singleton(20)
print(num1.num, num2.num)  # 20 20
print(id(num1), id(num2))  # 2467135043848 2467135043848