简单小算法

• 有一个数组，里面只有一个值是唯一的，其余值都是重复成对出现。请设计一个算法，在O1的空间复杂度和On的时间复杂度内，找出这个值。

def so(arr):
    ret = 0
    i = 0
    while i < len(arr):
        ret = ret ^ arr[i]
        i += 1
    return ret


l = [2, 4, 3, 3, 2, 5, 5]

print(so(l))

• 给定一个整数，统计其二进制表示里有多少个1。

def count1(a):
        '''
            整数的二进制表达里有多少个1，复杂度为a的二进制长度。
        '''
        num = 0
        while a != 0:
            num += a & 1
            a >>= 1
        return num

    def count2(a):
        '''
            整数的二进制表达里有多少个1，复杂度仅为1的个数
        '''
        num = 0
        while a != 0:
            a = a & (a - 1)  # 就是这个操作，需要掌握，它的本质含义是抹去了0不考虑
            num += 1
        return num

def count(a):
    num = 0
    while a != 0:
        a = a & (a - 1)
        print(a)
        num += 1
    return num


# Time3BitCount
def bit_count_solution(A):
    a = 0
    for i in A:
        a += 2 * i
    print(count(a * 3))


bit_count_solution([1, 4, 5])

简单做法
一个二进制数乘以2就是向左移动一位，然后乘以3就是[1,4,5]与[2,5,6]相加
就变成[1,2,4,5,5,6]相同进一就是变成[1,2,4,6,6]---->[1,2,4,7]

from itertools import chain


def add_to(item, dic):
    if item not in dic:
        dic[item] = 1
    else:
        dic.pop(item)
        add_to(item + 1, dic)


def solution(li):
    d = {}
    new_list = chain(li, [i + 1 for i in li])
    # print(list(new_list), 343434)

    for i in new_list:
        add_to(i, d)

    return d.keys()


A = [1, 4, 5]
print(solution(A))

• 最大切片和

# MaxSliceSum
def solution(A):
    before_sum = 0
    max_sum = 0
    for i in range(len(A)):
        before_sum += A[i]
        if before_sum >= max_sum:
            max_sum = before_sum
        elif before_sum < 0:
            before_sum = 0
    return max_sum


li = [3, 2, 0, -6, 4, 0]
print(solution(li))

• 计算序列中，在O(n)时间内求出，第二大元素

def d(li):
    max1 = li[0]
    max2 = li[0]
    for i in range(len(li)):
        if li[i] >= max1:
            max2 = max1
            max1 = li[i]
        if max1 > li[i] >= max2:
            max2 = li[i]
    return max2


l = [4, 2, 2, 3, 5, 10, 3, 4, 6, 8]

print(d(l))

• 得到二进制中1的位置

def test(int_num):
    bin_str = str(bin(int_num))
    bin_str = bin_str.replace('0b', '')
    print(bin_str, type(bin_str))
    for i in range(len(bin_str)):
        print(i, 00000)
        if (1 << i) & int_num:
            print(str(i))


test(50)