1217. 玩筹码
数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
- 将第
i个筹码向左或者右移动 2 个单位，代价为 0。 - 将第
i个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
猜了下结论，答案一定存在chips数组当中，我们直接遍历chips统计答案
class Solution(object):
def minCostToMoveChips(self, chips):
"""
:type chips: List[int]
:rtype: int
"""
ans = len(chips)
for i in chips:
cnt = 0
for j in chips:
tmp = i-j if i-j>0 else j-i
cnt += (tmp & 1)
ans = min(cnt,ans)
return ans
1218. 最长定差子序列
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
没有想太多，直接字典保留状态。递推上一位的状态，通过上一位的状态来更新现在的状态。并且更新答案
class Solution(object):
def longestSubsequence(self, arr, difference):
"""
:type arr: List[int]
:type difference: int
:rtype: int
"""
mp = {}
ans = 1
for i in arr:
tmp = max(mp.get(i-difference,0)+1,mp.get(i,0))
mp[i] = tmp
ans = max(ans,tmp)
return ans
1219. 黄金矿工
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
为了使收益最大化，矿工需要按以下规则来开采黄金：
每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为
0的单元格。-
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
范围比较小，可以考虑进行深度优先搜索，从每一个格子出发的最终答案就是经过的路径，通过确定路径和更新答案。
class Solution(object): def getMaximumGold(self, grid): """ :type grid: List[List[int]] :rtype: int """ m = len(grid) n = len(grid[0]) ans = 0 def check(x,y): if x>=0 and x<m and y>=0 and y<n and grid[x][y]: return True def dfs(x,y): if check(x,y): tmp = grid[x][y] grid[x][y] = 0 ans = 0 if check(x-1,y): ans = max(ans,dfs(x-1,y)) if check(x+1,y): ans = max(ans,dfs(x+1,y)) if check(x,y-1): ans = max(ans,dfs(x,y-1)) if check(x,y+1): ans = max(ans,dfs(x,y+1)) grid[x][y] = tmp return tmp + ans else: return 0 for i in range(m): for j in range(n): ans = max(ans,dfs(i,j)) return ans
1220. 统计元音字母序列的数目
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
- 字符串中的每个字符都应当是小写元音字母（
'a','e','i','o','u'） - 每个元音
'a'后面都只能跟着'e' - 每个元音
'e'后面只能跟着'a'或者是'i' - 每个元音
'i'后面 不能 再跟着另一个'i' - 每个元音
'o'后面只能跟着'i'或者是'u' - 每个元音
'u'后面只能跟着'a'
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
提示：
-
1 <= n <= 2 * 10^4因为递推关系明确，我们可以初始化n=1，以某一元音结尾时的状态，递推出n+1时以某一元音结尾的状态。 当然也可以初始化好2 * 10^4的答案，通过访问答案数组直接返回结果
class Solution(object): def countVowelPermutation(self, n): """ :type n: int :rtype: int """ dp = [ {'a':0,'e':0,'i':0,'o':0,'u':0} for i in range(n) ] dp[0] = {'a':1,'e':1,'i':1,'o':1,'u':1} mod = 10**9+7 for i in range(n-1): # 每个元音 'a' 后面都只能跟着 'e' dp[i+1]['e'] += dp[i]['a'] # 每个元音 'e' 后面只能跟着 'a' 或者是 'i' dp[i+1]['a'] += dp[i]['e'] dp[i+1]['i'] += dp[i]['e'] # 每个元音 'i' 后面 不能 再跟着另一个 'i' dp[i+1]['a'] += dp[i]['i'] dp[i+1]['e'] += dp[i]['i'] dp[i+1]['o'] += dp[i]['i'] dp[i+1]['u'] += dp[i]['i'] # 每个元音 'o' 后面只能跟着 'i' 或者是 'u' dp[i+1]['i'] += dp[i]['o'] dp[i+1]['u'] += dp[i]['o'] # 每个元音 'u' 后面只能跟着 'a' dp[i+1]['a'] += dp[i]['u'] for j in dp[0].keys(): dp[i+1][j] = dp[i+1][j] % mod ans = 0 for i,j in dp[n-1].items(): ans = (ans+j)%mod return ans
