中级农民
- 积分
- 104
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-3-17
- 最后登录
- 1970-1-1
|
Day 17:
Q1. Valid Parenthesis String 【Medium】
题目理解：1）输入：字符串s，里面仅包含“（”、“）”、“*”
2）输出：bool结果，表示原字符串s中的左右括号可否相互抵消
3）规则：每个“*”可以作为“（”或者“）”使用，要求每个“（”都必须有相应的“）”匹配，且“（”必须出现在“）”之前。注意，当s为空字符串时也算满足条件，应返回True
解决方法：直接遍历计数。因为原字符串s中仅有3种字符，我们最终只关注是否所有“（”均可以被完全匹配，且“*”的定义有两种可能性，这里我们只需要记录所有需要匹配的“（”数量的上下限，其中下限表示必须匹配的“（”，也就是原字符串s中“（”的数量，而上限则为“（”+“*”的数量和，这个上线是为了防止任何substring中“）”出现在“（”之前。而且使用上下限只是为了限定能否满足要求，并没有对每个“*”进行一一赋值（因为题目只要求输出bool结果，并没有要求我们进行一一匹配）。在进行循环的过程中，我们需要每次都判断上限是否为负，且下限为负时及时清零。最终循环结束时，只需要判断下限是否为零即可。具体实现如下（python）：
class Solution(object):
def checkValidString(self, s):
Min = 0
Max = 0
n = len(s)
if n == 0:
return True
for i in range(0, n):
if s[i] == "(":
Min += 1
else:
Min -= 1
if s[i] != ")":
Max += 1
else:
Max -= 1
if Min < 0:
Min = 0
if Max < 0:
return False
if Min == 0:
return True
Q2. Knight Probability in Chessboard 【Medium】
题目理解：1）输入：整数N，整数K，整数r，整数c。其中N表示棋盘的尺寸为N*N，K表示需要行走的步数，r、c分别表示棋盘上的起始行、列（作为起始位置）
2）输出：概率值，表示从[r, c]开始行走K步后，knight依然在棋盘上的概率
3）knight行走规则：“日”字形前进，即每次在棋盘上沿1:2的方向行走
解决方法： 递推计数，利用了动态规划。根据题目描述，knight从每个位置开始都有8种行走方式，下面代码里面directions表示的就是knight的8种行走方向。我们从第1步开始分别记录走到棋盘上每一个格子[i, j]的行走方式有几种，每多一步走过的位置，不断累加结果，直到最后走完K步。当走完K步之后，将棋盘上每个位置上对应的值求和total，就是最后knight留在棋盘上的结果数量，而因为每一次knight都有8种走法，所以总共有T = 8^N种情况，最后返回total/T即可。 具体实现如下（python）：
class Solution(object):
def knightProbability(self, N, K, r, c):
directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1,-2]]
dp0 = [[0.0]*N for row in range(0, N)]
dp0[r][c] = 1.0
for k in range(0, K):
dp1 = [[0.0]*N for row in range(0, N)]
for i in range(0, N):
for j in range(0, N):
for d in range(0, 8):
x = i + directions[d][0]
y = j + directions[d][1]
if x<0 or y<0 or x>=N or y>=N:
continue
dp1[x][y] += dp0[i][j]
temp = dp0
dp0 = dp1
dp1 = temp
total = 0.0
for i in range(0, N):
for j in range(0, N):
total += dp0[i][j]
T = 8**K
return total/T
Q3. Combination Sum 【Medium】
题目理解：1）输入：list[int]，candidates和整数target，其中candidates中没有重复元素，但是每个元素可以重复使用
2）输出：list[list[int]]，表示candidates中所有和为target的整数列表
解决方法：dfs。首先对原数组进行排序，利用自定义函数dfs(self, candidates, target, s, curr, ans)来递归求解candidates中以s为起始位置的情况，curr用于记录当前操作的list，递归终止条件为target = 0。需要回溯。具体实现如下（python）：
class Solution(object):
def combinationSum(self, candidates, target):
candidates.sort()
curr = []
ans = []
self.dfs(candidates, target, 0, curr, ans)
return ans
def dfs(self, candidates, target, s, curr, ans):
if target == 0:
ans.append(curr[:])
return
n = len(candidates)
for i in range(s, n):
if candidates[i] > target:
break
curr.append(candidates[i])
self.dfs(candidates, target - candidates[i], i, curr, ans)
curr.pop()
【优化】对于输出的结果，我们可以按照每个list的长度进行排序输出，除了对之前结果按照长度排序之外，我们也可以在求解时直接进行一些操作，几乎为同样的实现方式，只不过在dfs中需要多加一些变量来记录递归深度。具体实现如下：
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
curr = []
ans = []
for i in range(1, target/candidates[0]+1):
self.dfs(candidates, target, 0, 0, i, curr, ans)
return ans
def dfs(self, candidates, target, s, d, e, curr, ans):
if d == e:
if target == 0:
ans.append(curr[:])
return
n = len(candidates)
for i in range(s, n):
if candidates[i] > target:
break
curr.append(candidates[i])
self.dfs(candidates, target - candidates[i], i, d+1, e, curr, ans)
curr.pop()
Q4. Merge Intervals【Medium】
题目理解：1）输入：一个Interval列表（intervals），这里Interval为题目设定的一种数据结构，包含起始位置，且为闭区间
2）输出：Interval列表，表示将原输入进行区间融合后的结果，要求输出的列表中的每个区间没有交集
解决方法：排序。将原数组按照start从小到大排序，之后逐个遍历更新即可。若一个interval的start小于前一个interval的end，则进行融合。原理和实现都比较简单，就不赘述了。具体实现如下：
class Solution(object):
def merge(self, intervals):
intervals.sort(key = lambda x: x.start)
ans = []
for interval in intervals:
if not ans or interval.start > ans[-1].end:
ans.append(interval)
else:
ans[-1] = Interval(ans[-1].start, max(interval.end, ans[-1].end))
return ans
Q5. Construct Binary Tree from Preorder and Postorder Traversal 【Medium】
题目理解：1）输入：两个list，分别为先序遍历pre和后续遍历post。其中pre和post中所有元素均不重复
2）输出：二叉树（root），使得其先序遍历和后续遍历和pre、post相对应。
解决方法： dfs。根据先序遍历和后续遍历的特点可以知道，对于所有子树，先序遍历的根节点在最前，相应的后续遍历根节点在最后。所以我们可以依据这个特点对原数组分段重组。自定义递归函数build(self, pre, post, i, j, n)，i为pre中的位置（根节点位置），j为post中的起始位置，n表示该子树的长度，对于整棵二叉树来讲，n = len（pre），每次递归调用时，需要分别分段定义左右子树的范围和长度。具体实现过程如下：
class Solution(object):
def constructFromPrePost(self, pre, post):
n = len(pre)
return self.build(pre, post, 0, 0, n)
def build(self, pre, post, i, j, n):
if n == 0:
return None
root = TreeNode(pre[i])
if n == 1:
return root
k = j
while pre[i+1] != post[k]:
k += 1
l = k - j + 1
root.left = self.build(pre, post, i+1, j, l)
root.right = self.build(pre, post, i+1+l, k+1, n-l-1)
return root |
|
楼主: Wangjingru_1995
狗仔卡
楼主
