1.玩筹码
题目描述：数轴上放了一些筹码，每个筹码的位置存放在数组chips中，现在需要将所有筹码移动到同一位置。将筹码左右移动2个单位的代价为0，将筹码左右移动1个单位的代价为1，求最小代价。
思路：观察左右移动代价可知，如由一个奇数位置移动到另一个奇数位置的代价为0，由一个奇数位置移动到一个偶数位置的最小代价为1。因而，统计奇偶数个数，其中较小者即为所求代价。
代码:
class Solution:
def minCostToMoveChips(self, chips: List[int]) -> int:
odd = even = 0
for n in chips:
if n % 2 == 0:
even += 1
else:
odd += 1
return min(odd, even)
2.最长定差子序列
题目描述：给定整数数组arr和整数difference，数组中相邻元素差值为difference的子序列称谓定差子序列，求定差子序列的最大长度。
思路：遍历数组，假定遍历到整数a，那么以整数a为末尾的定差子序列的长度等于以(a-difference)为末尾的定差子序列长度加一。
代码：
from collections import defaultdict
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
d = defaultdict(int)
for n in arr:
d[n] = d[n - difference] + 1
return max(d.values())
3.黄金矿工
题目描述：给定m*n的网格grid，网格中的数字表示该单元格中黄金的数量，0表示该单元格为空。矿工移动规则：矿工可以从当前位置往上下左右四个位置走，但不能进入开采过的或者空的单元格；矿工可以从任意一个有黄金的单元格开始。
思路：典型的dfs题目。
代码：
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
self.grid = grid
self.m, self.n = len(grid), len(grid[0])
self.dx = [-1, 1, 0, 0]
self.dy = [0, 0, -1, 1]
self.res = -1
for i in range(self.m):
for j in range(self.n):
if grid[i][j] != 0:
t = self.grid[i][j]
self.grid[i][j] = 0
self.dfs(i, j, t)
self.grid[i][j] = t
return self.res
def dfs(self, x, y, current):
self.res = max(self.res, current)
for i in range(4):
x_n, y_n = x+self.dx[i], y + self.dy[i]
if 0 <= x_n < self.m and 0 <= y_n < self.n and self.grid[x_n][y_n] != 0:
t = self.grid[x_n][y_n]
self.grid[x_n][y_n] = 0
self.dfs(x_n, y_n, current + t)
self.grid[x_n][y_n] = t
4.统计元音字母序列的个数
题目描述：给定整数n，统计长度为n的、满足规则的小写元音字母序列。规则：a后只能接e；e 后面只能接a 或者i；i不能接i；o 后面只能接i 或者u；u后只能接a
思路：1.采用dfs的思路，根据规则去构造字符串。这种方法理论上是可行的，但是超过了最大递归深度；2.采用动态规划的思想，逆规则去做。例如可以接a的有e、i、u，那么长度为i且末尾为a的序列只能由长度为i-1且末尾为e、i、u的序列得到。
代码：
class Solution:
def countVowelPermutation(self, n: int) -> int:
#初始值
d = [1] * 5
for i in range(1, n):
n_d = [0] * 5
#可以接 'a' 的
n_d[0] = d[1] + d[2] + d[4]
#可以接 'e' 的
n_d[1] = d[0] + d[2]
#可以接 'i' 的
n_d[2] = d[1] + d[3]
#可以接 'o' 的
n_d[3] = d[2]
#可以接 'u' 的
n_d[4] = d[2] + d[3]
d = n_d
return sum(d) % (10**9+7)