703. Kth Largest Element in a Stream
## 思路
使用size為k的min_heap存前k大的值
## Code
```python
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.min_heap = []
self.k = k
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.min_heap, val)
if len(self.min_heap) > self.k:
heapq.heappop(self.min_heap)
return self.min_heap[0]
```
---
練習rolling hash
796. Rotate String
## 思路
檢查rotated str跟goal的hash值, 如果相同就回傳True
aL = 26 ** len(s) = 26 ** 3
123 = (26 ** 2) * 1 + (26 ** 1) * 2 + 3 = h
231 = (26 ** 2) * 2 + (26 ** 1) * 3 + 1
= 26 * h - aL * 1 + 1
```python
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
n = len(s)
h = target = 0
aL = 26 ** n
for i in range(n):
target = target * 26 + (ord(goal[i]) - ord('a'))
h = h * 26 + (ord(s[i]) - ord('a'))
if h == target:
return True
for i in range(n):
h = h * 26 + (ord(s[i]) - ord('a')) - aL * (ord(s[i]) - ord('a'))
if h == target:
return True
return False
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.186 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723440353.A.334.html