笔试算法题详解

主要介绍我在刷题过程中，遇到的题解方法，比如二分法，牛顿迭代法，双指针算法，动态规划，和一些经典或有趣的题型，比如：最长回文串、素数统计、背包问题、排列组合问题。

Python 字符和sckII码互相转换：ord()和chr()

ord('s')
Out: 115
chr(115)
Out: 's'

范围表： A~Z: 65~90 a~z: 97~122 0~9: 48~57

字符串匹配

题目：长字符串m，短字符串为n，求n出现在m出现的下标。

暴力算法：直接逐个匹配，时间复杂度为O(mn)。

RK算法(哈希匹配算法)，计算哈希值为O(1)的话，时间复杂度为O(m)，哈希冲突最差的话可能为O(m*n)

def rabin_karp(m_str, p_str) -> int:
    p_code = hash_code(p_str)
    p_len = len(p_str)
    for i in range(len(m_str)-p_len+1):
        if hash_code(m_str[i:i+p_len]) == p_code and m_str[i:i+p_len] == p_str:
            return i
    return -1


def hash_code(s):
    result = 0
    for i in s:
        result += ord(i)
    return result

KMP算法：最优解，时间复杂度为O(m+n)

# 计算next数组
def get_next(p_str):
    i = 0
    j = -1
    length = len(p_str)
    next_array = [0] * length
    next_array[0] = -1
    while i < length - 1:
        if j == -1 or p_str[i] == p_str[j]:
            i += 1
            j += 1
            next_array[i] = j
        else:
            j = next_array[j]
    return next_array

# 搜索
def KMP(m_str, p_str):
    next_array = get_next(p_str)
    i = 0
    j = 0
    print(next_array)
    while i < len(m_str) and j < len(p_str):
        if m_str[i] == p_str[j] or j == -1:
            i += 1
            j += 1
        else:
            j = next_array[j]


    if j == len(p_str):
        return i - j
    return -1

参考文档-KMP算法详解

二叉树遍历

前序遍历：根左右中序遍历：左根右后序遍历：左右跟层序遍历：从上往下、从左往右

LR实现

只需要记住，loss对w求偏导为：gradient=(y_predict-y)·x，w = w+lr·gradient进行权重更新

import numpy as np

weight = 0


def sigmoid(x):
    return 1 / (1+np.e**-x)


def train(train_x, train_y, lr=0.001, epochs=100):
    _train_x = np.array(train_x)  # (n, m) matrix
    _train_y = np.array(train_y)  # (n, 1) matrix
    global weight
    weight = np.ones((_train_x.shape[1], 1))  # (m, 1)
    for epoch in range(epochs):
        predict_y = sigmoid(np.dot(_train_x, weight))
        error = _train_y - predict_y
        weight = weight + lr * np.dot(_train_x.T, error)
    print('train finish.')


def predict(predict_x, threshold=0.5):
    _predict_x = np.array(predict_x)
    global weight
    predict_y = sigmoid(np.dot(_predict_x, weight))
    predict_y[predict_y >= threshold] = 1
    predict_y[predict_y < threshold] = 0
    return predict_y


x = np.random.random((10, 2))
y = np.random.randint(0, 2, (10, 1))

train(x, y)
pred_y = predict(x)

参考文档-loss偏导推理参考

参考文档-python实现参考

动态规划

一维形式：有一串连续数字，从中挑选任意个不相邻的数字，求相加的最大值。比如1，2，3，4，3，最大值为1+3+3=7 解题思路：数组某个下标往前的最大值，只需要考虑当前下标值、上一个下标和上上个下标的值

# 递归 max_sum(array, len(array)-1)
def max_sum(array, index):
    if index == 0:
        return array[0]
    elif index < 0:
        return 0
    return max(max_sum(array, index-1), max_sum(array, index-2) + array[index])


# 一维数组，空间复杂度O(n)
def max_sum2(array):
    length = len(array)
    if length == 1:
        return array[0]
    dp_array = [0] * length
    dp_array[0] = array[0]
    dp_array[1] = max(array[0], array[1])
    for index in range(2, length):
        dp_array[index] = max(dp_array[index-1], dp_array[index-2] + array[index])
    return dp_array[-1]


# 两个值，空间复杂度O(1)
def max_sum3(array):
    length = len(array)
    first_value = 0
    second_value = array[0]
    for index in range(1, length):
        temp = max(second_value, first_value + array[index])
        first_value = second_value
        second_value = temp
    return second_value

二维形式：有一个m*n的棋盘格，左上角有个棋子，只能往右或往下移动，移动到右下角，问可能有多少种不同的移动路径。解题思路：每个格子的移动路径数=右边格子的移动路径数+下边格子的移动路径数

import numpy as np


# 递归
def find_road_nums(m, n):
    if m == 1 or n == 1:
        return 1
    return find_road_nums(m-1, n) + find_road_nums(m, n-1)


# 二维数组
def find_road_nums2(m, n):
    if m == 1 or n == 1:
        return 1
    road_nums = np.ones((m, n))
    for i in range(1, m):
        for j in range(1, n):
            road_nums[i, j] = road_nums[i, j-1] + road_nums[i-1, j]
    return road_nums[-1, -1]

实际上换一种想法，总共需要走m-1+n-1=m+n-2步，其中n-1步是往右走的，m-1步是往下走的，等于只需要从m+n-2步中随意选择n-1往右即可（或选择m-1往下即可），即为组合问题：C(m+n-2)(n-1)或者C(m+n-2)(m-1)。

背包问题

分为0-1背包问题（物品最多只能取一次）和完全背包问题（物品可以取无数次）， 0-1背包的状态转移方程：完全背包的状态转移方程：，需要遍历每一个k 但是认真想一下的话，其实可以用本行中上一个值+v代替：

题目：给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1 。你可以认为每种硬币的数量是无限的。

# 最原始方法，二维DP，三层循环
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化为一个较大的值，如 +inf 或 amount+1
        # 合法的初始化
        dp[0][0] = 0    # 其他 dp[0][j]均不合法

        # 完全背包：套用0-1背包【遍历硬币数目k】
        for i in range(1, n+1):                     # 第一层循环：遍历硬币
            for j in range(amount+1):               # 第二层循环：遍历背包
                for k in range(j//coins[i-1]+1):    # 第三层循环：当前硬币coin取k个 (k*coin<=amount)
                    dp[i][j] = min( dp[i][j], dp[i-1][j-k*coins[i-1]] + k )

        ans = dp[n][amount]
        return ans if ans != amount+1 else -1


# 优化后，二维DP，两层循环
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化为一个较大的值，如 +inf 或 amount+1
        # 合法的初始化
        dp[0][0] = 0    # 其他 dp[0][j]均不合法

        # 完全背包：优化后的状态转移
        for i in range(1, n+1):             # 第一层循环：遍历硬币
            for j in range(amount+1):       # 第二层循环：遍历背包
                if j < coins[i-1]:          # 容量有限，无法选择第i种硬币
                    dp[i][j] = dp[i-1][j]
                else:                       # 可选择第i种硬币
                    dp[i][j] = min( dp[i-1][j], dp[i][j-coins[i-1]] + 1 )

        ans = dp[n][amount]
        return ans if ans != amount+1 else -1


# 终极优化，空间优化，一维DP，两层循环
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1] * (amount+1)    # 初始化为一个较大的值，如 +inf 或 amount+1
        dp[0] = 0        # 合法的初始化；其他 dp[j]均不合法

        # 完全背包：优化后的状态转移
        for coin in coins:                      # 第一层循环：遍历硬币
            for j in range(coin, amount+1):     # 第二层循环：遍历背包【正序】
                dp[j] = min( dp[j], dp[j-coin] + 1 )    # 可选择当前硬币

        ans = dp[amount]
        return ans if ans != amount+1 else -1

# 参考链接：https://leetcode.cn/problems/coin-change/solution/by-flix-su7s/

题目：查询最长回文串

从字符串找到最长的、中心堆成的回文子串中心扩展法比较容易想到和实现，manacher算法就会难理解一些，实现也复杂

# 中心扩展法，时间O(n*n)
def getLongestPalindrome(self, A: str) -> int:
    def find(l, r):
        while l >= 0 and r <= len(A) - 1 and A[l] == A[r]:
            l -= 1
            r += 1
        return r - l - 1


    max_len = 1
    for i in range(len(A) - 1):
        max_len = max(max_len, find(i, i), find(i, i + 1))
    return max_len

# manacher算法
# 可参考https://www.jianshu.com/p/116aa58b7d81
class Solution:
    def manacher(self, s: str, n: int, mp: List[int]):
        ms = ""
        ms += "$#"
        #预处理
        for i in range(n):
            #使之都变成奇数回文子串
            ms += s[i]
            ms += '#'
        #目前已知的最长回文子串的最右一位的后一位
        maxpos = 0
        #当前的最长回文子串的中心点
        index = 0
        for i in range(len(ms)):
            if maxpos > i:
                mp[i] = min(mp[2 * index - i], maxpos - i)
            else:
                mp[i] = 1
            #两边扫
            while i - mp[i] > 0 and i + mp[i] < len(ms) and ms[i + mp[i]] == ms[i - mp[i]]:
                mp[i] += 1
            #更新位置
            if i + mp[i] > maxpos:
                maxpos = i + mp[i]
                index = i
    def getLongestPalindrome(self , A: str) -> int:
        n = len(A)
        #记录回文子串长度
        mp = [0 for i in range(2 * n + 2)]
        self.manacher(A, n, mp)
        maxlen = 0
        #遍历数组
        for i in range(2 * n + 2):
            #找到最大的长度
            maxlen = max(maxlen, mp[i] - 1)
        return maxlen

素数统计

计算n以内的所有素数埃氏筛选法

# 0和1既不是素数也不是合数，已知基础2和3都是素数，没出现一个素数，将其倍数增长得到数均置为合数
def count_prime(n):
    is_prime = [True] * n
    prime_array = []
    for i in range(2, n):
        if is_prime[i]:
            prime_array.append(i)
            temp = 2 * i  # 可以进一步优化为 temp = i * i，减少计算
            while temp < n:
                is_prime[temp] = False  # 置为合数
                temp += i
    print(len(prime_array), prime_array)

双指针算法

一个指针指向真实的唯一元素数组下标，另一个指针扫描原始数组题目：删除有序数组内的重复元素，返回唯一元素的个数，不能使用额外空间

def remove_duplicates(array):
    if len(array) == 0:
        return 0
    i = 0
    for j in range(1, len(array)):
        if array[i] != array[j]:
            i += 1
            array[i] = array[j]
    return i+1

题目：给定一个数组，返回数组的“中心下标”，下标左边求和与右边求和的值相等

def middle_index(array):
    right_sum = sum(array)
    left_sum = 0
    for i in range(len(array)):
        left_sum += array[i]
        if left_sum == right_sum:
            # 因为 left_sum - array[i] == right_sum -array[i] 即为中心下标
            return i
        right_sum -= array[i]
    return -1

题目：合并两个有序数组，而不是用额外的空间，[1,3,5,0,0]和[2, 4]

# 双指针算法，时间O(n+m)，空间O(1)，不是用额外空间
def merge_array(array1, n, array2, m):
    p1 = n-1
    p2 = m-1
    p = len(array1) - 1
    while p1 >= 0 and p2 >= 0:
        if array1[p1] >= array2[p2]:
            array1[p] = array1[p1]
            p -= 1
            p1 -= 1
        else:
            array1[p] = array2[p2]
            p -= 1
            p2 -= 1
    if p1 < 0:
        while p2 >= 0:
            array1[p] = array2[p2]
            p -= 1
            p2 -= 1
    return array1

二分法

计算x的平方根的整数部分

def sqrt(x):
    value = -1
    left = 0
    right = x
    while left <= right:
        mid = int(left + (right - left)/2)
        if mid * mid <= x:
            value = mid
            left = mid + 1
        else:
            right = mid - 1
    return value

牛顿迭代法

计算x的平方根的整数部分，解题根源在于，对于[1,x]中的值i，i和x/i的中间值j，j2一定比i2和(x/i)*2更接近x 比如x=12，i=2，则x/I=6，中间值j=4，44一定比22和66更接近12，（其实不一定，比如两极端i=1，但是有助于理解，）直至j无限趋近于x的平方根。

def sqrt(x):
    return newton(1, x)


def newton(i, x):
    mid = (i + x/i)/2
    if mid == i:
        return i
    else:
        return newton(mid, x)

# 非递归
def newton(i, x):
    mid = (i + x / i) / 2
    while mid != i:
        i = mid
        mid = (i + x/i)/2
    return mid

真正的理解是：令f(x)=xx-a, f’(x)=2x,在xi处做切线，交x轴与xj，斜率：f(x1)/(xi-xj)=2xi,即:(xixi-a)/(xi-xj)=2xi 化简后得到：2xj-xi=a/xi, 当xj=xi时有:xi=a/xi，xi=xj即为a的平方跟。

题目：求一个无序数组里面的两个数的下标，两数之和为目标值。返回两个下标

# 空间换时间，时间O(n)
def solution(array, target):
    map_index = {}
    for i in range(len(array)):
        if map_index.get(target - array[i], -1) != -1:
            return map_index[target - array[i]], i
        map_index[array[i]] = i
    return 0

题目：求一个升序数组里面的两个数的下标，两数之和为目标值。返回两个下标

# 使用双指针算法，时间O(n)
def solution(array, target):
    left = 0
    right = len(array) - 1
    while left < right:
        temp_sum = array[left] + array[right]
        if temp_sum == target:
            return left, right
        elif temp_sum > target:
            right += 1
        else:
            left += 1
    return 0

题目：斐波那契数列，每一位的值等于它前两位数字之和，前两位固定：0，1，1，2，3，5，8。。。

# 双指针算法，时间O(n)，空间O(1)
def solution(num):
    if num <= 1:
        return num
    left = 0
    right = 1
    for i in range(2, num+1):
        tmp_sum = left + right
        left = right
        right = tmp_sum
    return right

题目：硬币排列，总共n枚硬币，排程阶梯形状，第k行必须刚好有k枚硬币，输出最大k

# 双指针算法，时间O(n)，空间O(1)
def solution(num):
    index = 0
    tmp_sum = 0
    while tmp_sum + index + 1 <= num:
        index += 1
        tmp_sum += index
    return index


# 二分查找，时间O(logn)
def solution2(num):
    left = 0
    right = num
    while left <= right:
        mid = int((right + left) / 2)
        tmp_sum = int((mid + 1) * mid / 2)
        if tmp_sum == num:
            return mid
        elif tmp_sum > num:
            right = mid - 1
        else:
            left = mid + 1
    return right

题目：给定一个n*n的二维数组array，array[i][j] = 1代表结点i和结点j有连线，0则代表没有连线，同一条线上的结点为同一组结点，求共有多少组结点

import queue

# 使用队列，广度优先搜索
def count_province(city_array):
    city_num = len(city_array)
    visited = [False] * city_num
    province_num = 0
    city_queue = queue.Queue()
    for i in range(city_num):
        if not visited[i]:
            city_queue.put(i)
            while not city_queue.empty():
                k = city_queue.get()
                visited[k] = True
                for j in range(city_num):
                    if city_array[k][j] == 1 and not visited[j]:
                        city_queue.put(j)
            province_num += 1
    return province_num

题目：给定一个有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合

def dfs(string, start):
    if start == len(string) - 1:
        result.append(''.join(string))
        return
    dfs(string, start+1)
    for i in range(start+1, len(string)):
        if string[start] == string[i] or string[i] == string[i-1]:
            continue
        swap(string, start, i)
        dfs(string, start+1)
        swap(string, start, i)


def swap(tmp_s, i, j):
    tmp = tmp_s[i]
    tmp_s[i] = tmp_s[j]
    tmp_s[j] = tmp


s = 'abcd'
s = list(sorted(s))
result = []
dfs(s, 0)

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合

def dfs(left_array, now_array, now_k):
    if now_k == 1:
        for i in left_array:
            result.append(now_array + [i])
    elif len(left_array) == now_k:
        result.append(now_array + left_array)
    else:
        for index in range(len(left_array)-now_k+1):
            dfs(left_array[index+1:], now_array+[left_array[index]], now_k-1)


n = 4
k = 2
array = list(range(1, n+1))
result = []
dfs(array, [], k)

题目：预测赢家，给定一个正整数序列，两名玩家轮流从两端抽取一个数，直到抽完未知，然后分别求和，求先手抽的人总数能不能必定大于后手的人。简化版：增加条件：序列为偶数，序列总和为奇数。则先手抽的人必定大于后手抽的人，只需要分别计算序列中：奇数下标的数值和，以及偶数下标的数值和，比较拿个大，先手的人就只抽对应奇数/偶数下标的数值。如果没有简化条件，则不能保证先手抽的人必赢。解题的关键在于：先手抽取序列某一端，后手抽的人只会留下他抽完之后子序列，这个子序列先手抽的人分数最小。

def max_score(array, left, right):
    if left == right:
        return array[left]
    elif right - left == 1:
        return max(array[left], array[right])
    else:
        # temp_sum = max_score(array, left+1, right-1)  # 初级优化
        # 关键代码
        left_sum = array[left] + min(max_score(array, left+2, right), max_score(array, left+1, right-1))
        right_sum = array[right] + min(max_score(array, left+1, right-1), max_score(array, left, right-2))
        return max(left_sum, right_sum)


def predict(array):
    total_sum = sum(array)
    p1 = max_score(array, 0, len(array)-1)
    p2 = total_sum - p1
    print(p1 >= p2)

优化1：直接计算赢面diff，先手的人比后手拿的多多少，减去，后手拿的比先手拿的多多少，根据diff的正负号判断输赢，ps：其实速度更慢，但可以引申出后面的动态规划方法

def max_score2(array, left, right):
    if left == right:
        return array[left]
    else:
        left_sum = array[left] - max_score2(array, left+1, right)
        right_sum = array[right] - max_score2(array, left, right-1)
        return max(left_sum, right_sum)


def predict2(array):
    p1 = max_score2(array, 0, len(array)-1)
    print(p1 >= 0, p1)

优化2：将赢面diff定义为二维dp数组，减少重复计算，时间O(nn)，空间O(nn)

def max_score3(array):
    length = len(array)
    diff_array = [[0 for i in range(length)] for j in range(length)]
    for i in range(length):
        diff_array[i][i] = array[i]
    for left in range(length-2, -1, -1):
        for right in range(left+1, length):
            diff_array[left][right] = max(array[left] - diff_array[left+1][right], array[right] - diff_array[left][right-1])
    return diff_array[0][length-1]


def predict3(array):
    p1 = max_score3(array)
    print(p1 >= 0, p1)

优化3：可以将二维dp数组转为一维数组，时间一样，但空间O(n)

def max_score4(array):
    length = len(array)
    diff_array = [0 for i in range(length)]
    for i in range(length):
        diff_array[i] = array[i]
    for left in range(length-2, -1, -1):
        for right in range(left+1, length):
            diff_array[right] = max(array[left] - diff_array[right], array[right] - diff_array[right-1])
    return diff_array[length-1]

题目：香槟塔，有100层的香槟杯组成的金字塔，第一层一个杯子，第二层两个杯子，导入香槟满了之后会平均向两边溢出，平均溢出到下边的两个杯子，求从顶层导入n杯香槟之后，第i行第j列的玻璃杯中香槟占容器的比例0-1

# 模拟过程就可以了，很简单
def champagne_tower(num, row, column):
    max_row = 100 + 1
    tower_array = [[0 for _ in range(max_row)] for _ in range(max_row)]
    tower_array[0][0] = num
    for i in range(max_row-1):
        is_left = False
        for j in range(i+1):
            if tower_array[i][j] > 1:
                left_num = (tower_array[i][j] - 1) / 2
                tower_array[i+1][j] += left_num
                tower_array[i+1][j+1] += left_num
                is_left = True
        if not is_left:
            break
    return min(tower_array[row-1][column-1], 1)

题目：素数伴侣。若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13。设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”。求最大“素数伴侣”组数。

def is_prime(num):
    if num <= 1:
        return False
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

# 关键1：素数不是偶数，那么和是素数的话就是奇数+偶数
# 那么可以分成两堆,一堆偶数，一堆奇数
n = int(input())
array = list(map(int, input().strip().split()))
odd_array = []
even_array = []
for i in array:
    if i % 2 == 0:
        even_array.append(i)
    else:
        odd_array.append(i)

# 标记偶数数组中对应位置匹配了哪个奇数伴侣，全局的历史
even_map_odd = [0 for _ in range(len(even_array))]


def find(_odd, _even_is_used):
    global even_array, even_map_odd
    for index in range(len(even_array)):
        # 如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
        if _even_is_used[index] == 0 and is_prime(_odd + even_array[index]):
            _even_is_used[index] = 1
            # 关键点2：匈牙利算法，如果偶数数组当前位置历史上没有伴侣，则记录历史
            # 如果当前位置历史上已有伴侣，则让这个奇数伴侣另外再找一个偶数伴侣，（递归调用，能让则让）
            if even_map_odd[index] == 0 or find(even_map_odd[index], _even_is_used):
                even_map_odd[index] = _odd
                return True
    return False


total = 0
for odd in odd_array:
    # 每个奇数独立的数组，标记偶数数组中哪些位置已经匹配了伴侣
    even_is_used = [0 for _ in range(len(even_array))]
    if find(odd, even_is_used):
        total += 1
print(total)

刷题链接-外网leetcode

刷题链接-国内力扣

刷题链接-牛客

⤧ 上一篇简单安全获取国外的AppleID-免费 ⤧ 下一篇模型层面知识点