数组-动态规划

一、题目列表

题目1、连续子数组和最大

题目2、滑动窗口的最大值

题目3、

题目4、丑数

二、题目

题目1、连续子数组和最大

1.思路

三行代码：利用动态规划的思想
(1)要求长度为n的子数组和最大，可以先求长度为2，3，4
(2)让数组每个值更新为当前长度最大的值就行

2.代码

(1)方法一:暴力求解

array = [1,-1,2,4,-3]
re = []
for i in range(len(array)):
    for j in range(len(array)):
        re.append(sum(array[j:j+i+1]))
print max(re)

(2)方法二:递归，动态规划

array = [1,-1,2,4,-3]
for i in range(1,len(array)):
    array[i]=max(array[i-1]+array[i],array[i])
print max(array)

题目2、滑动窗口的最大值

描述
给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

示例1
输入：
[2,3,4,2,6,2,5,1],3
复制
返回值：
[4,4,6,6,6,5]

1.思路

方法一：暴力求解
方法二：改进暴力缺点
1.先定义一个前一个窗口的最大值，
2.向后滑动一个窗口后的值，和最大值比较。分几种情况：
(1)如果新值比最大值大，直接更新最大值
(2)如果新值比最大值小，又分几种情况

如果窗口前一个值等于最大值，求窗口最大值
其他情况，就是最大值

2.代码

(1)方法一:暴力求解
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        if len(num) <= 0:
            return []
        if size>len(num):
            return []
        result = []
        length = len(num)-size +1
        for i in range(length):
            max_val = max(num[i:size+i])
            result.append(max_val)
        return result

方法二：
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        if len(num) <= 0:
            return []
        if size>len(num):
            return []
        cur_max = max(num[:size]) #当前窗口最大值
        max_nums = [cur_max] #结果存储
        for i in range(0, len(num)-size):
            
            if cur_max  < num[i+size]: #如果新增数据大于最大值
                cur_max = num[i+size]  #更新最大值
            else:
                if num[i] == cur_max:  #有分几种情况，只需要处理一种就行，如果第一个值是最大的，则需要求后续最大值
                    cur_max = max(num[i+1: i+size+1])

            max_nums.append(cur_max)    
        return max_nums

题目4、丑数

描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数

1.思路

step 1：第一个丑数1加入数组。
step 2：使用i、j、k三个索引表示该数字有无被乘2、乘3、乘5的指针
step 3：后续继续找n−1n-1n−1个丑数，每次取当前丑数索引乘2、乘3、乘5的最小值加入数组，并计数。
step 4：若是该丑数为相应索引乘上某个数字，则对应的索引往后一位。
参考：https://blog.csdn.net/slove3366/article/details/106724597

2.代码

class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        #排除0
        if index == 0:
            return 0
        #按顺序记录丑数
        num = []
        num.append(1)
        #记录这是第几个丑数
        count = 1; 
        #分别代表要乘上2 3 5的下标，定义三个指针
        i = 0
        j = 0 
        k = 0 
        while count < index:
            #找到三个数中最小的丑数
            num.append(min(num[i] * 2,num[j] * 3, num[k] * 5)); 
            count += 1
            #判断刚才插入数组是哪个指针，需要指针向前移动一个
            if num[count - 1] == num[i] * 2:
                i += 1
            #由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if num[count - 1] == num[j] * 3:
                j += 1 
            #由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
            if num[count - 1] == num[k] * 5:
                k += 1 
        return num[count - 1]