leetcode

作者: 张思思_113d | 来源:发表于2020-05-21 19:57 被阅读0次

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

    相关文章

      网友评论

          本文标题:leetcode

          本文链接:https://www.haomeiwen.com/subject/jcwtahtx.html