void land space 主页文章标签分类相册
数据类型
| algorithm

一些基础数据类型的算法

整形交换值

  • 在不适用其他变量的情况下，利用异或操作，交换两个变量的值
a, b = 1234, 5678
a = a + b  # 这种方法会可能产生数据溢出
b = a - b
a = a - b
a, b = 1234, 5678
a = a ^ b  # a = 4860
b = a ^ b  # b = 1234
a = a ^ b  # a = 5678

最大公约数

  • 求a,b的最大公约数。
  • 对整数求余，最著名的是欧几里得法：①先求两数相除后的余数，即d=a/b；②那么a,b的最大公约数就等于d,b的最大公约数。
def gcd(a,b):
    if a % b ==0:
        return b
    d = a % b
    return gcd(b,d)
print(128,48,gcd(128,48))
  • 尝试不使用乘法、除法和求余，计算最大公约数，这就需要位运算了。
  • 思路就是：a = k·b + d，那么k可以用二进制来代替，使用位运算，将b进行左移多次，从而利用加减法即可求出d。

b<<t1+b<<t2...<a<b<<t1+b<<t2...+bb<<t_1 + b<<t_2 ... < \quad a \quad < b<<t_1 + b<<t_2 ... + b

  • 得到t的数组，求出余数，再利用欧几里得法即可。

素数判定

  • 素数也称质数，质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。
  • 关于1是不是质数，1不是质数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。质数的定义中明确指出了一个前提条件，一个大于1的自然数。1不属于这个范围，所以1不是质数。
  • 历史上，曾经将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。
  • 题目：给定一个正整数n，返回1~n中所有的素数。

暴力法

def isPrime(num):
    if num <2:
        return False
    for i in range(2,num):
        if num % i == 0:
            return False
    return True
number = 100
primeList = []
for i in range(number):
    if isPrime(i):
        primeList.append(i)
print(primeList)
  • 时间复杂度：O(n2n^2)
  • 暴力法的缺点就是时间复杂度太高

只考虑是否能够整除素数

primeList = [2]
def isPrime(num):
    if num <2:
        return False
    for i in primeList:
        if num % i == 0:
            return False
    return True
number = 100
for i in range(number):
    if isPrime(i):
        primeList.append(i)
print(primeList)

删除所有素数的倍数

number = 100
primeList = [True for i in range(0,number+1)]
primeList[0],primeList[1] = False, False
for index,i in  enumerate(primeList):
    if i:
        j = 2
        while j*index<=number:
            primeList[j*index] = False
            j+=1
for index,i in enumerate(primeList):
    if i:
        print(index,end=", ")

Elias Gamma编码

  • 编码描述：给定整数，将其转化为二进制字符串形式，然后获取字符串长度减一，添加对应数量的0在字符串前面。
  • 要求：给定含有n个元素的整形数组，将每个元素进行Elias编码，并拼接字符串。同时实现解码字符串，返回整形数组。
class EliasGamma:
    def decode(self,str):
        valueStrList = self.get_binary_value_list(str)
        valueList = self.get_value_list(valueStrList)
    def get_value_list(self,valueStrList):
        result = []
        for value in valueStrList:
            content = 0
            for index,i in enumerate(value):
                if i=="1":
                    content += 1 << (len(value)-index-1)
            result.append(content)
        return result
    def get_binary_value_list(self,str):
        i = 0
        result = []
        length = 0
        if str[0]!="0":
            raise Exception("err")
        while i<len(str):
            if str[i]=="0":
                length += 1
                i += 1
            else:
                result.append(str[i:i+length+1])
                i += length+1
                length = 0
        return result
    def encode(self,valueList):
        result = ""
        for value in valueList:
            str = self.get_binary_string(value)
            result += self.add_zero_to_head(str)
        print(result)
    def get_binary_string(self,value):
        result = ""
        if value <=0:
            return "0"
        while value:
            if value%2==0:
                result = "0" + result
            else:
                result = "1" + result
            value = value>>1
        return result
    def add_zero_to_head(self,str):
        result = str
        for i in range(len(str)-1):
            result = "0" + result
        return result
if __name__ == '__main__':
    EliasGamma().decode("000101100011000001101")
    EliasGamma().encode([11,12,13])
  • 这里需要优化的是代码整体结构，将代码主逻辑和分支合理的划分，体现出业务逻辑转化为实际代码的能力，将复杂业务拆解为简单模块的组合。
data structure