#柠檬水找零

#记录5和10的个数，如果有一个透支了，就说明不能满足找零

class Solution:

def lemonadeChange(self, bills: List[int]) -> bool:

i=j=0

for k in bills:

if k==5:i+=1

elif k==10:j+=1;i-=1

else:

if j==0:i-=3

else:i-=1;j-=1

if i<0 or j<0:return False

return True

#买股票的最佳时机

#首先设置收益profit=0，接着从1到len(prices)进行迭代，后面的值是否比前面的值大，如果后面值减去前面值成立，则累加给profit，如果不成立那么就不管它，因为不会影响结果，最后全部迭代完return profit

class Solution:

def maxProfit(self, prices: List[int]) -> int:

profit = 0

for i in range(1,len(prices)):

if prices[i-1] < prices[i]:

profit += prices[i] - prices[i-1]

return profit

#单词接龙

class Solution:

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

# BFS

from collections import deque, defaultdict

# 先验判断

if endWord not in wordList:

return 0

# 提前构建邻接表 -> 用generic state做key

intermidiateWords = defaultdict(list)

wordLen = len(beginWord)

for word in wordList:

for i in range(wordLen):

intermidiateWords[word[:i] + '*' + word[i+1:]].append(word)

# 建队列 加初始状态

queue = deque()

memo = set()

queue.append(beginWord)

memo.add(beginWord)

step = 1

while queue:

size = len(queue)

for _ in range(size):

curWord = queue.popleft()

for i in range(wordLen):

intermidiateCurWord = curWord[:i] + '*' + curWord[i+1:]

# 下一个状态的所有word

for word in intermidiateWords[intermidiateCurWord]:

if word == endWord:

return step + 1

if word not in memo:

queue.append(word)

memo.add(word)

step += 1

else:

return 0

#岛屿数量

#把grid扩一圈，定义计数变量ret。

循环网格：如果是"1"，计数变量加一，然后搜索并替换相关连的"1"和本身为"0"。

class Solution:

def numIslands(self, grid: List[List[str]]) -> int:

if not grid:

return 0

def bfs(i: int, j: int) -> None:

if i == 0 or j == 0 or i == x-1 or j == y-1 or grid[i][j] == "0":

return

grid[i][j] = "0"

bfs(i-1, j)

bfs(i, j-1)

bfs(i+1, j)

bfs(i, j+1)

x = len(grid)+2

y = len(grid[0])+2

grid = [["0"]*x]+[["0"]+i+["0"] for i in grid]+[["0"]*x]

ret = 0

for i in range(1, x-1):

for j in range(1, y-1):

if grid[i][j] == "1":

bfs(i, j)

ret += 1

return ret