和数学有关的算法积累（2021年12月4日）

内容

主要是一些曾经做过的题中积累的算法代码模板，可以用来直接调用，其中包含

  • 判断是否是质数
  • 获取一定范围内质数的数量
  • 回文数判断
  • 组合数Cmn算法
  • 最大公约数
  • 最小公倍数
  • 一个数字以？开头或结尾的数量
  • 获取二进制字符串格式
  • 生成从[0, n) 内所有是完全平方数的数组
  • 判断一个数是否是每一位递减

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
# -*- encoding: utf-8 -*-
"""
PyCharm math
2021年11月27日
by littlefean
"""

import math

# C语言中一些数字类型上限
from typing import List

INT_MAX = 2147483647
LONG_MAX = 2147483647
UINT_MAX = 2 ** 32 - 1
LLONG_MAX = 2 ** 63 - 1
ULLONG_MAX = 2 ** 64 - 1
FLT_MAX = 3.4e38
DBL_MAX = 1.7e308
LDBL_MAX = 1.19e4932


def isPalindrome(x: int) -> bool:
    """判断是否是回文数"""
    return x > -1 and str(x)[::-1] == str(x)


def isPrim(n: int) -> bool:
    """判断是否是质数  O(✓n)"""
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def countPrim(n: int) -> int:
    """[0, n) 内有多少个质数 厄拉多塞筛法 O(n*(?n))"""
    count = 0
    signs = [True] * n
    for i in range(2, n):
        if signs[i]:
            count += 1
            for j in range(i + i, n, i):
                signs[j] = False
    return count


def c(m, n):
    """组合数"""
    return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))


def gcd(n1, n2):
    """最大公约数"""
    return gcd(n2, n1 % n2) if n2 > 0 else n1


def lcm(n1, n2):
    """最小公倍数"""
    return n1 * n2 // gcd(n1, n2)


def countDigOne(n: int) -> int:
    """给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。"""
    num = n
    i = 1
    s = 0
    while num:
        if num % 10 == 0:
            s = s + (num // 10) * i
        if num % 10 == 1:
            s = s + (num // 10) * i + (n % i) + 1

        if num % 10 > 1:
            s = s + math.ceil(num / 10) * i
        num //= 10
        i *= 10
    return s


def stripNum(n: int, targetDig: int, reverse=False) -> int:
    """
    n: 1112233
    targetDig: 1  要是个位数
    return: 3 表示有三个1是开头的
    reverse: 如果是True，则统计的是有多少个数字以它结尾的
    """
    strN = str(n)
    if reverse:
        strN = reversed(strN)
    res = 0
    for char in strN:
        if char == str(targetDig):
            res += 1
        else:
            break
    return res


def getBin(n: int) -> str:
    """获取一个数字的二进制回文串"""
    b = str(bin(n))
    if n < 0:
        return b[3:]
    else:
        return b[2:]


def squaresArr(n: int) -> List[int]:
    """生成从[0, n) 内所有是完全平方数的数组
    n: 100
    return: [1, 4, 9, 16, 25, 36, 49, 67, 81]"""
    if n < 1:
        return []
    res = []
    for i in range(1, int(n ** 0.5) + 1):
        res.append(i ** 2)
    return res


def isDown(n: int) -> bool:
    """判断这个数是不是按位数递减的"""
    if n < 10:
        return True
    s = str(n)
    for i in range(len(s) - 1):
        if int(s[i]) > int(s[i + 1]):
            continue
        else:
            break
    else:
        return False
    return True


def main():
    import datetime

    print(datetime.datetime.now() + datetime.timedelta(hours=15, minutes=53))
    for i in range(-10, 40):
        print(i, getBin(i))
    # inputData = input().split()
    # a, b = int(inputData[0]), int(inputData[1])
    # print(gcd(a, b), lcm(a, b))


if __name__ == '__main__':
    main()

内容还有待更新。如果代码有疏漏欢迎批评指正