赞
踩
Leetcode1636. 按照频率将数组升序排序:简单题 (详情点击链接见原题)
给你一个整数数组
nums
,请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同,请你按照数值本身将它们 降序 排序
解题思路
(x, cnt)
的形式转存到数组list
中【x
为对应的nums
中的数值,cnt
为x
在nums
中出现的频次】cnt
为第一关键字进行升序排序,以x
的大小为第二关键字进行降序排序python代码解法:
from collections import Counter
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
count = Counter(nums) # 1.对每个数以及该数出现的频率进行统计
count = list(count.items()) # 2.将数与频率转换为列表
count = sorted(count, key=lambda x: (x[1], -x[0])) # 3.以频率为第一关键字进行升序排序,以数字大小为第二关键字进行降序排序
res = []
for li in count:
for _ in range(li[1]):
res.append(li[0]) # 4.统计结果
return res
Leetcode1366. 通过投票对团队排名:中等题 (详情点击链接见原题)
现在有一个特殊的排名系统,依据参赛团队在投票人心中的次序进行排名,每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
方法1:利用哈希表
设参与排名的人数为n
,(即数组votes
中任一字符串的长度),利用哈希表,
key
: 键为一个参与排名的人,
value
: 值为一个长度为n
的数组rank
,rank[i]
表示这个人排名为i
的次数
votes
中的每一个字符串并进行统计,就可以得到上述存储了每一个人排名情况的哈希映射rank
相等的情况下,我们需要以 vid
为第二关键字进行升序排序(可以将vid
从字符转换成对应的ASCII
,并用其相反数进行升序排序)python代码解法1:
class Solution:
def rankTeams(self, votes: List[str]) -> str:
n = len(votes[0])
hash_map = {}
for vote in votes:
for k, v in enumerate(vote):
hash_map[v] = hash_map.get(v, [0] * n)
hash_map[v][k] += 1
rank_list = list(hash_map.items())
rank_list = sorted(rank_list, key=lambda x: (x[1], -ord(x[0])), reverse=True)
return "".join(x[0] for x in rank_list)
方法2:利用二维数组代替哈希
4. dw[26][27]的含义
:26
的含义为参赛队伍可能有26
支,dw[i]
是一个大小为 27
的一维数组,记录该队伍在每个排名下的频次
dw[0][0]=5
表示 A
队伍取得了 5
票排位第一dw[1][1] = 2
表示B
队伍取得了2
票排位第二,dw[1][2]=3
表示B
队伍取得了3
票排位第三dw[2][1] = 3
表示C
队伍取得了3
票排位第二,dw[2][2]=2
表示C
队伍取得了2
票排位第三ASCII
码ASCII
码取负值按降序排序即升序:负负得正】python代码解法2:
class Solution:
def rankTeams(self, votes: List[str]) -> str:
dw = [[0] * 27 for _ in range(26)]
res = ""
for vote in votes:
for i in range(len(vote)):
dw[ord(vote[i]) - ord('A')][i] += 1 # 1.记录每个队伍的排名信息
dw[ord(vote[i]) - ord('A')][-1] = (ord(vote[i]) - ord('A')) + 1 # 2.用最后一位记录该队伍信息
dw = sorted(dw, key=lambda x: (x[:-1], -x[-1]), reverse=True) # 3.根据排名情况按降序排序,如果排名相同,根据字母大小的相反数按降序排序(保证A和B排名一致的情况下,A仍然在B的前面)
for i in range(0, len(dw)): # 4.统计按要求排完后的队伍
if dw[i][-1] != 0:
res += chr(dw[i][-1] + ord('A') - 1)
return res
Leetcode451:根据字符串出现频率排序:中等题 (详情点击链接见原题)
给定一个字符串
s
,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数
python代码解法:
利用二维数组代替哈希
class Solution:
def frequencySort(self, s: str) -> str:
char_map = [[0 for _ in range(2)] for _ in range(128)]
for i in s:
char_map[ord(i)][0] = ord(i) # 1.记录该字符对应的 ASCII 码
char_map[ord(i)][1] += 1 # 2.记录该字符出现的频次
char_map = sorted(char_map, key=lambda x: x[1], reverse=True) # 3.按照频次进行降序排序
res = ''
for ch in char_map:
if ch[1] > 0:
res += chr(ch[0]) * ch[1] # 4.将字符以及该字符出现的频次记录到结果集中
return res
Leetcode179. 最大数:中等题 (详情点击链接见原题)
给定一组非负整数
nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数
python代码解法1: 类似于冒泡排序
class Solution:
def largestNumber(self, nums: List[int]) -> str:
n = len(nums)
nums = list(map(str, nums))
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] < nums[j] + nums[i]:
nums[i], nums[j] = nums[j], nums[i]
return str(int(''.join(nums)))
python代码解法2: 自定义排序规则
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def sort_rule(x, y):
if x + y < y + x:
return 1
else:
return -1
nums = list(map(str, nums))
nums.sort(key=cmp_to_key(sort_rule))
# print(nums)
return str(int(''.join(nums)))
Leetcode791:自定义字符串排序:中等题 (详情点击链接见原题)
给定两个字符串
order
和s
。order
的所有字母都是 唯一 的,并且以前按照一些自定义的顺序排序
python代码解法
class Solution: def customSortString(self, order: str, s: str) -> str: counts = [0] * 26 ans = '' for i in s: # 1.遍历s进行字符出现的频率统计 counts[ord(i) - ord('a')] += 1 for o in order: # 遍历order字符串 num = ord(o) - ord('a') if counts[num] >= 0: ans += o * counts[num] # 2.按照order中出现的字符的顺序,逐个乘以字符出现的频率追加到ans末尾 counts[num] = 0 # 3.添加到结果集后将对应字符出现频率置为0 for i in range(0, len(counts)): # 4.遍历count将s中的多余字符追加到ans的末尾 if counts[i] != 0: ans += chr(ord('a') + i) * counts[i] return ans
Leetcode1122. 数组的相对排序:简单题 (详情点击链接见原题)
给你两个数组,
arr1
和arr2
,arr2
中的元素各不相同,arr2
中的每个元素都出现在arr1
中,对arr1
中的元素进行排序,使arr1
中项的相对顺序和arr2
中的相对顺序相同。未在arr2
中出现过的元素需要按照升序放在arr1
的末尾
1 <= arr1.length, arr2.length <= 1000
题目条件中有前提条件
1001
的 count
数组arr1
数组中数字的大小为索引,值为该数字出现的频率记录到数组 count
中arr2
的同时,将 arr2
中的数置入 arr1
中,注意 count
中的频率arr2
之后,再处理剩下的数字,按照 count
数组中所记录的位置信息和频率信息追加到arr1
数组的末尾python代码解法(一维数组代替哈希映射)
class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: count = [0] * 1001 # 1.申请一个大小为 1001 的 count 数组 for i in arr1: # 2.以 arr1 数组中数字的大小为索引,值为该数字出现的频率 count[i] += 1 n = 0 for i in arr2: # 3.遍历 arr2 数组,按 arr2 中的顺序直接在 arr1 的基础上进行排序 while n < len(arr1) and count[i] > 0: arr1[n] = i count[i] -= 1 n += 1 for index in range(len(count)): # 4.遍历count数组中不为0的位置和该位置数字出现的频率 while n < len(arr1) and count[index] > 0: arr1[n] = index # 5.追加到 arr1 的末尾 count[index] -= 1 n += 1 return arr1
python代码解法(利用哈希表)
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
hash_map = Counter(arr1)
print(hash_map)
ans = []
for i in arr2:
for j in range(hash_map[i]):
ans.append(i)
hash_map.pop(i)
hash_list = list(hash_map.items())
hash_list.sort()
for item in hash_list:
for i in range(item[1]):
ans.append(item[0])
return ans
Leetcode539. 最小时间差:中等题 (详情点击链接见原题)
给定一个
24
小时制(小时:分钟"HH:MM"
)的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示
解题思路:我们需要找出时钟盘中夹角最小的两个时间点,其中包括分布在 00:00
左右两侧(横跨了一天)的时间点
因此一个简单的方式是对于每个timePointes[i]
,我们不仅记录【当天该时间点对应的偏移量】,还记录【下一天该时间点】对应的偏移量
python代码解法
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
n = len(timePoints) * 2
nums = [0] * n
index = 0
for time in timePoints:
hour, minute = int(time[:2]), int(time[-2:])
nums[index] = hour * 60 + minute
nums[index + 1] = nums[index] + 1440
index += 2
nums.sort()
min_gap = float('inf')
for i in range(n - 1):
min_gap = min(min_gap, nums[i + 1] - nums[i])
return min_gap
Leetcode945. 使数组唯一的最小增量:中等题 (详情点击链接见原题)
给你一个整数数组
nums
。每次move
操作将会选择任意一个满足0 <= i < nums.length
的下标i
,并将nums[i]
递增1
解题思路:首先将数组进行排序,然后从左到右遍历数组
continue
python代码解法
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
nums.sort()
ans = 0
for i in range(1, len(nums)):
if nums[i] <= nums[i - 1]:
ans += (nums[i - 1] - nums[i] + 1)
nums[i] = nums[i - 1] + 1
return ans
Leetcode274. H 指数:中等题 (详情点击链接见原题)
给你一个整数数组
citations
,其中citations[i]
表示研究者的第i
篇论文被引用的次数。计算并返回该研究者的h
指数
解题思路
设 n
为 citations
的长度,h
不可能超过 n
,对于引用次数大于 n
的论文,我们在统计的时候可以看成是引用次数等于 n
的论文
创建一个长度为 n + 1
的数组【因为最少的引用次数为 0
次,最大的引用次数大于 n
时取n
】
cnt[i]
:引用次数为 i
的论文的数量为 cnt[i]
为了快速算出有多少论文的引用次数 ≥ i
,每次循环把 cnt[i]
加到 s
种,只要 s >= i
成立,此时的 i
就是满足 s >= i
的最大的 i
,直接返回 i
作为答案
python代码解法
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
counts = [0] * (n + 1)
for c in citations:
counts[min(c, n)] += 1 # 引用次数 > n,等价于引用次数为 n
s = 0
for i in range(n, -1, -1): # i = 0 的时候,s >= i一定成立
s += counts[i]
if s >= i: # 说明至少有 i 篇论文的引用次数至少为i
return i
Leetcode912. 排序数组:中等题 (详情点击链接见原题)
给你一个整数数组
nums
,请你将该数组升序排列
每种排序算法都可以实现数组的升序和降序排序,其中涉及的时间复杂度这里不做过多介绍,博主在本文中根据每道题的侧重点不同分别讲一种排序算法
快速排序使用分治法(Divide and Conquer)
策略来把一个序列分为较小和较大的2
个子序列,然后递归的排序两个子序列
基本步骤
python代码解法(优化前):
class Solution: def partition(self, nums, low, high): pivot = nums[low] while low < high: while low < high and nums[high] >= pivot: # 当nums[right]==pivot的时候 high -= 1 nums[low] = nums[high] while low < high and nums[low] < pivot: low += 1 nums[high] = nums[low] nums[low] = pivot return low def quick_sort(self, nums, l, h): if l < h: point = self.partition(nums, l, h) self.quick_sort(nums, l, point - 1) self.quick_sort(nums, point + 1, h) def sortArray(self, nums: List[int]) -> List[int]: self.quick_sort(nums, 0, len(nums) - 1) return nums
选取基准值pivot
也有多种方式,且选取pivot
的方法对排序的时间性能有着决定性的影响,例如对于一个逆序数组,如果每次选取数组中的第一个元素为pivot
,那么将其正序排列的过程将会变得非常慢
如果没有针对特殊测试用例:针对顺序数组或者逆序数组,一定要随机化选择切分元素(pivot)
,否则在输入数组基本有序或者逆序的时候,快速排序会变得非常慢
python代码解法(优化后-随机选择partition):
import random class Solution: def partition(self, nums, low, high): pivot = nums[low] while low < high: while low < high and nums[high] >= pivot: # 当nums[right]==pivot的时候 high -= 1 nums[low] = nums[high] while low < high and nums[low] < pivot: low += 1 nums[high] = nums[low] nums[low] = pivot return low def randomPartition(self, arr, low, high): pivot_idx = random.randint(low, high) arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low] return self.partition(arr, low, high) def quick_sort(self, nums, l, h): if l < h: mid = self.randomPartition(nums, l, h) # 以mid为分割点【随机选择pivot】 self.quick_sort(nums, l, mid - 1) self.quick_sort(nums, mid + 1, h) def sortArray(self, nums: List[int]) -> List[int]: self.quick_sort(nums, 0, len(nums) - 1) return nums
Leetcode75. 颜色分类:中等题 (详情点击链接见原题)
给定一个包含红色、白色和蓝色、共
n
个元素的数组nums
,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列
p0
的值初始化为 0
,p2
的初始值为n - 1
,在遍历的过程中,我们需要找出所有的 0
交换到数组头部,找出所有的 2
交换至数组尾部
由于此时其中一个指针 p2
是从右向左移动的,因此当我们在从左向右遍历整个数组时,如果遍历到的位置超过了 p2
,那么就可以直接停止遍历了
python代码解法:
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) p0, p2 = 0, n - 1 i = 0 while i <= p2: # i指针从左往右扫描 while i <= p2 and nums[i] == 2: # case:i扫描的过程中如果nums[i]=2,不断将其与nums[p2]进行交换直到新的nums[i]不为2,如果i指向的位置大于p2直接停止遍历 nums[i], nums[p2] = nums[p2], nums[i] p2 -= 1 if nums[i] == 0: # case:i扫描的过程中如果nums[i]=0,将其与nums[p0]进行交换,并将p0向后移动一个位置 nums[i], nums[p0] = nums[p0], nums[i] p0 += 1 i += 1
前文中只字未提的堆排序在TopK
问题中可以发挥它真正的威力,所以我们在下面的几道题中仔细看看堆排序的底层实现原理
堆排序 Heapsort
是指利用堆 heap
这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点
对于一个待排序的包含 n
个元素的数组 nums
,堆排序的步骤如下
n-1
个元素重新构造成一个大根堆(小根堆),如此便可得到原数组 n
个元素中的次大值(次小值)Leetcode414. 第三大的数:中等题 (详情点击链接见原题)
给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数
python代码解法:
class Solution: def thirdMax(self, nums: List[int]) -> int: def max_heapify(heap, parent, heap_size): child = 2 * parent + 1 while child < heap_size: if child + 1 < heap_size and heap[child + 1] > heap[child]: child = child + 1 if heap[child] > heap[parent]: heap[child], heap[parent] = heap[parent], heap[child] parent = child child = 2 * parent + 1 else: break nums = list(set(nums)) # 1.利用set()方法过滤掉重复元素 n = len(nums) for i in range((n - 1) // 2, -1, -1): # 2.将题目所给的nums数组调整为一个最大堆 max_heapify(nums, i, n) if len(nums) >= 3: # 3.如果nums的规模大于等于3 for i in range(n - 1, n - 4, -1): nums[0], nums[i] = nums[i], nums[0] # 4.将堆顶元素与末尾元素互换 max_heapify(nums, 0, i) # 5.堆的规模-1,从堆顶开始将剩余元素重新调整为一个最大堆 return nums[-3] # 6.1 返回第三大的元素 else: return nums[0] # 6.2 返回最大的堆顶元素
Leetcode215:数组中的第K个最大元素:中等题 (详情点击链接见原题)
给定整数数组
nums
和整数k
,请返回数组中第k
个最大的元素。
请注意,你需要找的是数组排序后的第k
个最大的元素,而不是第k
个不同的元素
python代码解法:
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def max_heapify(heap, parent, heap_size): child = 2 * parent + 1 while child < heap_size: if child + 1 < heap_size and heap[child + 1] > heap[child]: child = child + 1 if heap[child] > heap[parent]: heap[child], heap[parent] = heap[parent], heap[child] parent = child child = 2 * parent + 1 else: break n = len(nums) for i in range((n - 1) // 2, -1, -1): # 1.从第一个非叶子节点开始调整为最大堆 max_heapify(nums, i, n) for i in range(n - 1, n - k - 1, -1): nums[0], nums[i] = nums[i], nums[0] # 2.将堆顶元素与末尾元素互换 max_heapify(nums, 0, i) # 3.堆的规模-1,从堆顶开始将剩余元素重新调整为一个最大堆 return nums[-k]
在TopK
问题中,和堆排序有点区别,因为在 TopK
问题中,涉及到维护一个规模为 K
的最大堆最小堆的问题,这就没有现成的数组让我们建堆,
TOPK
问题解题步骤
K
的大根堆或者小根堆K
TOPK
大或者 TOPK
小的元素Leetcode347. 前 K 个高频元素:中等题 (详情点击链接见原题)
给你一个整数数组
nums
和一个整数k
,请你返回其中出现频率前k
高的元素。你可以按 任意顺序 返回答案
解题思路
cnt
,转换为 list
k
个数构造规模为k
的最小堆min_heap
cnt
中剩余的数据,大于堆顶则入堆,对堆顶节点进行下沉操作维护规模为k
的最小堆cnt
后遍历 min_heap
,提取min_heap
中的键python代码解法:
class Solution: def sift_up(self, heap): child_index = len(heap) - 1 temp = heap[child_index] parent_index = (child_index - 1) // 2 while parent_index >= 0 and temp[1] < heap[parent_index][1]: heap[child_index] = heap[parent_index] child_index = parent_index parent_index = (child_index - 1) // 2 heap[child_index] = temp def sift_down(self, heap, parent_index, heap_size): temp = heap[parent_index] child_index = 2 * parent_index + 1 while child_index < heap_size: if child_index + 1 < heap_size and heap[child_index][1] > heap[child_index + 1][1]: child_index = child_index + 1 if heap[child_index][1] < temp[1]: heap[parent_index] = heap[child_index] parent_index = child_index child_index = 2 * parent_index + 1 else: break heap[parent_index] = temp def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = Counter(nums) cnt = list(cnt.items()) min_heap = [] for i in range(k): min_heap.append(cnt[i]) self.sift_up(min_heap) for i in range(k, len(cnt)): if cnt[i][1] > min_heap[0][1]: min_heap[0] = cnt[i] self.sift_down(min_heap, 0, k) return [item[0] for item in min_heap]
Leetcode692. 前K个高频单词:中等题 (详情点击链接见原题)
给定一个单词列表
words
和一个整数k
,返回前k
个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序
python代码解法:
import heapq from typing import List from collections import Counter class Word: def __init__(self, key, value): self.key = key self.value = value def __lt__(self, other): if self.value != other.value: return self.value < other.value return self.key > other.key # 从小到大 class Solution: def topKFrequent(self, words: List[str], k: int) -> List[str]: cnt = Counter(words) hp = [] for key, value in cnt.items(): heapq.heappush(hp, Word(key, value)) while len(hp) > k: heapq.heappop(hp) hp.sort(reverse=True) return [x.key for x in hp]
Leetcode703. 数据流中的第 K 大元素:中等题 (详情点击链接见原题)
设计一个找到数据流中第
k
大元素的类(class)。注意是排序后的第k
大元素,不是第k
个不同的元素
解题思路
K
的小根堆,在初始化的时候,保证堆中的元素个数不超过K
add()
的时候,将新元素 push()
到堆中,如果此时堆中元素超过了K
,那么需要把堆中的最小元素pop()
出来K
大元素关于heapq
模块的使用大家可以参考Python heapq库的用法介绍,实际的面试中,大家最好不要用模块和方法实际操作,其实heapq
底层的原理就是构建/维护一个最大堆/最小堆的操作,即排序算法中堆排序的底层实现,这里只是介绍另一种实现方法,大家如果对堆的相关操作感兴趣的话可以先手写堆排序(当你了解底层原理后再使用这个模块)
heappush(heap, num)
: 先创建一个空堆,然后将数据一个一个地添加到堆中。每添加一个数据后,heap
都满足小顶堆的特性,对应堆的插入操作【节点上浮】
heapify(array)
:直接将数据列表调整成一个小顶堆
heappop(heap)
: 将堆顶的数据出堆,并将堆中剩余的数据构造成新的小顶堆,对应堆的删除操作【节点下沉】
python代码解法1:
调用python
库函数heapq
import heapq
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.heap = nums
heapq.heapify(self.heap) # 1.将题目所给nums初始化为一个小根堆
def add(self, val: int) -> int:
heapq.heappush(self.heap, val) # 2.在堆中添加元素并维持小根堆的特性
while len(self.heap) > self.k:
heapq.heappop(self.heap) # 3.堆尾元素与堆顶元素互换,互换后将堆尾元素pop,对堆顶节点进行下沉操作重新维护一个最小堆
return self.heap[0]
python代码解法2:
手动实现堆的底层代码(困难做法)
class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.heap = nums for i in range(len(self.heap) // 2 - 1, -1, -1): # 1.从第一个非叶子节点开始调整为最小堆 self.min_heapify(self.heap, i, len(self.heap)) def min_heapify(self, heap, parent, heap_size): # 调整为最小堆的函数 child = 2 * parent + 1 while child < heap_size: if child + 1 < heap_size and heap[child + 1] < heap[child]: child = child + 1 if heap[child] < heap[parent]: heap[child], heap[parent] = heap[parent], heap[child] parent = child child = 2 * parent + 1 else: break def sift_up(self, min_heap): # 在堆的末尾插入节点的上浮操作 child_index = len(min_heap) - 1 parent_index = (child_index - 1) // 2 temp = min_heap[child_index] while child_index > 0 and temp < min_heap[parent_index]: min_heap[child_index] = min_heap[parent_index] child_index = parent_index parent_index = (child_index - 1) // 2 min_heap[child_index] = temp def sift_down(self, min_heap, parent_index, heap_size): # 针对于堆顶节点的下沉操作 temp = min_heap[0] child_index = 2 * parent_index + 1 while child_index < heap_size: if child_index + 1 < heap_size and min_heap[child_index + 1] < min_heap[child_index]: child_index += 1 if temp > min_heap[child_index]: min_heap[parent_index] = min_heap[child_index] parent_index = child_index child_index = 2 * parent_index + 1 else: break min_heap[parent_index] = temp def add(self, val: int) -> int: self.heap.append(val) self.sift_up(self.heap) n = len(self.heap) while n > self.k: self.heap[0] = self.heap[-1] self.heap.pop() self.sift_down(self.heap, 0, n - 1) n -= 1 return self.heap[0]
Leetcode147. 对链表进行插入排序:中等题 (详情点击链接见原题)
给定单个链表的头
head
,使用 插入排序 对链表进行排序,并返回 排序后链表的头
python代码解法:
class Solution: def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode() dummy_head.next = head cur = head while cur and cur.next: if cur.val <= cur.next.val: cur = cur.next else: temp = cur.next # 保存节点 cur.next = cur.next.next # 删除节点 prev = dummy_head while prev.next.val <= temp.val: prev = prev.next temp.next = prev.next prev.next = temp return dummy_head.next
Leetcode88. 合并两个有序数组:简单题 (详情点击链接见原题)
给你两个按 非递减顺序 排列的整数数组
nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目
python代码解法:
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ p1, p2 = m - 1, n - 1 # 创建两个指针分别指向nums1和nums2的第一个位置 k = m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[k] = nums1[p1] p1 -= 1 else: nums1[k] = nums2[p2] p2 -= 1 k -= 1 while p2 >= 0: nums1[k] = nums2[p2] p2 -= 1 k -= 1
Leetcode21. 合并两个有序链表:简单题 (详情点击链接见原题)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
python代码解法:
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = p = ListNode() # 创建一个虚拟头结点dummy_head用于返回链表,p指针用来扫描
l1, l2 = list1, list2 # l1和l2分别指向list1和list2的头结点
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 if l1 else l2
return dummy_head.next
Leetcode23. 合并 K 个升序链表:困难题 (详情点击链接见原题)
给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表
python代码解法:
class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: dummy_head = ListNode() # 1.创建一个虚拟头结点用于返回最终结果 for li in lists: # 2.按照合并两个有序链表的思路逐个对列表中的链表进行合并 cur_node = dummy_head # 3.cur_node指针重新指向合并后的链表的起始位置 p1, p2 = cur_node.next, li while p1 and p2: if p1.val < p2.val: cur_node.next = p1 p1 = p1.next else: cur_node.next = p2 p2 = p2.next cur_node = cur_node.next cur_node.next = p1 if p1 else p2 # 4.如果其中某个链表提前遍历完毕,将剩余链表直接挂在后面 return dummy_head.next
Leetcode148. 排序链表:中等题 (详情点击链接见原题)
给你链表的头结点
head
,请将其按 升序 排列并返回 排序后的链表
分割cut环节:
找到当前链表中点,并从中点
将链表断开
fast
, slow
快慢指针法,奇数个节点找到中点,偶数个节点找到中心左边的节点slow
后,执行slow.next=None
将链表切断head
和中心节点slow
的下一个节点tmp
(因为链表是从slow
切断的)head.next==None
说明只有一个节点,直接返回此节点合并 merge
环节:
将两个排序链表合并,转换为一个有序链表
ListNode h
作为头部left
, right
分别指向两链表的头部,比较两指针处节点值大小,由小到大加入合并链表头部,指针交替前进直至添加完两个链表ListNode h
作为头部的下一个节点 h.next
O(l + r)
,l, r
分别代表两个链表长度python代码解法:
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def sortList(self, head: ListNode) -> ListNode: if not head or not head.next: # 1.递归出口 return head # cut the LinkedList at the mid index. slow, fast = head, head.next while fast and fast.next: # 2.慢指针每走一步,快指针往前走两步,循环找到中间节点 fast, slow = fast.next.next, slow.next mid, slow.next = slow.next, None # 3.从中间节点处切断. # recursive for cutting. left, right = self.sortList(head), self.sortList(mid) h = res = ListNode(0) # 4.合并了两个有序链表的操作(即上面的第二题) while left and right: if left.val < right.val: h.next, left = left, left.next else: h.next, right = right, right.next h = h.next h.next = left if left else right return res.next # 5.返回合并后的链表
Leetcode164. 最大间距:中等题 (详情点击链接见原题)
给定一个无序的数组
nums
,返回 数组在排序之后,相邻元素之间最大的差值 。如果数组元素个数小于2
,则返回0
该题的难点在于如何用线性的时空复杂度来解决
桶排序的核心问题?每个桶的长度是多少?
我们期望将数组中的各个数等距离分配,也就是每个桶的长度相同
确定桶的数量
Leetcode621. 任务调度器:中等题 (详情点击链接见原题)
给你一个用字符数组
tasks
表示的CPU
需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在1
个单位时间内执行完。在任何一个单位时间,CPU
可以完成一个任务,或者处于待命状态
解题思路
建立大小为 n + 1
的桶子,个数为任务数量最多的那个任务,我们可以把一个桶子看作一轮任务
先从最简单的情况看,就算没有其他任务,我们完成任务 A
所需的时间应该是 (6 - 1) * 3 + 1
,因为最后一个桶子,不存在等待时间
C
其实并没有对总体时间产生影响,因为它被安排在其他任务的冷却期间,而 B
和 A
数量相同,这导致在最后一个桶子中我们需要多执行一次 B
任务,现在需要的时间是 (6 - 1) * 3 + 2 = 17
总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数
两个图对比可知我们刚排满了任务,此时所需的时间是 17
,如果还要执行两次任务 F
,此时我们执行任务所需的时间就是任务的数量
记录最大任务数量 N
,看下任务数量并列最多的任务有多少个,即最后一个桶子的任务数,计算 time1 = nums1 = (N - 1) * (n + 1) + x
,time2 = len(tasks)
这是不存在空闲时间的情况(当任务种类较多时,冷却时间不够用来处理其他任务,冷却时间已被填满)
python代码解法:
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
arr = [0] * 26 # 保存任务和任务数量的哈希表
max_tasks = 0 # 记录最多的任务数量
count = 0 # 最多任务数量的个数
for task in tasks:
arr[ord(task) - ord('A')] += 1
for i in range(26):
if arr[i] > max_tasks:
max_tasks = arr[i]
count = 1
elif max_tasks == arr[i]:
count += 1
return max(len(tasks), (max_tasks - 1) * (n + 1) + count)
面试题.手机App防沉迷系统:中等题 (详情点击链接见原题)
智能手机方便了我们生活的同时,也侵占了我们不少的时间。
“手机App防沉迷系统”能够让我们每天合理地规划手机App使用时间,在正确的时间做正确的事
解题思路
提前将输入的 APP
按照优先级降序【此时我们会先注册优先级高的 APP
,后注册的 APP
只要和前面注册的 APP
发生冲突,必然无法注册】
如果不存在低优先级的 APP
和高优先级的 APP
有冲突,则高优先级的 APP
提前注册对结果无影响
如果存在 低优先级的 APP
和 高优先级的 APP
有冲突,则无论低优先级的先注册还是后注册,结果都是低优先级的 APP
无法注册
python代码解法:
""" App1 1 09:00 10:00 App2 2 09:10 09:30 """ def convert(time): # 时间格式 HH:MM,小时和分钟都是两位,不足两位前面补0 hours, minutes = map(int, time.split(":")) return hours * 60 + minutes def hasInterSection(a, b): if b[2] <= a[2] < b[3] or a[2] <= b[2] < a[3]: return True return False class Solution: def getResult(self, app_list): app_list.sort(key=lambda x: -x[1]) registers = [] for app in app_list: conflict = False for register in registers: if hasInterSection(app, register): conflict = True break if conflict: continue registers.append(app) ans = "NA" # 注册成功的App时段之间互不冲突,因此queryTime只会对应一个App for registered in registers: if registered[2] <= queryTime < registered[3]: ans = registered[0] break return ans if __name__ == '__main__': s = Solution() # 输入获取 app_num = int(input()) # 注册的APP数量 # 需要注册的App:(APP名称,优先级,起始时间,结束时间) apps = [] for _ in range(app_num): name, priority, start, end = input().split(" ") apps.append((name, int(priority), convert(start), convert(end))) # 需要查询的时间点 queryTime = convert(input()) # 需要查询的时间结点 print(s.getResult(apps))
本文给大家介绍了面试中常考的关于排序问题的算法题,本文重点介绍了计数排序、快速排序、堆排序(重点)、插入排序、归并排序(重点)、桶排序、还有自定义排序规则,最后祝大家面试顺利,拿到心仪的offer~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。