leetcode

题号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]