算法比赛套路

2020-01-15 约 3002 字预计阅读 6 分钟

算法比赛套路

leetcode得进阶套路

如何判断出当前是第多少个case

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


import math
math.a=0
class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        math.a+=1
        print(math.a)
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

python 常见语法，常用函数

字符串篇

1
2
3
4
5
6
7


a = 'Aaaaa'
print(a.count('a'))  #统计某个字符串的次数
print(a.lower())
print(a.upper())

b= a.replace('a', 'b')  # 进行替换
print(b)

正则表达式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


import re   #引入正则表达式包
s  = "abcadffiwef/sdfsdf"
b = re.match('abc.*', s)
print(b[0])

c= re.search('c.*', s)
print(c[0])

out：
abcadffiwef/sdfsdf
cadffiwef/sdfsdf

format 格式化

1
2
3
4
5
6
7
8


s = 'asdf{},adfsdf{}'
print(s.format(2,1))

print('asdf{0},adfsdf{2}'.format(1,2,3)) #利用下标进行索引

print('asdf{name},adfsdf{pwd}'.format(name = 1, pwd = 32))  # 利用字符串进行替换，参数

print('{:.2f}'.format(2.339))

eval（） NB

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


x  = 10
ans  = eval('x + 2')
print(ans)

ans = eval('pow(2,x)')
print(ans)


out：
12
1024

上下界的查询

使用python的库bisect

1
2
3
4
5


import bisect
a  = [1,2,3]

tmp = bisect.bisect_right(a, 3)  #查询到右边
print(tmp)

位运算

保留小数位

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


x = 1.512187
print(round(x,4))  # 四舍五入保留几位
print(round(x,100)) # 但是不能强制输出多位


print('%.4f'%x)
print('%.10f'%x) #可以强制输出

import math
print(math.floor(x)) # 向下取整
print(math.ceil(x))  #向上取整

队列List

删除操作，添加操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


只是有这些操作而已，不过效率低下

nums = ['a', 'b', 'c', 'd']

nums.__delitem__(0)根据下标  # 类似的 {}集合也有这个方法
print(nums)

nums.append('a')
nums.append('b')  # 添加
nums.insert(1,'F') # 往下标所在位置插入

print(nums)

nums.remove('b')

print(nums)

nums.remove('b')  #删除看到的第一个元素

print(nums)

nums.extend([1,1])这个比加法运算符效率稍微高点

进制转换

 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
29
30


x  =14
print(bin(x))# 2进制
'{:018b}'.format(i) # 这样可以转化为进制后补0。 这里b代表二进制， 18 代表18位

print(oct(x))  # 8进制
print(hex(x))# 16进制
print(int(x))# 10进制


#将10 进制转化为N进制
def TentoN(num, N):
    num = int(num)
    ans =[]
    while num !=0:
        rest = num % N
        num = num // N
        ans.append(rest)

    ans.reverse()
    return ans


# 将N进制转化为10进制
def NtoTen(num, N):
    ans =0
    num = str(num)
    for i in num:
        ans= ans * N + int(i)

    return ans

数学排列组合

 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


import math

def factorial_(n):
    result=1
    for i in range(2,n+1):
        result=result*i
    return result

def comb_1(n,m):
    return math.factorial(n)//(math.factorial(n-m)*math.factorial(m))  #直接使用math里的阶乘函数计算组合数

def comb_2(n,m):
    return factorial_(n)//(factorial_(n-m)*factorial_(m))              #使用自己的阶乘函数计算组合数

def perm_1(n,m):
    return math.factorial(n)//math.factorial(n-m)                        #直接使用math里的阶乘函数计算排列数

def perm_2(n,m):
    return math.factorial(n)//math.factorial(n-m)                        #使用自己的阶乘函数计算排列数

if __name__=='__main__':
    print(comb_1(3,2))
    print(comb_2(3,2))
    print(perm_1(3,2))
    print(perm_2(3,2))

数据结构篇

常规的树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16



class node:
    def __init__(self):
        self.parent =None
        self.children =[]
        self.deep = None  # 层级
        self.tag = None
        self.id = None
        self.index =None

    def show(self):
        print('.' * self.deep*2, end='')
        # print(self.id, end=' ')
        print(self.tag + ' ')
        for i in self.children:
            i.show()

并查集

判断元素是否同集合以及合并

 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
29
30
31
32
33
34
35
36
37
38
39



class BQSet():
    def __init__(self):
        self.f = {}  # f[i]代表i的父节点
        # #init
        # for i in range(10):
        #     f[i] = i

    def getFather(self,origin):
        a = origin
        while self.f[a] != a:
            a = self.f[a]
        self.f[origin] = a
        return a

    # 只需要看a， b 是否 有共同父节点
    def judge(self,a, b):
        a  = self.getFather(a)
        b = self.getFather(b)

        if self.f[a] == self.f[b]:
            return True
        else:
            return False

    def Union(self,source, a):
        a = self.getFather(a)
        sF = self.getFather(source)
        self.f[a] = sF

if __name__ == '__main__':
    bq = BQSet()
    for i in range(10):
        bq.f[i] =i

    bq.f[2] =1
    a= bq.judge(1,2)
    bq.Union(2,3)
    print(a)

最小生成树 Kruskal

边权值和最小

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


n, m = input().split(' ')
n = int(n)

# print(n)
m = int(m)
edges = []
for i in range(m):
    s = input().split(' ')
    edges.append((int(s[0]), int(s[1]), int(s[2])))


# 并查集
class BQSet():
    def __init__(self):
        self.f = {}
        # #init
        # for i in range(10):
        #     f[i] = i

    def getFather(self, origin):
        a = origin
        while self.f[a] != a:
            a = self.f[a]
        self.f[origin] = a
        return a

    # 只需要看a， b 是否 有共同父节点
    def judge(self, a, b):
        a = self.getFather(a)
        b = self.getFather(b)

        if self.f[a] == self.f[b]:
            return True
        else:
            return False

    def Union(self, source, a):
        a = self.getFather(a)
        sF = self.getFather(source)
        self.f[a] = sF


#  Kruskal 关键是判断是不是同一个集合里面


def kruskal(edges):
    bq = BQSet()

    # 初始化并查集
    for i in range(1, n + 1):
        bq.f[i] = i

    # 先进行排序
    edges = sorted(edges, key=lambda x: x[2])
    # print(edges)
    arried = {}
    # finalE =[]
    sum = 0
    count = 0
    for u, v, w in edges:
        if bq.judge(u, v):
            pass
        else:  # 如果边不在同一个集合，就加入
            bq.Union(u, v)
            sum += w
            count += 1

    if count == n - 1:
        print(sum)
    else:
        print('orz')


# print(count)


kruskal(edges)

算法板子

快排板子

 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
29
30
31
32
33
34
35
36
37
38
39



# 可以自定义比较函数，决定排序方式
def cmp(a,b):
    return a>b


class quiteSort:
    def __init__(self):
        self.cmp = lambda a, b:a< b

    # 设置比较函数
    def setCmp(self, cmp):
        self.cmp =cmp

    # 随机找一个中间基准值，将数据分成左右两堆
    def randomized_partition(self, nums, l, r):
        import random
        pivot = random.randint(l, r)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if self.cmp(nums[j],nums[r]):
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

    # 不断进行细分
    def randomized_quicksort(self, nums, l, r):
        if r - l <= 0:
            return
        mid = self.randomized_partition(nums, l, r)
        self.randomized_quicksort(nums, l, mid - 1)
        self.randomized_quicksort(nums, mid + 1, r)

    def sortArray(self, nums):
        self.randomized_quicksort(nums, 0, len(nums) - 1)
        return nums

自定义二分查找

 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


class DichotomousSearch():
    def __init__(self):
        pass


    # 查找k在有序数组nums 中得位置。 nums是升序得
    #return index, flag flag是代表是否有和k匹配得数得bool。
    def search(self, nums, k):
        l = 0
        r = len(nums)-1

        while l<r:
            mid = (l + r) // 2

            if nums[mid]> k:   #  向左边找
                r = mid - 1
            elif nums[mid] <k:  # 向右边找
                l = mid +1
            elif nums[mid] == k:
                l = r = mid
                break


        if nums[l] == k:
            return l, True
        else:
            return l, False

Dijstra 最短路径

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42


import collections
INF =float('inf')
import heapq
class Solution(object):
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """


        adj ={} # 邻接表
        for i in range(1,N+1):
            adj[i] ={}



        for u, v, w in times:
            adj[u][v] =w


        def dijkstra(adj, K): #K是出发的点， 这里默认到达所有点
            arrived ={}   # 已经到的点
            pq = [(0, K)]# 存储需要到的点的最短值
            while pq:
                d, node = heapq.heappop(pq)
                if node in arrived: # 如果已经到达，
                    continue
                arrived[node] = d
                # print(node)
                for nei in adj[node]:
                    if nei not in arrived:
                        heapq.heappush(pq, (d + adj[node][nei], nei))

            return arrived


        print(dijkstra(adj, K))

Solution.networkDelayTime(None,times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2)

SPFA最短路

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


# 总结一下，SPFA是如何做到“只更新可能更新的点”的？
#
# 只让当前点能到达的点入队
# 如果一个点已经在队列里，便不重复入队
# 如果一条边未被更新，那么它的终点不入队


INF =float('inf')
class SPFA(object):
    def networkDelayTime(self, edges, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        times =edges
        arrived ={}   # 已经到的点
        for i in range(1, N + 1):
            arrived[i] = INF
        arrived[K] = 0


        adj ={} # 邻接表
        for i in range(1,N+1):
            adj[i] ={}

        for u, v, w in times:
            adj[u][v] =w

        q = [K]  # 优化队列
        vis ={}  # 是否正在队列里
        count = {}  # 统计在队列里出现多少次
        for i in range(1,N+1):
            vis[i] = False
            count[i] = 0
        vis[K] = True  # 代表在队列里面
        count[K] +=1
        while q:

            now = q.pop()
            vis[now] = False
            for i in adj[now]:
                to = i
                # 进行了松弛的点
                if arrived[to]> arrived[now] + adj[now][to]:
                    arrived[to] =  arrived[now] + adj[now][to]
                    if not vis[to]:
                        vis[to] = True
                        count[to] +=1
                        q.append(to)
                        if count[to] > N+1:  #  //判断负环
                            return False


        return arrived




a = SPFA.networkDelayTime(None,[[1,2,1],[2,3,7],[1,3,4],[2,1,2]],
3,
2)
print(a)

floyd最短路

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48



# 2、Floyd算法可以解决多源最短路径；
# k 前k个点代表在前k个的前提下的最短路径

import collections
INF =float('inf')
class Solution(object):
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """


        adj ={} # 邻接表
        # 初始化邻接表
        for i in range(1,N+1):
            adj[i]={}
            for j in range(1,N+1):
                adj[i][j]  = INF
                if i ==j:
                    adj[i][j] = 0

        for u, v, w in times:
            adj[u][v] =w

        def floyd(adj):
            for k in range(1, N+1):
                for i in range(1, N + 1):
                    for j in range(1, N + 1):
                        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])


            return adj

        adj = floyd(adj)


        if max(adj[K].values()) == INF:
            return -1

        return max(adj[K].values())


a = Solution.networkDelayTime(None,times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2)
print(a)

拓补排序

不断找入度为0的点

线段树

回溯全排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


arr = [i+1 for i in range(5)]


visit = [True for i in range(len(arr))]
temp = ["" for x in range(0, len(arr))]
# 回溯记录

def dfs(position):
    if position == len(arr):
        print(temp)
        return None

    for index in range(0, len(arr)):
        if visit[index] == True:
            temp[position] = arr[index]
            visit[index] = False
            dfs(position + 1)
            visit[index] = True


dfs(0)

查分约束

转化为图的问题

KMP字符串匹配

自动状态机

  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
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114



class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if haystack == '':
            if needle =='':
                return 0
            else:
                return -1
        elif needle =='':
            return 0



        # 计算next数组， next[i]代表前i个字符串的最长子串
        def getnext(s):
            n = len(s)
            next = [0,0]  # 第一个0代表空字符串
            for i in range(2, n+1):
                # print(next, s, i-1)
                if s[next[i-1]] == s[i-1]:
                    next.append(next[i-1] +1)
                else:
                    j = next[next[i-1]]
                    while j > 0:
                        if s[j] == s[i-1]:
                            next.append(j+1)
                            break
                        j = next[j]
                    if j ==0:
                        if s[i-1] == s[0]:
                            next.append(1)
                        else:
                            next.append(0)

            return next

        next  =getnext(needle)
        print(next)


        # 构造有限状态机
        def kmp(s, next):  # 一个状态机
            n = len(s)
            state = {'other':True}
            for i in s:
                state[i] = True

            matrix = [{} for i in range(n+1)]

            #初始化
            for i in state:
                matrix[0][i] = 0
            matrix[0][s[0]] =1


            # 归纳法进行递推
            for i in range(1, n+1):

                j = i
                while j> 0:
                    if j >= n:
                        j = next[j]
                        continue
                    char = s[j]
                    if char not in matrix[i]:
                        matrix[i][char] = j+1
                    j = next[j]
                if j ==0:
                    if s[0] not in matrix[i]:
                        matrix[i][s[0]] =1
                for k in state:
                    if k not in matrix[i]:
                        matrix[i][k] = 0
            return matrix, state






        m,state = kmp(needle, next)
        for i in range(len(m)):
            print(i, m[i])
        print(m)


        def search(txt):
            N = len(txt)
            l = len(needle)
            stateNow = 0
            for i in range(N):
                char = txt[i]
                if char in state:
                    stateNow = m[stateNow][char]
                else:
                    stateNow = m[stateNow]['other']

                if stateNow == l:
                    return i- l+1
            return -1

        print(search(haystack))
        return search(haystack)




Solution.strStr(None,"ababcaababcaabc",
"ababcaabc")

目录

算法比赛套路

算法比赛套路

leetcode得进阶套路

如何判断出当前是第多少个case

python 常见语法，常用函数

字符串篇

eval（） NB

上下界的查询

位运算

保留小数位

队列List

进制转换

数学排列组合

数据结构篇

常规的树

并查集

最小生成树 Kruskal

算法板子

快排板子

自定义二分查找

Dijstra 最短路径

SPFA最短路

floyd最短路

拓补排序

线段树

回溯全排列

查分约束

KMP字符串匹配