化工热力学补考成功，几天没有头脑了，赶紧赏自己几题Leetcode动态规划算法最长系列
@Author：Runsen
@Date：2020/10/9
“恭喜你昨天，化工热力学补考成功！”
“区区化工热力学还想让我重修，只不过浪费了我九月一半的精力和十月的九成精力，补考其实是庆祝你可以毕业而已。”
还有10/15号的化工原理补考，给我再来一次翻身的感受？
必须的，但是为了补考，错过了校招。我真的好点慌。
那赶紧趁着这几天刷下Leetcode恢复下Feel，剩下几天给我死命复习化工原理。
那必须的，从十月，我就没有写博客，没有刷Leetcode，人生就像没有了精彩。
那没办法，补考事重于泰山，你不能跟毕业证开玩笑。
动态规划算法最长系列，可以说是dp的重点，竟然我这么想死，那我就开始搞残我的大脑。
Leetcode5、 最长回文子串
Leetcode第五题、 最长回文子串，方法动态规划和中心扩展，有没有印象？
动态规划：dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
i表示回文左边的index，j表示回文右边的index，需要判断dp[i + 1][j - 1]是不是回文，而且要求 s[i] == s[j]，那么dp[i][j]就是回文。
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ len_s = len(s) if len_s < 2: return s # 因为是判断子串，根据子串的性质s[i:j]，因此必然涉及到两层循环，也就需要定义二维数组dp # 状态初始化：默认为True，可以省去很多计算 dp = [[True for _ in range(len_s)] for _ in range(len_s)] max_len = 0 start = 0 # 状态转移方程：表示i到j的子串是否是回文子串 # dp[i][j] = (s[i] == s[j] and dp[i+1][j-1]) # 遍历状态集：因为需要知道j-1，因此j需要从1开始 for j in range(1, len_s): # 因为是子串，i一定是要小于j for i in range(j): if s[i] == s[j]: # 如果头尾字符相等，那么直接正负取决于之前的子串 dp[i][j] = dp[i+1][j-1] else: # 如果不相等，不管子串如何，肯定不是回文 dp[i][j] = False # 更新最大长度 if dp[i][j] and max_len < j - i: max_len = j - i start = i return s[start:start+max_len+1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
还有一个方法是中心扩散的，注意s[l + 1:r]返回的位置。
def helper(s, l, r): # 中心扩散
while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1
return s[l + 1:r]
res = ""
for i in range(len(s)): # 奇数形回文, like "aba" tmp = helper(s, i, i) if len(tmp) > len(res): res = tmp # 偶数形回文, like "abba" tmp = helper(s, i, i + 1) if len(tmp) > len(res): res = tmp
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
更多的查看大佬的题解
Leetcode300、最长上升子序列
'''
@Author： Runsen
@WeChat：RunsenLiu
@微信公众号： Python之王
@CSDN： https://blog.csdn.net/weixin_44510615
@Github： https://github.com/MaoliRUNsen
@Date： 2020/10/9
'''
def lengthOfLIS(nums): # 如果定义dp dp[i] 最长上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0<k<i-1 m = len(nums) if m <= 1: return m dp = [ 1 for _ in range(m)] for i in range(1,m): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+ 1 ) return max(dp)
print(lengthOfLIS([1,3,6,7,9,4,10,5,6]))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
Leetcode674. 最长连续递增序列
Leetcode300、最长上升子序列要求是不连续的，而Leetcode674. 最长连续递增序列要求是连续的。
class Solution: def findLengthOfLCIS(self, nums: List[int]) -> int: """动态规划""" # n = len(nums) # if n == 0: # return 0 # dp = [0] * n # dp[0] = 1 # for i in range(1, n): # if nums[i] > nums[i-1]: # dp[i] = dp[i-1] + 1 # else: # dp[i] = 1 # return max(dp) """遍历一遍就解决问题""" n = len(nums) if n <= 1: return n count = 1 res = 1 for i in range(1, n): if nums[i] > nums[i-1]: count += 1 else: count = 1 res = max(res, count) return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
Lintcode 397. 最长上升连续子序列
Lintcode 此题和Leetcode中的第674多了一个要求，认为（最长上升连续子序列可以定义为从右到左或从左到右的序列。）
其实就是求最长连续递减序列。
class Solution: """ @param A: An array of Integer @return: an integer """ def longestIncreasingContinuousSubsequence(self, A): # write your code here # dp[i] = max(dp[i,dp[k]+ 1) m = len(A) if m <=1:return m dp1 = [1 for _ in range(m)] dp2 = [1 for _ in range(m)] for i in range(1,m): if A[i] > A[i-1]: dp1[i] =dp1[i-1]+ 1 else: dp1[i] =1 if A[i] < A[i-1]: dp2[i] =dp2[i-1]+ 1 else: dp2[i] =1 return max(max(dp1),max(dp2))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
总结
动态规划算法最长序列其中在看于动态规划的状态转移方程如何推导
现在大四了。大三结束后，那时的我还算壮志踌躇，我以为自己可以找到算法的实习，这是一条好路，我必须承认。校招方向只有Java，前端，C++和算法。但出于校招算法内积，没有过人的项目，学历专业的等我自身原因的考虑，我放弃了算法，决定把重心往前端靠靠，拿着一个不太好看的文凭，不太丰富的校内经历，就下定决心在春招找实习。毕竟秋招我给补考耽误了，我需要重新振作起来。
我已经看到了大四秋招的失败，但我还是要厚脸皮去尝试，我还有一些光阴，我曾经年轻过，也正在年轻着。
说完了激励自己的话，那就继续去面对生活吧。
文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。
原文链接：maoli.blog.csdn.net/article/details/108971860
- 点赞
- 收藏
- 关注作者
评论（0）