题号680(简单)
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
解题思路:
从字符串的两边向中间遍历判断
如果已经判断到中间位置则返回True
如果字符不相等:
去除最左的字符然后执行从字符串的两边向中间遍历判断,如果判断到中间位置则返回True,不相等则停止遍历
去除最右的字符然后执行从字符串的两边向中间遍历判断,如果判断到中间位置则返回True,不相等则停止遍历
返回False
class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if self.test(s) is True:
return True
else:
start,end = self.test(s)
if self.test(s[start:end]) is True:
return True
elif self.test(s[start+1:end+1]) is True:
return True
else:
return False
def test(self, s):
start = 0
end = len(s) - 1
while start<end and s[start] == s[end]:
start += 1
end -= 1
if start >= end:
return True
else:
return start,end
题号1238(中等)
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p,并且满足:
p[0] = start
p[i] 和 p[i+1] 的二进制表示形式只有一位不同
p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同
示例 1:
输入:n = 2, start = 3
输出:[3,2,0,1]
解释:这个排列的二进制表示是 (11,10,00,01),所有的相邻元素都有一位是不同的,另一个有效的排列是 [3,1,0,2]
示例 2:
输出:n = 3, start = 2
输出:[2,6,7,5,4,0,1,3]
解释:这个排列的二进制表示是 (010,110,111,101,100,000,001,011)
提示:
1 <= n <= 16
0 <= start < 2^n
解题思路:
根据题目描述联想到格雷码的生成,start条件则改变了格雷码的开始值。
第一步生成格雷码,使用二进制码生成格雷码,起始值设为0,下图为二进制转格雷码的过程
1238格雷码.jpg
第二步将上述列表,先找到start的位置s,然后得到列表[s : ]+列表[ : s],返回即可。
from typing import List
class Solution:
def getList(self, n):
if n == 1:
return [0, 1]
l = self.getList(n-1)
return l + [x + (1<<(n-1)) for x in reversed(l)]
def circularPermutation(self, n: int, start: int) -> List[int]:
data = self.getList(n)
pos = -1
for i in range(1<<n):
if start == data[i]:
pos = i
break
return data[pos:] + data[: pos]
网友评论