-
Leetcode | 算法（二）
数据结构
数组
48. Rotate Image（旋转90°）
- Medium
这个应该是找规律，第一行的都变为最后一列，第二行变为倒数第二列，第i第j个变为倒数i行第j个，也就是A[i,j]->A[n-1-i,j]
注意只能在原矩阵上修改，所以我们可以考虑先走外面一层，也就是i=0或j=0，再继续走里面一圈
外面一层怎么修改呢？第一行出发，A[0,i]→A[i,n-1]→A[n-1,i]→A[i,0]→A[0,i]
i从0到n-1遍历结束，就是把周围一圈旋转了再接着里面。
第j行出发，第j行第i个-倒数第j列第i个->倒数第j行 第i列，第j列第i个
A[j,i]→A[i,n-1-j]→A[n-1-j,i]→A[i,j]→A[j,i]
240. Search a 2D Matrix II
行和列都是从小到大升序排序
- 自己：错误思路
从A[0][0]开始，遍历到A[i][j]，先直接右下移动，如果target更大的话，则继续右下移动。否则，说明target一定在右边的行或者右边的列中，查看右移和下移两个方向，分别找。
这里需要注意的一点是，如果只有一行或者一列，就不能右下移动了
这个思路有问题，因为对于matrix = [[1,3,5,7,9],[2,4,6,8,10],[11,13,15,17,19],[12,14,16,18,20],[21,22,23,24,25]],target = 11来说，11在第一列，这样搜索是找不到11的
- 正确解法：从右上角搜索
从右上角开始查找，如果若当前值小于待搜索值，我们可以排除掉这一整行，向下移动一位；
若当前值大于待搜索值，我们向左移动一位。如果最终移动到左下角时仍不等于待搜索值，则说明待搜索值不存在于矩阵中。
769. Max Chunks To Make Sorted
- Medium
- 错误思路：从0开始，找到最后一个比arr[0]小的点，这个就是断点，再从断点处，找到最后一个比断点小的数
遇到问题：[1,4,0,2,3,5]，正确切割应该为[1],[4,0,2,3,5]
但是我们的思路做出来的确实[1,4,0],[2],[3],[5]- 正确思路
左往右遍历，同时记录当前的最大值，每当当前最大值等于数组位置时，我们可以多一次
分割。为什么可以通过这个算法解决问题呢？例如[1,4,0,2,3,5]，遍历到值为4时，当前最大值为4，但数组位置为1，这说明右边有比4小的数字，因为数组是从0到n的元素，所以4得和比他小的一起排序才行，不然拼不起来。
如果当前最大值大于数组位置，则说明右边一定有小于数组位置的数字，需要把它也加入待排序的子数组；又因为数组只包含不重复的 0 到 n，所以当前最大值一定不会小于数组位置。
如果当前最大值等于数组位置时，假设为 p，我们可以成功完成一次分割，并且其与上一次分割位置 q 之间的值一定是 q + 1 到 p 的所有数字。然后重新算当前最大值，所以令mx=-1
class Solution { public: int maxChunksToSorted(vector<int>& arr) { int mx = -1, ans = 0, n = arr.size(); for (int i = 0; i < n; i++) { mx = max(mx, arr[i]); if (mx == i) { mx = -1; ans++; } } return ans; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 方法二：栈
[i:j]可以分块的条件：位置j之后的元素都比max(arr[i:j])要小，那么找到相应的i和j呢？
我们新建一个栈，存放不同块的最大值，即[i:j]中最大。
初始先把第一个元素压入栈，从左往右遍历数组，如果当前元素比栈中最后一个还小，说明他们俩应该是一伙的，但注意，有可能这个元素比栈倒数第二个还要小，这就得合并。比如在[1,2,3,0]中，从左向右遍历，[1,2,3]均为最大值，但是一遇到0之后不仅0需要并入3所在分块，就连1和2都要并入3所在分块，所以这里我们还需要有一步弹出操作。
如果当前元素小于当前栈顶元素，那么我们就需要将栈顶元素弹出，直到栈为空或者栈顶元素小于当前元素。之后我们还需要将分块的代表元素重新压入栈，也就是需要记录弹出元素中最大的那一个。
然后我们遍历到这个元素比栈最后一个元素大，说明没法在合伙了，这时候就把合并的这块的最大值放进去，最后返回栈的个数，就是块的个数。
class Solution: def maxChunksToSorted(self, arr: List[int]) -> int: n = len(arr) stack=[] for i in range(n): m = arr[i] while stack and stack[-1] > arr[i]: m = max(stack.pop(), m) stack.append(m) return len(stack)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
栈和队列
232. Implement Queue using Stacks （尝试使用栈（stack）来实现队列（queue））
需要构造一些函数实现队列的功能
我们可以用两个栈来实现一个队列：因为我们需要得到先入先出的结果，所以必定要通过一
个额外栈翻转一次数组。这个翻转过程既可以在插入时完成，也可以在取值时完成。class MyQueue: def __init__(self): """ in主要负责push，out主要负责pop """ self.stack_in = [] self.stack_out = [] def push(self, x: int) -> None: """ 有新元素进来，就往in里面push """ self.stack_in.append(x) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ if self.empty(): return None if self.stack_out: return self.stack_out.pop() else: for i in range(len(self.stack_in)): self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) -> int: """ Get the front element. """ ans = self.pop() self.stack_out.append(ans) return ans def empty(self) -> bool: """ 只要in或者out有元素，说明队列不为空 """ return not (self.stack_in or self.stack_out)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
没看懂…
20. Valid Parentheses（有效的括号）
给定一个只由左右原括号、花括号和方括号组成的字符串，求这个字符串是否合法。合法的
定义是每一个类型的左括号都有一个右括号一一对应，且括号内的字符串也满足此要求。Input: “{[]}()”
Output: true
- 自己思路：建立一个栈st把分别把s的元素压入其中，接着建立一个栈re，存放未匹配的符号
首先，看re是否为空，如果为空就输出st的最后一个元素加入进去，如果不为空，就看st.pop()是否和re中最后的元素匹配，如果匹配就删除re的最后一个元素，不匹配就加入re中去
一直到遍历完st,最后看re是否为空，不为空说明还有元素未匹配，则返回False
注意：
"(){}}{"，也就是说{}和}{是不一样的class Solution(object): def isValid(self, s): #dic = {'[':']', '(':')', '{':'}', ']':'[', ')':'(', '}':'{'} dic = {']':'[',')':'(', '}':'{'} st, re = [], [] for i in range(len(s)): st.append(s[i]) while len(st)>0: m = st.pop() if len(re)>0: # 注意}{的情况 if re[-1] not in dic.keys(): re.append(m) elif dic[re[-1]] == m: re.pop() else: re.append(m) else: re.append(m) return True if len(re)==0 else False- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 题解思路
括号匹配是典型的使用栈来解决的问题。我们从左往右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符串不合法。
739. Daily Temperatures（等待变暖温度时间）
给定每天的温度，求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在
更暖和的天气，则记为 0。- 解法：单调栈
我们可以维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位置（即日期）而非温度本身，这个栈叫做indices，输出的等待天数数组叫做ans
首先，indices放入第一个元素位置0（温度73），遍历到temperatures[1]=74，考察温度74比indices中对应位置的73大，所以indices.pop()，然后ans[0]=1-0=1（位置相减），此时栈为空就把位置1（温度74）压入。
i=2, temperatures[2]=75，考察温度75比indices中栈顶对应位置的74大，所以indices.pop()，然后ans[1]=2-1=1，此时栈为空就把位置2（温度75）压入。
i=3, temperatures[3]=71，考察温度71比indices栈顶对应位置的74小，就把位置3（温度71）压入。
i=4, temperatures[4]=69，考察温度69比indices中栈顶对应位置的71小，就把位置4（温度69）压入。
i=5, temperatures[2]=72，考察温度72比indices中栈顶对应位置的71大，所以indices.pop()，然后ans[4]=5-4=1，再考察温度72比indices中栈顶对应位置的69大，所以indices.pop()，然后ans[3]=5-3=2
…
以此类推class Solution(object): def dailyTemperatures(self, temperatures): indices = [] ans = [0 for _ in range(len(temperatures))] for i in range(len(temperatures)): if len(indices)==0: indices.append(i) else: # 栈顶元素比当前温度低,说明已经等到了上升温度 while len(indices)!=0 and temperatures[indices[-1]]<temperatures[i]: ans[indices[-1]] = i - indices[-1] indices.pop() indices.append(i) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
栈和队列（python）
在python中，列表既可以作为栈使用，又可以作为队列使用。
栈：后进先出
队列：先进先出- 栈
主要是用append和pop
stack=[1,2,3] stack.append(4) #入栈，以列表尾部为栈顶 print(stack.pop()) #出栈 4 print(stack) #[1, 2, 3]- 1
- 2
- 3
- 4
- 队列
需要从collections 导包
dequedeque 是双边队列，同时具有栈和队列的性质，可进行栈、队列相关的操作。并且还在在 list 的基础上增加了移动、旋转和增删等操作。
先入先出：
append和popleftfrom collections import deque #需要导入模块 list=[1,2,3] deque=deque(list) #将列表转换为deque deque.append(4) #添加到尾部 print(deque) #deque([1, 2, 3, 0]) deque.appendleft(0) #添加到首部 print(deque) #deque([0, 1, 2, 3, 4]) print(deque.pop()) #弹出并返回最后一个元素 4 print(deque) #deque([0, 1, 2, 3]) print(deque.popleft()) #弹出并返回左边第一个元素 0 print(deque) #deque([1, 2, 3])- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
优先队列
python中的用法
https://blog.csdn.net/chuan_day/article/details/73554861//插入 A = [1,2,9,7,3] heapq.heappush(A,10) >>> [1, 2, 9, 7, 3, 10] //将最小值pop出 heapq.heappop(A) >>> [2, 9, 7, 3, 10] // 返回最小的，并插入其他数 >>> A [2, 3, 9, 7, 10] >>> heapq.heappushpop(A,11) 返回2 >>> A [3, 7, 9, 11, 10] >>> // 返回小到大或从大到小顺序的前N个元素 heapq.nsmallest(n,A,key) heapq.nlargest(n,A,key) itemsDict=[ {'name':'dgb1','age':23,'salary':10000}, {'name':'dgb2','age':23,'salary':15000}, {'name':'dgb3','age':23,'salary':80000}, {'name':'dgb4','age':23,'salary':80000} ] itemsDictlarge = heapq.nlargest(3,itemsDict,lambda s:s['salary']) print(itemsDictlarge) [{'name': 'dgb3', 'age': 23, 'salary': 80000}, {'name': 'dgb4', 'age': 23, 'salary': 80000}, {'name': 'dgb2', 'age': 23, 'salary': 15000}]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 列表转优先队列
heapq.heapify(x)：将list X转换为heap- 合并多个优先队列
heapq.merge(*iterable)：将多个可迭代合并，并且排好序，返回一个iterator>>> heap [8, 10, 9, 100] >>> heap1 = [10,67,56,80,79] >>> h = heapq.merge(heap,heap1) >>> list(h) [8, 10, 9, 10, 67, 56, 80, 79, 100]#需要 说明的是这里所谓的排序不是完全排序，只是两个list对应位置比较， #将小的值先push，然后大的值再与另外一个list的下一个值比较- 1
- 2
- 3
- 4
- 5
- 6
- 7
堆（数组实现完全二叉树）
优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子
节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置i的节点的父节点位置一定为(i-1)/2，而它的两个子节点的位置又一定分别为2i+1 和 2i+2。为什么堆中 i 位置的节点的子节点位置为 2i+1, 2i+2, 父节点为 (i-1) / 2
- 插入
大根堆：父总比子大
小根堆：子总比父大
# 入队操作 def heappush(self, nums:list, value): nums.append(value) size = len(nums) i = size - 1 # 遍历父节点 while (i - 1) // 2 >= 0: cur_root = (i - 1)//2 # 父节点更大 if nums[cur_root] > value: break # 父节点小,父节点后移 nums[i] = nums[cur_root] i = cur_root nums[i] = value- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
23. Merge k Sorted Lists（合并k个升序链表）
- 暴力解法：转为列表求解
class Solution(object): def mergeKLists(self, lists): res = [] # 所有的链表合并转为列表 for i in range(len(lists)): head = lists[i] while head!=None: res.append(head.val) head = head.next # 列表排序，变为链表 res.sort() if len(res)!=0: head = ListNode(res[0]) else: return None p = head for i in range(1,len(res)): p.next = ListNode(res[i]) p = p.next return head- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 归并的方法（分而治之）
首先，对于给定的len(lists)个链表，用二分法，不断地分割成为两份l1 和l2，直到每份都切成一个链表
再把l1和l2合并，这个就转化成了两个链表合并的问题
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def mergeKLists(self, lists): # 合并两个链表 def mergeTwoLists(l1, l2): if not l1:return l2 if not l2:return l1 if l1.val < l2.val: l1.next = mergeTwoLists(l1.next,l2) return l1 else: l2.next = mergeTwoLists(l1, l2.next) return l2 # 分 def divide(lists,left,right): if left>=right: return lists[left] mid = (left+right)/2 l1 = divide(lists,left,mid) l2 = divide(lists,mid+1,right) l = mergeTwoLists(l1,l2) return l # 分而治之 if not lists:return n = len(lists) return divide(lists, 0, n-1)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 优先队列
导入python中的包
heapq创建优先队列head，我们先把每个链表(首指针，在链表中是第几个)针加入到优先队列中，构造要输出的dummy，然后弹出优先队列中最小的，heapq.heappush，加入到dummy.next，然后再把这个输出的链表指针下一个加入进去。再看整体head中最小是哪个。
class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import heapq dummy = ListNode(0) p = dummy head = [] for i in range(len(lists)): if lists[i] : heapq.heappush(head, (lists[i].val, i)) lists[i] = lists[i].next while head: val, idx = heapq.heappop(head) p.next = ListNode(val) p = p.next if lists[idx]: heapq.heappush(head, (lists[idx].val, idx)) lists[idx] = lists[idx].next return dummy.next- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
218. The Skyline Problem（天际线问题）
- Hard
给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的左拐点。
思路：-
首先，height数组存放各个建筑物，最高的左右端点，其中左端点的高度存为负数，右端点存为正数，然后给height排序。排序结果就是，先按建筑物群排，同一个建筑物群里，先按左端点排，然后再按右端点。
例如，buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
那么第一个建筑物群，包含[2,9,10],[3,7,15],[5,12,12]，三个房子A,B,C，每个房子有两个最高端点，在height中的排序就是A左，B左，C左，B右，A右，C右
-
接着，我们找出左转折点。转折点我们可以分为上升阶段的转折点，和下降阶段的转折点。
创建heap（递增的顺序数组）维护当前最大高度,pre,cur用来判断是否发生变化。
从小到大遍历height，如果遇到左端点，就加入到heap中。令cur=heap中末尾元素为当前最大高度，pre为没加入这个边界前的当前最大高度，如果cur!=pre，说明加入的边界上升了高度，，这时候就是我们要找的左转折点
从小到大遍历height，如果遇到右端点，说明这个建筑物已经到头了，所以在height中删去右端点的高度，如果这时候height中的最大高度跟之前的比变化了，这说明这个右端点是下降了，我们需要加入的是下降后的左端点，也就是同等坐标，但是高度是下降后的，即变化后的高度。
class Solution { public: vector<vector<int>> getSkyline(vector<vector<int>>& buildings) { vector<pair<int, int>> height; for (auto &b : buildings) { // 正负用于判别是左边界还是右边界，同时保证排序后： // 左边界相同时，最高的楼排在前面，insert的一定是相同左边界中最大的高度 // 右边界相同时，最低的楼排在前面，erase的时候不会改变最大高度 height.push_back({b[0], -b[2]}); // 左边界 height.push_back({b[1], b[2]}); // 右边界 } sort(height.begin(), height.end()); // 维护当前最大高度 multiset<int> heap; heap.insert(0); vector<vector<int>> res; // pre 表示遇到一个边界之前的最大高度 // cur 表示遇到一个边界之后的当前最大高度 int pre = 0, cur = 0; for (auto &h : height) { if (h.second < 0) { // 左边界 heap.insert(-h.second); } else { // 右边界 heap.erase(heap.find(h.second)); } cur = *heap.rbegin(); // 最大高度发生改变，一定是一个 key point，即一个水平线段的左端点 if (cur != pre) { res.push_back({h.first, cur}); pre = cur; } } return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
双端队列
python中heapq堆的讲解：
https://blog.csdn.net/qq_35883464/article/details/99410423
注意 Python 默认的优先队列是小根堆
如果要构造大根堆，就把加入的值变为负数
239. Sliding Window Maximum
- Hard
- 暴力遍历：遍历i从0到n-k-1，然后求nums[i:i+k]的max
超出时间限制
- 前k个中的最大值mx和对应的位置index，依次遍历i，比较新增的和原来的最大哪个大
记录下前k个中的最大值mx和对应的位置index，然后往后移动的时候，新增了num[i+k]减少了nums[i-1]，如果index在i和i+k中，比较nums[i+k]和nums[index]哪个大，如果nums[i+k]大则更新index和最大值，并加入到结果中，如果nums[index]，则当前片段最大值仍为mx。
困难点：
- 如果index刚好在0处，那么计算nums[1:k+1]最大值的时候，就得重新求最大值和index。
- 当前片段最大值为5，但是整体片段中最大值index有好多个，怎么就能取到我们想要的那个呢？nums[i:i+k]求出最大值对应位置max1，则index=i+max1
python求最大值和最大值对应的位置
datalist = ["1", "2", "4", "3"] max1 = max(datalist) maxid = datalist.index(max1)- 1
- 2
- 3
- 4
- 5
又又超出时间限制- 双端队列
对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
对于本题而言，初始时，我们将数组 nums的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。**然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums中的位置出现在滑动窗口左边界的左侧。**因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num在数组中的下标为 index。
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) # 注意 Python 默认的优先队列是小根堆 q = [(-nums[i], i) for i in range(k)] heapq.heapify(q) ans = [-q[0][0]] for i in range(k, n): heapq.heappush(q, (-nums[i], i)) # 如果最大值下标不在范围内，则剔除，直到最大值下标出现在范围内 while q[0][1] <= i - k: heapq.heappop(q) ans.append(-q[0][0]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 单调队列
队列deque()，python给的队列是双向队列，就是可以在头尾两段进行操作的队列（append, appendleft, pop, popleft）。另外，这其实是一个循环队列，因此有rotate操作来进行循环右移。所以例如q=[1,3,5,2]是队列，则q.pop()之后q=[1,3,5]，q.popleft()之后是[3,5,2]
或者可以更简单的，用list搞定，就是l.pop(0)删除第一个元素。
我们构造一个队列，放入的元素是下标，并且使得最左边对应的是数组最大值，依次单调递减，如果两个下标对应的最大值相同，那么下标小的放后面。
意思就是，我们希望剔除掉最右边的，返回最左边的，但需要判断下最左边的下标是否是当前范围内的。
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = collections.deque() # nums = [1,3,-1,-3,5,3,6,7] # 找到最初k个中从大到小排序，记录下标，因此q=[1,2] for i in range(k): # 如果是后面的比最后的大，那么可以剔除掉最后的 while q and nums[i] >= nums[q[-1]]: q.pop() q.append(i) ans = [nums[q[0]]] for i in range(k, n): # 如果新增的数比队尾即最小的大，那么队尾的数不需要在保留 while q and nums[i] >= nums[q[-1]]: q.pop() q.append(i) while q[0] <= i - k: q.popleft() ans.append(nums[q[0]]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
哈希表
128. Longest Consecutive Sequence（最长连续序列）
注意：需要o(n)时间
- 首先，排序，然后求最长连续序列
注意：[0,1,1,2]最长连续序列是0,1,2，所以注意去重
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if len(nums)==0: return 0 nums = list(set(nums)) nums.sort() i, ans = 0, 1 while i<len(nums): cur = 1 while i+1<len(nums) and nums[i+1]==nums[i]+1: cur += 1 i += 1 ans = max(ans,cur) i = i+1 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 哈希表
有以下两个重点 1、把数组转换成hashmap 使得查找的速度变成O（1） 2、确保查找序列时是从最小点开始的，如果还有更小点就直接跳过，这也是减少复杂度的重点。
nums = [100,4,200,1,3,2]，构造哈希表存储，以当前数字为起点的最大序列，格式为即对应{数字：以该数字为起点数组中序列长度}的字典，最后结果res = {‘100’:1,‘4’:4,‘200’:1,‘1’:1,‘3’:3,‘2’:2}遍历num in nums，看num-1有没有在数组中，如果没有我们从num+1开始往后找，看看以num为起点算序列长度，我们把这个序列长度记录到hash表中；如果num-1在数组中，那nu对应的序列长度就是num-1对应的长度-1，或者也可以不管，反正他也不会是最大。
class Solution: def longestConsecutive(self, nums: List[int]) -> int: res = {} nums = list(set(nums)) for num in nums: res[num] = 1 mx = 0 for num in nums: print(num) if num-1 not in res.keys(): begin = num+1 while begin in res.keys(): begin += 1 res[num] += 1 mx = max(mx,res[num]) return mx- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
149. Max Points on a Line
- Hard
- 一条线可以由一个点和斜率而唯一确定
对于每个点，我们对其它点建立哈希表，统计同一斜率的点一共有多少个。这里利用的原理是，一条线可以由一个点和斜率而唯一确定。另外也要考虑斜率不存在和重复坐标的情况。
本题也利用了一个小技巧：在遍历每个点时，对于数组中位置 i 的点，我们只需要考虑 i 之
后的点即可，因为 i 之前的点已经考虑过 i 了。即遍历i，对每个i建立新的哈希表，计算以i为起点和i之后的点的斜率，找出斜率中点最多的，记录下来点个数。
注意，分母为0的时候，也就是竖着的线，得单独计算，统计与i点x相同的点数
class Solution(object): def maxPoints(self, points): mx = 0 if len(points)<=1: return len(points) for i in range(len(points)): dic = {} same_x = 1 for j in range(i+1,len(points)): if points[i][0]==points[j][0]: same_x += 1 else: dx = points[i][0] - points[j][0] dy = points[i][1] -points[j][1] key = 1.0*dy/dx if key not in dic.keys(): # 包含i本身这个点 dic[key] = 2 else: dic[key] += 1 mx = max(mx,dic[key]) mx = max(mx,same_x) return mx- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
多重集合和映射
332. Reconstruct Itinerary
- Hard
给定一些票，有起始点，已知从"JFK"出发，需要走完这些票的形成，途中地点可以经过多次，要求返回字典序最短的旅程路径
- dfs回溯，每次先找字典序最小的，走不通路了再返回
具体做法：
首先，字典中所有机票起点，对应的终点信息，可能起点有很多终点，对这些进行字典序排序，确保我们先遍历的是字典序靠前的
接着，dfs遍历，如果用完了所有的票返回。否则分别遍历当前起点下所有终点，先遍历字典序小的，并且删除这个终点，如果可以一直走下去，就说明我们已经找到了要找的，返回，不再继续走了，如果走到死路（即手里还有票但是没法再走了）
例如，[[“JFK”,“KUL”],[“JFK”,“NRT”],[“NRT”,“JFK”]]
则需要往回走，这时候需要把删除的点加回来，并且在路中pop掉走的节点
class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: #1.存哈希表并按字典序排序 dic = {} for ticket in tickets: start, end = ticket[0], ticket[1] if start not in dic.keys(): dic[start] = [end] else: dic[start].append(end) for key in dic.keys(): dic[key].sort() #2.dfs回溯 def dfs(cur_city, used_ticket,ans): if used_ticket==len(tickets): return True # 没用完票但是无路可走 if cur_city not in dic.keys() or len(dic[cur_city])==0: return False nexts = dic[cur_city] for i in range(len(nexts)): #print(i,cur_city,nexts) next_city = nexts[i] dic[cur_city].remove(next_city) ans.append(next_city) # 在该递归分支中能找到一个用完所有机票的路径 # 找到想要的，可以剪枝，后面不再遍历 if dfs(next_city,used_ticket+1, ans): return True else: dic[cur_city].insert(i,next_city) #重新加回去 ans.pop() #回溯,删除节点 ans = ['JFK'] dfs('JFK',0,ans) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 欧拉通路
因为本题保证至少存在一种合理的路径，也就告诉了我们，这张图是一个欧拉图或者半欧拉图。我们只需要输出这条欧拉通路的路径即可
- 由于必然存在一条有效路径(至少是半欧拉图)，所以算法不需要回溯（既加入到结果集里的元素不需要删除）
- 整个图最多存在一个死胡同(出度和入度相差1），且这个死胡同一定是最后一个访问到的，否则无法完成一笔画。
- DFS的调用其实是一个拆边的过程（既每次递归调用删除一条边，所有子递归都返回后，再将当前节点加入结果集保证了结果集的逆序输出），一定是递归到这个死胡同（没有子递归可以调用）后递归函数开始返回。所以死胡同是第一个加入结果集的元素。
- 最后逆序的输出即可。
class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: def dfs(curr: str): while vec[curr]: tmp = heapq.heappop(vec[curr]) dfs(tmp) stack.append(curr) vec = collections.defaultdict(list) # 构造哈希表 for depart, arrive in tickets: vec[depart].append(arrive) # 每个key对应列表转为堆结构，方便找出最小值 for key in vec: heapq.heapify(vec[key]) stack = list() dfs("JFK") return stack[::-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
以[[“JFK”,“KUL”],[“JFK”,“NRT”],[“NRT”,“JFK”]]，简单记作[[“J”,“K”],[“J”,“N”],[“N”,“J”]]
变成hash表就是vec = {‘J’:[‘K’,‘N’],‘N’:‘J’}
首先，stack =[]，遍历J的邻点，加入最小值K，发现K后面没有了，回到上一层，加入N，在N邻点加入J，然后结束了。stack=[K,J,N,J]输出就是J,N,J,K
这里特别的一点是，被堵的路只有一条，然后肯定是最后输出的，其他路线都能构成环路
前缀和与积分图
304. Range Sum Query 2D - Immutable
- Medium
给定一个矩阵，再给定起点和终点，计算起点和终点包含的区域求和
NumMatrix就是给定的矩阵，sumRegion(int row1, int col1, int row2, int col2)是指起点(row1, col1)和终点(row2, col2)，例如红色部分框的就是NumMatrix[2][1]和NumMatrix[4][3]为起始点框的- 解法：动态规划
关键点在于：动态规划矩阵，我们可以简单记为dp，dp[i][j]表示以(i,j)为终点，计算（0,0）到（i,j）包含的和。 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] − d p [ i − 1 ] [ j − 1 ] + m a t r i x [ i − 1 ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]+matrix[i−1][j−1]
如果要求给定（row1,col1）到（row2,col2）的和，结果= d p [ r o w 2 ] [ c o l 2 ] − d p [ r o w 1 − 1 ] [ c o l 2 ] − d p [ r o w 2 ] [ c o l 1 − 1 ] + d p [ r o w 1 − 1 ] [ c o l 1 − 1 ] dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[row1-1][col1-1] dp[row2][col2]−dp[row1−1][col2]−dp[row2][col1−1]+dp[row1−1][col1−1]
PS：需要处理，只有一行的情况，题目规定了传进来的矩阵m,n都≥1，即至少有数所以不用考虑为空
不知道为什么这段代码有问题
class NumMatrix(object): def __init__(self, matrix): m, n = len(matrix),len(matrix[0]) self.matrix = matrix def sumRegion(self, row1, col1, row2, col2): m, n = len(self.matrix),len(self.matrix[0]) dp = [[0 for _ in range(n)] for _ in range(m)] dp[0][0] = self.matrix[0][0] # 第一行 for j in range(1,n): dp[0][j] = dp[0][j-1]+self.matrix[0][j] # 第一列 for i in range(1,m): dp[i][0] = dp[i-1][0]+self.matrix[i][0] # 其余 for i in range(1,m): for j in range(1,n): dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+self.matrix[i][j] if row1==0 and col1==0: return dp[row2][col2] return dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[row1-1][col1-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
560. Subarray Sum Equals K
- Medium
注意：连续的就是子数组，不连续 叫做子序列
也就是说不可以跳数进行组合- 前缀和数组
preSum 表示0到i的和，我们这里设置为n+1维的，初始为0，preSum[1]表示第一个数求和
我们求连续和的时候，left到right的和就是preSum[right + 1] - preSum[left]，我们遍历left从0到n，对于每个left依次往后查找，如果发现了和为k的就加1
public class Solution { public int subarraySum(int[] nums, int k) { int len = nums.length; // 计算前缀和数组 int[] preSum = new int[len + 1]; preSum[0] = 0; for (int i = 0; i < len; i++) { preSum[i + 1] = preSum[i] + nums[i]; } int count = 0; for (int left = 0; left < len; left++) { for (int right = left; right < len; right++) { // 区间和 [left..right]，注意下标偏移 if (preSum[right + 1] - preSum[left] == k) { count++; } } } return count; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 前缀和数组+哈希
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # key：前缀和，val：对应的数量 pre_sum_map = {0:1} # 初始化，前缀和为 0 的个数为 1 pre_sum = 0 # 记录自首个元素累计的前缀和 count = 0 for num in nums: # 遍历所有元素：计算前缀和，寻找 k，更新 map pre_sum += num # 累计前缀和 # 根据 pre - (pre - k) = k，寻找连续数组为 pre - k 的数量，即连续数组的和为 k 的数量 # 说明：pre 为自首个元素开始累计的连续数组； # pre - k 为包含在连续数组 pre 中的一个连续子数组（自首个元素开始累计） # 连续数组 - 连续子数组 = 连续子数组，对应 pre - (pre - k) = k # 则连续数组的和为 pre - k 的数量，即为连续数组的和为 k 的数量 if pre_sum - k in pre_sum_map: count += pre_sum_map[pre_sum - k] if pre_sum in pre_sum_map: # 此时的前缀和被记录过，则在原始记录上 + 1 pre_sum_map[pre_sum] += 1 else: # 如果此时的前缀和没有出现过，则初始化为 1 pre_sum_map[pre_sum] = 1 return count- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
注意，如果当前是i，那么pre_sum_map中记录的是，0到i-1时各个计算的前缀和值以及个数
数据结构练习题
566. Reshape the Matrix
- Easy
给定一个m×n的矩阵，要求转为r×c的矩阵，如果r×c不符合要求，则返回原矩阵
class Solution(object): def matrixReshape(self, mat, r, c): m,n = len(mat),len(mat[0]) if m*n!=r*c: return mat x,y = 0,0 re_mat = [[0 for _ in range(c)] for _ in range(r)] for i in range(r): for j in range(c): if y == n: y = 0 x = x+1 re_mat[i][j] = mat[x][y] y += 1 return re_mat- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
503. Next Greater Element II （下一个较大数）
- Medium
给定一个数组，对于每一个数，依次往后遍历，找出比这个数更大的数，返回下标。如果没有比他更大的数，就返回-1，注意，我们认为数组最后一个的下一个数是数组的第一个数
最暴力的方法就是对于每个数，再依次遍历下一个提示：Daily Temperature 的变种题。但是怎么才能做到最后一个的时候，下一个会遍历到第一个呢，那就i从0到2n+1，然后比较的时候取模
class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) ret = [-1] * n stk = list() for i in range(n * 2 - 1): while stk and nums[stk[-1]] < nums[i % n]: ret[stk.pop()] = nums[i % n] if i<n: stk.append(i % n) return ret- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] res = new int[n]; Arrays.fill(res,-1); Stack<Integer> stack = new Stack<>(); for(int i=0;i<2*n-1;i++){ while(!stack.isEmpty()&& nums[stack.peek()]<nums[i%n]){ res[stack.pop()] = nums[i%n]; } if(i<n) stack.add(i); } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
697. Degree of an Array
- Easy
给定一个数组，返回包含出现次数最多数字的序列长度
我只能想到依次统计每个数字出现的次数，然后找到出现次数最多的那个数字，接着找到他的先出现和最后出现的点。优化，我们可以计算出现次数的时候，分别也记录下最先和最后出现的位置。
但注意：可能会出现好多个相同次数的，所以我们需要对这些中的最后-最先，求最小值
class Solution(object): def findShortestSubArray(self, nums): count, start, end = {}, {}, {} mx,mx_inedx = 0,0 for i in range(len(nums)): if nums[i] not in count: count[nums[i]] = 1 start[nums[i]] = i else: count[nums[i]] += 1 end[nums[i]] = i mx = max(count.values()) ans = len(nums) for k, v in count.items(): if v == mx: ans = min(ans,end[k]-start[k]+1) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
594. Longest Harmonious Subsequence
我们定义harmonious array 为最大值和最小值差刚好是1，给定一个数组，找到最长的harmonious 子序列（可以不连续，就是跳着选）
我能想到的就是，对于每个元素，都从头到尾遍历一遍，找到比他大1的以及相等的元素，记录在哈希表中，需要注意的是[1,1,1,1]没有比他刚好大1的元素，这时候返回0class Solution(object): def findLHS(self, nums): dic = {} for i in range(len(nums)): if nums[i] not in dic: flag, count = 0, 0 for j in range(len(nums)): if (nums[j]==nums[i] or nums[j]==nums[i]+1): count += 1 if nums[j]==nums[i]+1: flag = 1 dic[nums[i]] = count if flag else 0 return max(dic.values())- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
但是超出了时间限制
- 自己的优化：记录每个数字出现的次数，然后再对每一个数字，遍历他前一个和后一个出现的次数
class Solution(object): def findLHS(self, nums): dic = {} # 统计每个数字出现的次数 for i in range(len(nums)): if nums[i] not in dic: dic[nums[i]] = 1 else: dic[nums[i]] += 1 mx = 0 # 对于每个数字，找出前后数字出现的次数，加上本身出现的次数求和取最大 # 注意：[1,1,1]没有前后数字 for k,v in dic.items(): v1 = dic[k-1] if k-1 in dic else 0 v2 = dic[k+1] if k+1 in dic else 0 if v1 or v2: mx = max(mx,dic[k]+max(v1,v2)) return mx- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
还可以优化，不需要求前后，只需要求后或者前两个之一就行。
JAVA版本
//统计每个字符出现的次数 Map<Integer, Integer> dic = new HashMap<>(); for(int i =0;i<nums.length;i++){ if(dic.containsKey(nums[i])) dic.put(nums[i],dic.get(nums[i])+1); else dic.put(nums[i],1); } int mx = 0; for(Map.Entry<Integer, Integer> entry:dic.entrySet()){ int key = entry.getKey(); int value = entry.getValue(); if(dic.containsKey(key+1)){ mx = Math.max(mx,dic.get(key+1)+dic.get(key)); } } return mx;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
287. Find the Duplicate Number
- Medium
给定一个数组，有n+1个数字，每个数字是1到n之间的，找出重复的数字，并返回。注意只有一个重复的数字，并且，可能会出现[2,2,2]这样
注意：要求O(n)时间，题目要求查找重复的整数，很容易想到使用「哈希表」，但是题目中要求：「你设计的解决方案必须不修改数组 nums 且只用常量级 O(1)的额外空间」，因此使用「哈希表」不满足题目的要求；
- 用哈希表（不被允许）
class Solution(object): def findDuplicate(self, nums): dic = {} for i in range(len(nums)): if nums[i] not in dic: dic[nums[i]] = 1 else: return nums[i]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 二分法
首先,left=1，right = len - 1，令 mid = left + (right - left) / 2，我们计算nums中比mid小的个数，如果没有重复，那么比mid小的个数应该≤mid，否则就说明有重复，我们把区间缩小到左半边，否则就是右半边有重复
public class Solution { public int findDuplicate(int[] nums) { int len = nums.length; int left = 1; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; int cnt = 0; for (int num : nums) { if (num <= mid) { cnt += 1; } } // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个，此时重复元素一定出现在 [1..4] 区间里 if (cnt > mid) { // 重复元素位于区间 [left..mid] right = mid; } else { // if 分析正确了以后，else 搜索的区间就是 if 的反面区间 [mid + 1..right] left = mid + 1; } } return left; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 快慢指针
class Solution { public int findDuplicate(int[] nums) { /** 快慢指针思想, fast 和 slow 是指针, nums[slow] 表示取指针对应的元素 注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界), 因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素, 即按照寻找链表环入口的思路来做 **/ int fast = 0, slow = 0; while(true) { fast = nums[nums[fast]]; slow = nums[slow]; if(slow == fast) { fast = 0; while(nums[slow] != nums[fast]) { fast = nums[fast]; slow = nums[slow]; } return nums[slow]; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd判圈法）。给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果fast可以无限走下去，那么说明一定有环路，且一定存 在一个时刻slow和fast相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并 让slow和fast每次都前进一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; // 判断是否存在环路 do { if (!fast || !fast->next) return nullptr; fast = fast->next->next; slow = slow->next; } while (fast != slow); // 如果存在，查找环路节点 fast = head; while (fast != slow) { slow = slow->next; fast = fast->next; } return fast; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
313. Super Ugly Number
- 动态规划
新建数组dp用于记录丑数，初始化dp[0]=1。分析得到，dp中的数一定是primes数的倍数，也就是说dp中的数是primes数的乘积组成
但是， d p [ i ] ≠ d p [ i − 1 ] dp[i]≠dp[i-1] dp[i]=dp[i−1]乘prime最小，有可能是 d p [ i ] = d p [ i − 1 ] dp[i]=dp[i-1] dp[i]=dp[i−1]乘prime次小
我们构造一个新数组idnex，存放prime中数依次需要乘dp多少
以primes=[2,7,13,19]为例，初始化index=[0,0,0,0]
i=0, d p [ i ] = 1 dp[i]=1 dp[i]=1
i=1,此时index=[0,0,0,0]，所以 d p [ 1 ] = m i n { 1 ∗ 2 , 1 ∗ 7 , . . . 1 ∗ 19 } = 2 dp[1]=min\{1*2,1*7,...1*19\}=2 dp[1]=min{1∗2,1∗7,...1∗19}=2，加入到dp中此时dp=[1,2]，index=[1,0,0,0]i=2,此时index=[1,0,0,0]，所以 d p [ 2 ] = m i n { d p [ 1 ] ∗ 2 , d p [ 0 ] ∗ 7... d p [ 0 ] ∗ 19 } = m i n { 2 ∗ 2 , 1 ∗ 7 , . . . 1 ∗ 19 } = 4 dp[2]=min\{dp[1]*2,dp[0]*7...dp[0]*19\}=min\{2*2,1*7,...1*19\}=4 dp[2]=min{dp[1]∗2,dp[0]∗7...dp[0]∗19}=min{2∗2,1∗7,...1∗19}=4，加入到dp中此时dp=[1,2,4]，index=[2,0,0,0]
i=3,此时index=[2,0,0,0]，所以 d p [ 3 ] = m i n { d p [ 2 ] ∗ 2 , d p [ 0 ] ∗ 7... d p [ 0 ] ∗ 19 } = m i n { 4 ∗ 2 , 1 ∗ 7 , . . . 1 ∗ 19 } = 7 dp[3]=min\{dp[2]*2,dp[0]*7...dp[0]*19\}=min\{4*2,1*7,...1*19\}=7 dp[3]=min{dp[2]∗2,dp[0]∗7...dp[0]∗19}=min{4∗2,1∗7,...1∗19}=7，加入到dp中此时dp=[1,2,4,7]，index=[2,1,0,0]
i=4,此时index=[2,1,0,0]，所以 d p [ 4 ] = m i n { d p [ 2 ] ∗ 2 , d p [ 1 ] ∗ 7... d p [ 0 ] ∗ 19 } = m i n { 4 ∗ 2 , 2 ∗ 7 , . . . 1 ∗ 19 } = 8 dp[4]=min\{dp[2]*2,dp[1]*7...dp[0]*19\}=min\{4*2,2*7,...1*19\}=8 dp[4]=min{dp[2]∗2,dp[1]∗7...dp[0]∗19}=min{4∗2,2∗7,...1∗19}=8，加入到dp中此时dp=[1,2,4,7,8]，index=[3,1,0,0]
以此类推
class Solution: def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int: m = len(primes) # dp[i] 代表第i+1个丑数 dp = [inf] * n dp[0] = 1 # indexes代表每个质因子现在应该跟哪个丑数相乘 indexes = [0] * m for i in range(1, n): # 哪个质因子相乘的丑数将会变化 changeIndex = 0 for j in range(m): # 如果当前质因子乘它的丑数小于当前的丑数，更新当前丑数并更新变化坐标 if primes[j] * dp[indexes[j]] < dp[i]: changeIndex = j dp[i] = primes[j] * dp[indexes[j]] # 如果相等直接变化，这样可以去重复 elif primes[j] * dp[indexes[j]] == dp[i]: indexes[j] += 1 # 变化的坐标+1 indexes[changeIndex] += 1 return dp[-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 优先队列（堆）
构造一个优先队列q，初始化放入1
- 起始先将最小丑数 1放入队列
- 每次从队列取出最小值 x，然后将 x所对应的丑数 2x、7x…19x进行入队。
- 对步骤 2 循环多次，第 n次出队的值即是答案。
例如，我们i从0开始遍历到n-1,循环n次，第n个被队列输出的即为所求
i=0，输出当前q最小值1，遍历primes，把12,…119入队，此时q=[2,7,…19]
i=1,输出当前q最小值2，遍历primes，把22,…219入队，此时q=[7,…19;4,14…38]
i=2,输出当前q最小值4，遍历primes，把42,…419入队，此时q=[7,…19;14…38;8,…]入队一直到n次，但是注意的是入队的时候，可能入队的值已经在我们q中存在。
为了防止同一丑数多次进队，我们需要使用数据结构 Set，我们记作explored 来记录入过队列的丑数。
class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ nums = [2,3,5] explored = {1} pq = [1] for i in range(1, n+1): x = heapq.heappop(pq) if i == n: return x for num in nums: t = num * x if t not in explored: explored.add(t) heapq.heappush(pq,t) return -1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
870. Advantage Shuffle（田忌赛马）
策略：选我方最弱的出战，打不过对方最弱的话，就和对方最强的一换一。
具体：定义assigned 字典，存储A比B大的数，如果A中某数都小于B中数，则把这个数加入到remaining
从小到大遍历A，看A最小是否比B最小大，如果是就加入到assigned B最小定义的位置中，如果不是就加入到remaining，再看A次小是不是比B最小orB次小大，如果是就加入到assigned B最小或次小定义的位置中，如果不是就加入到remaining。
也就是说，每次拉A中数出来看看，看看能不能打过当前B最小的，打不过就打最大的去一换一。你连最小的都打不过，别的肯定更打不过
class Solution(object): def advantageCount(self, A, B): sortedA = sorted(A) sortedB = sorted(B) # assigned[b] = list of a that are assigned to beat b # remaining = list of a that are not assigned to any b assigned = {b: [] for b in B} remaining = [] # populate (assigned, remaining) appropriately # sortedB[j] is always the smallest unassigned element in B j = 0 for a in sortedA: if a > sortedB[j]: assigned[sortedB[j]].append(a) j += 1 else: remaining.append(a) # Reconstruct the answer from annotations (assigned, remaining) return [assigned[b].pop() if assigned[b] else remaining.pop() for b in B]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
字符串
242. Valid Anagram（s打乱顺序是否能变成t）
- Easy
给定两个字符串s,t，判断s打乱顺序后是否能变成t
三种不同的解法class Solution public boolean isAnagram1(String s, String t) { char[] sChars = s.toCharArray(); char[] tChars = t.toCharArray(); Arrays.sort(sChars); Arrays.sort(tChars); return Arrays.equals(sChars, tChars); } public boolean isAnagram2(String s, String t) { Map<Character, Integer> map = new HashMap<>(); for (char ch : s.toCharArray()) { map.put(ch, map.getOrDefault(ch, 0) + 1); } for (char ch : t.toCharArray()) { Integer count = map.get(ch); if (count == null) { return false; } else if (count > 1) { map.put(ch, count - 1); } else { map.remove(ch); } } return map.isEmpty(); } public boolean isAnagram3(String s, String t) { int[] sCounts = new int[26]; int[] tCounts = new int[26]; for (char ch : s.toCharArray()) { sCounts[ch - 'a']++; } for (char ch : t.toCharArray()) { tCounts[ch - 'a']++; } for (int i = 0; i < 26; i++) { if (sCounts[i] != tCounts[i]) { return false; } } return true; } public boolean isAnagram4(String s, String t) { int[] counts = new int[26]; t.chars().forEach(tc -> counts[tc - 'a']++); s.chars().forEach(cs -> counts[cs - 'a']--); return Arrays.stream(counts).allMatch(c -> c == 0); } public boolean isAnagram(String s, String t) { return Arrays.equals(s.chars().sorted().toArray(), t.chars().sorted().toArray()); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
205. Isomorphic Strings（s能否映射为t）
- Easy
- 自己思路，建立字典，s中的字母作为key，t中的作为value，看是否s中的被映射到了t
但是容易出现问题的是：s=“badc”,t=“baba”，可能s中两个都映射为t中同一个字母了，我想法就是构建两个字典，key分别是S中的字母，t中的字母
class Solution(object): def isIsomorphic(self, s, t): dic = {} dic2 = {} if len(s)!=len(t): return False for i in range(len(s)): if s[i] not in dic.keys(): dic[s[i]] = t[i] if t[i] not in dic2.keys(): dic2[t[i]] = s[i] if t[i] in dic2.keys() and s[i] in dic.keys(): if dic[s[i]] != t[i] or dic2[t[i]] != s[i]: return False return True- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
java，利用key-map，看没有key的时候，有没有对应的value在，如果有则返回错误
class Solution { public boolean isIsomorphic(String s, String t) { if(s.length()!=t.length()) return false; HashMap<Character,Character> map = new HashMap<>(); for(int i = 0; i<s.length();i++){ if(!map.containsKey(s.charAt(i))){ if(map.containsValue(t.charAt(i))){ return false; } map.put(s.charAt(i),t.charAt(i)); } else{ if(map.get(s.charAt(i))!=t.charAt(i)){ return false; } } } return true; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 题解方法：将问题转化为：判断两个字符串每个位置的字符第一次出现的位置是否相同。
举例来说，对于“paper”和“title”，假设我们现在遍历到第三个字符“p”和“t”，发现它们第一次出现的位置都在第一个字符，则说明目前位置满足同构。
647. Palindromic Substrings（回文子串）
- Medium
给定一个字符，求其有多少个回文子字符串。回文的定义是左右对称。
我能想到的解法就是，从i=0开始遍历到结尾，看以i位置开头的回文字符串有几个
python截取字符串：string[start: end: step]：获取从 起点位置 到 终点位置 - 1 的，每个之间距离 步长 的所有字符
string = "freeCodeCamp" print(string[0:5])- 1
- 2
- 解法思路，从i=0开始遍历到结尾，以当前位置i为中心，判断存在多少以当前位置为中轴的回文子字符串。
class Solution(object): def countSubstrings(self, s): def extendSubstrings(s,l,r): count = 0 while l>=0 and r<len(s) and s[l]==s[r]: l -= 1 r += 1 count += 1 return count ans = 0 for i in range(len(s)): ans += extendSubstrings(s,i,i) # 奇数长度 ans += extendSubstrings(s,i,i+1) # 偶数长度 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
class Solution { public int countSubstrings(String s) { int ans = 0; for(int i=0; i<s.length();i++){ ans += extendSubstrings(s,i,i); ans += extendSubstrings(s,i,i+1); } return ans; } public int extendSubstrings(String s, int l, int r){ int count = 0; while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){ count ++; r++; l--; } return count; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
696. Count Binary Substrings
- Easy
给定一个 0-1 字符串，求有多少非空子字符串的 0 和 1 数量相同，并且子字符的0和1是连续出现的，例如0011，但是001100就不是连续出现，所以就不是
- 官方题解
建立list列表，按0和1划分，计算每个划分部分包含的点数，例如 s = “00110011”，则 l = [2,3,2,2]
然后在遍历l，在l [i] 和 l[i-1]之间取最小再相加，就是0和1相同的字符串数量。
Python版本
class Solution(object): def countBinarySubstrings(self, s): l = [] i = 0 while i<len(s): count = 1 while i+1<len(s) and s[i+1]==s[i]: count += 1 i += 1 l.append(count) i+=1 ans = 0 for i in range(len(l)-1): ans += min(l[i],l[i+1]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
JAVA版本
class Solution { public int countBinarySubstrings(String s) { List<Integer> counts = new ArrayList<Integer>(); int ptr = 0, n = s.length(); while (ptr < n) { char c = s.charAt(ptr); int count = 0; while (ptr < n && s.charAt(ptr) == c) { ++ptr; ++count; } counts.add(count); } int ans = 0; for (int i = 1; i < counts.size(); ++i) { ans += Math.min(counts.get(i), counts.get(i - 1)); } return ans; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 方法二
227. Basic Calculator II
- Medium
给定一个包含加减乘除整数运算的字符串，求其运算结果，只保留整数。
注意：这里只会出现+ - * /，不会出现()括号运算，同时此类型题也考察很多细节处理，如无运算符的情况，和多个空格的情况等等表达式计算
- 双栈解法
定义两个栈nums和ops，分别存放数字和运算符
以表达式：-7+(3+2*3)*12+5举例
先在nums里面加入0，避免出现一开始就是负数的情况。定义运算calc，运行calc则计算ops中栈顶运算规则。
遍历s，如果遇到数字则加入nums（注意可能是两位数字），需要进制处理；如果遇到“(”则加入ops；如果遇到“)”则对()进行计算，pop出ops中的运算符，但是注意不要pop出"(“，最后删去”("，如果遇到运算符，则考察要加入的运算符，和当前栈顶运算符的优先级，如果要加入的更小，则我们循环计算ops中的运算符，直到栈顶运算符变小
最后，可能出现运算符没计算完的，我们计算完，注意不要出现运算符"("
class Solution(object): def calculate(self, s): def calc(nums,ops): if len(nums)<2 or len(ops)==0: return a = nums.pop() b = nums.pop() op = ops.pop() if op=="+": nums.append(a+b) elif op=="-": nums.append(a-b) elif op=="*": nums.append(a*b) elif op=="/": nums.append(a/b) elif op=="^": nums.append(math.pow(a,b)) # 为了防止第一个数为负数，先往 nums 加个 0 nums, ops = [0], [] op_priority = {'+': 0, '-': 0, '*': 1, '/': 1, '%': 1, '^': 2} s.replace(" ","") s.replace("(-","(0-") i = 0 while i<len(s): c = s[i] i += 1 if(c.isdigit()): #数字不仅仅是个位数，可能是123 num = int(c) while i<len(s) and s[i].isdigit(): num = num*10+int(s[i]) i += 1 nums.append(num) elif c=='(': ops.append(c) elif c==')': while ops and ops[-1] != '(': calc(nums,ops) ops.pop() else: while ops and op_priority[ops[-1]] > op_priority[c]: calc(nums,ops) ops.append(c) #运算符没计算完 while ops and ops[-1]!='(': calc(nums,ops) return nums[-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
Java
public int calculate(String s) { Map<Character, Integer> map = new HashMap<Character, Integer>(){{ put('-', 1); put('+', 1); put('*', 2); put('/', 2); put('%', 2); put('^', 3); }}; Deque<Integer> nums = new ArrayDeque<>(); Deque<Character> ops = new ArrayDeque<>(); nums.add(0); int i=0; s = s.replaceAll(" ", ""); while(i<s.length()){ char c = s.charAt(i); i++; if(Character.isDigit(c)){ int num = c-'0'; while(!nums.isEmpty()&&i<s.length()&&Character.isDigit(s.charAt(i))){ num = num*10 + s.charAt(i)-'0'; i++; } nums.addLast(num); } else if(c=='('){ ops.addLast(c); } else if (c == ')') { while (!ops.isEmpty() && ops.peekLast() != '(') { calc(nums, ops); } ops.pollLast(); } else{ while(!ops.isEmpty()&&ops.peekLast()!='('&&map.get(ops.peekLast())>=map.get(c)){ calc(nums,ops); } ops.add(c); } } while(!ops.isEmpty()&& ops.peekLast()!='('){ calc(nums,ops); } return nums.peekLast(); } void calc(Deque<Integer> nums, Deque<Character> ops) { if(nums.size()<2 || ops.size()==0) return; int b = nums.pollLast().intValue(); int a = nums.pollLast().intValue(); char op = ops.pollLast().charValue(); int ans = 0; if (op == '+') ans = a + b; else if (op == '-') ans = a - b; else if (op == '*') ans = a * b; else if (op == '/') ans = a / b; else if (op == '^') ans = (int)Math.pow(a, b); else if (op == '%') ans = a % b; nums.addLast(ans); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
28. Implement strStr()
- Easy
判断一个字符串是不是另一个字符串的子字符串，并返回其位置。
class Solution(object): def strStr(self, haystack, needle): def Next(P): j, k =0, -1 next = [-1 for _ in range(len(P))] while j<len(P)-1: if k==-1 or P[k]==P[j]: k += 1 j += 1 next[j] = k else: k = next[k] return next next = Next(needle) i, j = 0, 0 while i<len(haystack) and j<len(needle): # j==-1找不到匹配的，i得移动 if j==-1 or haystack[i]==needle[j]: i += 1 j += 1 else: j = next[j] if j == len(needle): return i-j else: return -1 return -1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
3. Longest Substring Without Repeating Characters（最长不含重复字母的子字符串长度）
-
Medium
返回最长不含重复字母的子字符串长度，例如 Input: s = “pwwkew”，返回Output: 3 -
滑动窗口
新建一个list，存储当前的字符串，如果新加入的字母在字符串中，则一直往前删除，直到没有这个字母
class Solution(object): def lengthOfLongestSubstring(self, s): curs = [] mx = 0 for i in range(len(s)): while curs and s[i] in curs: curs.pop(0) curs.append(s[i]) mx = max(mx,len(curs)) return mx- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
java
class Solution { public int lengthOfLongestSubstring(String s) { ArrayList<Character> ll = new ArrayList<>(); int max = 0; for(int i = 0;i<s.length();i++){ while(!ll.isEmpty() && ll.contains(s.charAt(i))){ ll.remove(0); } ll.add(s.charAt(i)); max = Math.max(max,ll.size()); } return max; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
5. Longest Palindromic Substring（最长回文子串）
- Medium
给定一个字符串s，返回最长回文子串，它本身也算
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.-
中心扩散
以i为中心，往左往右判断是否相等，返回最长回文序列注意：s[l+1:r]表示 l+1可以取到，但是r不能取到
class Solution(object): def longestPalindrome(self, s): def Palindromic(s,l,r): while l>=0 and r<len(s) and s[l]==s[r]: l -= 1 r += 1 return s[l+1:r] mx = 0 cur = s[0] for i in range(len(s)): sub1 = Palindromic(s,i,i) sub2 = Palindromic(s,i,i+1) if len(sub1)>=len(sub2): if len(sub1)>mx: mx = len(sub1) cur = sub1 else: if len(sub2)>mx: mx = len(sub2) cur = sub2 return cur- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
java
public class stringmax { public String longestPalindrome(String s) { String cur = s.substring(0,1); int max = 1; for(int i=0; i<s.length()-1;i++){ String sub1 = Palindrome(s, i, i); String sub2 = Palindrome(s, i, i+1); max = Math.max(Math.max(sub1.length(),sub2.length()),max); if(max==sub1.length()){ cur = sub1; } if(max==sub2.length()){ cur = sub2; } } return cur; } String Palindrome(String s, int l, int r){ while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ l--; r++; } return s.substring(l+1,r); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 动态规划
dp[i][j] 表示 s[i…j] 是否是回文串,
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s max_len = 1 begin = 0 # dp[i][j] 表示 s[i..j] 是否是回文串 dp = [[False] * n for _ in range(n)] for i in range(n): dp[i][i] = True # 递推开始 # 先枚举子串长度 for L in range(2, n + 1): # 枚举左边界，左边界的上限设置可以宽松一些 for i in range(n): # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得 j = L + i - 1 # 如果右边界越界，就可以退出当前循环 if j >= n: break if s[i] != s[j]: dp[i][j] = False else: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置 if dp[i][j] and j - i + 1 > max_len: max_len = j - i + 1 begin = i return s[begin:begin + max_len] 作者：LeetCode-Solution 链接：https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
链表
206. Reverse Linked List（反转链表）
class Solution: def reverseList(self, head: ListNode) -> ListNode: pre, p = None, head while p: p_next = p.next p.next = pre pre = p p = p_next return pre- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
为什么是return pre而不是return p，因为最后肯定是p是none才跳出循环，所以它前一个点
我们看看java怎么写
lass Solution { public ListNode reverseList(ListNode head) { ListNode pre = null, p = head; while(p!=null){ ListNode p_next = p.next; p.next = pre; pre = p; p = p_next; } return pre; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
-
相关阅读:
vxe-table 将表格指定行设置颜色后，选中行、悬浮行样式失效解决。
Windows 批量部署简易脚本
Rabbitmq 常见问题处理
c/c++中指针和取址符
如何从800万数据中快速捞出自己想要的数据？
技术管理进阶——成长加速的秘密
【Vue 开发实战】基础篇 # 13：如何优雅地获取跨层级组件实例（拒绝递归）
MYSQL DBA运维实战 SQL2
Shell变量与赋值、变量运算、特殊变量、重定向与管渠
华为防火墙基础自学系列 | Site to Site IPSec VdPdNd
- 原文地址：https://blog.csdn.net/qq_40933711/article/details/124780763
