251. Flatten 2D Vector (Medium)

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.
Implement the Vector2D class:
Vector2D(int[][] vec) initializes the object with the 2D vector vec.
next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
hasNext() returns true if there are still some elements in the vector, and false otherwise.

class Vector2D:

    def __init__(self, vec: List[List[int]]):
        self.data = vec
        self.cur  =  []
 
        
    def next(self) -> int:
        if self.hasNext():
            return self.cur.pop(0)

    def hasNext(self) -> bool:
        while not self.cur:
            if len(self.data)==0: return False
            self.cur = self.data.pop(0)
        
        return len(self.cur)>0
        


class Vector2D:

    def __init__(self, v: List[List[int]]):
        # We need to iterate over the 2D vector, getting all the integers
        # out of it and putting them into the nums list.
         
        self.nums = []
        for inner_list in v:
            for num in inner_list:
                self.nums.append(num)
        # We'll keep position 1 behind the next number to return.
        self.position = -1

    def next(self) -> int:
        # Move up to the current element and return it.
        self.position += 1
        return self.nums[self.position]

    def hasNext(self) -> bool:
        # If the next position is a valid index of nums, return True.
        return self.position + 1 < len(self.nums)

自己写的这个递归调用比较tricky。。。答案很简答。

252. Meeting Rooms （Easy）

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals=sorted(intervals,key=lambda x:x[0])
        pre_end = None
        for interval in intervals:
            if pre_end is not None and interval[0]<pre_end:
                return False
            pre_end = interval[1]
        return True

253. Meeting Rooms II (Medium)

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # max meeting at same time
        res = 1
        dic = dict()
        intervals = sorted(intervals,key=lambda x:x[0])
        for a,b in intervals:
            dic[a] = dic.get(a,0)+1
            dic[b] = dic.get(b,0)-1
        
        c=0
        for k in sorted(dic.keys()):
            c+=dic[k]
            res = max(res,c)
        return res

虽然做出来了，感觉下次再做可能会忘记怎么做的， 思路： 把所有时节节点从小到大排序，如果是start， counter+=1 如果是end， counter-=1， 找出counter变化过程中最大值。 答案做的感觉没自己的思路简单。

254. Factor Combinations （Medium）

Numbers can be regarded as the product of their factors.

For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

#Iterative:

def getFactors(self, n):
    todo, combis = [(n, 2, [])], []
    while todo:
        n, i, combi = todo.pop()
        while i * i <= n:
            if n % i == 0:
                combis += combi + [i, n/i],
                todo += (n/i, i, combi+[i]),
            i += 1
    return combis

#Recursive:

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        
        res=[]
        def factor(n, i, tmp):
            while i * i <= n:
                if n % i == 0:
                    res.append(tmp + [i, n//i])
                    factor(n//i, i, tmp+[i])
                i += 1
        factor(n, 2, [])
        return res

思路类似，但是还是没写粗来，这个不应该， res 先append tmp+[i,n//i],然后再factor（n//i， i，tmp+【i】，res）

255. Verify Preorder Sequence in Binary Search Tree （Medium）

def verifyPreorder(self, preorder):
    stack = []
    low = float('-inf')
    for p in preorder:
        if p < low:
            return False
        while stack and p > stack[-1]:
            low = stack.pop()
        stack.append(p)
    return True

没思路，答案思路： 模拟traversal，stack是左子树的栈。 如果下一个数小于栈顶，说明还在左子树，所以append。 如果当前preorder值大于栈顶，所有小于当前值元素出栈。说明当前元素跳到了右子树。low=stack.pop() 很巧妙， lower bound是满足小于当前值的最后一个pop出去的元素。

256. Paint House （Medium)

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        mem=dict()
        def paint(n,color):
            if (n,color) in mem:
                return mem[(n,color)]
            res = costs[n][color]
            
            if n!=len(costs)-1:
                if color==0:
                    res+=min(paint(n+1,1),paint(n+1,2))
                elif color==1:
                    res+=min(paint(n+1,0),paint(n+1,2))
                else:
                    res+=min(paint(n+1,0),paint(n+1,1))
            mem[(n,color)]=res
            return res
       
        return min([paint(0,0),paint(0,1),paint(0,2)])

#
class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        if not costs:return 0
        for n in range(len(costs)-2,-1,-1):
            costs[n][0]+=min(costs[n+1][1],costs[n+1][2])
            costs[n][1]+=min(costs[n+1][0],costs[n+1][2])
            costs[n][2]+=min(costs[n+1][0],costs[n+1][1])
        return min(costs[0])

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        # dp[i][j] = paint up to ith house with current color j , the min cost
        # dp[i][j] =  cost[i][j] + min(dp[i-1][k]  k !=j )
        # dp[0][j] = cost[0][j]

        m = len(costs)
        n = 3

        dp = [[0]*n for _ in range(m)]
        for j in range(3):
            dp[0][j] = costs[0][j]
        
        for i in range(1,m):
            for j in range(3):
                dp[i][j] = costs[i][j]+min([dp[i-1][k] for k in range(3) if k!=j])
        
        return min(dp[-1])

这个应该是递归mem的经典题和dp的经典题。用dynamic programming，但是写出来一版是错的。。。应该定义dp=【#costs】【#color】。从最后一个房子开始， 倒数第二个 cost红=最后一个min（绿，蓝），。。。

257. Binary Tree Paths （Easy）

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res=[]
        def bt(tmp,node):
            if not node: return
            if not node.left and not node.right:
                tmp.append(str(node.val))
                res.append('->'.join(tmp))
                return
            tmp.append(str(node.val))
            bt(tmp[:],node.left)
            bt(tmp[:],node.right)
        bt([],root)
        return res

258. Add Digits (Easy)

class Solution:
    def addDigits(self, num: int) -> int:
        
        while num//10!=0:
            new_num = 0
            while num:
                lastdig = num%10
                num = num//10
                new_num+=lastdig
            num = new_num
        
        return num
# answer way of writing
class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        if num % 9 == 0:
            return 9
        return num % 9

答案用了一个数能被九整除，那么他们所有位数和能被9整除。

259. 3Sum Smaller （Medium）

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

 
class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        for i in range(len(nums)-2):
            l = i+1
            r = len(nums)-1
            
            while l<r:
                if nums[i]+nums[l]+nums[r] < target:
                    res+= r-l
                    l+=1
                else:
                    r-=1
            
        return res

3sum转成2sum，然后定义left=start+1，right=len（nums）-1， 若left +right 值小于target 说明 left 到right所有都满足条件，这样left+1求解下一步， 若left +right 值大于target说明right太大得减1.

260. Single Number III （Medium）

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor=0
        for n in nums:
            xor = xor^n
        
        # rightmost 1-bit diff between a and b
        diff = xor & -xor
        
        a=0
        for n in nums:
            if n&diff:
                # diff means a's last bit is diff then b's last bit
                # by using this filter we could get a 
                a= a^n
        return [a,xor^a]

没思路， one pass 只能找出xor=a^b 但不能确定出a，b具体值。
答案思路：用了一个不知道的trick， x & (-x) 保留x中最右边bit，设置其他bit为0. 这样就能用a，b 的diff bit把所有数字过滤一次，只有a可以被过滤出来，因为a的diff bit是1 其余diff bit是1的都出现了2次抵消了。。