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 []

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

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))

 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

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))  #向上取整

 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)

 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

 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)

 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)

 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)

 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)

  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")