快排,冒泡,插入,二分,单例,交错01串(python),回文字符串

import random

# 二分
def binary_search(li, val):
    low = 0
    high = len(li)-1
    while low <= high:
        mid = (low + high) // 2
        if li[mid] < val:
            low = mid + 1
        elif li[mid] > val:
            high = mid - 1
        else:
            return mid
    return None

# 快排

def partition(li, left, right):
    i = random.randint(left, right)
    li[left], li[i] = li[i], li[left]

    tmp = li[left]
    while left < right:
        # 从右边找比tmp小的数
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        # 从左边找比tmp大的数
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left


def _quick_sort(li, left, right):
    if left < right:    # 表示至少两个元素
        mid = partition(li, left, right)
        _quick_sort(li, left, mid-1)
        _quick_sort(li, mid+1, right)

# li = list(range(100))
# random.shuffle(li)
# _quick_sort(li, 0, len(li)-1)
# print(li)

# 冒泡
def bubble_sort(li):
    for i in range(len(li)-1):  # i表示第i趟,共n-1趟
        # 第i趟 无序区范围 0~n-i-1
        for j in range(len(li)-i-1): # j表示箭头
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

# li = list(range(100))
# random.shuffle(li)
# bubble_sort(li)
# print(li)

# 插入
def insert_sort(li):
    for i in range(1, len(li)):
        # i 表示趟数 还表示摸到牌的位置
        j = i - 1
        tmp = li[i]
        while j >= 0 and li[j] > tmp:
            # 两个终止条件： 1. j==-1 2. j位置的值小于等于tmp
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

# li = list(range(100))
# random.shuffle(li)
# insert_sort(li)
# print(li)

匹配语法括号  

def solve_brace(exp):
    d = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in exp:
        if ch in {'(', '[', '{'}:
            stack.append(ch)
        elif len(stack) == 0:
            return False
        elif d[ch] == stack[-1]:
            stack.pop()
        else:
            return False
    if len(stack) > 0:
        return False
    else:
        return True

print(solve_brace("{[]}"))


单例

# class Earth(object):
#     __instance = None  # 定义一个类属性做判断
#     def __new__(cls):
#         if cls.__instance == None:
#             # 如果__instance为空证明是第一次创建实例
#             # 通过父类的__new__(cls)创建实例
#             cls.__instance = object.__new__(cls)
#             return cls.__instance
#         else:
#             # 返回上一个对象的引用
#             return cls.__instance
# a = Earth()
# print(id(a))
# b = Earth()
# print(id(b))

编程用sort进行排序,然后从最后一个元素开始判断去重

a = [1,3,3,5,2,4,5,3,1]
a.sort()
print(a)

list=a[-1]
for i in range(len(a)-2,-1,-1):
    if list == a[i]:
        del a[i]
    else:list = a[i]
print(a)



交错01串
如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。例如: “1”,”10101”,”0101010”都是交错01串。 

line="01110101"
def get_longest_str(s):
    len_s=len(s)
    max_list=[]
    max_len=0
    for i in range(len_s-1):
        if s[i+1]!=s[i]:
            max_list.append(s[i])

        else:
            if len(max_list)+1>max_len: #加1 因为上面01串应该是包括s[i+1]的
                max_len=len(max_list)+1
            max_list=[]

#这是为了防止01串一直到结束，未求最长01串的长度
    if len(max_list)+1>max_len:
        max_len=len(max_list)+1
    return max_len
print(get_longest_str(line))

回文字符串

def ishuiwen(sub):
    # 判断当前串是否是回文串
    for i in range(len(sub)):
        if sub[i] != sub[len(sub) - i - 1]:
            return False
    return True


def find_huiwen(s):
    huiwenchuan = []
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            sub = s[i:j + 1]
            # 判断回文字符串
            if ishuiwen(sub):
                huiwenchuan.append(sub)

    return huiwenchuan


if __name__ == '__main__':
    s = 'abcbcbcab'  # 首先，可以看到该字符串中的最大回文为
    huiwen = find_huiwen(s)
    print(huiwen)