如何编写网站建设销售的心得,网络营销专业可以干什么工作,自动建立wordpress,网站建设与管理是学什么目录 3. 无重复字符的最长子串206. 反转链表146. LRU 缓存215. 数组中的第K个最大元素25. K 个一组翻转链表15. 三数之和53. 最大子数组和21. 合并两个有序链表1. 两数之和5. 最长回文子串912. 排序数组 3. 无重复字符的最长子串 题目链接
class Solution:def lengthOfLongest… 目录 3. 无重复字符的最长子串206. 反转链表146. LRU 缓存215. 数组中的第K个最大元素25. K 个一组翻转链表15. 三数之和53. 最大子数组和21. 合并两个有序链表1. 两数之和5. 最长回文子串912. 排序数组 3. 无重复字符的最长子串 题目链接
class Solution:def lengthOfLongestSubstring(self, s: str) - int:stack[]max_cnt0for c in s:while c in stack:stack.pop(0)stack.append(c)if len(stack)max_cnt:max_cntlen(stack)return max_cnt206. 反转链表 题目链接
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:preNonecurheadwhile cur:tempcur.nextcur.nextpreprecurcurtempreturn pre146. LRU 缓存 题目链接
用到的数据结构哈希表双向链表 class ListNode:def __init__(self,keyNone,valueNone):self.keykeyself.valuevalueself.preNoneself.nextNoneclass LRUCache:def __init__(self, capacity: int):self.capacitycapacityself.hashmap{}self.headListNode()self.tailListNode()self.head.nextself.tailself.tail.preself.headdef move_to_tail(self,key):nodeself.hashmap[key]node.pre.nextnode.nextnode.next.prenode.prenode.nextself.tailnode.preself.tail.preself.tail.pre.nextnodeself.tail.prenodedef get(self, key: int) - int:if key in self.hashmap:self.move_to_tail(key)resself.hashmap.get(key,-1)if res-1:return reselse:return res.valuedef put(self, key: int, value: int) - None:if key in self.hashmap:self.hashmap[key].valuevalueself.move_to_tail(key)else:if len(self.hashmap)self.capacity:self.hashmap.pop(self.head.next.key)self.head.nextself.head.next.nextself.head.next.preself.headnewNodeListNode(key,value)self.hashmap[key]newNodenewNode.nextself.tailnewNode.preself.tail.preself.tail.pre.nextnewNodeself.tail.prenewNode# Your LRUCache object will be instantiated and called as such:
# obj LRUCache(capacity)
# param_1 obj.get(key)
# obj.put(key,value)注意 本题的数据结构哈希表双向链表self总是忘记写 215. 数组中的第K个最大元素 题目链接
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:return self.quickSelect(nums,k)def quickSelect(self,nums,k):pivotrandom.choice(nums)big,equal,small[],[],[]for num in nums:if num pivot:big.append(num)elif numpivot:small.append(num)else:equal.append(num)if klen(big):return self.quickSelect(big,k)elif klen(nums)-len(small):return self.quickSelect(small,k-len(nums)len(small))else:return pivot25. K 个一组翻转链表 题目链接
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverse(self,head):curheadpreNonewhile cur:tempcur.nextcur.nextpreprecurcurtempreturn predef reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:dummyListNode(nexthead)pre,enddummy,dummywhile end.next:for _ in range(k):if end:endend.nextif not end:breaktempend.nextend.nextNonestartpre.nextpre.nextself.reverse(start)start.nexttemppre,endstart,startreturn dummy.next15. 三数之和 题目链接
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()res[]nlen(nums)for i in range(n):if nums[i]0:return resif i0 and nums[i]nums[i-1]:continueLi1Rn-1while LR:if nums[i]nums[L]nums[R]0:res.append([nums[i],nums[L],nums[R]])while LR and nums[L]nums[L1]:L1while LR and nums[R]nums[R-1]:R-1L1R-1elif nums[i]nums[L]nums[R]0:R-1else:L1return res 53. 最大子数组和 题目链接
class Solution:def maxSubArray(self, nums: List[int]) - int:# dp[i]表示nums中下标从0到i的部分最大的子数组和nlen(nums)if n1:return nums[0]dp[0]*ndp[0]nums[0]for i in range(1,n):if dp[i-1]0:dp[i]dp[i-1]nums[i]else:dp[i]nums[i]return max(dp)21. 合并两个有序链表 题目链接
# 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]:if not list1:return list2if not list2:return list1if list1.vallist2.val:list1.nextself.mergeTwoLists(list1.next,list2)return list1else:list2.nextself.mergeTwoLists(list2.next,list1)return list21. 两数之和 题目链接
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:hashmap{}for i,num in enumerate(nums):if target-num in hashmap:return [i,hashmap[target-num]]hashmap[num]ireturn [] 5. 最长回文子串 题目链接
class Solution:def longestPalindrome(self, s: str) - str:nlen(s)dp [[False]*n for _ in range(n)]begin0max_len1for i in range(n-1,-1,-1):for j in range(i,n):if s[i]s[j] and (j-i2 or dp[i1][j-1]):dp[i][j]Trueif j-i1max_len:max_lenj-i1beginireturn s[begin:beginmax_len]
912. 排序数组 题目链接
快速排序
class Solution:def sortArray(self, nums: List[int]) - List[int]:self.quick(nums, 0, len(nums) - 1)return numsdef quick(self, nums, left, right):if left right:return nums# 选择一个随机的索引作为pivotpivot_index random.randint(left, right)# 将随机选择的pivot和最左侧的元素交换nums[left], nums[pivot_index] nums[pivot_index], nums[left]pivot nums[left]left0, right0 left, rightwhile left right:while left right and nums[right] pivot:right - 1while left right and nums[left] pivot:left 1nums[left], nums[right] nums[right], nums[left]# 恢复pivot到正确的位置nums[left0], nums[left] nums[left], nums[left0]self.quick(nums, left 1, right0)self.quick(nums, left0, left - 1)归并排序
class Solution:# 合并两个有序数组def merge(self,left,right):merged[]ij0while ilen(left) and jlen(right):if left[i]right[j]:merged.append(left[i])i1else:merged.append(right[j])j1while ilen(left):merged.append(left[i])i1while jlen(right):merged.append(right[j])j1return merged# 划分左右数组def sortArray(self, nums: List[int]) - List[int]:if len(nums)1:return numsmidlen(nums)//2leftself.sortArray(nums[:mid])rightself.sortArray(nums[mid:])return self.merge(left,right)堆排序
class Solution:def adjust(self,nums,parent,length):nums待排序数组parent父结点的索引length参与调整的数组长度结点个数childparent*21while childlength:if child1length and nums[child1]nums[child]:child1if nums[parent]nums[child]:nums[parent],nums[child]nums[child],nums[parent]parentchildchild2*parent1else:breakdef sortArray(self, nums: List[int]) - List[int]:# 建立堆结构for i in range(len(nums)//2-1,-1,-1):self.adjust(nums,i,len(nums))for i in range(len(nums)-1,0,-1):nums[0],nums[i]nums[i],nums[0]self.adjust(nums,0,i)return nums冒泡排序
def bubble_sort(lis):n len(lis)# 控制比较的轮数for j in range(n - 1):count 0# 控制每一轮的比较次数# -1是为了让数组不要越界# -j是每一轮结束之后, 我们就会少比一个数字for i in range(n - 1 - j):if lis[i] lis[i 1]:lis[i], lis[i 1] lis[i 1], lis[i]count 1# 算法优化# 如果遍历一遍发现没有数字交换退出循环说明数列是有序的if count 0:break总结 快速排序、堆排序、归并排序的时间复杂度都是 O(nlogn)快速排序、堆排序是不稳定的归并排序、冒泡排序是稳定的。
