目录

1. 最大矩形  &＃x1f31f;&＃x1f31f;&＃x1f31f;

2. 反转链表 II  &＃x1f31f;&＃x1f31f;

3. 单词接龙 II  &＃x1f31f;&＃x1f31f;&＃x1f31f;

&＃x1f31f; 每日一练刷题专栏 &＃x1f31f;

Golang每日一练 专栏

Python每日一练 专栏

C/C&＃43;&＃43;每日一练 专栏

Java每日一练 专栏

1. 最大矩形

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

示例 1&＃xff1a;

输入&＃xff1a;matrix &＃61; [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出&＃xff1a;6
解释&＃xff1a;最大矩形如上图所示。

示例 2&＃xff1a;

输入&＃xff1a;matrix &＃61; []
输出&＃xff1a;0

示例 3&＃xff1a;

输入&＃xff1a;matrix &＃61; [["0"]]
输出&＃xff1a;0

示例 4&＃xff1a;

输入&＃xff1a;matrix &＃61; [["1"]]
输出&＃xff1a;1

示例 5&＃xff1a;

输入&＃xff1a;matrix &＃61; [["0","0"]]
输出&＃xff1a;0

提示&＃xff1a;

• rows &＃61;&＃61; matrix.length
• cols &＃61;&＃61; matrix[0].length
• 0 <&＃61; row, cols <&＃61; 200
• matrix[i][j] 为 &＃39;0&＃39; 或 &＃39;1&＃39;

出处&＃xff1a;

https://edu.csdn.net/practice/23885007

代码&＃xff1a;

from typing import Listclass Solution(object):def maximalRectangle(self, matrix):""":type matrix: List[List[str]]:rtype: int"""if matrix is None or len(matrix) &＃61;&＃61; 0:return 0ls_row, ls_col &＃61; len(matrix), len(matrix[0])left, right, height &＃61; [0] * ls_col, [ls_col] * ls_col, [0] * ls_colmaxA &＃61; 0for i in range(ls_row):curr_left, curr_right &＃61; 0, ls_colfor j in range(ls_col):if matrix[i][j] &＃61;&＃61; &＃39;1&＃39;:height[j] &＃43;&＃61; 1else:height[j] &＃61; 0for j in range(ls_col):if matrix[i][j] &＃61;&＃61; &＃39;1&＃39;:left[j] &＃61; max(left[j], curr_left)else:left[j], curr_left &＃61; 0, j &＃43; 1for j in range(ls_col - 1, -1, -1):if matrix[i][j] &＃61;&＃61; &＃39;1&＃39;:right[j] &＃61; min(right[j], curr_right)else:right[j], curr_right &＃61; ls_col, jfor j in range(ls_col):maxA &＃61; max(maxA, (right[j] - left[j]) * height[j])return maxA# %%
s &＃61; Solution()
matrix &＃61; [["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 &＃61; []
print(s.maximalRectangle(matrix))
matrix &＃61; [["0"]]
print(s.maximalRectangle(matrix))
matrix &＃61; [["1"]]
print(s.maximalRectangle(matrix))
matrix &＃61; [["0","0"]]
print(s.maximalRectangle(matrix))


输出&＃xff1a;

6
0
0
1
0

---

2. 反转链表 II

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

示例 1&＃xff1a;

输入&＃xff1a;head &＃61; [1,2,3,4,5], left &＃61; 2, right &＃61; 4
输出&＃xff1a;[1,4,3,2,5]

示例 2&＃xff1a;

输入&＃xff1a;head &＃61; [5], left &＃61; 1, right &＃61; 1
输出&＃xff1a;[5]

提示&＃xff1a;

• 链表中节点数目为 n
• 1 <&＃61; n <&＃61; 500
• -500 <&＃61; Node.val <&＃61; 500
• 1 <&＃61; left <&＃61; right <&＃61; n

进阶&＃xff1a; 你可以使用一趟扫描完成反转吗&＃xff1f;

出处&＃xff1a;

https://edu.csdn.net/practice/23885008

代码&＃xff1a;

class ListNode(object):def __init__(self, x):self.val &＃61; xself.next &＃61; Noneclass LinkList:def __init__(self):self.head&＃61;Nonedef initList(self, data):self.head &＃61; ListNode(data[0])r&＃61;self.headp &＃61; self.headfor i in data[1:]:node &＃61; ListNode(i)p.next &＃61; nodep &＃61; p.nextreturn rdef convert_list(self,head):ret &＃61; []if head &＃61;&＃61; None:returnnode &＃61; headwhile node !&＃61; None:ret.append(node.val)node &＃61; node.nextreturn retclass Solution(object):def reverseBetween(self, head, m, n):""":type head: ListNode:type m: int:type n: int:rtype: ListNode"""if m &＃61;&＃61; n:return headsplit_node, prev, curr &＃61; None, None, headcount &＃61; 1while count <&＃61; m and curr is not None:if count &＃61;&＃61; m:split_node &＃61; prevprev &＃61; currcurr &＃61; curr.nextcount &＃43;&＃61; 1tail, next_node &＃61; prev, Nonewhile curr is not None and count <&＃61; n:next_temp &＃61; curr.nextcurr.next &＃61; prevprev &＃61; currcurr &＃61; next_tempcount &＃43;&＃61; 1if split_node is not None:split_node.next &＃61; previf tail is not None:tail.next &＃61; currif m &＃61;&＃61; 1:return prevreturn head# %%
l &＃61; LinkList()
list1 &＃61; [1,2,3,4,5]
l1 &＃61; l.initList(list1)
left &＃61; 2
right &＃61; 4
s &＃61; Solution()
print(l.convert_list(s.reverseBetween(l1, left, right)))


输出&＃xff1a;

[1, 4, 3, 2, 5]

---

3. 单词接龙 II

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

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si&＃xff08;1 <&＃61; i <&＃61; k&＃xff09;必须是字典 wordList 中的单词。注意&＃xff0c;beginWord 不必是字典 wordList 中的单词。
• sk &＃61;&＃61; endWord

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

示例 1&＃xff1a;

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

示例 2&＃xff1a;

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

提示&＃xff1a;

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

出处&＃xff1a;

https://edu.csdn.net/practice/23885009

代码&＃xff1a;

from typing import Listclass Solution:def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:import collectionsans &＃61; []steps &＃61; float("inf")if not beginWord or not endWord or not wordList or endWord not in wordList:return []word_dict &＃61; collections.defaultdict(list)L &＃61; len(beginWord)for word in wordList:for i in range(L):word_dict[word[:i] &＃43; "*" &＃43; word[i&＃43;1:]].append(word)queue &＃61; [[beginWord]]cost &＃61; {beginWord : 0}while queue:words_list&＃61; queue.pop(0)cur_word &＃61; words_list[-1]if cur_word &＃61;&＃61; endWord:ans.append(words_list[:])else:for i in range(L):intermediate_word &＃61; cur_word[:i] &＃43; "*" &＃43; cur_word[i&＃43;1:]for word in word_dict[intermediate_word]:w_l_temp &＃61; words_list[:]if word not in cost or cost[word] >&＃61; cost[cur_word] &＃43; 1:cost[word] &＃61; cost[cur_word] &＃43; 1w_l_temp.append(word)queue.append(w_l_temp[:])return ans# %%
s &＃61; Solution()
beginWord &＃61; "hit"
endWord &＃61; "cog"
wordList &＃61; ["hot","dot","dog","lot","log","cog"]
print(s.findLadders(beginWord, endWord, wordList))


输出&＃xff1a;

[[&＃39;hit&＃39;, &＃39;hot&＃39;, &＃39;dot&＃39;, &＃39;dog&＃39;, &＃39;cog&＃39;], [&＃39;hit&＃39;, &＃39;hot&＃39;, &＃39;lot&＃39;, &＃39;log&＃39;, &＃39;cog&＃39;]]

---

&＃x1f31f; 每日一练刷题专栏 &＃x1f31f;

✨ 持续&＃xff0c;努力奋斗做强刷题搬运工&＃xff01;

&＃x1f44d; 点赞&＃xff0c;你的认可是我坚持的动力&＃xff01; 

&＃x1f31f; 收藏&＃xff0c;你的青睐是我努力的方向&＃xff01; 

✎ 评论&＃xff0c;你的意见是我进步的财富&＃xff01;  

☸ 主页&＃xff1a;https://hannyang.blog.csdn.net/

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C&＃43;&＃43;每日一练 专栏
	Java每日一练 专栏