121. Best Time to Buy and Sell Stock (Easy)

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #two pointer
        profit = 0
        min_price = float('inf')
        for i,n in enumerate(prices):
            min_price= min(min_price,n)
            profit=max(profit,n-min_price)
        return profit

122. Best Time to Buy and Sell Stock II (Medium)

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # this means I can accumulate every increase trend in fluctuation of price
        if len(prices)<=1: return 0
        profit=0
        for i in range(1,len(prices)):
            profit_i = prices[i]-prices[i-1]
            if profit_i>0:
                profit+=profit_i
        return profit

123. Best Time to Buy and Sell Stock III (Hard)

Find the maximum profit you can achieve. You may complete at most two transactions.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        min_=[float('inf')]*3
        r=[0]*3
        
        for i in range(len(prices)):
            for k in range(1,3):
                min_[k]=min(min_[k],prices[i]-r[k-1])
                r[k]=max(r[k],prices[i]-min_[k])
        
        return r[2]

第一感觉是用Dynamic Programming。但是没想出来递推关系。。。Two pointer 的扩展， 求第二次min的时候是price[i]-第一次profit， 因为算第二次profit时候会用price[j] - (price[i]-第一次profit) 所以正好加上了第一次profit。比较巧妙。。

124. Binary Tree Maximum Path Sum （Hard）

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0

            # max sum on the left and right sub-trees of node
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # the price to start a new path where `node` is a highest node
            price_newpath = node.val + left_gain + right_gain
            
            # update max_sum if it's better to start a new path
            max_sum = max(max_sum, price_newpath)
        
            # for recursion :
            # return the max gain if continue the same path
            return node.val + max(left_gain, right_gain)
   
        max_sum = float('-inf')
        max_gain(root)
        return max_sum

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        res = float('-inf')
        def helper(root):
            '''
            return the path sum up to the root
            '''
            nonlocal res
            if not root: return 0
            left = helper(root.left)
            right = helper(root.right)
            res = max([res,root.val+left+right,root.val+left,root.val+right,root.val])
            return max(root.val,root.val+max(left,right))
        helper(root)
        return res

Fail to writing a working recursive solution!....问题出在recursion的return部分。
思路： local_max_sum = root.val + leftpath+rightpath 但在return时候，由于之前调用自己计算root.left 的leftpath和root.right的rightpath，所以是root.val+max(leftpath,rightpath) 这样return的路径是从root.left/root.right 单点延申出去的。不存在重复计算问题， 要是return root.val+ leftpath+rightpath， 那么调用自己在root.left计算的是root.left的左右扩展了， 而不是 root.left 的单一延申。 这样返回值会错误。

125. Valid Palindrome （Easy）

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l=0
        r=len(s)-1
        s=s.lower()
        while l<=r:
            while l<=r and s[l] not in '0123456789abcdefghijklmnopqrstuvwxyz':
                l+=1
            while l<=r and s[r] not in '0123456789abcdefghijklmnopqrstuvwxyz':
                r-=1
            
            if l<=r and s[l]!=s[r]:
                return False
            
            l+=1
            r-=1
        
        return True

注意while l<=r的判断。。。即使在内循环中。

126. Word Ladder II （Hard）

#answer way of writting
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # sortest path, graph bfs 
        # node is word
        # node neighbors are word differ by 1 letter in wordList.
        # find sortest path from beginWordd to endWord
        tree=collections.defaultdict(set)
        words = set(wordList)
        if endWord not in words:
            return []
        starts = {beginWord}
        ends = {endWord}
        rev=False
        FOUND=False
        
        while starts and not FOUND:
            
            words -= starts
            next_words = set()
            for word in starts:
                for i in range(len(word)):
                    left = word[:i]
                    right = word[i+1:]
                    for char in string.ascii_lowercase:
                        next_word = left + char + right
                        if next_word in words:
                            if next_word in ends:
                                FOUND= True
                            else:
                                next_words.add(next_word)
                            
                            tree[word].add(next_word) if not rev else tree[next_word].add(word)
            starts = next_words
            if len(starts) > len(ends):
                starts, ends = ends, starts
                rev=not rev
        
        def bt(x):
            if x==endWord:
                return [[x]]
            else:
                res = []
                for y in tree[x]:
                    for rest in bt(y):
                        res.append([x]+rest)
                return res
      
        return bt(beginWord)
        

整出来一个写的巨丑但还算正确的time limit exceeded解决方法,思路应该是graph bfs 找最短路径。
答案思路很巧妙， 用了bfs但是是从2端查找，缩小了时间。 然后通过collections.defaultdict(set)记录下一个节点。最后通过backtracking 得到结果。果然是hard 题目。

127. Word Ladder （Hard）

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
      
        visited =set()
        
        def neigh(word, wordList):
            nei = []
            for w in wordList:
                if w not in visited:
                    valid = 0
                    for a,b in zip(w,word):
                        if ord(a)^ord(b)==0:
                            continue
                        else:
                            valid+=1
                    if valid==1:
                        nei.append(w)
            return nei
        
        queue = [beginWord]
        res = []
        Found=False
        level=0
        while queue:
            level += 1
            for i in range(len(queue)):
                cur = queue.pop(0)
                if cur==endWord:
                    Found=True
                    return level
                if Found:
                    break
                
                visited.add(cur)
                
                for w in neigh(cur,wordList):
                    queue.append(w)
            if Found:
                break
        return 0

#answer way of writring
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        words = set(wordList)
        if endWord not in words:
            return 0
        starts = {beginWord}
        ends = {endWord}
        level = 1
        # charSet = {w for word in wordList for w in word}
        while starts:
            level += 1
            words -= starts
            next_words = set()
            for word in starts:
                for i in range(len(word)):
                    left = word[:i]
                    right = word[i+1:]
                    for char in string.ascii_lowercase:
                        next_word = left + char + right
                        if next_word in words:
                            if next_word in ends:
                                return level
                            next_words.add(next_word)
            starts = next_words
            if len(starts) > len(ends):
                starts, ends = ends, starts
        return 0 
# bfs 1 direction
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        begins = {beginWord}
        Found = False
        if endWord not in wordList: return 0
        wl = set(wordList)
        c=1
        while begins and not Found:
            c+=1
            wl-=begins
            next_begins = set()
            for word in begins:
                for i in range(len(word)):
                    for ch in string.ascii_lowercase:
                        nei = word[:i] +ch + word[i+1:]
                        if nei in wl:
                            if nei==endWord:
                                return c
                            next_begins.add(nei)
            begins = next_begins
        
        return 0

简单复用之前代码还是会得到time limit exceeded，因为bfs不是2头扫的。但2头扫bfs 怎么写？？

128. Longest Consecutive Sequence （Medium）

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        res=0
        nums=set(nums)
        
        for num in nums:
            if num-1 not in nums:
                cur=num
                cres=1
                
                while cur+1 in nums:
                    cur+=1
                    cres+=1
                    
                res=max(res,cres)
        
        return res

O（n）没思路。。。 看到答案后。。。大悟。 用了set，这样 num-1 not in nums时候知道当前值为开头。 如果当前值+1还在nums里。 更新当前值和局部最大值。 扫一次，虽然右内部while loop但还是O（n）

129. Sum Root to Leaf Numbers (Medium)

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        
        res = 0
        def calc(root,tmp):
            nonlocal res
            if not root: return
            if not root.left and not root.right:
                #I am leaf do calculatoin and the sum
                res +=  tmp*10+root.val
            
            tmp = tmp*10+root.val
            calc(root.left,tmp)
            calc(root.right,tmp)
            
            
        calc(root,0)
        return res

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        res = 0
        def helper(node, val):
            nonlocal res
            if not node.left and not node.right:
                res+= val
            if node.left:
                helper(node.left,val*10+node.left.val)
            if node.right:
                helper(node.right,val*10+node.right.val)
    
        helper(root,root.val)
        return res

思路：到达leave 才把结果加和给res。 如果不是leave只更新tmp值。 然后前序遍历。

130. Surrounded Regions （Medium）

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        
        def dfs(board,i,j):
            
            if m>i>=0 and n>j>=0:
                if board[i][j]=='O':
                    board[i][j]='#'
                    
            
                    for newi,newj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                        dfs(board,newi,newj)
      
        
        for i in range(m):
            for j in range(n):
                if i==0 or i==m-1 or j==0 or j==n-1 and board[i][j]=='O':
                    dfs(board,i,j)
        
        for i in range(m):
            for j in range(n):
                if board[i][j]!='#':
                    board[i][j]='X'
        for i in range(m):
            for j in range(n):
                if board[i][j]=='#':
                    board[i][j]='O'

#BFS way of writting
class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board: return 
        m=len(board)
        n=len(board[0])
        #boarder bfs O->#          else to  X  restore # to O
        
      
        def nei(i,j):
            r= [ (i+1,j),(i-1,j),(i,j+1),(i,j-1)]
            return [ (xy[0],xy[1]) for xy in r if  (0<=xy[0]<m and 0<=xy[1]<n)]
        
      
        def bfs(i,j):
            visited=set()
            q=[(i,j)]
            visited.add((i,j))
            board[i][j]='#'
            while q:
                x,y=q.pop(0)
                neis=nei(x,y)
                for xy in neis:
                    if xy not in visited:
                        if board[xy[0]][xy[1]]=='O':
                            q.append(xy)
                            board[xy[0]][xy[1]]='#'
                            visited.add(xy)
                            
                         
                        
                    
                    
                
        
        for i in range(m):
            for j in range(n):
                if i==0 or i==m-1 or j==0 or j==n-1:
                    if board[i][j]=='O':
                        bfs(i,j)
            
        
        for row in board:
            print(row)
        for i in range(m):
            for j in range(n):
                if board[i][j]!='#':
                    board[i][j]='X'
                if board[i][j]=='#':
                    board[i][j]='O'

思路，在board边界地方为O的点做dfs，更新为#。之后把所有不为#的变为X。之后把#变为O。 得写个bfs dfs模板总结。