code programming

计算数组子数组之和的最大值

• 描述：给定一个包含N个整数的数组，求数组子数组之和的最大值
• 思路：子数组(子串)保证了是一个连续的
  • 直接暴力求解，双层遍历
  • 贪心策略：如果s<0，那么从a[n]开始重新计算，确保a[n]的值不会减小；否则s=s+a[n]
• 代码实现(python)

def max_sub_sum_problem(arr):
    """
    问题：给定一个整数数组，计算连续子数组的最大和
    思路：以s[n]代表到n时候最大和，如果s[n-1]<0，那么a[n]应该从头开始；否则s[n]=s[n-1]+a[n]
    如果当前计算的子数组和>=0，就将当前遍历的数组成员加到里面；如果当前计算的子数组和<0，就从当前遍历的数组成员开始计算
    :return:
    """
    res, _max = 0, 0
    for i in arr:
        if res < 0:
            res = i
        else:
            res += i
        if res > _max:
            _max = res
    return _max

计算数组最长递增子序列

• 描述：给定数组，包含正负整数，求最长递增子序列的长度(子序列可以不连续)
• 思路：动态规划
  • dp[i]代表以第i个数结尾的最长的递增子序列的长度(dp的状态方程)
  • dp[i+1]=arr[0-i]中小于arr[i+1]的最长递增子序列+1
  • 即：如果在前i个数中存在小于第i+1的数，那么将第i+1个数添加到后面即可形成新的最长递增子序列
• 代码实现(python)

def max_len_sub_arr(arr):
    """
    问题：求解给定数组中最长的递增子序列
    思路：动态规划，时间复杂度O(n^2)
    :return:
    """
    dp = [1] * len(arr)
    for i in range(len(arr)):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

部分反转字符串

• 描述：给定一个字符串s和给定位置start，将s[0, start]保持顺序情况下移动到尾部
• 思路：三步反转法
  • 将s[0, start]部分按位翻转
  • 将s[start, n]部分按位翻转
  • 将s[0, n]字符串翻转
• 代码实现(python)

def str_reverse(txt, start, n):
    """
    问题：字符串s旋转，给定位置start，将s[0,start]部分保持顺序情况下移动到尾部，例如start=2, s='abcdef'->'defabc'
    思路：三部反转法(X^TY^T)^T=YX, 以字符串s='abcdef', start=3为例
    1. 对于前缀字符串'abc', 旋转后变成'cba'
    2. 对于后缀字符串'def', 旋转后变成'fed'
    3. 对于旋转后字符串'cbafed', 旋转后变成'defabc'
    :param txt: 输入字符串
    :param start: 旋转后新字符串头字符
    :param n: 字符串长度
    :return: 结果
    """
    def sub_reverse(text, s, e):
        while s < e:
            text[s], text[e] = text[e], text[s]
            s += 1
            e -= 1
        return text
    _text = list(txt)
    txt = sub_reverse(_text, 0, start - 1)
    txt = sub_reverse(txt, start, n-1)
    txt = sub_reverse(txt, 0, n-1)
    return ''.join(txt)

数组子序列求和问题

• 描述：给定一个数n，计算1-n的序列中，连续整数序列和等于n的所有序列
• 思路：双指针法
  • 定义两个指针i=j=1，计算sum[i, j]的和
    • 如果sum[i, j] < n, 那么j+=1
    • 如果sum[i, j] > n, 那么i+=1
    • 如果sum[i, j] = n, 记录序列[i, j], i+=1
• 代码实现(python)

def slide_widows_sum(target):
    """
    问题：给定target，求从1到target的连续整数数组中，和为target的连续整数序列
    思路：滑动窗口左右索引i,j，那么窗口内的值的和，代表了连续整数序列的和w[i, j]
    1. 如果w[i, j] < target, j++
    2. 如果w[i, j] > target, i++
    3. 如果w[i, j] == target, 记录，并将i++
    滑动窗口求连续序列和等于n的问题
    :param target: 目标值
    :return: 结果序列
    """
    i, j, _sum, res = 1, 1, 0, []
    while i <= target // 2:
        if _sum < target:
            _sum += j
            j += 1
        elif _sum > target:
            _sum -= i
            i += 1
        else:
            res.append(list(range(i, j)))
            _sum -= i
            i += 1
    return res

求解两个字符串编辑距离

• 描述：给定字符串s1, s2，计算s1和s2的编辑距离
• 思路：动态规划
  • 用dis表示编辑距离，如果s1[i]=s2[j]，那么dis[i, j]=dis[i-1, j-1]
  • 如果s1末尾增加s2末尾相同字符使得s1[i+1]=s2[j]，一次增加操作，那么dis[i, j]=dis[i-1, j]+1
  • 如果s2末尾增加s1末尾相同字符使得s1[i]=s2[j+1]，一次增加操作，那么dis[i, j]=dis[i, j-1]+1
  • 如果修改任意字符串末尾使其相同s1[i]=s2[j]，一次修改操作，那么dis[i, j]=dis[i-1, j-1]+1
• 代码实现(python)

def levenshtein_by_dynamic_programming(s1, s2):
    """
    问题：求解两个字符串s1, s2的编辑距离
    思路：s[i], s[j] 分别代表s1, s2的第i, j个字符, dis[i, j]代表分别从s1, s2头开始到i, j的编辑距离
    1. 如果s[i] == s[j], 那么dis[i, j] == dis[i-1, j-1]
    2. 如果s[i] ≠ s[j], 那么存在增、删、改三种操作
        1) s2增加一个s1末尾相同字符情况下：s[i] == s[j+1], dis[i, j+1] == dis[i-1, j] + 1
        2) s1增加一个s2末尾相同字符情况下：s[i+1] == s[j], dis[i+1, j] == dis[i, j-1] + 1
        3) 修改任意一个字符末尾变成相同：s[i] == s[j], dis[i, j] == dis[i-1, j-1] + 1
    动态规划——字符串的编辑距离
    s1 = "abc", s2 = "def"
    计算公式：
             | 0                                           i = 0, j = 0
             | j                                           i = 0, j > 0
    d[i,j] = | i                                           i > 0, j = 0
             | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1])    s1(i) = s2(j)
             | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1)  s1(i) ≠ s2(j)
    定义二维数组[4][4]：
         d e f            d e f
      |x|x|x|x|        |0|1|2|3|
    a |x|x|x|x|  =>  a |1|1|2|3|  => 编辑距离d = [4][4] = 3
    b |x|x|x|x|      b |2|2|2|3|
    c |x|x|x|x|      c |3|3|3|3|
    :param s1: 第一个字符串
    :param s2: 第二个字符串
    :return: 返回的编辑距离
    """
    len_s1, len_s2 = len(s1), len(s2)
    if len_s1 == 0 and len_s2 > 0:
        return len_s2
    if len_s1 > 0 and len_s2 == 0:
        return len_s1
    mat = [[0 for __ in range(len_s1 + 1)] for _ in range(len_s2 + 1)]
    for i in range(len_s1 + 1):
        mat[0][i] = i
    for j in range(len_s2 + 1):
        mat[j][0] = j
    for i in range(1, len_s1 + 1):
        s1i = s1[i - 1]
        for j in range(1, len_s2 + 1):
            s2j = s2[j - 1]
            flag = 0 if s1i == s2j else 1
            mat[i][j] = min(mat[i - 1][j] + flag, mat[i][j - 1] + flag, mat[i - 1][j - 1] + flag)
    return mat[len_s1][len_s2]

无穷数据流采样问题

• 描述：给定一个无穷数据流，从其中等概率采样n个数据
• 思路：蓄水池算法
  • 第一个数，直接接受，第二个数以1/2概率保存，第三个以1/3概率保留，以此类推
  • 可以保证选择的每个数的概率是1/n
• 代码实现(python)

def reservoir_sampling(nums):
    """
    问题：从一个极大的数据流中，以相同概率采样nums个数据
    思路：蓄水池算法
    1. 首先蓄水满池子m
    2. 对于后续到达的第n个数据，总是以1/n的概率保留第n个数
    3. 以(n-1)/n的概率保留之前的数据，最终采样的每个数据都是1/n的概率
    :param nums:
    :return:
    """
    import random
    sample_titles = []
    for index, num in enumerate(list(range(10000000))):
        if index < nums:  # 先给池子蓄满水
            sample_titles.append(num)
        else:
            r = random.randint(0, index)
            if r < nums:
                sample_titles[r] = num
    return sample_titles

子集和问题

• 描述：给定一个集合A，判断A的所有子集中是否存在自己和等于target
• 思路：动态规划
  • 如果一个子集和等于某个值k，那么包含该子集的所有集合都满足等于k的条件
  • 如果一个子集和不等于k，那么可以判断刨除子集最后元素差是否满足
• 代码实现(python)

def subset_sum_problem(arr, target):
    """
    问题：给定一个集合，判断该集合是否存在子集A，使得A的和为target
    思路：动态规划
    1. 定义s[i, j]=True/False:表示arr中前i(含)个元素组成的集合和为j的值
    2. 基于集合性质可知：如果集合s[i, j]=True, 那么s[i+1, j]=True
        i+1元素形成的集合的子集，肯定包含i个元素形成的集合的所有子集
    3. 如果s[i, j] = False, 那么s[i+1, j] = s[i, j-arr[i+1]]
    :param arr: 数据集合
    :param target: 目标和
    :return: 结果
    """
    res = [[False for __ in range(target + 1)] for _ in range(len(arr) + 1)]
    for i in range(target + 1):
        res[0][i] = False
    for j in range(len(arr) + 1):
        res[j][0] = True
    for i in range(1, len(arr) + 1):
        for j in range(1, target + 1):
            res[i][j] = (res[i - 1][j] or res[i - 1][j - arr[i]])
    return res[len(arr) - 1][target - 1]

0-1背包问题

• 描述：给定背包容量W，和一堆物品，每个物品价值p，重量w，使得背包不超重前提下价值最大
• 思路：动态规划
• 代码实现(python)

def zero_one_bag_problem(weight, price, target):
    """
    问题：0-1背包问题
    思路：动态规划
    1. s[i, j] 表示前i个物品下最大价值j
              | s[i - 1, j]                      (j - wi < 0)
    s[i, j] = |     | s[i - 1, j]
              | Max |                            (j - wi >= 0)
              |     | s[i - 1, j -wi] + pi
    :param weight:
    :param price:
    :param target: 
    :return:
    """
    row, col = len(weight) + 1, target + 1
    res, values = [[0 for __ in range(col)] for _ in range(row)], [0] * row
    for m in range(1, row):
        for n in range(1, col):
            if weight[m-1] < n:
                res[m][n] = max(res[m-1][n], res[m-1][n-weight[m-1]] + price[m-1])
            else:
                res[m][n] = res[m - 1][n]
    return res[-1][-1]