271. Encode and Decode Strings (Medium)

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

class Codec:
    def encode(self, strs: [str]) -> str:
        """Encodes a list of strings to a single string.
        """
        candidate='a'
        set_ = set()
        for str in strs:
            for s in str:
                set_.add(s)
        while candidate in set_:
            candidate = chr(ord(candidate)+1)
        return candidate + candidate.join(strs)
        

    def decode(self, s: str) -> [str]:
        """Decodes a single string to a list of strings.
        """
        candidate = s[0]
        s = s[1:]
        return s.split(candidate)
        


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))

272. Closest Binary Search Tree Value II (Hard)

快排法是On解法，LOGN解法最好 的确是个hard

#ANSWER 1 Recursive Inorder + Sort, O(N log N) time
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def inorder(r: TreeNode):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        
        nums = inorder(root)
        nums.sort(key = lambda x: abs(x - target))
        return nums[:k]

#ANSWER 2 
from heapq import heappush, heappop
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def inorder(r: TreeNode):
            if not r:
                return
            
            inorder(r.left)
            heappush(heap, (- abs(r.val - target), r.val))
            if len(heap) > k:
                heappop(heap)
            inorder(r.right) 
    
        heap = []
        inorder(root)
        return [x for _, x in heap]

#ANSWER 3 QuickSelect, O(N) time.
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def inorder(r: TreeNode):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        
        def partition(pivot_idx, left, right):
            pivot_dist = dist(pivot_idx)
            
            # 1. move pivot to end
            nums[right], nums[pivot_idx] = nums[pivot_idx], nums[right]
            store_idx = left
            
            # 2. move more close elements to the left
            for i in range(left, right):
                if dist(i) < pivot_dist:
                    nums[i], nums[store_idx] = nums[store_idx], nums[i]
                    store_idx += 1
                    
            # 3. move pivot to its final place
            nums[right], nums[store_idx] = nums[store_idx], nums[right]
            
            return store_idx
            
        def quickselect(left, right):
            """
            Sort a list within left..right till kth less close element
            takes its place.
            """
            # base case: the list contains only one element
            if left == right:
                return 
            
            # select a random pivot_index
            pivot_idx = randint(left, right)
            
            # find the pivot position in a sorted list
            true_idx = partition(pivot_idx, left, right)
            
            # if the pivot is in its final sorted position
            if true_idx == k:
                return
            
            if true_idx < k:
                # go left
                quickselect(true_idx, right)
            else:
                # go right
                quickselect(left, true_idx)
        
        nums = inorder(root)
        dist = lambda idx : abs(nums[idx] - target)
        quickselect(0, len(nums) - 1)
        return nums[:k]


#BSET LOGN SOLUTION
# 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 closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        #smaller save the node smaller than target
        smaller = []
        #larger save the node larger than target
        larger = []

        node = root
        while node:
            if node.val==target:
                smaller.append(node)
                larger.append(node)
                break
            elif target<node.val:
                smaller.append(node)
                node=node.left
            else:
                larger.append(node)
                node=node.right
        
        #larger than smaller node could be a res add them to smaller
        def get_larger(smaller):
            node = smaller.pop()
            cur = node
            if cur.right:
                cur=cur.right
                while cur:
                    smaller.append(cur)
                    cur=cur.left
            return node.val
        
        #smaller than larger node could be a res add them to larger
        def get_smaller(larger):
            node = larger.pop()
            cur = node
            if cur.left:
                cur = cur.left
                while cur:
                    larger.append(cur)
                    cur = cur.right
            return node.val


        #if same val pop anyone is OK
        if smaller and larger and smaller[-1]==larger[-1]:
            get_smaller(larger)
            #get_larger(smaller)
             
        
        res = []
        while k:
            if not smaller:
                res.append(get_smaller(larger))
            elif not larger:
                res.append(get_larger(smaller))
            else:
                diff1 = abs(smaller[-1].val-target)
                diff2 = abs(larger[-1].val-target)
                
                if diff1<diff2:
                    res.append(get_larger(smaller))
                else:
                    res.append(get_smaller(larger))
             
            k-=1
        
        return res
 

虽然做出来了，但是感觉用minheap会更好。我的方法得一直sort，时间复杂度太高。 需要记住 from heapq import heappush，heappop 用法 heappush（heap，val） heappop（heap） 每次pop出来的是最小的元素。 O（n）方法用到了快排。LOGN方法最好

273. Integer to English Words （Hard）

Convert a non-negative integer num to its English words representation.

class Solution:
    def numberToWords(self, num: int) -> str:
      
        nums = []
      
        if num==0: nums.append(0)
        while num:
            nums.append(num%1000)
            num//=1000
        
    
        res = []
        l=len(nums)
        dic = {0:'',1:'Thousand',2:'Million',3:'Billion',4:'Trillion'}
        def helper(n):
            if type(n)==str: return ''
            s  = ''
            dic = {0:'Zero',1:'One',2:'Two',3:'Three',4:'Four',5:'Five',6:'Six',7:'Seven',8:'Eight',9:'Nine',10:'Ten',11:'Eleven',12:'Twelve',13:'Thirteen',14:'Fourteen',15:'Fifteen',16:'Sixteen',17:'Seventeen',18:'Eighteen',19:'Nineteen',20:'Twenty',30:'Thirty',40:'Forty',50:'Fifty',60:'Sixty',70:'Seventy',80:'Eighty',90:'Ninety'}
            
            if n<10: return dic[n]
            if n>99:
                s+= dic[n//100]+' Hundred'
            n = n%100
            if n==0: return s
            if n in dic:
                s+= ' '+dic[n]
                return s
            else:
                s+=' '+dic[10*(n//10)]
                n=n%10
                if n==0:
                    return s
                else:
                    s+= ' '+ dic[n]
                    return s
       
        tmp=[]
        while nums:
            if nums[0]==0:
                nums.pop(0)
                tmp.append('#')
            else:
                tmp.append(nums.pop(0))

        nums=tmp
        if nums==['#']:
            nums=[0]
        for i,number in enumerate(nums):
            if number!='#':
                res.append(helper(number)+ ' ' + dic[i])
        return ' '.join([ e.strip() for e in res[::-1] if e.strip()])
#ANSWER
class Solution:
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        def one(num):
            switcher = {
                1: 'One',
                2: 'Two',
                3: 'Three',
                4: 'Four',
                5: 'Five',
                6: 'Six',
                7: 'Seven',
                8: 'Eight',
                9: 'Nine'
            }
            return switcher.get(num)

        def two_less_20(num):
            switcher = {
                10: 'Ten',
                11: 'Eleven',
                12: 'Twelve',
                13: 'Thirteen',
                14: 'Fourteen',
                15: 'Fifteen',
                16: 'Sixteen',
                17: 'Seventeen',
                18: 'Eighteen',
                19: 'Nineteen'
            }
            return switcher.get(num)
        
        def ten(num):
            switcher = {
                2: 'Twenty',
                3: 'Thirty',
                4: 'Forty',
                5: 'Fifty',
                6: 'Sixty',
                7: 'Seventy',
                8: 'Eighty',
                9: 'Ninety'
            }
            return switcher.get(num)
        

        def two(num):
            if not num:
                return ''
            elif num < 10:
                return one(num)
            elif num < 20:
                return two_less_20(num)
            else:
                tenner = num // 10
                rest = num - tenner * 10
                return ten(tenner) + ' ' + one(rest) if rest else ten(tenner)
        
        def three(num):
            hundred = num // 100
            rest = num - hundred * 100
            if hundred and rest:
                return one(hundred) + ' Hundred ' + two(rest) 
            elif not hundred and rest: 
                return two(rest)
            elif hundred and not rest:
                return one(hundred) + ' Hundred'
        
        billion = num // 1000000000
        million = (num - billion * 1000000000) // 1000000
        thousand = (num - billion * 1000000000 - million * 1000000) // 1000
        rest = num - billion * 1000000000 - million * 1000000 - thousand * 1000
        
        if not num:
            return 'Zero'
        
        result = ''
        if billion:        
            result = three(billion) + ' Billion'
        if million:
            result += ' ' if result else ''    
            result += three(million) + ' Million'
        if thousand:
            result += ' ' if result else ''
            result += three(thousand) + ' Thousand'
        if rest:
            result += ' ' if result else ''
            result += three(rest)
        return result

corner case 有点太多了。。。写出来是写出来了。

274. H-Index （Medium)

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return compute the researcher's h-index.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # [1,3,1]
        # 
        #  0 1 2 3
        # []
        
        dp = [0]*(len(citations)+1)
        for c in citations:
            if c>len(citations):
                c=len(citations)
            dp[c]+=1
        
        for i in range(len(dp)-2,-1,-1):
            dp[i]=dp[i]+dp[i+1]
        
        hindex=[]
        print(dp)
        for ind, n in enumerate(dp):
            if n>=ind:
                hindex.append(ind)
        
        return max(hindex)

#ANSWER reverse SORT
class Solution:
    def hIndex(self, citations: List[int]) -> int:
    
        citations.sort(reverse=True)
        print(citations)
        hindex=0
        for ind, cit in enumerate(citations):
            hindex_candidate = ind+1
            if cit>=hindex_candidate:
                hindex = hindex_candidate
                
        return hindex

#MY ANSER
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        l=len(citations)
        dp = [0]*(l+1)
        for c in citations:
            if c>l:
                c = l
            dp[c]+=1
        for i in range(l-1,-1,-1):
            dp[i] +=dp[i+1]
        
        candi = 0
        for i,p in enumerate(dp):
            if p>=i:
                candi  =i
        return candi

275. H-Index II (Medium)

sorted citations O(lgn) time to solve

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        l = len(citations)
        
        left = 0
        right = l-1
        candi = 0
        while left<=right:
            mid = (left+right)//2
            cit = citations[mid]
            hidx = l-mid
            if cit>=hidx:
                candi = max(candi,hidx)
                right = mid-1
            else:
                left = mid+1
        return candi


#ANSWER
class Solution:
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations)
        for idx, c in enumerate(citations):
            if c >= n - idx:
                return n - idx
        return 0
#binary serach
class Solution:
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations)
        left, right = 0, n - 1

        # We need to find the rightmost 'index' such that: (citations[index] <= n - index)
        while left <= right:
            mid = left + (right - left) // 2

            # There's (n - mid) papers with an equal or higher citation count than citations[mid]
            # If (citations[mid] == n - mid) it's the optimal result and can be returned right away
            if citations[mid] == n - mid:
                return n - mid

            # If citations[mid] is less than (n - mid), narrow down on the right half to look for a paper
            # at a future index that meets the h-index criteria. Otherwise, narrow down on the left half
            if citations[mid] < n - mid:
                left = mid + 1
            else:
                right = mid - 1

        # We didn't find an exact match, so there's exactly (n - left) papers that have citations
        # greater than or equal to citations[left] and that is our answer
        return n - left

虽然做出来了，但是还是不熟。

276. Paint Fence (Medium)

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
Every post must be painted exactly one color.
There cannot be three or more consecutive posts with the same color.
Given the two integers n and k, return the number of ways you can paint the fence.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        # dp    
        # n = 0    0  
        # n = 1    k
        # n = 2    k*k    
        # n = 3    diff color  (k-1)*dp[i-1]   same color 1*  (k-1)*dp[i-2]  
        # so, dp[i] = (k-1)dp[i-1]+(k-1)*dp[i-2]
        
        if n==1:
            return k
        if n==2:
            return k*k
        dp=[0]*(n+1)
        dp[1]=k
        dp[2]=k*k
        for i in range(3,n+1):
            dp[i] = (k-1)*(dp[i-1]+dp[i-2])
        
        return dp[n]

感觉是DP，递推关系是？ 已经想到了，但是没仔细去想。 当前颜色和前一个相同， 当前颜色和前一个不同。

277. Find the Celebrity （Medium)

class Solution:
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if knows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if knows(i, j) or not knows(j, i):
                return False
        return True

#MY ANSWER
class Solution:
    def findCelebrity(self, n: int) -> int:
        candi = -1
        for i in range(n):
            if candi!=i and  knows(candi,i):
                candi = i
     
        for i in range(n):
           if i!=candi and (not knows(i,candi) or knows(candi,i) ):
                return -1
        return candi

答案找possible candidate O（n）时间的方法第一次没想出来。。。

278. First Bad Version （Easy）

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        l=1
        r=n
        while l<=r:
            m=(l+r)//2
            if isBadVersion(m):
                r=m-1
            else:
                l=m+1
        return l

279. Perfect Squares (Medium)

Given an integer n, return the least number of perfect square numbers that sum to n.

#ANSWER O（n*sqrt（n））
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        dp = [float('inf')] * (n+1)
        # bottom case
        dp[0] = 0
        
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i-square] + 1)
        
        return dp[-1]

#MY ANSWER
class Solution:
    @lru_cache(None)
    def numSquares(self, n: int) -> int:
        if n==1:
            return 1
        if int(n**0.5)**2 == n:
            return 1
        res = n
        for i in range(1, int(n**(0.5))+1):
            res=min(res,1+ self.numSquares(n - i*i))
        return res
#MY DP ANSWER
class Solution:
    def numSquares(self, n: int) -> int:
        
        dp = [float('inf')]*(n+1)
        for i in range(1, int(n**0.5)+1 ):
            dp[i*i]=1
        
        for i in range(1,n+1):
            for j in range(int(i**0.5)+1):
                if i-j*j>=0 and dp[i-j*j]:
                    dp[i] = min(dp[i],1+dp[i-j*j])
        
        return dp[n]

答案pre calculate square_nums 省了很多时间也不用判断是否为完全平方数。

280. Wiggle Sort （Medium）

Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
You may assume the input array always has a valid answer.

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        for i in range(1,len(nums)-1,2):
            nums[i],nums[i+1]=nums[i+1],nums[i]

#ANSWER
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        less=True
        for i in range(len(nums)-1):
            if less:
                if nums[i]>nums[i+1]:
                    nums[i],nums[i+1]=nums[i+1],nums[i]
            else:
                if nums[i]<nums[i+1]:
                    nums[i],nums[i+1]=nums[i+1],nums[i]
            
            less=not less

too late today。 思路1 sort first， 从第二个元素开始swap。 思路2，如果顺序不正确就纠正。