今天是day10
題目一：滑動窗口最大值，要求從一個大小為k的滑動窗口從數組的最左端移動到數組的最右側最終返回窗口中的最大值
from collections import deque
class MyQueue:
def __init__(self):
"雙端隊列"
self.queue = deque()
def pop(self,value):
"確保隊列不為空且要彈出的值等于隊列中的第一個值"
"因為隊列是單調遞減的，所以當隊列的第一個值等于當前要彈出的值時，這個值應該是隊列中最大的值。"
if self.queue and value == self.queue[0]:
self.queue.popleft()
def push(self,value):
"確保隊列不為空且當前要添加的值大于隊列中最后一個值"
"因為當前值大于隊尾值，所以隊尾值不可能成為滑動窗口中的最大值，需要被移除。"
while self.queue and value > self.queue[-1]:
self.queue.pop()
"將當前值添加到隊列的右端，保持隊列的單調遞減性質"
self.queue.append(value)
def front(self):
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = MyQueue()
result = []
"對于給定的滑動數組長度進行分割將值直接推入隊列"
for i in range(k):
que.push(nums[i])
"此時確保了隊列的值的單調，即第一個數值必定為最大值，故直接將其加入至result中"
result.append(que.front())
"如下幾步實現了滑動"
for i in range(k,len(nums)):
que.pop(nums[i-k])
que.push(nums[i])
result.append(que.front())
return result
type MyQueue struct {
queue []int
}
//初始化聲明一個數組
func NewMyQueue() *MyQueue{
return &MyQueue{
queue:make([]int,0),
}
}
//取數組的第一個元素
func (m *MyQueue) Front() int{
return m.queue[0]
}
//取數組的最后一個元素
func (m *MyQueue) Back() int{
return m.queue[len(m.queue)-1]
}
//判空
func (m *MyQueue) Empty() bool {
return len(m.queue) == 0
}
//確保隊列不為空且當前要添加的值大于隊列中最后一個值,因為當前值大于隊尾值，所以隊尾值不可能成為滑動窗口中的最大值，需要被移除
func (m *MyQueue) Push(val int) {
for !m.Empty()&& val > m.Back() {
m.queue = m.queue[:len(m.queue)-1]
}
m.queue = append(m.queue,val)
}
//因為隊列是單調遞減的，所以當隊列的第一個值等于當前要彈出的值時，這個值應該是隊列中最大的值
func (m *MyQueue) Pop(val int) {
if !m.Empty() && val == m.Front() {
m.queue = m.queue[1:]
}
}
func maxSlidingWindow(nums []int, k int) []int {
queue :=NewMyQueue()
length := len(nums)
res := make([]int,0)
for i:=0;i<k;i++{
queue.Push(nums[i])
}
res = append(res,queue.Front())
for i:=k;i<length;i++{
queue.Pop(nums[i-k])
queue.Push(nums[i])
res = append(res,queue.Front())
}
return res
}
題目二：
前k個高頻元素，給定一個非空的整數數組，返回其中的出現頻率前k個高的元素
"導入 Python 的 heapq 模塊，該模塊提供了堆（heap）相關的函數和類。"
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
map_ = {}
"統計數組中每個元素的出現頻率，并將其存儲在字典 map_ 中。如果字典中不存在該元素，則初始化其出現頻率為 0，然后加 1。"
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i],0) + 1
"創建了一個空列表 pri_que，用于存儲元素頻率和元素值的元組，并將其作為堆（heap）使用。"
pri_que = []
"將元素的頻率和值作為一個元組 (freq, key)，壓入堆 pri_que 中。由于 Python 的堆默認是最小堆（即根節點的值最小），所以這里存儲的是 (頻率, 元素值) 的元組。"
for key,freq in map_.items():
heapq.heappush(pri_que,(freq,key))
"如果堆的大小超過了 k，則執行下面的操作。這是為了保持堆中始終只有前 k 高的元素。"
if len(pri_que) > k:
heapq.heappop(pri_que)
result = [0] * k
"逆向遍歷 result 列表，從后向前依次填充元素。"
for i in range(k-1,-1,-1):
"將堆 pri_que 中的元素依次彈出，并將其值（即元素值）賦給 result[i]，這樣 result 列表中存儲的就是出現頻率前 k 高的元素。"
result[i] = heapq.heappop(pri_que)[1]
return result
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
time_dict = defaultdict(int)
for num in nums:
"更新字典 time_dict 中元素 num 的出現頻率，如果 num 不在字典中，則默認值為 0。"
time_dict[num] +=1
index_dict = defaultdict(list)
for key in time_dict:
"將元素 key 添加到字典 index_dict 中對應頻率的列表中。"
index_dict[time_dict[key]].append(key)
"獲取字典 index_dict 的所有鍵（即出現的頻率），并轉換為列表。"
key = list(index_dict.keys())
"頻率小的元素會排在列表的前面。"
key.sort()
result = []
cnt = 0
"循環條件是頻率列表不為空且已經添加到 result 中的元素個數不等于 k。"
while key and cnt != k:
"將頻率列表中最大的頻率對應的元素列表添加到 result 中。"
result += index_dict[key[-1]]
"更新已經添加到 result 中的元素個數。"
cnt += len(index_dict[key[-1]])
"彈出頻率列表中最大的頻率。"
key.pop()
"返回 result 列表中前 k 個元素，即出現頻率前 k 高的元素。"
return result[0:k]
//這行定義了一個新的類型 IHeap，它是一個切片，每個元素是長度為 2 的整數數組
type IHeap [][2] int
//這段代碼定義了類型 IHeap 的方法 Len()，返回切片的長度，它實現了 heap.Interface 接口的 Len() 方法
func (h IHeap) Len() int {
return len(h)
}
//這段代碼定義了類型 IHeap 的方法 Less()，用于定義堆的排序規則。這里是根據切片中元素的第二個值進行比較，從小到大排序。它實現了 heap.Interface 接口的 Less() 方法。
func (h IHeap) Less(i,j int) bool {
return h[i][1] < h[j][1]
}
//這段代碼定義了類型 IHeap 的方法 Swap()，用于交換切片中的兩個元素。它實現了 heap.Interface 接口的 Swap() 方法。
func (h IHeap) Swap(i,j int) {
h[i],h[j] = h[j],h[i]
}
//這段代碼定義了類型 IHeap 的方法 Push()，用于向堆中添加元素。它首先將接收到的元素類型轉換為 [2]int，然后將其追加到切片中。
func (h *IHeap) Push(x interface{}) {
*h = append(*h,x.([2]int))
}
//這段代碼定義了類型 IHeap 的方法 Pop()，用于從堆中彈出元素。它首先保存當前堆的副本，然后獲取最后一個元素，并將切片的長度減少 1。最后，返回被彈出的元素。
func (h *IHeap) Pop() interface{} {
old:=*h
n:=len(old)
x:=old[n-1]
*h = old[0:n-1]
return x
}
//這段代碼是解決「前 K 個高頻元素」問題的主要函數。它首先創建了一個映射 map_num，用于存儲每個元素的頻率。然后創建了一個 IHeap 類型的指針 h，并通過 heap.Init() 方法將其初始化為空堆。
func topKFrequent(nums []int, k int) []int {
map_num := map[int]int{}
for _,item := range nums{
map_num[item] ++
}
h:=&IHeap{}
heap.Init(h)
//這是一個循環，遍歷了 map_num 中的鍵值對，即元素及其頻率。
for key,value := range map_num{
//將元素及其頻率作為一個長度為 2 的數組 [2]int 添加到堆 h 中。
heap.Push(h,[2]int{key,value})
//如果堆的長度超過了 k，則執行以下操作：heap.Pop(h)：從堆中彈出一個元素，因為我們只需要前 k 個高頻元素。
if h.Len()>k{
heap.Pop(h)
}
}
//創建一個長度為 k 的整數切片 res，用于存儲前 k 個高頻元素。遍歷 res 中的每個位置。從堆中彈出元素 [2]int，并將其中的第一個值（元素本身）存儲到 res 中。這里之所以使用 k-i-1 是因為堆是按照從小到大排序的，而我們需要的是前 k 個高頻元素，所以要從 res 的末尾開始存儲。
res:=make([]int,k)
for i:=0;i<k;i++{
res[k-i-1] = heap.Pop(h).([2]int)[0]
}
return res
}
func topKFrequent(nums []int, k int) []int {
ans:=[]int{}
//初始化一個映射 map_num，用于統計每個數字在切片 nums 中出現的次數。
map_num:=map[int]int{}
//遍歷切片 nums 中的每個元素 item，并將元素作為鍵存儲在 map_num 中，值為該元素出現的次數。這樣，map_num 就記錄了 nums 中每個元素的頻率。
for _,item:=range nums {
map_num[item]++
}
//遍歷 map_num 中的鍵（即切片 nums 中的元素），并將鍵添加到結果切片 ans 中。這樣，ans 中存儲的是 nums 中出現過的不重復的元素。
for key,_ := range map_num{
ans = append(ans,key)
}
//使用 sort.Slice 函數對切片 ans 進行排序。排序的方式是根據每個元素在 map_num 中對應的值（即元素在 nums 中出現的頻率）進行降序排序。
sort.Slice(ans,func (a,b int) bool {
return map_num[ans[a]] > map_num[ans[b]]
})
//返回排序后的結果切片 ans 的前 k 個元素，即出現頻率最高的前 k 個元素。
return ans[:k]
}
浙公網安備 33010602011771號