Leetcode-Easy 942. DI String Match
Leetcode-Easy 942. DI String Match
致Great
发布于 2019-03-06 11:25:31
发布于 2019-03-06 11:25:31
题目描述
给定仅包含“I”（增加）或“D”（减少）的字符串S，令N = S.length。
返回[0,1，...，N]的任何排列A，使得对于所有i = 0，...，N-1：
- 如果S [i] ==“I”，那么A [i] <A [i + 1]
- 如果S [i] ==“D”，那么A [i]> A [i + 1]
Example 1:
Input: "IDID"
Output: [0,4,1,3,2]Example 2:
Input: "III"
Output: [0,1,2,3]Example 3:
Input: "DDI"
Output: [3,2,0,1]思路
- 我们可以用的数字是一个整数数组[0,1,2,...,len(S)]
- 当看到“I”时，最安全的选择就是为下次移动设置最低（最左边）的数字，所以它总会增加
- 当看到“D”时，最安全的选择是为下次移动放置最高（最右边）的数字，所以它总会减少
- 最后放入当lo==hi的数字
代码实现
class Solution:
def diStringMatch(self, S: 'str') -> 'List[int]':
lo,hi=0,len(S)
ans=[]
for x in S:
if x=='I':
ans.append(lo)
lo+=1
if x=='D':
ans.append(hi)
hi-=1
return ans+[hi]
# return ans+[hi] 和上语句同样效果，此时lo==hi 思路来自：https://leetcode.com/problems/di-string-match/solution/
其实我们发现返回的结果不一定是唯一的，例如S='IDID'时，我们方法得出的结果是[0,4,1,3,2],但是像[1,4,0,3,2]，[0,4,2,3,1]也是符合题意的。这个思路可以理解是贪婪算法，然后我们每次求的都是最优解。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.02.18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录