中间搞laser project浪费了不少时间~~~

401. Binary Watch (Easy)

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.
Given an integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent. You may return the answer in any order.

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        return ['{}:{}'.format(h, str(m).zfill(2))  for h in range(12) for m in range(60) if (bin(h) + bin(m)).count('1') == turnedOn]

#Backtracking way of answer it
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res=set()
        nums1=[8,4,2,1]
        nums2=[32,16,8,4,2,1]
        
        
        def generateDigs(nums,count):
            res=set()
            def helper(c,pos,sum_):
                if c==0:
                    res.add(sum_)
                    return
                for i in range(pos,len(nums)):
                    helper(c-1,i+1,sum_+nums[i])
            helper(count,0,0)
            return res
        
        for i in range(turnedOn+1):
            list1=generateDigs(nums1,i)
            list2=generateDigs(nums2,turnedOn-i)
            for num1 in list1:
                if num1>=12: continue
                for num2 in list2:
                    if num2>=60: continue
                    res.add('{}:{}'.format(num1,str(num2).zfill(2)))
        return res


#MY ANSWER
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
      
        res = []


        def process(tmp):
            #print('R',tmp)
            r=''
            h,m = tmp
            if not h:
                r+='0:'
            else:
                r+=str(h)+':'
            
            if not m:
                r+='00'
            else:
                r+= str(m).zfill(2)
            return r
        
        def bt(on_remain,tmp,i,j,v_h,v_m,bebug=''):
            if on_remain<0: return 
            #print(bebug, i,j)
            h = [1,2,4,8]
            m = [1,2,4,8,16,32]
     
            if on_remain == 0:
                res.append(process(tmp))
                return
            if i>=4 and  j>=6: return 
            
            hour = h[i] if i<4 else None
            mini = m[j]  if j<6 else None
            if hour and mini:
                #slect ith hour, j the min
                if hour not in v_h and mini not in v_m:
                    if not (tmp[0]+hour>=12 or tmp[1]+mini>=60): 
                        
                        v_h.add(hour)
                        v_m.add(mini)
                        bt(on_remain-2,[tmp[0]+hour,mini+tmp[1]],i+1,j+1,v_h,v_m,bebug+'H{}M{} '.format(i,j))
                        v_h.remove(hour)
                        v_m.remove(mini)
            
            #select jth min
            if mini:
                #print('m' ,mini,'j',j ,'h',tmp[0])
                if mini not in v_m:
                    if not tmp[1]+mini>=60:  
                        #print('@',mini,on_remain,tmp)
                        v_m.add(mini)
                        bt(on_remain-1,[tmp[0],mini+tmp[1]],i,j+1,v_h,v_m,bebug+'M{} '.format(j))
                        v_m.remove(mini)

            #selet ith hour 
            if hour:
                if hour not in v_h:
                    if not tmp[0]+hour>=12: 
                        v_h.add(hour)
                        bt(on_remain-1,[tmp[0]+hour, tmp[1]],i+1,j,v_h,v_m,bebug+'H{} '.format(i))
                        v_h.remove(hour)
            #skip
            bt(on_remain,tmp.copy(), i+1,j+1,v_h,v_m,bebug+'SKIP{}{} '.format(i,j))

           
        
        bt(turnedOn,[0,0],0,0,set(), set())
        
         
        return list(set(res))

是一个backtracking问题， 写起来难度很大，然而是一个easy问题。。。直接暴力解即可。
但用backtracking就是一个比较难的问题了。注意的是i，j终止条件， if i>=4 or j>=6: return 这个是错的，当i 已经violate时候，j还是能继续+的，eg i=4， j还可以是1，2，3.。。。所以终止条件应该是 if i>=4 and j>=6: return。

402. Remove K Digits （Medium）

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        #
        # 2     1    4
        # left  cur
        # if cur<left, we know left must be removed
        
        stack=[]
        for n in num:
            while k and stack and n<stack[-1]:
                stack.pop()
                k-=1
            stack.append(n)
        
        #truncate remaining k digits at the end
        # if k==0 return entire list
        final_stack=stack[:-k] if k else stack
        
        return ''.join(final_stack).lstrip('0') or '0'

greedy+stack 这个方法第一次比较难想到，需要考虑corner case。

403. Frog Jump （Hard）

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.
If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

class Solution:
    def canCross(self, stones: List[int]) -> bool:
       
        dp=[False]*len(stones)
        dic={s:i for i,s in enumerate(stones)}
        
        @lru_cache(None)
        def can(ith,k):
            if k<=0: return
            if ith==0:
                dp[0]=True
                if stones[0]+1 in dic:
                    jth=dic[stones[0]+1] 
                    can(jth,1)
            else:
                for i,step in enumerate([k+1,k,k-1]):
                    if stones[ith]+step in dic:
                        stone_ind=dic[stones[ith]+step]
                        dp[stone_ind]=True
                        can(stone_ind,[k+1,k,k-1][i])
            
        can(0,1)
        return dp[-1]

#ANSWER
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        
        dic=dict()
        for s in stones:
            dic[s]=set()
        dic[0].add(0)
        
        for i in range(len(stones)):
            for k in dic[stones[i]]:
                for step in range(k-1,k+2):
                    if step>0 and stones[i]+step in dic:
                        dic[stones[i]+step].add(step)
                        
        return len(dic[stones[-1]])>0

#ANSWER
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        
        seen = set()
        stoneSet = set(stones)
        end = stones[-1]
        stack = [(0, 0)]
        while len(stack) > 0:
            loc, steps = stack.pop()
            if (loc, steps) in seen:
                continue
            seen.add((loc, steps))
            if loc == end:
                return True
            elif loc < end:
                for i in range(steps-1, steps+2):
                    if i <= 0:
                        continue
                    if loc + i in stoneSet:
                        stack.append((loc+i, i))
        return False

#MY ANSWER
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        if len(stones)==0: return True
        if len(stones)>1 and stones[1]-stones[0]!=1: return False
 
        target = stones[-1]
        s = set(stones)

        @lru_cache(None)
        def dfs(cur_pos,k):
            if cur_pos==target:
                return True
         
            res = False
            if cur_pos+k in s:
                res = res or dfs(cur_pos + k, k)
            if cur_pos+k+1 in s:
                res = res or dfs(cur_pos + k+1,k+1)
            if k-1>0 and cur_pos+k-1 in s:
                res =res or dfs(cur_pos+k-1,k-1)
            return res

        return dfs(1,1)

没想到做出来了。。。。。dp with mem。。。
答案更好。答案3思路： each node has 3 children. The goal is to check if we can reach to the end along the edges. We can do it with a Depth First Search with a Hashtable(to avoid redundant calculation)

404. Sum of Left Leaves （Easy）

Given the root of a binary tree, return the sum of all left leaves.

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        if root.left and root.left.left is None and root.left.right is None:
            return root.left.val+self.sumOfLeftLeaves(root.right)
        return  self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)

405. Convert a Number to Hexadecimal (Easy)

Given an integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.
All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

class Solution:
    def toHex(self, num: int) -> str:

        li16 = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']
        stack = []
        if num<0: 
            num+=0xffffffff+1
        while num>0:
            lastdig = num%16
            stack.append(li16[lastdig])
            num//=16
        
        return ''.join(stack[::-1]) or '0'

406. Queue Reconstruction by Height (Medium)

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        output = []
        for p in people:
            output.insert(p[1], p)
        return output

思路：最高的sort完了，插入次高的，插入位置？

407. Trapping Rain Water II （Hard）

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        
        class Cell:
            def __init__(self,row,col,h):
                self.row=row
                self.col=col
                self.h=h
            
            def __lt__(self,other):
                return self.h<other.h
            
        
        if not heightMap or len(heightMap)==0 or len(heightMap[0])==0:
            return 0
        
        q=[]
        m=len(heightMap)
        n=len(heightMap[0])
        visited=[[False]*n for _ in range(m)]
        #Initially, add all the Cells which are on borders to the queue.
        for i in range(m):
            visited[i][0]=True
            visited[i][n-1]=True
            heapq.heappush(q, Cell(i,0,heightMap[i][0]))
            heapq.heappush(q, Cell(i,n-1,heightMap[i][n-1]))
        for j in range(n):
            visited[0][j]=True
            visited[m-1][j]=True
            heapq.heappush(q, Cell(0,j,heightMap[0][j]))
            heapq.heappush(q, Cell(m-1,j,heightMap[m-1][j]))
        #from the borders, pick the shortest cell visited and check its neighbors: if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped add all its neighbors to the queue.
        dirs = [[-1,0],[1,0],[0,-1],[0,1]]
        res=0
        while q:
            cur_cell=heapq.heappop(q)
            for dir in dirs:
                row=cur_cell.row+dir[0]
                col=cur_cell.col+dir[1]
                if row>=0 and row<m and col>=0 and col<n and not visited[row][col]:
                    visited[row][col]=True
                    res+=max(0,cur_cell.h-heightMap[row][col])
                    heapq.heappush(q,Cell(row,col,max(cur_cell.h,heightMap[row][col])))
                    
        
        return res
                    
#ANSWER
class Solution(object):
    def trapRainWater(self, heightMap):
        if not heightMap or not heightMap[0]:
            return 0
        
        import heapq    
        m, n = len(heightMap), len(heightMap[0])
        heap = []
        visited = [[0]*n for _ in xrange(m)]

        # Push all the block on the border into heap
        for i in xrange(m):
            for j in xrange(n):
                if i == 0 or j == 0 or i == m-1 or j == n-1:
                    heapq.heappush(heap, (heightMap[i][j], i, j))
                    visited[i][j] = 1
        
        result = 0
        while heap:
            height, i, j = heapq.heappop(heap)    
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0 <= x < m and 0 <= y < n and not visited[x][y]:
                    result += max(0, height-heightMap[x][y])
                    heapq.heappush(heap, (max(heightMap[x][y], height), x, y))
                    visited[x][y] = 1
        return result      
        

思路：边界最低的板子是开始点，BFS，如果邻居低说明能存水，做计算，然后埋土。

408. Valid Word Abbreviation （Easy）

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.
For example, a string such as "substitution" could be abbreviated as (but not limited to):
"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)
The following are not valid abbreviations:
"s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
"s010n" (has leading zeros)
"s0ubstitution" (replaces an empty substring)
Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.
A substring is a contiguous non-empty sequence of characters within a string.

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        
        dig=0
        while abbr:
            
            if abbr[0].isdigit():
                if dig==0 and abbr[0]=='0': return False
                dig=dig*10+int(abbr[0])
                abbr=abbr[1:]
            else:
                if dig!=0:
                    if len(word)<dig: return False
                    word=word[dig:]
                    dig=0
                else:
                    if not word: return False
                    if abbr[0]!=word[0]: return False
                    abbr=abbr[1:]
                    word=word[1:]
        if dig:
            if len(word)<dig: return False
            if not word: return False
            word=word[dig:]
         
        return not abbr and not word


#MY ANSWER
class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:

        while word and abbr:
            dig = ''
            while abbr and abbr[0].isdigit():
                dig+=abbr[0]
                abbr =abbr[1:]
            
            if not dig:
                head = abbr[0]
                if head!=word[0]: return False
                abbr= abbr[1:]
                word =word[1:]
            else:
                if dig[0]=='0': return False
                dig = int(dig)
                if dig>len(word): return False
                word = word[dig:]
        
        return not word and not abbr

409. Longest Palindrome (Easy)

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        dic=Counter(s)
        res=0
        for k,v in dic.items():
            res+=v//2*2
            if res%2==0 and v%2==1:
                res+=1
        return res


class Solution:
    def longestPalindrome(self, s: str) -> int:
        c =Counter(s)
        odd = 0
        res = 0
        for k,v in c.items():
            if v%2==0:
                res+=v
            else:
                res+=v-1
                odd = max(v,odd)
        return res+1 if odd else res

找到能组成palindrom的最长组合方式，如果是奇数个，可以变成偶数个，比如bbb只用bb。 但当res%2==0时候，遇到奇数情况可以加1.

odd全变成偶数，但是最大的odd是可以完整加入的， 因为对odd是v-1，所以但凡odd有值，就应该+1.

410. Split Array Largest Sum （Hard）

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m subarrays.

#DFS TLE
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        self.res = float('inf')
        def dfs(i,j,cur,max_):
            # i is pointer for nums
            # j is the counter for k
            if i==len(nums):
                if j==k:
                    self.res = min(self.res,max_)
                return
            if i>0:
                dfs(i+1,j,cur+nums[i],max(max_,cur+nums[i]))
            if j<k:
                dfs(i+1,j+1,nums[i],max(max_,nums[i]))
        
        dfs(0,0,0,0)
        return self.res

 
 # TOP DOWN DP

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n=len(nums)
        prefix_sum = [0]
        for num in nums:
            prefix_sum.append(prefix_sum[-1]+num)
        
        @lru_cache(None)
        def get_min_largest_split_sum(cur_idx, k):
            #we have processd sum before cur_idx
            if k==1:
                return prefix_sum[n]-prefix_sum[cur_idx]
            
            res = prefix_sum[n]
            for split_spot in range(cur_idx, n-k+1):
                # cur_idx, split_spot
                head_sum = prefix_sum[split_spot+1]-prefix_sum[cur_idx]
                tmp = max(head_sum, get_min_largest_split_sum(split_spot+1,k-1))
                res = min(res,tmp)

                if head_sum>=res:
                    break
            return res
        
        return get_min_largest_split_sum(0,k)

#DP  BOTTOM UP
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        memo = [[0] * (k + 1) for _ in range(n)]
        prefix_sum = [0]
        for num in nums:
            prefix_sum.append(prefix_sum[-1]+num)
        
        for subarray_count in range(1, k + 1):
            for curr_index in range(n):
                if subarray_count == 1:
                    memo[curr_index][subarray_count] = prefix_sum[n] - prefix_sum[curr_index]
                    continue 
                minimum_largest_split_sum = prefix_sum[n]
                for i in range(curr_index, n - subarray_count + 1):
                     
                    first_split_sum = prefix_sum[i + 1] - prefix_sum[curr_index]

                   
                    largest_split_sum = max(first_split_sum, memo[i + 1][subarray_count - 1])

                     
                    minimum_largest_split_sum = min(minimum_largest_split_sum, largest_split_sum)

                    if first_split_sum >= minimum_largest_split_sum:
                        break
            
                memo[curr_index][subarray_count] = minimum_largest_split_sum
        
        return memo[0][k]

#Binary Seasrch THIS IS THE BEST METHOD
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        
        def min_subarrays_required(max_sum_allowed: int) -> int:
            current_sum = 0
            splits_required = 0
            
            for element in nums:
                # Add element only if the sum doesn't exceed max_sum_allowed
                if current_sum + element <= max_sum_allowed:
                    current_sum += element
                else:
                    # If the element addition makes sum more than max_sum_allowed
                    # Increment the splits required and reset sum
                    current_sum = element
                    splits_required += 1

            # Return the number of subarrays, which is the number of splits + 1
            return splits_required + 1
        
        # Define the left and right boundary of binary search
        left = max(nums)
        right = sum(nums)
        while left <= right:
            # Find the mid value
            max_sum_allowed = (left + right) // 2
            
            # Find the minimum splits. If splits_required is less than
            # or equal to m move towards left i.e., smaller values
            if min_subarrays_required(max_sum_allowed) <= m:
                right = max_sum_allowed - 1
                minimum_largest_split_sum = max_sum_allowed
            else:
                # Move towards right if splits_required is more than m
                left = max_sum_allowed + 1
        
        return minimum_largest_split_sum
###Binary Seasrch


class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        https://leetcode.com/explore/learn/card/binary-search/146/more-practices-ii/1042/discuss/89817/Clear-Explanation:-8ms-Binary-Search-Java?page=1
        """
 
        max_ = sum=0
        for  num in nums:
            max_ = max(num, max_);
            sum += num
            
            
        def valid(target, nums, m):
            count = 1
            total = 0
            for num in nums:
                total += num
                if total > target: 
                    total = num
                    count+=1
                    if count > m:
                        return False
                    
            return True
        
        if m == 1: return sum
        #binary search
        l = max_ 
        r = sum
        while l <= r:
            mid = (l + r)// 2;
            if  valid(mid, nums, m): 
                r = mid - 1 
            else: 
                l = mid + 1
            
        return l


#MY ANSWER
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        l =max(nums)
        r =res = sum(nums)
        
        def allowed(m):
            sum = 0
            split = 0
            for n in nums:
                sum+=n
                if sum>m:
                    sum = n
                    split+=1
            return split+1

        while l<=r:
            m =(l+r)//2

            if allowed(m) <=k:
                # m is larger, that split NO. is small, need shrink
                res = min(res,m)
                r = m-1        
            else:
                l = m+1
        return  res

无思路。。。m=2时候很容易，sort然后找到左右平衡点。m=3，4？
DP很好， bianry search是最优解法。