本文主要是介绍【Leetcode】 top100 round2 直接开背版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
25 K个一组翻转数组
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
思路：先按k个分段，标记段头段尾，写一个翻转k个节点的链表的函数，传回新的段头段尾，完成到下一段的切换；
class Solution(object):def reverseKGroup(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""if head.next==None or k==1: return headp = ListNode(0) #创建一个虚拟的头结点# p.next = headold_head, left, right = p, head, headwhile right:for _ in range(k-1):right = right.nextif not right: return p.next old_tail = right.nextnew_head, new_tail = self.reverse(left, right)old_head.next = new_headnew_tail.next = old_tailold_head, left, right = new_tail, old_tail, old_tailreturn p.nextdef reverse(self, head, tail):pre, cur = head, head.nextwhile pre != tail:cur.next, cur, pre = pre, cur.next, cur #必须同步更新，不然更改指向后无法切换到下一结点（或者用一个新结点记录）return pre, head # 新头和新尾
138 随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。返回复制链表的头节点。你的代码 只 接受原链表的头节点 head 作为传入参数。
思路一：一次遍历节点，在当前节点后创建一个相同的节点，完成next指针的复制；
再次遍历节点，完成random指针的复制，复制节点（当前节点下一结点）的随机指针指向当前节点随机指针的下一结点（复制的随机节点），p.next.random = p.random.next；
最后遍历分离两链表；
class Solution(object):def copyRandomList(self, head):""":type head: Node:rtype: Node"""if not head:return Nonep = headwhile p: # 插入复制的新结点p.next = Node(p.val, p.next, None)p = p.next.nextp = headwhile p: # 设置random指针if p.random: p.next.random = p.random.nextp = p.next.nextp = headnew_head = Node(0)q = new_headwhile p: # 分离两链表q.next = p.nextq = q.nextp.next = q.next # 不直接用p.next.next是因为要恢复原链表p = p.nextreturn new_head.next思路二：一次遍历用hashmap存放{当前节点：复制节点}；
再次遍历复制next/random指针；
class Solution(object):def copyRandomList(self, head):""":type head: Node:rtype: Node"""if not head:return Nonehash = {}p = headwhile p:# hash[p] = Node(p.val, p.next, p.random) next和random需要下一轮指定，因为此时结点还未完全创建hash[p] = Node(p.val)p = p.nextp = headwhile p:if p.next: hash[p].next = hash[p.next]if p.random: hash[p].random = hash[p.random]p = p.nextreturn hash[head]
148 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
思路一：冒泡排序—偷懒的方法是直接改变节点的值
class Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""if head is None or head.next is None:return headhead0 = ListNode(0)head0.next = headtail = Nonewhile head0.next != tail:pre, cur, nxt = head0, head0.next, head0.next.nextwhile nxt != tail: # 一次冒泡将当前最大值移到末尾if cur.val > nxt.val:pre.next, cur.next, nxt.next = nxt, nxt.next, curpre, nxt = nxt, cur.nextelse:pre, cur, nxt = pre.next, cur.next, nxt.nexttail = curreturn head0.next# 只能通过25/30，一个巨长的案例会超出时间限制；思路二：归并排序—时间复杂度下降到O(nlogn)
class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:def merge(head1, head2):dummy = ListNode(0)p = dummywhile head1 and head2:if head1.val<head2.val:p.next = head1p, head1 = p.next, head1.nextelse:p.next = head2p, head2 = p.next, head2.nextif head1: p.next = head1elif head2: p.next = head2return dummy.nextdef mergeSort(head):if not (head and head.next): return headslow, fast = head, head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nextslow_head, fast_head = head, slow.nextslow.next = None # 断开连接return merge(mergeSort(slow_head), mergeSort(fast_head))return mergeSort(head)
23 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路一：两两合并直至成为一个链表—自底向上；
将链表二分，先完成左侧排序，再完成右侧排序，然后两侧合并—自顶向下；
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:def merge(head1, head2):dummy = ListNode(0)p = dummywhile head1 and head2:if head1.val<head2.val:p.next = head1p, head1 = p.next, head1.nextelse:p.next = head2p, head2 = p.next, head2.nextif head1: p.next = head1elif head2: p.next = head2return dummy.nextn = len(lists)if n==0: return Noneelif n==1: return lists[0]else:left = self.mergeKLists(lists[:n//2])right = self.mergeKLists(lists[n//2:])return merge(left, right)思路二：在比较k个链表未合并的节点值时可以利用堆排序来找到当前的最小值，而不是全部遍历；甚至于将全部节点入堆；
import heapq class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:# 需要设定节点比较，否则在堆化时会报错# 也可以只取node.val构造堆，然后根据pop出的值构造新节点即可,这种方法需要在初始化时将全部节点入堆setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)tmp = [head for head in lists if head] # 头结点入堆heapq.heapify(tmp)dummy = ListNode(0)p = dummywhile tmp:node = heapq.heappop(tmp)if node.next: heapq.heappush(tmp, node.next)p.next = nodep = p.nextreturn dummy.next# 全部节点入堆 import heapq class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:tmp = []for head in lists:while head:tmp.append(head.val)head = head.nextheapq.heapify(tmp)dummy = ListNode(0)p = dummywhile tmp:val = heapq.heappop(tmp)p.next = ListNode(val)p = p.nextreturn dummy.next
146 LRU缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
考察：双向链表+哈希 在python中可以使用OrderedDict( )
# 有序字典 class LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.lru = collections.OrderedDict()def get(self, key: int) -> int:if key in self.lru:self.lru.move_to_end(key)return self.lru[key]return -1def put(self, key: int, value: int) -> None:if self.get(key) == -1 and len(self.lru) == self.capacity:self.lru.popitem(last=False)self.lru[key] = value# 双向链表+哈希 class LRUCache:def __init__(self, capacity):self.cache = dict()self.head = DLinkedNode() # 使用伪头部和伪尾部节点 self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacityself.size = 0def get(self, key):if key not in self.cache: return -1node = self.cache[key] # 如果key存在，先通过哈希表定位，再移到头部self.moveToHead(node)return node.valuedef put(self, key, value):if key not in self.cache:node = DLinkedNode(key, value) # 如果key不存在，创建一个新的节点 self.cache[key] = node # 添加进哈希表self.addToHead(node) # 添加至双向链表的头部self.size += 1if self.size > self.capacity:removed = self.removeTail() # 如果超出容量，删除双向链表的尾部节点self.cache.pop(removed.key) # 删除哈希表中对应的项self.size -= 1else:node = self.cache[key] # 如果key存在，先通过哈希表定位，再修改value，并移到头部node.value = valueself.moveToHead(node)def addToHead(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):self.removeNode(node)self.addToHead(node)def removeTail(self):node = self.tail.prevself.removeNode(node)return node
236 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
三种情况：p是q的最近公共祖先；q是p的最近公共祖先；p和q位于某个节点node的左右子树中，node为p和q的最近公共祖先；
即判断node是否为p，node是否为q，然后切换到node.left/node.right；
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root==p or root==q or root==None: return rootleft=self.lowestCommonAncestor(root.left,p,q)right=self.lowestCommonAncestor(root.right,p,q)if left and right:return rootif left and right==None:return leftif right and left==None:return right
124 二叉树的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
含有当前节点的最大路径和=left+right+node.val
当前节点能给其父节点提供的最大路径和=max(left, right)+node.val 若该值为负则清零
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:global max_sum max_sum = float('-inf')def partPathSum(node):if node is None:return 0left = partPathSum(node.left) # 左侧最大路径right = partPathSum(node.right) # 右侧最大路径global max_summax_sum = max(max_sum, node.val+left+right) # 当前节点的最大路径return max(node.val+max(left, right), 0) # 单侧的最大路径（负数归零）partPathSum(root)return max_sum
208 实现前缀树
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
前缀树中一个父节点会对应多个子节点，且涉及到查找——hashmap
class TrieNode:def __init__(self):self.child = {}self.end = Falseclass Trie:def __init__(self):self.root = TrieNode() # 虚拟根节点def insert(self, word: str) -> None:node = self.rootfor strr in word:if strr not in node.child:node.child[strr] = TrieNode()node = node.child[strr]node.end = Truedef search(self, word: str) -> bool:node = self.rootfor strr in word:if strr not in node.child:return Falsenode = node.child[strr]return node.enddef startsWith(self, prefix: str) -> bool:node = self.rootfor strr in prefix:if strr not in node.child:return Falseelse:node = node.child[strr]return True
4 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
不断以二分的方式剔除不可能为中位数的值；
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def getKthElement(k):index1, index2 = 0, 0while True:# 特殊情况if index1 == m:return nums2[index2 + k - 1]if index2 == n:return nums1[index1 + k - 1]if k == 1:return min(nums1[index1], nums2[index2])# 正常情况newIndex1 = min(index1 + k // 2 - 1, m - 1) # 防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]if pivot1 <= pivot2:k -= newIndex1 - index1 + 1index1 = newIndex1 + 1else:k -= newIndex2 - index2 + 1index2 = newIndex2 + 1m, n = len(nums1), len(nums2)totalLength = m + nif totalLength % 2 == 1:return getKthElement((totalLength + 1) // 2)else:return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2.
84 柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)left, right = [-1]*n, [n]*nstack = []for i in range(n):while stack and heights[stack[-1]] >= heights[i]: # 找到val的左界stack.pop()if stack: left[i] = stack[-1]stack.append(i)print(left)stack = []for i in range(n-1, -1, -1): while stack and heights[stack[-1]] >= heights[i]: # 找到val的右界stack.pop()if stack: right[i] = stack[-1]stack.append(i)print(right)out = 0for i in range(n):ans = heights[i]*(right[i]-left[i]-1)out = max(ans, out)return out
堆 215/347/295
【Leetcode】top 100 堆-CSDN博客
32 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
方法一：动态规划：dp[i]代表长度为i的字符串的最长有效括号子串的长度
当s[i] = '('时，不考虑有效情况；
当s[i] = ')'时，若dp[i-1]=k且s[i-k-1]='('，dp[i]=dp[i-1]+2
如果此时能与dp[i-k-2]连接起来，dp[i]=dp[i-1]+2+dp[i-k-2]
class Solution:def longestValidParentheses(self, s: str) -> int:n = len(s)dp = [0]*nmaxlen = 0for i in range(n):if s[i] == '(': continueelse:if i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(': # 需要下标i-dp[i-1]-1有效if i-dp[i-1]-2>=0: # 需要下标i-dp[i-1]-2有效dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]else:dp[i] = dp[i-1]+2maxlen = max(maxlen, dp[i])return maxlen方法二：栈来判断匹配是否成功，开辟数组记录匹配成功的括号，最后统计连续的最长长度；
class Solution:def longestValidParentheses(self, s: str) -> int:stack, tmp = [], [0]*len(s)for i, strr in enumerate(s):if strr=='(': stack.append(i)else:if stack and s[stack[-1]]=='(':tmp[i], tmp[stack[-1]] = 1, 1stack.pop()length, maxlen = 0, 0for num in tmp:if num: length += numelse:maxlen = max(maxlen, length)length = 0maxlen = max(maxlen, length)return maxlen
5 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
方法一：直接模拟 一次遍历以当前字符为回文中心进行扩展，更新最长回文子串；
方法二：动态规划 区间dp
dp[i][j]代表s[i:j+1]的字符串的回文情况，最长回文子串选择记录起始点和长度
状态转移：当s[i]==s[j]时且dp[i+1][j-1]为回文子串时，dp[i][j]也为回文子串；
因为dp[i][j]状态依赖于dp[i+1][j-1]，所以需要从下往上/从左往右遍历来更新dp；
class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)dp = [[False]*n for _ in range(n)]start, maxlen = 0, 1for i in range (n-1,-1,-1):for j in range (i, n): # 注意j的范围# 奇长度的回文串中心if j==i: dp[i][j] = True #i=0/j=0仍为False# 偶长度的回文串中心elif j==i+1: if s[i]==s[j]: dp[i][j] = True# 长度扩展else:if s[i]==s[j] and dp[i+1][j-1]: dp[i][j] = Trueif dp[i][j]: # 更新起点和长度if j-i+1>maxlen:maxlen = j-i+1start = ireturn s[start:start+maxlen]
这篇关于【Leetcode】 top100 round2 直接开背版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
