算法的自我修养(Python)

Posted on Edited on In Views:
Symbols count in article: 7k Reading time ≈ 6 mins.
本篇主要叙述用Python描述的算法，全部都是学习Python中积累查阅得到的，留待补充。

Algorithm

目录

[TOC]

一些感想

  • 目前学到的算法感觉都是有一个优化过程：暴力遍历 —> 优化思路 —> 优化查找 —> 优化数据结构 —> 优化语法 —> Finish！

素数算法

欧拉筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
def OlaPrimeCalc(n):
    Prime = []
    Compare = [1] * (n + 1)
    for x in range(2, n + 1):
        if Compare[x] == 1:
            Prime.append(x)
        for p in Prime:
            if x * p > n:
                break
            Compare[x * p] = 0
            if x % p == 0:
                break
    return Prime

埃氏筛法

1
2
3
4
5
6
7
8
9
def eladuosai(n):
    l = list(range(1,n+1))
    l[0] = 0
    for i in range(2,n+1):
        if l[i-1] != 0 :
            for j in range(i*2,n+1,i):
                l[j-1] = 0
    result = [x for x in l if x != 0]
    return set(result)

正整数拆分算法

简洁递归法

分解的正整数超出100，时间即大幅增加。

1
2
3
4
5
6
7
8
9
10
def f(n,a):
    '''从a开始拆分n，如果a>(n/2)，则出现重复情况'''
    if(a>n):
        return 0
    m=n/2
    s=1
    while(a<=m):
       s+=f(n-a,a)
       a+=1
    return s

输出情况法

分解的正整数超出80，时间即大幅增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
sys.setrecursionlimit(5000000) # set the maximum depth as 5000000
global Answer
times = 0
Answer = [0] * 10000
def Calc(x,k):
    '''从1开始分解x，第一位储存在第k位，将分解的情况放入列表'''
    for num in range(1, x+1):
        if num >= Answer[k-1]:
            Answer[k] = num
            rest = x - num
            if rest == 0:
                global times
                times += 1
            else:
                Calc(rest, k + 1)

母函数法

1

五边形数定理法

1

递归算法

例一：台阶走法问题（一次只能走1或2步，到n阶有多少种走法）

最后一步、倒推

1、n=0 和 n=1 时，可以得出f(0)=0、f(1)=1； 2、n>=2时情况变复杂，但是最后一步只有2种情况：走1步(n-1)、走2步(n-2)。所以可以得到递推公式：

f(n)=f(n-1)+f(n-2)； 3、使用递归或迭代。

动态规划

01相等连续子串（前缀和）

说明：给定一个0、1组成的字符串，请找到一个尽可能长的连续子串，其中包含的0与1的个数相等。

将0视作-1，1视作1，利用前缀和。

那么一对(0, 1)之和为0，满足‘0’、‘1’个数相同的子串首尾前缀和相同。（首：开头前一个；尾：最后一个）

例如：

索引：0 1 2 3 4

数值：0 0 1 1 0

sum：-1 -2 -1 0 -1

思路：

使用字典1记录某一个前缀和第一次出现的索引

临时变量1依次记录前缀和

字典2记录相等前缀和的后一个索引

临时变量2记录相等前缀和的最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n = int(input())
# 替换‘0’为‘-1’后去掉空格变为列表
s = list(map(int, input().replace('0','-1').split()))
# END = 0
MapFirst = {0:-1}
MapSecond = {0:-1}

# Sum为前缀和，i为对应索引，lenth为子串最大长度；
# 若前缀和第一次出现，则加入MapFirst，记录索引；
# 若该前缀和已经出现过，则更新MapSecond对应索引。
Sum = 0
lenth = 0
for i in range(n):
    Sum += s[i]
    if Sum not in MapFirst:
        MapFirst[Sum] = i
    else:
        MapSecond[Sum] = i
        temp = MapSecond[Sum] - MapFirst[Sum]
        if temp > lenth:
            lenth = temp
print("Max Lenth is: {}\nMap is: {}, {}".format(lenth, MapFirst, MapSecond))

两数之和（哈希应用）

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答

  • 一般想法：遍历所有可能，二重循环，时间复杂度是\(O(n^2)\)，空间复杂度是\(O(1)\)。
  • 高级点的想法：由于两数之和一定，有无效的遍历，可以减小解空间。先对目标数组进行排序（方法自选），再进行二分查找。这样做的缺点是算法不稳定： 1、对于特殊构造的数组会花费大量时间排序； 2、答案为相同元素相加时，返回原数组寻找下标很麻烦； 3、需要对二分查找进行优化，使其能够在无法找到的情况下收敛。 时间复杂度约为\(O(n\log_2{n})\)。
  • 遍历的瓶颈在于查找时间长，那么使用哈希表为查找提速（两次使用哈希函数，第一次添加，第二次查询）
  • 使用一次哈希函数，边添加边查找。

一份哈希函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        # enumerate()将可遍历的序列和默认的下标组合成元组，构成(下标, 数值)
        for index, num in enumerate(nums):
            # 先判断目标是否在字典内，后添加进字典
            if hashmap.get(target - num) is not None:
                # 目标在字典，获取下标列表
                end = [index, hashmap.get(target - num)]
                # 要求下标小的在前
                end.sort()
                return end
            # 目标不在字典，添加进去
            hashmap[num] = index

Q：这里就有问题了：如果数组中存在两个同样的数字x，target为这两个数字之和。这样构造的哈希表存储的x的下标就是后面那个（前面的x下标被覆盖），信息被筛选了，这样得出的解答合理吗？

A：根据题目要求，target则必为这两个数字之和，且组合方式唯一。

在两份哈希函数的解法中，第一次遍历是为了获取哈希表，第二次遍历的是原数组，因此仍然能够获取到哈希表中被覆盖的那个下标，并得出正确解答。

在一份哈希函数解法中，依然先遍历原数组，后添加字典，信息可以在筛选前发挥用处。

分析

思路是优化二重循环的过程：

优化首先要找瓶颈，代码时间上的瓶颈就是遍历两次，一次遍历目标（很难优化哦），一次查找（😍，可以）。

二重循环暴力破解 —> 排序 + 二分查找 —> 遍历 + 哈希函数提速查找 —> 哈希函数结合遍历

还可以用首尾递进查找，时间复杂度\(O(n\log_2{n})\)

各有优缺点：哈希函数用空间换时间（Python版本空间消耗尤其明显）。在如今不怕内存小的环境下，也许能够为大家接受吧。

查找优化看hash

整数反转（取数位）

题目

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入: 123
输出: 321

 示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [\(−2^{31}\), \(2^{31} − 1\)]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解答

  • 对于Python这种支持超长整数的语言来说，这里的溢出是不存在的，所以这道题对Python来说有些鸡肋。
  • 不考虑语言，从效率入手，首先想到的就是通过%10获取数位，正负整数可以一起判断。
  • 至于32 bits整数溢出问题，这里需要采用64 bits的整数，通过不等判断来判断是否溢出。

Python字符串方法（非算法）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverse(self, x: int):
        if x < 0:
            str_temp = str(x)[1:][::-1]
            end = -int(str_temp)
        else:
            end = int(str(x)[::-1])
        if end < -pow(2,31) or end > (pow(2, 31)-1):
            end = 0
        return end

Python数值方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def reverse(self, x: int) -> int:
        y = abs(x)
        end = 0
        if -10 < x <10:
            end = x
        else:
            # 记录符号位
            flag = 1 if x > 0 else -1
            while y != 0:
                end *= 10
                end += y % 10
                y //= 10
            end *= flag
            end = 0 if end > 2147483647 or end < -2147483648 else end
        return end

C数值方法

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
27
28
int reverse(int x){
    MAX = 2147483647;
    MIN = -2147483648;
    long end;
    if(x / 10 == 0) end = x;
    else{
        while(x != 0){
            end *= 10;
            end += x % 10;
            if(end > MAX || end < MIN){
                end = 0;
                break;
            }
            x /= 10;
        }
    }
    return end;
}

或者标准一点，返回int类型的变量
int reverse(int x){
    int max = 0x7fffffff, min = 0x80000000;
    long rs = 0;
    int end;
    for(;x;rs = rs*10+x%10,x/=10);
    end = rs;
    return rs>max||rs<min?0:end;
}

\(2^n = 1 << n\)，位运算，表示\(1*2^n\)；相反，\(m >> n\)表示\(m/2^n\)

分析

C语言中，取模运算分离了整数的最后一位，并且带上了原数的符号。

Python中，取模运算使得商尽可能小，而C语言中，取模运算使得商尽可能大，。这就导致了余数的不同。

反转数字的算法：用一个数来累计反转后的数字，每次*10提高数位，再加上原数分离的数位；原数不断通过%10和/10分离数位，更新自身。

斐波那契数列生成第n项

规定第0项为0，第一项为1.

初学者一般使用递归方法，简单明了：

1
2
3
4
5
6
def fab(N: int) -> int:
    if N == 0:
        return 0
    elif N == 1:
        return 1
    return fab(N-1) + fab(N-2)

缺点

递归耗时间，每一个中间的fab(k)都需要再递归求解，时间复杂度是可怕的\(O(2^n)\)，笔记本求解第45-50项时已经需要耗费大量时间了。

优化

我们把计算过的fab(k)储存起来怎么样？这样就不用再次求中间的数了。

因此可以使用数组储存斐波那契数列。

但是这样只能求解有限项数的fab(k)，所以想到了动态内存，但是一旦项数太大，内存也装不下这么多数据。

再次优化

数组方式极大减少了计算量，但是我们计算指定项数的斐波那契数列时，只用到了“两项”：fab(k-1)，fab(k-2)，因此只需使用两个中间变量即可：

1
2
3
4
5
6
7
8
9
10
11
def fab(N: int) -> int:
    a, b = 0, 1
    if N == 0:
        return a
    elif N == 1:
        return b
    else:
        for i in range(N-1):
            b = a + b
            a = b - a
        return b

当然，可以使用Python一些语法来加速运算，这里力求明确显示出算法的过程

当从0项开始时，循环次数是N-1，从1项开始时，循环次数是N-2

二维数组中的查找

题目

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

解答

我的初始思路是：比较每行第一个值确定行范围，再比较每行最后一个值筛选行，并遍历符合条件的行。

但是这样对于规模十分大的方阵来说，算法的最坏情况是\(O(n^2)\)，即全部遍历一遍，即使对于小规模矩阵，也很可能遍历一半以上。

优化

我们希望减少遍历查找的规模，如果能确定遍历的方向（纵横）那就再好不过了。

观察矩阵，从左上角元素开始，比它大的方向有两个，这就导致了初始思路需要多次比较确定范围；从右下角元素开始，比它小的方向也有两个，同样难以减少规模。

但是呢，从矩阵右上角和左下角的元素开始，比它们大和小的方向各只有一个，这样就可以确定便利的方向啦。

算法描述

  • 指针指向矩阵右上角元素；
  • 大于target，指针左移一格；
  • 小于target，指针下移一个；
  • 等于target，返回指针位置；
  • 重复2、3、4步。
1
2
3
4
5
6
7
8
9
10
def MatrixSearch(target: int, nums: List[int][int]) -> Tuple[int]:
    length = len(nums)
    point = (0, length-1)
    while 1:
        if target < nums[point[0]][point[1]]:
            point[1] -= 1
        elif target > nums[point[0]][point[1]]:
            point[0] += 1
        else:
            return point

这里假设一定有解，如果可能没有解，需要加终止条件。

移除元素

题目

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

1
2
3
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
4
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

解答

双指针法（首尾指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, j = -1, len(nums)-1
        if j == -1:
            return 0
        while(i < j):
            if nums[j] == val:
                j -= 1
            else:
                if nums[i+1] == val:
                    nums[i+1] = nums[j]
                    i += 1
                    j -= 1
                else:
                    i += 1
        return i+1

上述代码由于判断分支（if else）比较多，效率不太高。

不过优化它的办法不属于算法范围，故此处不加讨论，只显示代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 0:
            return 0
        i=0
        while i <len(nums):
            if nums[i] == val:
                nums.pop(i)
                i = i-1
            i = i+1
        return len(nums)

emmm，Leetcode上显示22ms，然而我提交时只有44ms，也许是机器问题吧。。。

不过真是。。。思路简单清晰，代码好写。

==所以，计算机运行if else的效率到底如何呢？==

要点

注意到，第一块代码从末端遍历，第一个指针指向i = -1，这种设计能够让输入空数组或者全是弹出数的数组时能够正常运行。

==思考==

双指针法（一端）

1
2
3
4
5
6
7
8
9
10
11
// 官方解法，在数组小时有不必要的交换操作
public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

这代码，简洁，有效率，容易理解。。。。双指针好优雅