题目5最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
用例
输入: “babad”
输出: “bab”
输入: “cbbd”
输出: “bb”
解题思路
利用动态规划,二维动态规划,dp[i][j]表示字符串从i到j是一个回文串(i<j),那么对于一个定好尾节点为j的字符串,dp[i][j]是回文串的条件是
s[i]=s[j],且dp[i+1][j-1]也是回文串,注意特殊情况当j-i<3时,是不合法的,要单独说明中心扩展法,定好某一个字符作为回文的中心,向两边扩展,搜索最大的回文串长度
马拉车算法——网上看分析
代码
1 | class Solution: |
题目491.递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。
说明:
- 给定数组的长度不会超过15。
- 数组中的整数范围是 [-100,100]。
- 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。
用例
1 | 输入: [4, 6, 7, 7] |
解题思路
利用dfs递归进行求解,注意数据中会有重复的数字,要求把这部分数字造成的重复序列去掉
第二个代码会更好些,因为在每次循环时通过将一个哈希表,将重复的序列直接排除了
代码
1 | from typing import List |
题目486. 预测赢家
给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数,随后玩家2继续从剩余数组任意一端拿取分数,然后玩家1拿,……。
每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
用例
输入: [1, 5, 2]
输出: False
输入: [1, 5, 233, 7]
输出: True
解题思路
- 直接利用dfs模拟取牌的过程,用turn表明当前玩家是先手还是后手,如果是先手,turn为1,如果是后手,turn为-1,
每次抽取时都分两种情况,取左边的或者取右边的,两种结果表示为- nums[i]+dfs(i+1,j)
- nums[j]+dfs(i,j-1)
对于先手,应返回两者的最大值,对于后手,应返回两者的最小值
- 采用动态规划算法,dp[i][j]表示当数组剩下i到j的拍时,当前用户可以从这些牌里取到的最大值,所以dp[i][j]
的转移方程可以写为
dp[i][j]=max(nums[i]+dp[i+1][j],nums[j]+dp[i][j-1])
dp[i][i]=nums[i]
代码
1 | from typing import List |
题目494. 目标和
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号+和-。对于数组中的任意一个整数,你都可以从+或-中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
说明:
解题思路
直接dfs求解,或者利用stack中间的值,方法的复杂度为O(2**n)
动态规划,这道题本质上是一道01背包问题,题目已经给出了利用包中的数字可能构成的数字的范围[-1000,1000],所以对这样的题目
可以用dp[i][j]表示用0到i个数构成数字j的方式,其转移方程可表示为:dp\[i]\[j+nums\[i]+1000]+=dp\[i-1]\[j+1000] dp\[i]\[j-nums\[i]+1000]+=dp\[i-1]\[j+1000]
由于可能构成负数,所以需要+1000,由于i的状态只与i-1相关,所以可以在空间上进行优化,
这道题就是找一个子集是正数,剩下是负数,他们之和等于S,假设正数集和为P,负数集合为N,有sum(P)−sum(N)=S,因为sum(nums)=sum(P)+sum(N),
那么有sum(P)−sum(N)+sum(P)+sum(N)=S+sum(nums),有:2∗sum(P)=S+sum(nums),所以题目就转化成找一个正数集合之和sum(P)为(S+sum(nums))/2,当然这里的(S + sum(nums))大于0并且可以被2整除。
代码
1 | from typing import List |
发布时间: 2020-05-21
最后更新: 2020-05-21
本文标题: leetcode-day9
本文链接: http://huangketsudou.github.io/2020/05/21/leetcode-day9/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处