算法复习

1、冒泡排序

# 冒泡排序
# 思路：前后进行对比，如从小到大进行排列，i循环是大循环次数，比len小1即range(len(li))
# j的循环是为了前后比大小，把大的放倒数第一第二，所以次数会减少，因为大的已经放到后面了，所以为range(len(li)-i-1)

def maopao(li):
    for i in range(len(li)):
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
    return li

2、二分查找

'''二分查找
    在有序数组中查找元素
    思路：永远跟中间值进行比较，比中间值小向左区间找right=middle-1
    比中间值大向又区间找left=middle+1，直到middle=k结束
'''
def erFenDiGui(li,k,left,right):
    # 递归结束
    if left > right:
        return -1
    # 找区间中间值，向下取整
    middle = (left + right) // 2
    # 最终找到返回中间值停止循环
    if k  ==  li[middle]:
        return middle
    # 比中间值小，向左区间进行
    elif k < li[middle]:
        return erFenDiGui(li,k,left,middle - 1)
    # 比中间值大，向右区间进行
    else:
        return erFenDiGui(li,k,middle +1,right)

3、判断回文：

解法一(切片)、

# 回文
# 思路：1、切片反转跟原字符串对比
# 用到函数：i.isalpha()————是否为字母
#           i.isdigit()————是否为数字
#           i.lower()转换成小写字母
#           s_new[::-1]切片，反转字符串
def huiWen01(s):
    s=s.lower()
    s_new = ''
    # 提取数字和字母全转小写
    for i in s:
        if i.isalpha():
            s_new = s_new + (i)
        if i.isdigit():
            s_new = s_new + (str(i))
    if s_new == s_new[::-1]:
        return True
    else:
        return False

解法二（双指针）

# 回文：双指针做法
# 左右两个指针，循环用while，当left<right时
# 记一个高端写法： s = [ch.lower() for ch in s if ch.isalnum() // 一句话剔除除字母数字外的字符并转为小写
def huiWen02(s):
    if len(s)<=1:
        return True
    s = s.replace(' ','').lower()
    # s = [ch.lower() for ch in s if ch.isalnum()]
    left,right = 0,len(s)-1
    while left < right:
        if s[left] == s[right]:
            left +=1
            right -=1
        elif not s[left].isalnum():
            left +=1
        elif not s[right].isalnum():
            right -=1
    return True

4、基于排列构建数组

# 基于排列构建数组
# 给你一个 从 0 开始的排列 nums（下标也从 0 开始）。
# 请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），
# 都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans

# 知识点：高级写法一句话：return [nums[nums[_]] for _ in range(len(nums))]
def new_ans(nums):
    ans = []
    for i in range(len(nums)):
        ans.append(nums[nums[i]])
    return ans
# return [nums[nums[_]] for _ in range(len(nums))]

5、数组串联

知识点：extend()和+的区别：https://www.cnblogs.com/liusijun113/p/10263093.html

# 数组串联
# 给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标 从 0 开始计数 ，
# 对于所有 0 <= i < n 的 i ，满足下述所有要求：
# ans[i] == nums[i]
# ans[i + n] == nums[i]
# 具体而言，ans 由两个 nums 数组 串联 形成。
# 返回数组 ans

# 知识点：nums.extend(nums); return nums
def shuZuChuanLian(nums):
    # return [nums[_] for _ in range(len(nums))]
    return nums+nums