ARTS Week 34
ARTS Week 34ARTS Week 34
不勝，則亡。但，不戰，就不會勝利。
Algoithm
零錢兌換
概述
給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回-1。
你可以認為每種硬币的數量是無限的。
示例1：
輸入：coins = [1, 2, 5], amount = 11 輸出：3 解釋：11 = 5 + 5 + 1 示例 2：
輸入：coins = [2], amount = 3 輸出：-1 示例 3：
輸入：coins = [1], amount = 0 輸出：0 示例 4：
輸入：coins = [1], amount = 1 輸出：1 示例 5：
輸入：coins = [1], amount = 2 輸出：2
提示：
1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
coding
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
Review
12 Things I Stole From People More Successful Than Me
概述
- Pare Down The Number of Decisions You Make Every Day
- Tear Up Your To-Do List
- Turn “Have-To” Into “Get-To”
- Use People’s Favorite Sound
- Look At People’s Feet
- Mise En Place
- Don’t Be A Donkey
- Stop Using The Number 7
- Be A Whiner
- Take Sabbaticals From Your Work
- Never Ask For Someone’s ‘Opinion’
- Practice What’s It’s Like To Be Poor
Tip
Redis-删除資料後記憶體未減少
概述
redis 删除後，還沒有釋放記憶體。
- 當資料删除後，Redis 釋放的記憶體空間會由記憶體配置設定器管理，并不會立即傳回給作業系統。是以，作業系統仍然會記錄着給 Redis 配置設定了大量記憶體。
記憶體碎片
原因
内因是作業系統的記憶體配置設定機制，外因是 Redis 的負載特征。
内因：記憶體配置設定器的配置設定政策
Redis 可以使用 libc、jemalloc、tcmalloc 多種記憶體配置設定器來配置設定記憶體，預設使用 jemalloc。
jemalloc 的配置設定政策之一，是按照一系列固定的大小劃分記憶體空間，例如 8 位元組、16 位元組、32 位元組、48 位元組，…, 2KB、4KB、8KB 等。當程式申請的記憶體最接近某個固定值時，jemalloc 會給它配置設定相應大小的空間。
外因：鍵值對大小不一樣和删改操作
- 存儲資料的大小不一緻
- 鍵值對會被修改和删除,導緻空間的擴容和釋放
檢視方法 INFO 指令
INFO memory
# Memory
used_memory:1073741736
used_memory_human:1024.00M
used_memory_rss:1997159792
used_memory_rss_human:1.86G
mem_fragmentation_ratio:1.86
mem_fragmentation_ratio 的名額，就是記憶體碎片率。
mem_fragmentation_ratio = used_memory_rss/ used_memory
經驗閥值
- mem_fragmentation_ratio 大于 1 但小于 1.5
- mem_fragmentation_ratio 大于 1.5
處理辦法
- 重新開機redis
- 未開啟 AOF，可能會資料丢失
- 恢複時間過長
- Redis 自身提供了一種記憶體碎片自動清理的方法
-
ARTS Week 34ARTS Week 34
-
config set activedefrag yes
# 設定redis相關系統
# 表示記憶體碎片的位元組數達到 100MB 時，開始清理；
active-defrag-ignore-bytes 100mb
# 表示記憶體碎片空間占作業系統配置設定給 Redis 的總空間比例達到 10% 時，開始清理。
active-defrag-threshold-lower 10
### 為了不影響其redis性能
# 表示自動清理過程所用 CPU 時間的比例不低于 25%，保證清理能正常開展；
active-defrag-cycle-min 25
# 表示自動清理過程所用 CPU 時間的比例不高于 75%，一旦超過，就停止清理，進而避免在清理時，大量的記憶體拷貝阻塞 Redis，導緻響應延遲升高。
active-defrag-cycle-max 75
Share
0-1背包類型題目示例
概述
最低票價
描述
在一個火車旅行很受歡迎的國度，你提前一年計劃了一些火車旅行。在接下來的一年裡，你要旅行的日子将以一個名為days的數組給出。每一項是一個從1到365的整數。
火車票有三種不同的銷售方式：
- 一張為期一天的通行證售價為costs[0] 美元；
- 一張為期七天的通行證售價為costs[1] 美元；
- 一張為期三十天的通行證售價為costs[2] 美元。
通行證允許數天無限制的旅行。 例如，如果我們在第 2 天獲得一張為期 7 天的通行證，那麼我們可以連着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
傳回你想要完成在給定的清單days中列出的每一天的旅行所需要的最低消費。
示例 1：
輸入：days = [1,4,6,7,8,20], costs = [2,7,15]
輸出：11
解釋：
例如，這裡有一種購買通行證的方法，可以讓你完成你的旅行計劃：
在第 1 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 買了一張為期 7 天的通行證，它将在第 3, 4, …, 9 天生效。
在第 20 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它将在第 20 天生效。
你總共花了 $11，并完成了你計劃的每一天旅行。
示例 2：
輸入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
輸出：17
解釋：
例如，這裡有一種購買通行證的方法，可以讓你完成你的旅行計劃：
在第 1 天，你花了 costs[2] = $15 買了一張為期 30 天的通行證，它将在第 1, 2, …, 30 天生效。
在第 31 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它将在第 31 天生效。
你總共花了 $17，并完成了你計劃的每一天旅行。
提示：
1 <= days.length <= 365
1 <= days[i] <= 365
days按順序嚴格遞增
costs.length == 3
1 <= costs[i] <= 1000
分析
狀态：是否出門
-
是否出門
如果不出門，那麼dp[i]=dp[i-1]
如果出門，那麼：
dp[i] = min(dp[i-1]+costs[0],dp[i-7]+costs[1],dp[i-30]+costs[2])
coding
class Solution:
def mincostTickets(self, days: list[int], costs: list[int]) -> int:
max_day = days[-1]
# 這裡是為了規避不足31天的結果
dp = [0]*(max_day+31)
days_set = set(days)
#
for i in range(max_day,-1,-1):
if i in days_set:
dp[i] = min(dp[i+1]+costs[0],dp[i+7]+costs[1],dp[i+30]+costs[2])
else:
dp[i] = dp[i+1]
print(dp)
return dp[0]