[leetcode]第二十部分

125-Valid Palindrome

问题难度: ♣

问题描述

给定一个字符串, 判断其是一个回文,只考虑字母数字字符,忽略符号。

注意:在这个问题中,我们将空字符串定义为一个回文。

示例1

Input: "A man, a plan, a canal: Panama"
Output: true

示例2

Input: "race a car"
Output: false

解题思路

解法1: 递归法

针对当前字符串
– 如果字符串的长度小于等于1,那么直接返回true
– 取字符串的首尾分别为startend
– 如果start为空格或者符号,那么s=s[1:],递归调用
– 如果end为空格或者符号,那么s=[:-1],递归调用
– 否则,返回s[0] == s[-1]并且s=[1:-1],递归调用

然后,这个方法超过内存限制了…分析下原因,应该是在字符串长度很长的时候,递归会占用太多内存.

解法2:遍历法

使用两个指针(ij),分别指向字符串的前后,当i<j时:
– 当i<j and not s[i].isalnum时, i+=1
– 当i<j and not s[j].isalnum时, j-=1
– 如果s[i] == s[j], i+=1, j-= 1
– 否则,直接返回false

最后直接返回true

这个方法的时间复杂度为O(n),空间复杂都为O(1)

代码

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        i, j = 0, len(s)-1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

126-Word Ladder II

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定两个单词 (beginWordendWord), 以及一个词典的单词列表,找到从beginWordendWord的所有最短转换序列,使得:

  • 一次只能修改一个字符
  • 每次转化后的单词必须存在于单词列表中。 注意:beginWord不属于转换后的词

注意:

  • 如果没有这样的转换序列,返回一个空列表
  • 所有单词有相同的长度
  • 所有单词只包含小写的数字字母字符
  • 可以假设在单词列表中没有重复
  • 可以假设beginWordendWord都非空,并且不相同

示例1

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

示例2

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

解释: endWord "cog" 不在单词列表中, 因此没有可能的转换序列。

解题思路

这一题其实是下面127题的进阶版.(自己没做出来,查阅了网上的各种资料,发现很多人都在说这道题目是leetcode上通过率最低的题目之一).

127题相比,需要注意几点:

  • 新增一个前驱单词字典(pre_dict)来存储单词的前驱, key为当前层的单词,value为单词的前驱
  • 使用两个set()来模拟队列,candidate[previous]存储上一层的单词. 程序执行的过程中,先将上一层单词candidate[previous]从候选的wordList中删除,再将candidate[current]清空,然后根据candidate[previous]的单词寻找下一层的单词,并将其存入candidate[current]中,同时,将该单词存入pre_dict中,下一次循环开始时,candidate[current]变成了candidate[previous],而上一次循环的candidate[previous]变成了candidate[current]并清空.循环执行,当某一次循环中的candidate[current]中出现了end单词时,说明已找到路径.
  • 使用一个子函数buildPath来重建每一条路径

代码

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        pre_dict = {}
        word_set = set(wordList)
        for word in word_set:
            pre_dict[word] = []
        res = []
        def buildPath(path, word):
            if word == beginWord or len(pre_dict[word]) == 0:
                path.append(word)
                cur_path = []
                for i in range(len(path)-1, -1, -1):
                    cur_path.append(path[i])
                res.append(cur_path)
                path.pop()
                return
            path.append(word)
            for tmp in pre_dict[word]:
                buildPath(path, tmp)
            path.pop()
        candidate = [set(), set()]
        word_len = len(beginWord)
        current, previous = 0, 1
        candidate[current].add(beginWord)
        while True:
            current, previous = previous, current
            for word in candidate[previous]:
                word_set.discard(word)
            candidate[current].clear()
            for word in candidate[previous]:
                for i in range(word_len):
                    left = word[:i]
                    right = word[i+1:]
                    for char in "abcdefghijklmnopqrstuvwxyz":
                        if word[i] != char:
                            next_word = left + char + right
                            if next_word in word_set:
                                pre_dict[next_word].append(word)
                                candidate[current].add(next_word)
            if len(candidate[current]) == 0:
                return res
            if endWord in candidate[current]:
                break
        buildPath([], endWord)
        return res

127- Word Ladder

问题难度: ♣ ♣ ♣

问题描述

给定两个单词 (beginWordendWord), 以及一个词典的单词列表,返回从beginWordendWord的所有最短转换序列长度,使得:

  • 一次只能修改一个字符
  • 每次转化后的单词必须存在于单词列表中。 注意:beginWord不属于转换后的词

注意:

  • 如果没有这样的转换序列,返回一个空列表
  • 所有单词有相同的长度
  • 所有单词只包含小写的数字字母字符
  • 可以假设在单词列表中没有重复
  • 可以假设beginWordendWord都非空,并且不相同

示例1

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

解释: 由于最短的转换之一为: "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回序列的长度为5.

示例2

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

解释: endWord "cog" 不在单词列表中, 因此没有可能的转换序列。

解题思路

这道题目考察了最短路径的长度,可以考虑使用广度优先(BFS)的方法进行求解.广度优先算法是一个很经典的算法,BFS是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则演算终止。广度优先搜索的实现一般采用open-closed表。

这个题目中BFS需要注意的点在于:
– 和当前词相邻的单词是:对于当前单词改变一个字母并且在字典中存在的单词
– 找到一个单词的相邻单词,加入BFS队列后,要从字典中删除,因为不删除会造成死循环,而删除对求最短路径没有影响,因为我们第一次找到该单词肯定是最短路径,即使后面其他单词也可能转化得到它,路径肯定不会比当前路径短
BFS队列中用None来标识层与层之间的间隔,每次碰到层的结尾,遍历深度加1

但是…超时了.o(╯□╰)o

查了下资料,发现主要耗时是在判断单词是否在list中时,所以务必要把list先转化为dict,提高运行效率…

代码

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        queue = list()
        queue.append(beginWord)
        queue.append(None)
        distance = 1
        wordDict = dict()
        for word in wordList:
            wordDict[word] = 1
        char_list = [chr(x) for x in range(ord('a'), ord('z') + 1)]
        while len(queue) > 0:
            startWord = queue[0]
            queue = queue[1:]
            if startWord is not None:
                wordLen = len(startWord)
                startWordArr = list(startWord)
                for i in range(wordLen):
                    tmp = startWord[i]
                    for char in char_list:
                        if char == tmp:
                            continue
                        startWordArr[i] = str(char)
                        tmpStartWord = "".join(startWordArr)
                        if tmpStartWord in wordDict:
                            if tmpStartWord == endWord:
                                return distance + 1
                            queue.append(tmpStartWord)
                            del wordDict[tmpStartWord]
                    startWordArr[i] = tmp
            elif len(queue) > 0:
                distance += 1
                queue.append(None)
        return 0

128- Longest Consecutive Sequence

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定一个未排序的整数数组, 找到最长连续元素序列的长度.算法复杂度应该小于O(n)的复杂度.

示例

Input: [100, 4, 200, 1, 3, 2]
Output: 4
解释: 最长的连续元素序列为: [1, 2, 3, 4]. 因此其长度为: 4.

解题思路

使用一个hashmap存储到每个数字的最大连续长度,第一遍遍历数组,将hashmap中的值设置为0。第二次遍历数组,判断其减1是否在hashmap中,如果不存在,则直接将当前值设置为1;如果在,并且不为0,则将当前值设置为该值+1,判断长度是否大于max_seq,如果大于,则max_seq设置为该长度;如果存在并且为0,那么将其置为1,并且继续向前遍历。

代码

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_dict = {}
        max_seq = 0
        for num in nums:
            num_dict[num] = 0
        for num in nums:
            if num_dict[num] == 0:
                # unreached num
                pre_num = num - 1
                seq = 1
                if pre_num in num_dict:
                    if num_dict[pre_num] > 0:
                        seq += num_dict[pre_num]
                    else:
                        while pre_num in num_dict:
                            if num_dict[pre_num] > 0:
                                seq += num_dict[pre_num]
                                break
                            seq += 1
                            num_dict[pre_num] = 1
                            pre_num -= 1
                num_dict[num] = seq
                if seq > max_seq:
                    max_seq = seq
        return max_seq

129. Sum Root to Leaf Numbers

问题难度: ♣ ♣ ♣

问题描述

给的那个一个只包含数字0-9的二叉树,每个从根到叶子的路径都可以表示一个数字。

举个例子,根到叶子的路径1->2->3可以表示数字123

返回所有根到叶子路径的总和。

注意:叶子节点为没有孩子的节点。

示例1

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
解释:
根到叶子路径 1->2 表示数字 12.
根到叶子路径 1->3 表示数字 13.
因此, sum = 12 + 13 = 25.

示例2

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
解释:
根到叶子路径 4->9->5 表示数字 495.
根到叶子路径 4->9->1 表示数字 491.
根到叶子路径 4->0 表示数字 40.
因此, sum = 495 + 491 + 40 = 1026.

解题思路

深度优先的遍历方法,使用一个栈的数据结构来存储节点,从根节点开始,cur_node=root queue.append(cur_node)

  • cur_node = queue[-1], 如果cur_nodeNone,表示上一个节点的右边节点已经被遍历过了,直接queue.pop, queue.pop
  • 如果cur_node.left不是None,那么直接将queue.append(cur_node)
  • 如果cur_node.rightNone,那么说明已经到了叶子节点,遍历queue获得对应的数值并叠加;queue.pop, cur_node=queue[-1]
    • 如果cur_node.right不是 None,那么queue.append(None), queue.append(cur_node.right)
    • 否则queue.pop, cur_node=queue[-1],循环
  • 如果cur_node.right不是Nonequeue.append(None), queue.append(cur_node.right)

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        num = 0
        queue = []
        queue.append(root)
        def getNum():
            res = 0
            for i in range(len(queue)):
                if queue[i] is not None:
                    res = res * 10 + queue[i].val
            return res
        while len(queue) > 0:
            cur_node = queue[-1]
            if cur_node is None:
                queue.pop()
                queue.pop()
            elif cur_node.left is not None:
                queue.append(cur_node.left)
            else:
                if cur_node.right is None:
                    num += getNum()
                    queue.pop()
                    while len(queue) > 0:
                        cur_node = queue[-1]
                        if cur_node is None:
                            queue.pop()
                            queue.pop()
                        elif cur_node.right is not None:
                            queue.append(None)
                            queue.append(cur_node.right)
                            break
                        else:
                            queue.pop()
                else:
                    queue.append(None)
                    queue.append(cur_node.right)
        return num

130-Surrounded Regions

问题难度: ♣ ♣ ♣

问题描述

给定一个包含XO字母O)的二维面板,获取所有X包围的区域。

一个区域通过从在被包围的区域中的所有O设置为X来获得。

示例

X X X X
X O O X
X X O X
X O X X

在运行代码之后,面板应该变成:

X X X X
X X X X
X X X X
X O X X

解释:

被包围的区域不应该在边界,这就意味着面板边缘的所有O均不会被覆盖为X。不在边缘并且没有连接到任何边缘的00将会被覆盖为X, 两个格子相邻的定义为: 它们水平或垂直相连。

解题思路

最基础的想法是:给所有O的位置都打上类的标识,然后给类打上是否为被包围的边界的标识。需要额外申请三个dictregionkey为下标,值为区域的IDsurroundedkey为区域ID,值为1,标识区域为被包围的区域,region_cellkey为区域ID,值为下标的列表。

第一次遍历board,i0mj0n:

  • 如果board[i][j] == 'O', 如果i>0 && board[i-1][j] == 'O', 那么region[(i,j)] = region[(i-1,j)], region_cell[region[(i-1,j)]].append((i,j)),如果j>0 && region[(i,j-1)] == 'O',那么将region_cell[region[(i,j-1)]]中的下标都更新为当前区域;否则如果j>0 && region[(i,j-1)] == 'O'region[(i,j)] = region[(i,j-1)], 否则: region[(i,j)] = cluster_id, cluster_id += 1, 并且根据情况更新surrounded的值

针对非surrounded的区域中保护的下标,更新其值为X

代码

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return
        m, n = len(board), len(board[0])
        regions, region_cells, surrended = {}, {}, {}
        cluster = 0
        def updateRegion(i, j, cluster_id):
            regions[(i, j)] = cluster_id
            if cluster_id not in region_cells:
                region_cells[cluster_id] = []
            region_cells[cluster_id].append((i,j))
        def checkBoard(i, j):
            if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                return True
            return False
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    if i > 0 and board[i-1][j] == "O":
                        cluster_id = regions[(i-1, j)]
                        if j > 0 and board[i][j-1] == "O":
                            pre_cluster_id = regions[(i,j-1)]
                            if pre_cluster_id != cluster_id:
                                cells =  region_cells[pre_cluster_id]
                                for (tmp_i,tmp_j) in cells:
                                    updateRegion(tmp_i, tmp_j, cluster_id)
                                del region_cells[pre_cluster_id]
                                if pre_cluster_id in surrended:
                                    surrended[cluster_id] = True
                                    del surrended[pre_cluster_id]
                    elif j > 0 and board[i][j-1] == "O":
                        cluster_id = regions[(i, j-1)]
                    else:
                        cluster_id = cluster
                        cluster += 1
                    updateRegion(i, j, cluster_id)
                    if checkBoard(i,j):
                        surrended[cluster_id] = True
        for cluster_id in region_cells:
            if cluster_id not in surrended:
                cells = region_cells[cluster_id]
                for (i,j) in cells:
                    board[i][j] = "X"

131-Palindrome Partitioning

问题难度: ♣ ♣ ♣

问题难度

给定一个字符串s, 对s进行分割使得每个子串部分都是回文。

返回s所有可能的回文分词。

示例

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

解题思路

由于需要判断所有可能的回文分词,因此需要使用到DFS(深度优先搜索)进行遍历,逐个判断子字符串是否为回文。

代码

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ans = []
        def isPalindrome(s):
            for i in range(len(s)):
                if s[i] != s[len(s)-i-1]:
                    return False
            return True
        def dfs(s, val_list):
            if 0 == len(s):
                ans.append(val_list)
            for i in range(1, len(s) + 1):
                if isPalindrome(s[:i]):
                    dfs(s[i:], val_list + [s[:i]])
        dfs(s, [])
        return ans
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注