Python物语：Leetcode 算法

# coding:utf-8
# win 10 + python3

# 冒泡排序
def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


# 选择排序
def selection_sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr


# 插入排序
def insertion_sort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

# 数组合并去重
a = [2,3,1]
b = [4,3,5]
f = a + b
# 去重并排序
c = set(f)
c = list(c)
print(c)
# 去重并保留原有顺序
c = sorted(c,key=f.index)
print(c)


# 两数之和
# 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

nums = [1, 2, 7, 11, 15]
target = 9
def two_sum(nums,target):
    n = len(nums)
    d = {}
    for x in range(n):
        a = target-nums[x]
        if nums[x] in d:
            return d[nums[x]],x
        else:
            d[a] = x
        print(d)

# 统计字符串中字母出现次数
def count_strnum_1():
    d = {}
    for i in s:
        d[i] = s.count(i)
    print(d)

def count_strnum_2():
    d={}
    s='helloworld'
    for x in s:
        if x not in d:
            d[x]=1
        else:
            d[x]= d[x] +1  
    print(d)

# 回文数
def isPalindrome(self, x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    revertedNumber = 0
    while x > revertedNumber:
        revertedNumber = revertedNumber * 10 + x % 10
        x = int(x/10)
    return x == revertedNumber or x == int(revertedNumber/10)

# 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
nums = [1,2,3,4,5,6,7] 
k = 3
def list_move():
    if nums:
      k = k % len(nums)
      nums[:]=nums[-k:] + nums[:-k]
    return nums


# 无重复字符的最长子串
s='wwwkewippacvbn'
def longest_str(s):
    max_number = 0
    number = 0
    test = ''
    for i in s:
        #如果i不在test字符串里面，字符串test添加这个字符，number+1
        if i not in test:
            test += i
            number += 1
            s1=test
        else:  #i在test字符串里
            if number >= max_number:
                max_number = number
            index = test.index(i)
            test = test[(index+1):] + i
            number=len(test)
        if number > max_number:
            max_number = number
    print(s1)
    print(max_number)

"""

有红、黄、蓝三种颜色的气球。

在牛客王国，1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票。

2个红气球+1个黄气球可以兑换1个蓝气球。

2个黄气球+1个蓝气球可以兑换1个红气球。

2个蓝气球+1个红气球可以兑换1个黄气球。

现在牛牛有a个红气球，b个黄气球， c个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。
3红 + 2黄 = 1彩票
3黄 + 2蓝 = 1彩票
3蓝 + 2红 = 1彩票
"""


def three_max(r, y, b):
    min_num = min(r, y, b)
    r = r - min_num
    y = y - min_num
    b = y - min_num
    if r == 0:
        num = min_num + min(y/3, b/2)
    if y == 0:
        num = min_num + min(b/3, r/2)
    if b == 0:
        num = min_num + min(r/3, y/2)

    print(num)

# 最长重复字符串
def maxRepeatStr(arr):
    if not arr:
        return arr
    # 去重后的每个元素的重复字符串可能的最大长度
    len_up_border = len(arr) - len(set(arr)) + 1
    # 缓存遍历，最大长度和当前元素（分别初始化为1和最大ASCII码对应的字符）
    max_len = 1
    cur_element = chr(127)
    # res[max_len] = min_ascii_element_with_max_length
    res = {}
    # 长度反向遍历的跳出标识
    flag = False
    for i in range(len_up_border, 0, -1):
        for s in set(arr):
            spt = s * i
            # 以 spt 分割原始字符串作为判断依据:如果spt在arr中存在，则分割后长度>1; 若不存在，分割后长度=1
            splited = arr.split(spt)
            if len(splited) > 1:
                # print('i-->', i, 's-->', s, 'splited-->', splited)
                max_len = max(max_len, i)
                cur_element = min(cur_element, s)
                res[i] = cur_element
                flag = True
        if flag:
            break
    output = [v * k for k, v in res.items()]
    return output[0]