134. 加油站
在一條環(huán)路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升。
你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā)，開始時油箱為空。
如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1。
如果 sum(gas) < sum(cost) ，那么不可能環(huán)行一圈，這種情況下答案是 -1 。
對于加油站 i ，如果 gas[i] - cost[i] < 0 ，則不可能從這個加油站出發(fā)，因?yàn)樵谇巴?i + 1 的過程中，汽油就不夠了。
class Solution:
def canCompleteCircuit(self, gas, cost):
n = len(gas)
total_residue_tank, next_residue_tank = 0, 0
starting_station = 0
for i in range(n):
total_residue_tank += gas[i] - cost[i] # 所有加的油減去所有的消耗，最后剩下的油
next_residue_tank += gas[i] - cost[i] # 到達(dá)下一站后油箱里的油
# 能否到達(dá)下一站
if next_residue_tank < 0:
# 不能到達(dá)下一站以下一站為起點(diǎn)
starting_station = i + 1
# 此時油箱里的油為空
next_residue_tank = 0
return starting_station if total_residue_tank >= 0 else -1
146. LRU緩存機(jī)制
設(shè)計(jì)和實(shí)現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字/值」。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
實(shí)現(xiàn)一個可以存儲 key-value 形式數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，并且可以記錄最近訪問的 key 值。首先想到的就是用字典來存儲 key-value 結(jié)構(gòu)，這樣對于查找操作時間復(fù)雜度就是 O(1)O(1)。
但是因?yàn)樽值浔旧硎菬o序的，所以我們還需要一個類似于隊(duì)列的結(jié)構(gòu)來記錄訪問的先后順序，這個隊(duì)列需要支持如下幾種操作：
在末尾加入一項(xiàng)
去除最前端一項(xiàng)
將隊(duì)列中某一項(xiàng)移到末尾
# 雙向鏈表
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.nex = None
self.pre = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
# 新建兩個節(jié)點(diǎn) head 和 tail
self.head = ListNode()
self.tail = ListNode()
# 初始化鏈表為 head <-> tail
self.head.nex = self.tail
self.tail.pre = self.head
# 因?yàn)間et與put操作都可能需要將雙向鏈表中的某個節(jié)點(diǎn)移到末尾，所以定義一個方法
def move_to_end(self, key):
node = self.hashmap[key]
# 先將哈希表key指向的節(jié)點(diǎn)node拎出來
node.pre.nex = node.nex
node.nex.pre = node.pre
# 之后將node插入到尾節(jié)點(diǎn)前
node.pre = self.tail.pre
node.nex = self.tail
self.tail.pre.nex = node
self.tail.pre = node
def get(self, key: int) -> int:
if key in self.hashmap:
# 如果已經(jīng)在鏈表中了久把它移到末尾（變成最新訪問的）
self.move_to_end(key)
node = self.hashmap.get(key, -1)
return node if node == -1 else node.value
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
# 如果key本身已經(jīng)在哈希表中了就不需要在鏈表中加入新的節(jié)點(diǎn)
# 但是需要更新字典該值對應(yīng)節(jié)點(diǎn)的value
self.hashmap[key].value = value
self.move_to_end(key)
else:
if len(self.hashmap) == self.capacity:
# 去掉哈希表對應(yīng)項(xiàng)
self.hashmap.pop(self.head.nex.key)
# 去掉最久沒有被訪問過的節(jié)點(diǎn)，即頭節(jié)點(diǎn)之后的節(jié)點(diǎn)
self.head.nex = self.head.nex.nex
self.head.nex.pre = self.head
# 如果不在的話就插入到尾節(jié)點(diǎn)前
new = ListNode(key, value)
self.hashmap[key] = new
new.pre = self.tail.pre
new.nex = self.tail
self.tail.pre.nex = new
self.tail.pre = new
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
202. 快樂數(shù)
定義為：對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和，然后重復(fù)這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。如果 可以變?yōu)? 1，那么這個數(shù)就是快樂數(shù)。
最終會得到 1。
最終會進(jìn)入循環(huán)。
值會越來越大，最后接近無窮大。
| Digits | Largest | Next |
|---|---|---|
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
| 13 | 9999999999999 | 1053 |
對于 3 位數(shù)的數(shù)字，它不可能大于 243。這意味著它要么被困在243 以下的循環(huán)內(nèi)，要么跌到 1。4 位或 4 位以上的數(shù)字在每一步都會丟失一位，直到降到 3 位為止。所以我們知道，最壞的情況下，算法可能會在 243 以下的所有數(shù)字上循環(huán)，然后回到它已經(jīng)到過的一個循環(huán)或者回到 11。但它不會無限期地進(jìn)行下去，所以我們排除第三種選擇。
# 檢測單鏈表是否有環(huán)，用快慢指針
class Solution:
def get_next(self, num):
all_squre_sum = 0
while num > 0:
num, digit = divmod(num, 10)
all_squre_sum += digit ** 2
return all_squre_sum
def isHappy(self, n: int) -> bool:
slow_index = n
fast_index = self.get_next(n)
while fast_index != 1 and slow_index != fast_index:
slow_index = self.get_next(slow_index)
fast_index = self.get_next(self.get_next(fast_index))
return fast_index == 1
289. 生命游戲
給定一個包含 m × n 個格子的面板，每一個格子都可以看成是一個細(xì)胞。每個細(xì)胞都具有一個初始狀態(tài)：1即為活細(xì)胞（live），或 0 即為死細(xì)胞（dead）。每個細(xì)胞與其八個相鄰位置（水平，垂直，對角線）的細(xì)胞都遵循以下四條生存定律：
1.如果活細(xì)胞周圍八個位置的活細(xì)胞數(shù)少于兩個，則該位置活細(xì)胞死亡；
2.如果活細(xì)胞周圍八個位置有兩個或三個活細(xì)胞，則該位置活細(xì)胞仍然存活；
3.如果活細(xì)胞周圍八個位置有超過三個活細(xì)胞，則該位置活細(xì)胞死亡；
4.如果死細(xì)胞周圍正好有三個活細(xì)胞，則該位置死細(xì)胞復(fù)活；
根據(jù)當(dāng)前狀態(tài)，寫一個函數(shù)來計(jì)算面板上所有細(xì)胞的下一個（一次更新后的）狀態(tài)。下一個狀態(tài)是通過將上述規(guī)則同時應(yīng)用于當(dāng)前狀態(tài)下的每個細(xì)胞所形成的，其中細(xì)胞的出生和死亡是同時發(fā)生的。
如果你直接根據(jù)規(guī)則更新原始數(shù)組，那么就做不到題目中說的 同步 更新。假設(shè)你直接將更新后的細(xì)胞狀態(tài)填入原始數(shù)組，那么當(dāng)前輪次其他細(xì)胞狀態(tài)的更新就會引用到當(dāng)前輪已更新細(xì)胞的狀態(tài)，但實(shí)際上每一輪更新需要依賴上一輪細(xì)胞的狀態(tài)，是不能用這一輪的細(xì)胞狀態(tài)來更新的。
拓展一些復(fù)合狀態(tài)使其包含之前的狀態(tài)。
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
neighbors = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
rows, cols = len(board), len(board[0])
# 遍歷面板每一個格子里的細(xì)胞,根據(jù)周圍細(xì)胞改變聯(lián)合狀態(tài)
for r in range(rows):
for c in range(cols):
# 對于每一個細(xì)胞統(tǒng)計(jì)其八個相鄰位置里的活細(xì)胞數(shù)量
live_neighbor = 0
for i in neighbors:
if 0 <= r+i[0] < rows and 0 <= c+i[1] < cols and abs(board[r+i[0]][c+i[1]]) == 1:
# abs() 因?yàn)楹竺鏁?改成-1
live_neighbor += 1
# 規(guī)則 2 不造成狀態(tài)變化
# 規(guī)則 1 或規(guī)則 3 活細(xì)胞，周圍活的少于兩個多于三個，死
if board[r][c] == 1 and (live_neighbor > 3 or live_neighbor < 2):
board[r][c] = -1
# 規(guī)則 4 死細(xì)胞，周圍活的為2或3，活
if board[r][c] == 0 and live_neighbor == 3:
board[r][c] = 2
# # 遍歷面板每一個格子里的細(xì)胞
# 遍歷 board 得到一次更新后的狀態(tài)
for r in range(rows):
for c in range(cols):
if board[r][c] > 0:
board[r][c] = 1
else:
board[r][c] = 0
371. 兩整數(shù)之和
正數(shù)的補(bǔ)碼就是原碼，而負(fù)數(shù)的補(bǔ)碼=原碼符號位不變，其他位按位取反后+1。
不使用運(yùn)算符 + 和 - ???????，計(jì)算兩整數(shù) ???????a 、b ???????之和。
異或的一個重要特性是無進(jìn)位加法。我們來看一個例子：
a = 5 = 0101
b = 4 = 0100
a ^ b 如下：
0 1 0 1
0 1 0 0
0 0 0 1
a ^ b 得到了一個無進(jìn)位加法結(jié)果，如果要得到 a + b 的最終值，我們還要找到進(jìn)位的數(shù)，把這二者相加。
在位運(yùn)算中，我們可以使用與操作獲得進(jìn)位：
a = 5 = 0101
b = 4 = 0100
a & b 如下：
0 1 0 1
0 1 0 0
0 1 0 0
由計(jì)算結(jié)果可見，0100 并不是我們想要的進(jìn)位，1 + 1 所獲得的進(jìn)位應(yīng)該要放置在它的更高位，即左側(cè)位上，因此我們還要把 0100 左移一位，才是我們所要的進(jìn)位結(jié)果。
總結(jié)一下：
- a + b 的問題拆分為 (a 和 b 的無進(jìn)位結(jié)果) + (a 和 b 的進(jìn)位結(jié)果)
- 無進(jìn)位加法使用異或運(yùn)算計(jì)算得出
- 進(jìn)位結(jié)果使用與運(yùn)算和移位運(yùn)算計(jì)算得出
- 循環(huán)此過程，直到進(jìn)位為 0
在 Python 中，整數(shù)不是 32 位的，也就是說你一直循環(huán)左移并不會存在溢出的現(xiàn)象，這就需要我們手動對 Python 中的整數(shù)進(jìn)行處理，手動模擬 32 位 INT 整型。
a=-2 ; b=3
a=1 1 1 0
b=0 0 1 1
- 將輸入數(shù)字轉(zhuǎn)化成無符號整數(shù)
a &= 0xF # a = a & 0b1111 = 1110
b &= 0xF # b = 0011- 計(jì)算無符號整數(shù)相加并的到結(jié)果
while b:
carry = a & b
a ^= b
b = carry << 1 & 0xF # 模擬溢出操作
過程為
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| carry | 0010 | 0100 | 1000 | |
| a | 1110 | 1101 | 1001 | 0001 |
| b | 0011 | 0100 | 1000 | 0000 |
最后結(jié)果為 1 是沒有問題的
但是對于 -2 + -2 , 最后結(jié)果為 1110 + 1110 = 1100 (12) 會出現(xiàn)問題
- 講結(jié)果根據(jù)范圍判定,映射為有符號整型
首先有符號整數(shù)的值域應(yīng)該為 [-8, 7] 對于初步運(yùn)算的結(jié)果,當(dāng)結(jié)果小于8直接返回就可.
對于大于 7 的結(jié)果, 可知符號位必為1. 現(xiàn)在的問題轉(zhuǎn)化為, 如何通過位運(yùn)算把負(fù)數(shù)轉(zhuǎn)換出來.
假設(shè)python用的是 8bit 有符號整數(shù),當(dāng)前結(jié)果為0000 1100, 對應(yīng)8bit有符號整數(shù)為12, 但結(jié)果應(yīng)該為-4對應(yīng)8bit有符號整數(shù)為1111 1100
通過兩步轉(zhuǎn)換可以得到:
1.結(jié)果 與 0b1111 異或
2.對異或結(jié)果按位取反
~(a ^ 0xF)
# 異或 - -> 無進(jìn)位加法
# 與，向左移動一位 - - > 進(jìn)位
class Solution:
def getSum(self, a: int, b: int) -> int:
# 截取后32位為無符號整數(shù)
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
# 無符號整數(shù)加法
while b:
# 模擬進(jìn)位
carry = (a & b) << 1
# 模模擬相加
a ^= b
b = carry & 0xFFFFFFFF # 模擬溢出操作
# 結(jié)果映射為有符號整數(shù)
return a if a < 0x80000000 else ~(a ^ 0xFFFFFFFF)
412. Fizz Buzz
寫一個程序，輸出從 1 到 n 數(shù)字的字符串表示。
- 如果 n 是3的倍數(shù)，輸出“Fizz”；
- 如果 n 是5的倍數(shù)，輸出“Buzz”；
3.如果 n 同時是3和5的倍數(shù)，輸出 “FizzBuzz”。
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
result_list = []
# 映射關(guān)系放在散列表,可以對散列表添加/刪除映射關(guān)系
key_value = {3: 'Fizz', 5: 'Buzz'}
for i in range(1, n+1):
result = ''
for k in key_value:
if i % k == 0:
result += key_value[k]
if not result:
result += str(i)
result_list.append(result)
return result_list
