雄安邯郸网站制作多少钱,wordpress5.21开启多站点,景德镇市城市建设规划网站,模板网站建设清单25 K个一组翻转数组
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。
k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。 思路#xff…25 K个一组翻转数组
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 思路先按k个分段标记段头段尾写一个翻转k个节点的链表的函数传回新的段头段尾完成到下一段的切换 class Solution(object):def reverseKGroup(self, head, k)::type head: ListNode:type k: int:rtype: ListNodeif head.nextNone or k1: 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: Nodeif 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: Nodeif 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: ListNodeif 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.valhead2.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.valhead2.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 n0: return Noneelif n1: 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(lastFalse)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 node236 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 三种情况p是q的最近公共祖先q是p的最近公共祖先p和q位于某个节点node的左右子树中node为p和q的最近公共祖先 即判断node是否为pnode是否为q然后切换到node.left/node.right class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:if rootp or rootq or rootNone: return rootleftself.lowestCommonAncestor(root.left,p,q)rightself.lowestCommonAncestor(root.right,p,q)if left and right:return rootif left and rightNone:return leftif right and leftNone:return right 124 二叉树的最大路径和
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。 含有当前节点的最大路径和leftrightnode.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.valleftright) # 当前节点的最大路径return max(node.valmax(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 (mn)) 。 不断以二分的方式剔除不可能为中位数的值 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]2dp[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]-10 and s[i-dp[i-1]-1](: # 需要下标i-dp[i-1]-1有效if i-dp[i-1]-20: # 需要下标i-dp[i-1]-2有效dp[i]dp[i-1]2dp[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:j1]的字符串的回文情况最长回文子串选择记录起始点和长度 状态转移当s[i]s[j]时且dp[i1][j-1]为回文子串时dp[i][j]也为回文子串 因为dp[i][j]状态依赖于dp[i1][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 ji: dp[i][j] True #i0/j0仍为False# 偶长度的回文串中心elif ji1: if s[i]s[j]: dp[i][j] True# 长度扩展else:if s[i]s[j] and dp[i1][j-1]: dp[i][j] Trueif dp[i][j]: # 更新起点和长度if j-i1maxlen:maxlen j-i1start ireturn s[start:startmaxlen]
