Python_algorithm

2020-12-08

总结一些自己学习过的算法

概念

递归（Recursion)

递归这部分在最开始的《Python Questions》也提到过，在这里再次归纳进来

def rec(n):
    if n==1:
      return 1
    else:
      return n+rec(n-1)
print(rec(100))

二分查找（Binary search）

直接将输入数据坎半，继而查找范围也减半

def binary(input_data,target):
    max= len(input_data)-1
    min= 0
    while(min<=max):
          #整数除法
          mid=(max+min)//2
          if(target==input_data[mid]):
              return input_data[mid]
          elif(input_data[mid]>target):
              max=mid-1
          else:
              min=mid+1
    else:
        print("no result!")

new_list=binary([1,2,3,4,5,6,7],6)

冒泡排序（Bubble sort）

相邻两个数比大小，遍历整个数组后，将输入数据按大小排列

def bubble_sort(input_data):
    for i1 in range(len(input_data)-1):
        for i2 in range(len(input_data)-1-i1):
            if input_data[i2]>input_data[i2+1]:
                input_data[i2],input_data[i2+1]=input_data[i2+1],input_data[i2]
    return input_data

从大到小排序：<
从小到大排序：>
例如有一列input_data[1,3,4,2,5],则len(input_data)为5

#遍临4次
for i1 in range(5-1=4):
#遍临4，3，2，1次
    for i2 in range(4-i1(0,1,2,3)):
#两两比较大小，然后排序，然后返回再次遍临比较
#第一次
before:[1,3][3,4][4,2][4,5]
after:[1,3][3,4][2,4][4,5]
#第二次
before:[1,3][3,2][3,4]
after:[1,3][2,3][3,4]
#以此类推

问题

总结一些我碰到过的算法问题

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

方法一

class Solution(object):
    def twoSum(self,nums,target):
        n=len(nums)
        for x in range(n):
            a=target-nums[x]
            if a in nums:
                y= nums.index(a)
                if x==y:
                    continue
                else:
                    print(x,y)
                    print(nums[x],nums[y])
                    break
            else:
                continue

s=Solution()
s.twoSum([2,7,11,15],9)

方法二

def find(input_list,target):
    index=0
    length=len(input_list)
    #print(length)
    while(index!=length):
        for i in range(length):
            #print(i)
            n=input_list[index]+input_list[i]
            #print(index,i)
            #print(input_list[index],input_list[i])
            #print(n)
            if(n==target):
                #print("!!!")
                #print(index,i)
                return index,i
            #else:
                #print(n)
        index=index+1
        #length=length-1

new_list=[11,2,15,7]
find(new_list,9)
print(find(new_list,9))

Wordbreak(动态规划)

根据词典数组将输入文本切割成词语数组并输出

data_list=["京张","京张高铁","京张高铁北京北站","宣传","宣传活动","活动展台",
       "在","今天","在今天","今天的","的","宣布","了","开通","正式开通","上","，","。"]
input_data='在今天的宣传活动展台上，宣布了京张高铁北京北站开通。'

def solution(source,dict):
    res=[]
    length=len(input_data)
    def search(li,new):
        #print(li)
        if new==length:
            res.append(li[1:])
        for i in range(new,length):
            #print(source[new:i+1])
            if source[new:i+1] in dict:
                #print(source[new:i+1])
                print(li+" "+source[new:i+1],i+1)
                search(li+" "+source[new:i+1],i+1)
    search('',0)
    print(res[0])
solution(input_data,data_list)

find the maximum number of neighbouring pairs whose sums are even

#import itertools
#from itertools import combinations
def solution(li):
    #new_list= combinations(li,2)
    new=zip(*([iter(li)]*2))
    new_list=[]
    if(li[0]!=li[-1]):
        last=(li[0],li[-1])
        new_list.append(last)
    for a in new:
        new_list.append(a)
    print(new_list)
    res=0
    for i in range(len(new_list)):
        if(sum(new_list[i])%2==0):
            res=res+1
    return res

my_list=[14,21,16,35,22]
my_list_2=[4,2,5,8,7,3,7]
my_list_3=[5,5,5,5,5,5]
print(solution(my_list))
print(solution(my_list_2))
print(solution(my_list_3))

输出列表中的数据，该数据出现的次数大于等于该列表长度的一半

def func(li):
    index=1
    length=len(li)
    l2=0.5*length
    print(l2)
    for i in range(length-1):
        for j in range(i,length-1):
            print(li[i],li[j+1])
            if(li[i]==li[j+1]):
                index=index+1
        if(index>=l2):
            return li[i]
            break
        index=1
my_list=[1,2,3,4,2,1,2,2]
print(func(my_list))

概念