341. Flatten Nested List Iterator （Medium）

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

#MY ANSWER
class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.res = []
        def helper(nli):
            for e in nli:
                if e.isInteger():
                    self.res.append(e.getInteger())
                else:
                    helper(e.getList())
        helper(nestedList)
            
    def next(self) -> int:
        return self.res.pop(0)
         
    def hasNext(self) -> bool:
        return bool(self.res)
         
#USING STACK
class NestedIterator(object):
    def __init__(self, nestedList):
        self.stack = nestedList[::-1]
        
    def next(self):
        return self.stack.pop().getInteger()
        
    def hasNext(self):
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack = self.stack[:-1] + top.getList()[::-1]
        return False

#USING GENERTOR
class NestedIterator:

    def __init__(self, nestedList: [NestedInteger]):
        # Get a generator object from the generator function, passing in
        # nestedList as the parameter.
        self._generator = self._int_generator(nestedList)
        # All values are placed here before being returned.
        self._peeked = None

    # This is the generator function. It can be used to create generator
    # objects.
    def _int_generator(self, nested_list) -> "Generator[int]":
        # This code is the same as Approach 1. It's a recursive DFS.
        for nested in nested_list:
            if nested.isInteger():
                yield nested.getInteger()
            else:
                # We always use "yield from" on recursive generator calls.
                yield from self._int_generator(nested.getList())
        # Will automatically raise a StopIteration.
    
    def next(self) -> int:
        # Check there are integers left, and if so, then this will
        # also put one into self._peeked.
        if not self.hasNext(): return None
        # Return the value of self._peeked, also clearing it.
        next_integer, self._peeked = self._peeked, None
        return next_integer
        
    def hasNext(self) -> bool:
        if self._peeked is not None: return True
        try: # Get another integer out of the generator.
            self._peeked = next(self._generator)
            return True
        except: # The generator is finished so raised StopIteration.
            return False

generator 解法没见过， 普通解法，要么初始化时候分解，要么用stack倒序，保证栈顶是integer。

342. Power of Four （Easy）

Given an integer n, return true if it is a power of four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4^x.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n==0: return False 
        while n:
            if n==1: return True
            if n%4!=0:
                return False
            n//=4
        return True

class Solution(object):
    def isPowerOfFour(self, n):
        if n == 0:
            return False
        while n % 4 == 0:
            n /= 4
        return n == 1

343. Integer Break (Medium)

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[1]=1
        for i in range(2,n+1):
            for j in range(1,i):
                dp[i]=max(dp[i],max(dp[j],j)*max(i-j,dp[i-j]))
        return dp[n]
  
class Solution:
    def integerBreak(self, n: int) -> int:
        if n==2: return 1
        if n==3: return 2
        product = 1
        while n>4:
            product*=3;
            n-=3
        product*=n;
        return product

#
class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2: 
            return 1 
        elif n == 3:
            return 2
        elif n%3 == 0:
            return 3**(n//3)
        elif n%3 == 1:
            return 4* 3**((n - 4) // 3)
        else: 
            #n%3==2
            return 2 * (3** (n//3))


#MY SOLUTION
class Solution:
    def integerBreak(self, n: int) -> int:
        # 2(1+1)   1
        # 3(1+2)   2
        # 4(2+2,1+3) 4
        # 5(2+3,1+4) 6
        # 6(2+4)     9
        # 7 (2+5,3+4)   12
        # 8             16
        # 9             20
        # 10             36

        # dp[i] = maximum product by breaking i
        # max( i-2*2 , 2*dp[i-2] , 3*dp[i-3]...)

        dp = [0]*(n+1)
        dp[2]=1

        for i in range(3,n+1):
            for j in range(2,n+1):
                if i-j>0:
                    dp[i] = max(dp[i], (i-j)*j)
                    dp[i] = max(dp[i], j*dp[i-j])
                else:
                    break
        
        #print(dp)
        return dp[n]

没思路,答案一，dp，dp【i】保存i可以被分解的最大乘集，假设i被分解成 a和b的和， 那么a或者b可以选中集训分解dp【a/b】或者不分解保留原始值a/b. 思路2： 用3 as many as possible. 比如 6, 3 乘 3大于2 乘 2 乘 2. 因此答案不会有超过3个的2. 尽力用3. 答案3： 有了思路2 ，和容易写出答案3.但dp这种方法应该想出来。。。

344. Reverse String (Easy)

Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l=0
        r=len(s)-1
        while l<r:
            s[l],s[r]=s[r],s[l]
            l+=1
            r-=1

345. Reverse Vowels of a String (Easy)

Given a string s, reverse only all the vowels in the string and return it.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both cases.

class Solution:
    def reverseVowels(self, s: str) -> str:
        s=[e for e in s]
        l=0
        r=len(s)-1
        vowels={'a','e','i','o','u'}
        while l<r:
            while l<r and s[l].lower() not in vowels:
                l+=1
            while l<r and s[r].lower() not in vowels:
                r-=1
            
            s[l],s[r]=s[r],s[l]
            r-=1
            l+=1
        
        return ''.join(s)

346. Moving Average from Data Stream (Easy)

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:
MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.

class MovingAverage:

    def __init__(self, size: int):
        self.size=size
        self.q=[]
    def next(self, val: int) -> float:
        if len(self.q)<self.size:
            self.q.append(val)
            return sum(self.q)/len(self.q)
        else:
            self.q.pop(0)
            self.q.append(val)
            return sum(self.q)/len(self.q)
        
from collections import deque
class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        # number of elements seen so far
        self.window_sum = 0
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1
        # calculate the new sum by shifting the window
        self.queue.append(val)
        tail = self.queue.popleft() if self.count > self.size else 0

        self.window_sum = self.window_sum - tail + val

        return self.window_sum / min(self.size, self.count)

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = [0] * self.size
        self.head = self.window_sum = 0
        # number of elements seen so far
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1
        # calculate the new sum by shifting the window
        tail = (self.head + 1) % self.size
        self.window_sum = self.window_sum - self.queue[tail] + val
        # move on to the next head
        self.head = (self.head + 1) % self.size
        self.queue[self.head] = val
        return self.window_sum / min(self.size, self.count)

用queue 和 Circular Queue 都是好想法。

347. Top K Frequent Elements （Medium）

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic_c = collections.Counter(nums)
        return sorted(dic_c.keys(),key=lambda x: dic_c[x],reverse=True)[:k]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:        
        from heapq import heappush, heappop
        c = Counter(nums)
        res = []
        for kk,vv in c.items():
            heappush(res, (-vv,kk) )
        r = []
        for i in range(k):
            r.append( heappop(res)[1])
        return r


#ANSWER
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        unique = list(count.keys())
        
        def partition(left, right, pivot_index) -> int:
            pivot_frequency = count[unique[pivot_index]]
            # 1. move pivot to end
            unique[pivot_index], unique[right] = unique[right], unique[pivot_index]  
            
            # 2. move all less frequent elements to the left
            store_index = left
            for i in range(left, right):
                if count[unique[i]] < pivot_frequency:
                    unique[store_index], unique[i] = unique[i], unique[store_index]
                    store_index += 1

            # 3. move pivot to its final place
            unique[right], unique[store_index] = unique[store_index], unique[right]  
            
            return store_index
        
        def quickselect(left, right, k_smallest) -> None:
            """
            Sort a list within left..right till kth less frequent element
            takes its place. 
            """
            # base case: the list contains only one element
            if left == right: 
                return
            
            # select a random pivot_index
            pivot_index = random.randint(left, right)     
                            
            # find the pivot position in a sorted list   
            pivot_index = partition(left, right, pivot_index)
            
            # if the pivot is in its final sorted position
            if k_smallest == pivot_index:
                 return 
            # go left
            elif k_smallest < pivot_index:
                quickselect(left, pivot_index - 1, k_smallest)
            # go right
            else:
                quickselect(pivot_index + 1, right, k_smallest)
         
        n = len(unique) 
        # kth top frequent element is (n - k)th less frequent.
        # Do a partial sort: from less frequent to the most frequent, till
        # (n - k)th less frequent element takes its place (n - k) in a sorted array. 
        # All element on the left are less frequent.
        # All the elements on the right are more frequent.  
        quickselect(0, n - 1, n - k)
        # Return top k frequent elements
        return unique[n - k:]

#ANSWER
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        bucket = [[] for _ in range(len(nums) + 1)]
        Count = Counter(nums).items()  
        for num, freq in Count: 
            bucket[freq].append(num) 
        flat_list = [item for sublist in bucket for item in sublist]
        return flat_list[::-1][:k]

答案给出了quick selelct的解法O（n）。但bucket 方法更好。 也是O（n）。

348. Design Tic-Tac-Toe （Medium）

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves are allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe class:
TicTacToe(int n) Initializes the object the size of the board n.
int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

class TicTacToe:

    def __init__(self, n: int):
        self.n=n
        self.rows_p1 = [0]*n
        self.rows_p2 = [0]*n
        self.cols_p1 = [0]*n
        self.cols_p2 = [0]*n
        self.i_plus_j_n_1_p1=0
        self.i_plus_j_n_1_p2=0
        self.i_equal_j_p1=0
        self.i_equal_j_p2=0
                
    def move(self, row: int, col: int, player: int) -> int:
        if player==1:
            self.rows_p1[row]+=1
            if self.rows_p1[row]==self.n: return player
            self.cols_p1[col]+=1
            if self.cols_p1[col]==self.n: return player
            if row+col==self.n-1:
                self.i_plus_j_n_1_p1+=1
                if self.i_plus_j_n_1_p1==self.n: return player
            if row==col:
                self.i_equal_j_p1+=1
                if self.i_equal_j_p1==self.n: return player
        else:
            self.rows_p2[row]+=1
            if self.rows_p2[row]==self.n: return player
            self.cols_p2[col]+=1
            if self.cols_p2[col]==self.n: return player
            if row+col==self.n-1:
                self.i_plus_j_n_1_p2+=1
                if self.i_plus_j_n_1_p2==self.n: return player
            if row==col:
                self.i_equal_j_p2+=1
                if self.i_equal_j_p2==self.n: return player
        
        return 0


#MY ANSWER
class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.p1 = {'row':[0]*n, 'col':[0]*n, 'rpc':0 ,'rmc':0} 
        self.p2 = {'row':[0]*n, 'col':[0]*n, 'rpc':0 ,'rmc':0} 
    
    def check(self):
        if self._check(self.p1):
            return 1
        if self._check(self.p2):
            return 2
        return 0
    
    def _check(self, info):
        for n in info['row']:
            if n==self.n:
                return True
        for n in info['col']:
            if n==self.n:
                return True
        if info['rpc']==self.n:
            return True
        if info['rmc']==self.n:
            return True
        return False

    def move(self, row: int, col: int, player: int) -> int:
        if player==1:
            info = self.p1
        else:
            info = self.p2

        info['row'][row]+=1
        info['col'][col]+=1
        if row+col==self.n-1:
            info['rpc']+=1 
        if row-col==0:
            info['rmc']+=1
        return self.check()
        

349. Intersection of Two Arrays (Easy)

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1)&set(nums2))

folowup, solve in O(n) time O(1) space given nums1,nums2 are sorted.

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    # if the lists are already sorted and you're told to solve in O(n) time and O(1) space:
    nums1.sort() # assume sorted
    nums2.sort() # assume sorted

    # iterate both nums backwards till at least 1 is empty
    # if num2[j] > num1[i], pop num2
    # if num2[j] < num1[i], pop num1
    # if equal and num not last appended to result, append to result and pop both nums
    
    result = []
            
    while nums1 and nums2:
        if nums2[-1] > nums1[-1]:
            nums2.pop()
        elif nums2[-1] < nums1[-1]:
            nums1.pop()
        else:
            # to avoid duplicates
            if not result or (result and nums1[-1] != result[-1]):
                result.append(nums1[-1])
            nums1.pop()
            nums2.pop()

    return result

350. Intersection of Two Arrays II （Easy）

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c1=collections.Counter(nums1)
        c2=collections.Counter(nums2)
        res=[]
        for k in c1:
            if k in c2:
                res.extend([k]*min(c1[k],c2[k]))
        return res

#Bad but save space answer
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        result = []
    
        while nums1 and nums2:
            if nums2[-1] > nums1[-1]:
                nums2.pop()
            elif nums2[-1] < nums1[-1]:
                nums1.pop()
            else:
                result.append(nums1[-1])
                nums1.pop()
                nums2.pop()

        return result