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'
出处：
https://edu.csdn.net/practice/23885007
代码：
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
进阶： 你可以使用一趟扫描完成反转吗？
出处：
https://edu.csdn.net/practice/23885008
代码：
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 中的所有单词 互不相同
出处：
https://edu.csdn.net/practice/23885009
代码：
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']]
