Python每日一练(20230327)

发布人：shili8 发布时间：2023-03-27 19:08 阅读次数：41

1. 最大矩形??🌟🌟🌟

2. 反转链表 II??🌟🌟

3. 单词接龙 II??🌟🌟🌟

🌟 每日一练刷题专栏?🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 最大矩形

给定一个仅包含?0?和?1?、大小为?rows x cols?的二维二进制矩阵，找出只包含?1?的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j]?为?'0'?或?'1'

出处：

/caseinfo/link/4578e697fe7540a8885ac9df2c13ee22

代码：

from typing import List

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if matrix is None or len(matrix) == 0:
            return 0
        ls_row, ls_col = len(matrix), len(matrix[0])
        left, right, height = [0] * ls_col, [ls_col] * ls_col, [0] * ls_col
        maxA = 0
        for i in range(ls_row):
            curr_left, curr_right = 0, ls_col
            for j in range(ls_col):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0
            for j in range(ls_col):
                if matrix[i][j] == '1':
                    left[j] = max(left[j], curr_left)
                else:
                    left[j], curr_left = 0, j + 1
            for j in range(ls_col - 1, -1, -1):
                if matrix[i][j] == '1':
                    right[j] = min(right[j], curr_right)
                else:
                    right[j], curr_right = ls_col, j
            for j in range(ls_col):
                maxA = max(maxA, (right[j] - left[j]) * height[j])
        return maxA
    
# %%
s = Solution()
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
print(s.maximalRectangle(matrix))
matrix = []
print(s.maximalRectangle(matrix))
matrix = [["0"]]
print(s.maximalRectangle(matrix))
matrix = [["1"]]
print(s.maximalRectangle(matrix))
matrix = [["0","0"]]
print(s.maximalRectangle(matrix))

输出：

6
0
0
1
0

2. 反转链表 II

给你单链表的头指针?head?和两个整数?left?和?right?，其中?left <= right?。请你反转从位置?left?到位置?right?的链表节点，返回?反转后的链表?。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为?n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶：?你可以使用一趟扫描完成反转吗？

出处：

/caseinfo/link/1247aaafaa3d42afbf3d4207dd2934b8

代码：

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class LinkList:
    def __init__(self):
        self.head=None
    def initList(self, data):
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def convert_list(self,head):
        ret = []
        if head == None:
            return
        node = head
        while node != None:
            ret.append(node.val)
            node = node.next
        return ret

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if m == n:
            return head
        split_node, prev, curr = None, None, head
        count = 1
        while count <= m and curr is not None:
            if count == m:
                split_node = prev
            prev = curr
            curr = curr.next
            count += 1
        tail, next_node = prev, None
        while curr is not None and count <= n:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            count += 1
        if split_node is not None:
            split_node.next = prev
        if tail is not None:
            tail.next = curr
        if m == 1:
            return prev
        return head

# %%
l = LinkList()
list1 = [1,2,3,4,5]
l1 = l.initList(list1)
left = 2
right = 4
s = Solution()
print(l.convert_list(s.reverseBetween(l1, left, right)))

输出：

[1, 4, 3, 2, 5]

3. 单词接龙 II

按字典?wordList?完成从单词?beginWord?到单词?endWord?转化，一个表示此过程的?转换序列?是形式上像?beginWord -> s1 -> s2 -> ... -> sk?这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词?si（1 <= i <= k）必须是字典?wordList?中的单词。注意，beginWord?不必是字典?wordList?中的单词。
sk == endWord

给你两个单词?beginWord?和?endWord?，以及一个字典?wordList?。请你找出并返回所有从?beginWord?到?endWord?的?最短转换序列?，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表?[beginWord, s1, s2, ..., sk]?的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

1 <= beginWord.length <= 7
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord?和?wordList[i]?由小写英文字母组成
beginWord != endWord
wordList?中的所有单词?互不相同

出处：

/caseinfo/link/877f468ae1884bf4936362be737ed0c4

代码：

from typing import List

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        import collections
        ans = []
        steps = float("inf")
        if not beginWord or not endWord or not wordList or endWord not in wordList:
            return []
        word_dict = collections.defaultdict(list)
        L = len(beginWord)
        for word in wordList:
            for i in range(L):
                word_dict[word[:i] + "*" + word[i+1:]].append(word)
        queue = [[beginWord]]
        cost = {beginWord : 0}
        while queue:
            words_list= queue.pop(0)
            cur_word = words_list[-1]
            if cur_word == endWord:
                ans.append(words_list[:])
            else:
                for i in range(L):
                    intermediate_word = cur_word[:i] + "*" + cur_word[i+1:]
                    for word in word_dict[intermediate_word]:
                        w_l_temp = words_list[:]
                        if word not in cost or cost[word] >= cost[cur_word] + 1:
                            cost[word] = cost[cur_word] + 1
                            w_l_temp.append(word)
                            queue.append(w_l_temp[:])
        return ans

# %%
s = Solution()
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print(s.findLadders(beginWord, endWord, wordList))

输出：

[['hit', 'hot', 'dot', 'dog', 'cog'], ['hit', 'hot', 'lot', 'log', 'cog']]