常见的算法题python

字符串倒序

def func1(str):
    return str[::-1]
def func2(str):
    new_str =""
    for i in str:
        new_str = i+new_str
    return new_str
if __name__=='__main__':
    str="linda"
    print(func2(str))

合并两个有序的列表

def func3(list1,list2):
    for i in list1:
        list2.append(i)
        list2.sort()
    return list2

if __name__=='__main__':
    list1 = [1,2,3]
    list2=[4,7,8]
    print(func3(list1,list2))

删除列表中有重复的项

def func4(list1):
    return list(set(list1))

def func5(list1):
    for i in list1:
        if list1.count(i)>1:
            list1.remove(i)
            return list1
if __name__=='__main__':
    list1 = [1,2,3,4,4]
    print(func5(list1))

求两个数之和等与某个数的下标

def func6(list,target):
    for i in range(len(list)):
        for j in range(i+1,len(list)):
            if list[i]+list[j]==target:
                return [i,j]

if __name__=='__main__':
    list1=[1,5,7,10,2]
    target =9
    print(func6(list1,target))

求斐波那契数列

def func7(n):

    if n<=1:
        return n
    else:
        return func7(n-1)+func7(n-2)

if __name__=='__main__':
    print(func7(7))

冒泡排序

如果前面的数比后面的数大就交换两数，否则不交换，有N个数，则比较N-1趟

def func8(list):
    for i in range(len(list)-1):#减去1是因为最后一个数不需要比较了
        for j in  range(len(list)-1-i):#减去i是因为每次循环后，最后一个数已经是最大的了，不需要比较了
            if list[j]>list[j+1]:
                list[j],list[j+1]=list[j+1],list[j]
    return list
list=[2,3,4,10,0,8]
print(func8(list))

二分查找

将数组分成两半，通过比较中间元素与目标值的大小，逐步缩小搜索范围，直到找到目标值或搜索范围为空，如果目标值大于中间元素，则就会在右边查找，如果目标值小于中间元素，则就会在左边查找
初始化：
left =0
right=len(list)-1
mid=(left+right)//2

def func9(list,target):
    left =0
    right = len(list)-1
    while left<=right:
        mid = (left+right)//2
        if list[mid]>target:
            right=mid-1
        elif list[mid]<target:
            left = mid+1
        else:
            return mid
    return -1
if __name__=='__main__':
    list1=[2,5,1,6,10]
    target=10
    print(func9a(list1,target))

统计列表中元素出现的次数

#使用字典

list =[1,1,3,4,3,4,30,30,30,20,4]
def func10(list):
    dict ={}
    #首先对列表进行遍历
    for i in list:
        if i in dict:
            dict[i]+=1
        else:
            dict[i]=1
    return dict
print(func10(list))