**

本文主要是介绍**，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • 快排
  • 整数拆分问题
  • 大数相乘
  • 字符串的全排列
  • 跳跃比赛
  • 海拔路径
  • 字符串展开
  • 归并排序
  • 背包问题
  • 最大回文子串
  • 二分查找
  • 起泡排序

快排

def quick_sort(arr):
    '''
    用栈实现非递归
    '''
    if len(arr) < 2:
        return arr
    stack = []
    stack.append(len(arr)-1)
    stack.append(0)
    while stack:
        left = stack.pop()
        right = stack.pop()
        i = partition(arr, left, right)
        if left < i - 1:
            stack.append(i - 1)
            stack.append(left)
        if right > i + 1:
            stack.append(right)
            stack.append(i + 1)

def partition(arr, left, right):
    # 分区操作，返回基准线下标
    key = arr[left]
    while left < right:
        while left < right and arr[right] >= key:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= key:
            left += 1
        arr[right] = arr[left]
    # 此时left = right
    arr[left] = key
    return left

整数拆分问题

【问题描述】：
求将正整数n无序拆分成最大数为k的拆分方案个数，要求所有的拆分方案不重复。
【问题求解】：
n = 5, k = 5, 对应的拆分方案如下：
5 = 5
5 = 4 +１
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1

一、递归法
根据n和m的关系，考虑下面几种情况：
（1）当n=1时，不论m的值为多少（m>0），只有一种划分，即{1}；
（2）当m=1时，不论n的值为多少（n>0），只有一种划分，即{1,1,…1,1,1}；
（3）当n=m时，根据划分中是否包含n，可以分为两种情况：
（a）划分中包含n的情况，只有一个，即{n}；
（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；
因此，f(n,n) = 1 + f(n, n - 1)。
（4）当n<m时，f(n,m) = f(n,n)。
（5）当n>m时，根据划分中是否包含m，可以分为两种情况：
（a）划分中包含m的情况，即{m,{x1,x2,x3,…,xi}}，其中{x1,x2,x3,…,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m, m)；
（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n, m - 1)；
因此，f(n,m) = f(n - m,m) + f(n, m - 1)。

def GetPartitionCount(n,m):
    if n == 1 or m == 1:
        return 1
    elif n < m:
        return GetPartitionCount(n,n)
    elif n == m:
        return 1 + GetPartitionCount(n,n-1)
    else:
        return GetPartitionCount(n-m,m) + GetPartitionCount(n,m-1)

二、动态规划

def GetPartitionCount(n,m):
    for i in range(1,n+1):
        for j in range(1,m+1):
            if j == 1 or i == 1:
                dp[i][j] = 1
            elif i == j:
                dp[i][j] = dp[i][j-1]+1
            elif i<j:
                dp[i][j]=dp[i][i]
            else:
                dp[i][j]=dp[i-j][j]+dp[i][j-1]
    return dp[n][m]

三、给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

def integerBreak(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        dp = [0 for _ in range(n+1)]
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(3,n+1):
            tmp = 0
            for j in range(1,i):
                tmp = max(tmp,max(j * dp[i - j],j*(i-j)))
            dp[i] = tmp
        return dp[n],dp

大数相乘

def list2str(lis):
    while lis[0]==0:
        del lis[0]
    res=''
    for i in lis:
        res+=str(i)
    return res

def multi(a,b):
    lis_a,lis_b = list(a),list(b)
    len_a,len_b = len(a),len(b)
    # 乘积最长（len_a+len_b）位
    result = [0 for _ in range(len_a+len_b)]
    for i in range(len_a):
        for j in range(len_b):
            # 0开始，i位和j位结果加到i+j位上
            result[len_a-i-1+len_b-j-1] += int(lis_a[i])*int(lis_b[j])
    # 进位
    for i in range(len(result)-1):
        if result[i]>=10:
            result[i+1]+=result[i]//10
            result[i]=result[i]%10
    return list2str(result[::-1])

if __name__ == '__main__':
    values = input().split()
    a,b = values[0],values[1]
    print(multi(a,b))
    # 2899887676637907866 1788778992788348277389943

字符串的全排列

输入"abc"
输出"abc",“acb”,“bac”,“bca”,“cab”,“cba”

递归：

def permutation(nums, p, q):
    if p == q:
        s.append(list(nums))
    else:
        for i in range(p, q):
            nums[i], nums[p] = nums[p], nums[i]
            permutation(nums, p+1, q)
            nums[i], nums[p] = nums[p], nums[i]
s= []
nums = [i for i in range(1, 4)]
permutation(nums, 0, len(nums))
print(s)

跳跃比赛

给出一组正整数，你从第一个数向最后一个数方向跳跃，每次至少跳跃1格，每个数的值表示你从这个位置可以跳跃的最大长度。计算如何以最少的跳跃次数跳到最后一个数。
示例1 输入 7 2 3 2 1 2 1 5 输出 3

(1)从起点开始，找到第一个可以一步到达终点的位置；
(2)把刚刚找到的位置作为新的终点，重复(1);
(3)直到新的终点和起点重合，结束。

def jump(end,num):
    if end == 0:
        return 0
    i = 0
    while num[i] < (end-i):
        i += 1
    return 1+jump(i,num)


if __name__ == '__main__':
    num = list(map(int,input().split()))
    print(jump(len(num)-1,num))
    # 2 3 2 1 2 1 5

海拔路径

矩阵中指定起点和终点，每次只能往高海拔移动，求路径数。

def findpath(now,path):
    if now == end:
        paths.append(path)
    # 左移
    if now[0]-1 >= 0:
        if matrix[now[0]-1][now[1]]  > matrix[now[0]][now[1]]:
            findpath([now[0]-1,now[1]],path+'left|')
    # 右移
    if now[0]+1 < int(matrix_size[0]):
        if matrix[now[0]+1][now[1]]  > matrix[now[0]][now[1]]:
            findpath([now[0]+1,now[1]],path+'right|')
    # 上移
    if now[1]-1 >= 0:
        if matrix[now[0]][now[1]-1]  > matrix[now[0]][now[1]]:
            findpath([now[0],now[1]-1],path+'up|')
    # 下移
    if now[0]+1 < int(matrix_size[1]):
        if matrix[now[0]][now[1]+1]  > matrix[now[0]][now[1]]:
            findpath([now[0],now[1]+1],path+'down|')

if __name__ == '__main__':
    matrix_size = input().split()
    matrix = []
    for i in range(int(matrix_size[0])):
        matrix.append(list(map(int,input().split())))
    a = list(map(int,input().split()))
    start = [a[0],a[1]]
    end =  [a[2],a[3]]
    paths = []
    findpath(start,'')
    print(len(paths))
    print(paths)
'''
4 5
0 1 0 0 0
0 2 3 0 0
0 3 4 5 0
0 0 7 6 0
0 1 3 2
'''

字符串展开

输入：abc4[3(A)B]
输出：BAAABAAABAAABAAAcba

def solution(s):
    res=''
    number = []
    # 数字入栈
    for i in s:
        if i.isdigit():
            number.append(int(i))
        elif i == ')':
            cur_number = number.pop()
            temp=''
            # 找括号内字符串
            for j in range(len(res)-1,-1,-1):
                if res[j]!='(':
                    temp+=res[j]
                else:
                    break
            # 扩展
            res=res[0:j]+cur_number*temp[::-1]

        elif i == ']':
            cur_number = number.pop()
            temp = ''
            for j in range(len(res) - 1, -1, -1):
                if res[j] != '[':
                    temp += res[j]
                else:
                    break
            res = res[0:j] + cur_number*temp[::-1]

        elif i == '}':
            cur_number = number.pop()
            temp = ''
            for j in range(len(res) - 1, -1, -1):
                if res[j] != '{':
                    temp += res[j]
                else:
                    break
            res = res[0:j] + cur_number*temp[::-1]
        else:
            res+=i
    return res[::-1]

if __name__ == '__main__':
    s = input()
    print(solution(s))

归并排序

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i = 0; j = 0; k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1

背包问题

w = [0, 1, 4, 3, 1]   # n个物体的重量(w[0]无用)
p = [0, 1500, 3000, 2000, 2000]   # n个物体的价值(p[0]无用)
n = len(w) - 1   #计算n的个数
m = 4   #背包的载重量

x = []   #装入背包的物体，元素为True时，对应物体被装入(x[0]无用)
v = 0
# n行为物件，m列为自背包载重量,dp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值
dp = [[0 for col in range(m + 1)] for raw in range(n + 1)]

def knapsack_dynamic(w, p, n, m, x):
    for i in range(1, n + 1):       # 物品
        for j in range(1, m + 1):   # j为子背包的载重量，寻找能够承载物品的子背包
            if (j >= w[i]):         # 当物品的重量小于背包能够承受的载重量的时候，才考虑能不能放进去
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i])    # dp[i - 1][j]是上一个单元的值， dp[i - 1][j - w[i]]为剩余空间的价值
            else:
                dp[i][j] = dp[i - 1][j]

    #递推装入背包的物体,寻找跳变的地方，从最后结果开始逆推
    j = m
    for i in range(n, 0, -1):
        if dp[i][j] > dp[i - 1][j]:
            x.append(i)
            j = j - w[i]  

    #返回最大价值，即表格中最后一行最后一列的值
    v = dp[n][m]
    return v

print ('最大值为：' + str(knapsack_dynamic(w, p, n, m, x)))
print ('物品的索引：',x)

最大回文子串

def manacher(s):
    ss = '#'+'#'.join(s)+'#'
    print(ss)
    rl = [0]*len(ss)
    maxright = 0
    pos = 0
    maxlen = 0
    for i in range(len(ss)):
        # i在maxright左边时找对称回文串
        if i < maxright:
            rl[i] = min(rl[2*pos-i],maxright-i)
        else:
            rl[i] = 1
        # 左右两边扩展找回文串
        while i-rl[i] >= 0 and i+rl[i] < len(ss) and ss[i-rl[i]] == ss[i+rl[i]]:
            rl[i] += 1
        # 更新maxright和pos
        if rl[i]+i-1 > maxright:   
            maxright = i+rl[i]-1
            pos = i
        # 更新maxlen
        maxlen = max(maxlen,rl[i])
    return maxlen-1

动态规划：

def longestPalindrome(s):
    str_length = len(s)
    if str_length == 0:
        return ''
    max_length = 0
    i_start = 0
    for i in range(str_length):
        if i - max_length >= 1 and \
        	s[i - max_length - 1:i + 2] == \
        	s[i - max_length - 1:i + 2][::-1]:
            i_start = i - max_length - 1
            max_length += 2
            continue
        if i - max_length >= 0 and \
        s[i - max_length:i + 2] == \
        s[i - max_length:i + 2][::-1]:
            i_start = i - max_length
            max_length += 1
    return s[i_start:i_start + max_length+1]

二分查找

def binarySearch(arr, item):
	if len(arr) < 1:
		return False
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right)//2
        if arr[mid] > item:
            right = mid - 1
        elif arr[mid] < item:
            left = mid + 1
        else:
            return mid+1
    return False

起泡排序

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

这篇关于**的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！