毕业网站设计代做,河南住房与城乡建设部网站,网站数据统计怎么做,微信小程序商城怎么开通文章目录 5 普通数组5.1 【动态规划】最大子数组和5.2 【排序】合并区间5.3 【数组】轮转数组5.4 【前缀和】除自身以外数组的乘积5.5 【哈希表】缺失的第一个正数 6 矩阵6.1 【哈希表】矩阵置零6.2 【模拟】螺旋矩阵6.3 【模拟】旋转图像6.4 【分治】搜索二维矩阵 II 7 链表7.… 文章目录 5 普通数组5.1 【动态规划】最大子数组和5.2 【排序】合并区间5.3 【数组】轮转数组5.4 【前缀和】除自身以外数组的乘积5.5 【哈希表】缺失的第一个正数 6 矩阵6.1 【哈希表】矩阵置零6.2 【模拟】螺旋矩阵6.3 【模拟】旋转图像6.4 【分治】搜索二维矩阵 II 7 链表7.1 【双指针】相交链表7.2 【链表】反转链表7.3 【双指针】【递归】回文链表7.4 【双指针】环形链表7.5 【双指针】环形链表 II7.6 【链表】合并两个有序链表7.7 【链表】两数相加7.8 【双指针】删除链表的倒数第 N 个结点7.9 【递归】两两交换链表中的节点7.10 【链表】K 个一组翻转链表7.11 【哈希表】随机链表的复制7.12 【排序】排序链表7.13 【分治】合并 K 个升序链表7.14 【哈希表】LRU 缓存 5 普通数组
5.1 【动态规划】最大子数组和
题目链接https://leetcode.cn/problems/maximum-subarray/description/?envTypestudy-plan-v2envIdtop-100-liked
利用动态规划首先定义数组 d p [ i ] dp[i] dp[i]表示终点的下标为 i i i的序列的最大子数和那么主要取决于以下两种情况 如果 d p [ i − 1 ] dp[i-1] dp[i−1]大于0则加上当前的数字作为 d p [ i ] dp[i] dp[i]的子数和 如果 d p [ i − 1 ] dp[i-1] dp[i−1]小于0则停止计算子数和从第 i i i个开始重新计算赋值为0并加上当前的数字作为 d p [ i ] dp[i] dp[i]的子数和
最后的最大子数组和就是这个数组中最大的那个
class Solution:def maxSubArray(self, nums: List[int]) - int:ans -10001cur 0for n in nums:cur nans max(cur,ans)if cur 0:cur 0return ans5.2 【排序】合并区间
题目链接https://leetcode.cn/problems/merge-intervals/description/?envTypestudy-plan-v2envIdtop-100-liked
首先对区间进行排序然后遍历并合并重叠区间最终返回合并后的非重叠区间列表。
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort()l,r intervals[0][0],intervals[0][1]ans []for i in range(1,len(intervals)):if intervals[i][0] r:r max(intervals[i][1],r)else:ans.append([l,r])l,r intervals[i][0],intervals[i][1]if [l,r] not in ans:ans.append([l,r])return ans5.3 【数组】轮转数组
题目链接https://leetcode.cn/problems/rotate-array/description/?envTypestudy-plan-v2envIdtop-100-liked
翻转整个数组。翻转前 k 个元素将它们移到数组的开始。翻转剩余的元素将它们移到正确的位置。
class Solution:def rotate(self, nums: List[int], k: int) - None:def reverse(i,j):while i j:nums[i],nums[j] nums[j],nums[i]i 1j - 1l len(nums)if k! 0:k % lreverse(0,l-1)reverse(0,k-1)reverse(k,l-1)5.4 【前缀和】除自身以外数组的乘积
题目链接https://leetcode.cn/problems/product-of-array-except-self/description/?envTypestudy-plan-v2envIdtop-100-liked
分别计算索引左边的数字乘积和索引右边的数字乘积两者乘积结果即为该索引的乘积结果。
# 方法一
class Solution:def productExceptSelf(self, nums: List[int]) - List[int]:length len(nums)left_ans, right_ans, answer [0]*length, [0]*length, [0]*lengthleft_ans[0] 1for i in range(1,length):left_ans[i] left_ans[i-1]*nums[i-1]right_ans[length-1] 1for i in range(length-2,-1,-1):right_ans[i] right_ans[i1]*nums[i1]for i in range(length):answer[i] left_ans[i]*right_ans[i]return answer
# 方法二——不需要额外空间
class Solution:def productExceptSelf(self, nums: List[int]) - List[int]:n len(nums)suf [1] * nfor i in range(n - 2, -1, -1):suf[i] suf[i 1] * nums[i 1]pre 1for i, x in enumerate(nums):suf[i] * prepre * xreturn suf5.5 【哈希表】缺失的第一个正数
题目链接https://leetcode.cn/problems/first-missing-positive/?envTypestudy-plan-v2envIdtop-100-liked
这个问题可以通过将数组中的每个数字放到它应该在的位置来解决即 nums[i] 应该放在 nums[i-1] 的位置相当于把原来的数组当作一个哈希表来使用具体步骤如下 初始化设置 max_len 为数组长度加1这是我们需要处理的最大正整数。 标记无效数字将所有非正数或大于 n 的数字设置为0。 放置数字 对于每个数字 nums[i]如果它在范围内1 到 max_len - 1则将其放到正确的位置 nums[nums[i] % max_len - 1]并加上数组的最大长度标记这个位置的数已经出现过了。 使用一个循环来重复这个过程直到所有在范围内的数字都被放到了正确的位置。 查找缺失的最小正整数 遍历数组如果 nums[i] 小于 max_len则 i1 就是缺失的最小正整数。 如果所有位置都填满了那么缺失的最小正整数就是 max_len。
class Solution:def firstMissingPositive(self, nums: List[int]) - int:n len(nums)max_len n1for i in range(n):if nums[i] 0 or nums[i] max_len:nums[i] 0for i in range(n):if nums[i] % max_len ! 0:cur (nums[i] % max_len) - 1nums[cur] (nums[cur] % max_len) max_lenfor i in range(n):if nums[i] max_len:return i1return max_len6 矩阵
6.1 【哈希表】矩阵置零
题目链接https://leetcode.cn/problems/set-matrix-zeroes/description/?envTypestudy-plan-v2envIdtop-100-liked
用第一行和第一列的元素来表示每一行或者每一列是否存在零。
class Solution:def setZeroes(self, matrix: List[List[int]]) - None:row len(matrix)col len(matrix[0])zero_first [False,False]# 第一行是否有零for i in range(col):if matrix[0][i] 0:zero_first[0] Truebreak# 第一列是否有零for i in range(row):if matrix[i][0] 0:zero_first[1] Truebreak# 记录其他行和列的零for i in range(1,row):for j in range(1,col):if matrix[i][j] 0:matrix[i][0] matrix[0][j] 0# 矩阵置零for i in range(1,row):for j in range(1,col):if matrix[i][0] 0 or matrix[0][j] 0:matrix[i][j] 0if zero_first[0] True:for i in range(col):matrix[0][i] 0if zero_first[1] True:for i in range(row):matrix[i][0] 06.2 【模拟】螺旋矩阵
题目链接https://leetcode.cn/problems/spiral-matrix/description/?envTypestudy-plan-v2envIdtop-100-liked
按照题目的意思从左往右从上往下从右往左从下往上依次遍历矩阵元素每次遍历完判断是否越界。
class Solution:def spiralOrder(self, matrix: List[List[int]]) - List[int]:l,r,t,b,res 0,len(matrix[0])-1,0,len(matrix)-1,[]while True:# left to rightfor i in range(l,r1):res.append(matrix[t][i])t 1if t b:break# top to bottomfor i in range(t,b1):res.append(matrix[i][r])r - 1if r l:break# right to leftfor i in range(r,l-1,-1):res.append(matrix[b][i])b - 1if b t:break# bottom to topfor i in range(b,t-1,-1):res.append(matrix[i][l])l 1if l r:breakreturn res6.3 【模拟】旋转图像
题目链接https://leetcode.cn/problems/rotate-image/description/?envTypestudy-plan-v2envIdtop-100-liked
主对角线翻转左右翻转。
class Solution:def rotate(self, matrix: List[List[int]]) - None:length len(matrix)# 主对角线for i in range(length):for j in range(i1,length):matrix[i][j],matrix[j][i] matrix[j][i],matrix[i][j]# 左右for i in range(length):for j in range(length//2):matrix[i][j],matrix[i][length-j-1] matrix[i][length-j-1],matrix[i][j]6.4 【分治】搜索二维矩阵 II
题目链接https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envTypestudy-plan-v2envIdtop-100-liked
从矩阵左下角开始遍历如果比当前的数小则索引上移如果比当前的数大则索引右移。
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:i,j len(matrix)-1,0while i 0 and j len(matrix[0]):if matrix[i][j] target:i - 1elif matrix[i][j] target:j 1else:return Truereturn False7 链表
7.1 【双指针】相交链表
题目链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envTypestudy-plan-v2envIdtop-100-liked
让A和B同时遍历A遍历完了换到B的开始B遍历完了换到A的开始两者相等时就是遇到了公共节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:A,B headA,headBwhile A ! B:A A.next if A else headBB B.next if B else headAreturn A7.2 【链表】反转链表
题目链接https://leetcode.cn/problems/reverse-linked-list/description/?envTypestudy-plan-v2envIdtop-100-liked
头插法。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:cur,pre head,Nonewhile cur:cur.next,pre,cur pre,cur,cur.nextreturn pre7.3 【双指针】【递归】回文链表
题目链接https://leetcode.cn/problems/palindrome-linked-list/description/?envTypestudy-plan-v2envIdtop-100-liked
首先找到链表的中间位置然后对链表的后半部分进行翻转最后比较翻转后的部分和前半部分是否一致。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def isPalindrome(self, head: Optional[ListNode]) - bool:if not head:return True# search for the median nodefast,slow head,headwhile fast.next and fast.next.next:fast fast.next.nextslow slow.next# reverse the right listnodecur,pre slow.next,Nonewhile cur:cur.next,pre,cur pre,cur,cur.next# comparewhile pre:if head.val ! pre.val:return Falsehead,pre head.next,pre.nextreturn True7.4 【双指针】环形链表
题目链接https://leetcode.cn/problems/linked-list-cycle/description/?envTypestudy-plan-v2envIdtop-100-liked
定义快慢指针快指针一次走两步慢指针一次走一步如果存在环则两个指针总会相遇否则不存在环。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) - bool:if not head:return Falsefast,slow head,headwhile fast.next and fast.next.next:fast fast.next.nextslow slow.nextif fast slow:return Truereturn False7.5 【双指针】环形链表 II
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/?envTypestudy-plan-v2envIdtop-100-liked
这道题在环形链表的基础上做了升级首先还是用双指针判断链表是否成环如果成环的话此时让head和slow同时移动最后相遇的时候就是环形开始的地方。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return Nonefast,slow head,headwhile fast and fast.next:fast fast.next.nextslow slow.nextif fast slow:while slow ! head:slow slow.nexthead head.nextreturn slowreturn None7.6 【链表】合并两个有序链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/description/?envTypestudy-plan-v2envIdtop-100-liked
常规做法挨个比较大小。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]:l1p,l2p list1,list2ans l ListNode()while l1p and l2p:if l1p.val l2p.val:l.next ListNode(l1p.val)l1p l1p.nextl l.nextelse:l.next ListNode(l2p.val)l2p l2p.nextl l.nextwhile l1p:l.next ListNode(l1p.val)l1p l1p.nextl l.nextwhile l2p:l.next ListNode(l2p.val)l2p l2p.nextl l.nextreturn ans.next7.7 【链表】两数相加
题目链接https://leetcode.cn/problems/add-two-numbers/description/?envTypestudy-plan-v2envIdtop-100-liked
挨个相加保留进位最后判断是否有多余的进位。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:ans l ListNode()sign 0while l1 or l2:l1_num l1.val if l1 else 0l2_num l2.val if l2 else 0num l1_num l2_num signl.next ListNode(num%10)sign num//10l l.nextif l1:l1 l1.nextif l2:l2 l2.nextif sign:l.next ListNode(sign)return ans.next7.8 【双指针】删除链表的倒数第 N 个结点
题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envTypestudy-plan-v2envIdtop-100-liked
利用双指针left和right首先让right遍历n个节点再让两个指针同时遍历当right遍历到链表结尾时left所指的就是倒数第n个节点正常删除即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:left right headcnt 0while cnt n:right right.nextcnt 1if not right:return head.nextwhile right.next:left left.nextright right.nextleft.next left.next.nextreturn head7.9 【递归】两两交换链表中的节点
题目链接https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envTypestudy-plan-v2envIdtop-100-liked
详见代码。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:node0 dummy ListNode(nexthead)node1 headwhile node1 and node1.next:node2 node1.nextnode3 node2.nextnode0.next node2node2.next node1node1.next node3node0 node1node1 node3return dummy.next7.10 【链表】K 个一组翻转链表
题目链接https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envTypestudy-plan-v2envIdtop-100-liked
详见代码。
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:n 0cur headwhile cur:n 1cur cur.nextp0 dummy ListNode(nexthead)pre Nonecur headwhile n k:n - kfor _ in range(k):nxt cur.nextcur.next prepre curcur nxtnxt p0.nextnxt.next curp0.next prep0 nxtreturn dummy.next7.11 【哈希表】随机链表的复制
题目链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envTypestudy-plan-v2envIdtop-100-liked
利用哈希表首先构建链表中的每个结点再根据哈希表中的结点分别构造next和random引用相当于对原始链表遍历两次。 # Definition for a Node.
class Node:def __init__(self, x: int, next: Node None, random: Node None):self.val int(x)self.next nextself.random random
class Solution:def copyRandomList(self, head: Optional[Node]) - Optional[Node]:dict {}cur headwhile cur:dict[cur] Node(cur.val)cur cur.nextcur headwhile cur:dict[cur].next dict.get(cur.next)dict[cur].random dict.get(cur.random)cur cur.nextif not head:return headelse:return dict[head]7.12 【排序】排序链表
题目链接https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2envIdtop-100-liked
首先找到链表的中间位置然后使用归并排序以此递归遍历链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headslow,fast head,head.nextwhile fast and fast.next:slow,fast slow.next,fast.next.nextmid slow.nextslow.next Noneleft,right self.sortList(head),self.sortList(mid)h ans ListNode()while left and right:if left.val right.val:h.next leftleft left.nextelse:h.next rightright right.nexth h.nexth.next left if left else rightreturn ans.next7.13 【分治】合并 K 个升序链表
题目链接https://leetcode.cn/problems/merge-k-sorted-lists/description/?envTypestudy-plan-v2envIdtop-100-liked
两两合并。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:def merge(l1,l2):cur tmp ListNode()while l1 and l2:if l1.val l2.val:tmp.next l1l1 l1.nextelse:tmp.next l2l2 l2.nexttmp tmp.nextif l1:tmp.next l1if l2:tmp.next l2return cur.nextans Nonefor i in lists:ans merge(ans,i)return ans7.14 【哈希表】LRU 缓存
题目链接https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked
详见代码通过构造双向链表和哈希表来模拟LRU缓存要注意及时将最久未使用的结点移动到链表末尾便于删除这里采取的措施是定义一个函数将链表中的某个结点移动到链表末尾在get和put方法中都会遇到这种情况。
class ListNode:# 双向链表构建def __init__(self, keyNone, valueNone):self.key keyself.value valueself.prev Noneself.next Noneclass LRUCache:def __init__(self, capacity: int):self.capacity capacityself.hashmap {}# 头结点head和尾结点tailself.head ListNode()self.tail ListNode()# 初始化双向链表self.head.next self.tailself.tail.prev self.head# 将链表中的某个结点移到链表末尾taildef move_to_tail(self, key):node self.hashmap[key]# 取出node结点node.next.prev node.prevnode.prev.next node.next# 移到末尾node.next self.tailnode.prev self.tail.prevself.tail.prev.next nodeself.tail.prev nodedef get(self, key: int) - int:if key in self.hashmap:self.move_to_tail(key)res self.hashmap.get(key)if res None:return -1else:return res.valuedef put(self, key: int, value: int) - None:if key in self.hashmap:self.hashmap[key].value valueself.move_to_tail(key)else:if len(self.hashmap) self.capacity:# 删除最久未访问结点self.hashmap.pop(self.head.next.key)self.head.next self.head.next.nextself.head.next.prev self.headnewNode ListNode(key, value)self.hashmap[key] newNodenewNode.prev self.tail.prevnewNode.next self.tailself.tail.prev.next newNodeself.tail.prev newNode# Your LRUCache object will be instantiated and called as such:
# obj LRUCache(capacity)
# param_1 obj.get(key)
# obj.put(key,value)
