261. Graph Valid Tree （Medium)

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.

class Solution:
    
    class UnionFind:
        def __init__(self,n):
            self.parent = [None]*n
            self.rank = [0]*n
            for i in range(n):
                self.parent[i]=i
                
        def find(self,i):
            if self.parent[i]!=i:
                self.parent[i]=self.find(self.parent[i])
            return self.parent[i]
        
        def union(self,x,y):
            rootx=self.find(x)
            rooty=self.find(y)
            if rootx!=rooty:
                if self.rank[rootx]>self.rank[rooty]:
                    self.parent[rooty]=rootx
                elif self.rank[rootx]<self.rank[rooty]:
                    self.parent[rootx]=rooty
                else:
                    self.parent[rooty]=rootx
                    self.rank[rootx]+=1
                
    
        
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        #UNIONFIND
        uf =self.UnionFind(n)
        for (a,b) in edges:
            uf.union(a,b)
        
        if len(set( [uf.find(i) for i in range(n)]))!=1:
            return False
    
        return len(edges)==n-1

#answer DFS
def validTree(self, n: int, edges: List[List[int]]) -> bool:
    
    if len(edges) != n - 1: return False
    
    # Create an adjacency list.
    adj_list = [[] for _ in range(n)]
    for A, B in edges:
        adj_list[A].append(B)
        adj_list[B].append(A)
    
    # We still need a seen set to prevent our code from infinite
    # looping if there *is* cycles (and on the trivial cycles!)
    seen = {0}
    stack = [0]
    
    while stack:
        node = stack.pop()
        for neighbour in adj_list[node]:
            if neighbour in seen:
                continue
            seen.add(neighbour)
            stack.append(neighbour)
    
    return len(seen) == n
#answer 
def validTree(self, n: int, edges: List[List[int]]) -> bool:
    
    if len(edges) != n - 1: return False
    
    # Create an adjacency list.
    adj_list = [[] for _ in range(n)]
    for A, B in edges:
        adj_list[A].append(B)
        adj_list[B].append(A)
    
    # We still need a seen set to prevent our code from infinite
    # looping if there *is* cycles (and on the trivial cycles!)
    seen = set()

    def dfs(node):
        if node in seen: return
        seen.add(node)
        for neighbour in adj_list[node]:
            dfs(neighbour)

    dfs(0)
    return len(seen) == n

#answer
def validTree(self, n: int, edges: List[List[int]]) -> bool:
    
    if len(edges) != n - 1: return False
    
    # Create an adjacency list.
    adj_list = [[] for _ in range(n)]
    for A, B in edges:
        adj_list[A].append(B)
        adj_list[B].append(A)
    
    # We still need a seen set to prevent our code from infinite
    # looping if there *is* cycles (and on the trivial cycles!)
    seen = {0}
    queue = collections.deque([0])
    
    while queue:
        node = queue.popleft()
        for neighbour in adj_list[node]:
            if neighbour in seen:
                continue
            seen.add(neighbour)
            queue.append(neighbour)
    
    return len(seen) == n

猜到了使用UnionFind做，但是还是copy了UnionFind Class 代码，还没熟练到自己写出来。 思路很简单，union后同一个parent，#edges+1=#node 答案思路：DFS或者BFS 判断是树1）n-1 edges， 2）graph fully connected。

262. Trips and Users （Hard）

# Write your MySQL query statement below
select   request_at as 'Day', round(sum(counter)/sum(total),2) as 'Cancellation Rate' from (
select CASE WHEN Trips.status='completed' THEN 0 else 1 END as counter, 1 as total, Trips.request_at  from
Trips left join Users c on Trips.client_id=c.users_id left join Users d on Trips.driver_id=d.users_id where c.banned!='Yes' and d.banned!='Yes'
) tmp  where Request_at>="2013-10-01" AND Request_at<="2013-10-03" group by request_at

#ANSWER 
SELECT Request_at as Day,
ROUND(SUM(CASE WHEN Status!="completed" THEN 1 ELSE 0 END)/COUNT(*),2) as "Cancellation Rate" 
FROM Trips
WHERE Client_Id NOT IN
(
    SELECT Users_Id FROM Users
    WHERE Banned="Yes"
)
AND Request_at>="2013-10-01" AND Request_at<="2013-10-03"
GROUP BY Request_at;

263. Ugly Number (Easy)

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number.

class Solution:
    def isUgly(self, n: int) -> bool:
        if n==0: return False
        if n==1: return True
        
        while n%2==0:
            n//=2
        if n==1: return True
        while n%3==0:
            n//=3
        if n==1: return True
        while n%5==0:
            n//=5
        if n==1: return True
        
        return False

class Solution:
    def isUgly(self, n: int) -> bool:
        if n==0: return False
        while n!=1:
            if n%2==0:
                n //=2
            elif n%3==0:
                n//=3
            elif n%5==0:
                n//=5
            else:
                return False
        return True

264. Ugly Number II (Medium)

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * n
        t2 = t3 = t5 = 0
        dp[0] = 1
        for i in range(1,n):
            dp[i] = min(dp[t2]*2,dp[t3]*3,dp[t5]*5)
            if(dp[i] == dp[t2]*2): t2 += 1
            if(dp[i] == dp[t3]*3): t3 += 1
            if(dp[i] == dp[t5]*5): t5 += 1
        return dp[-1]

没思路 。。。或者知道思路但写不出代码。 要是添加2倍，3倍，4倍，5倍还是会有空隙当n很大时候。 答案，用了dynamic programming。 思路是多个pointer。 t2，t3，t5记录已经遍历的数字里2，3，5都有多少个。 关键点是找到下一个最小的ugly number当乘以2，3，5时候。 又因为已经存在的数字只能被2，3，5乘1次，所以可以用pointer保持下次2，3，5要乘以的位置。

265. Paint House II （Hard）

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        #  cost last =     [a1,a2,a3,a4]
        #  cost last-1 =   [a1'+min(a2,a3,a4),a2'+min(a1,a3,a4),...]
        #  ...
        #  cost  0     =    [a1''',a2'''....]
        # ans= min(cost0)
        for i in range(len(costs)-2,-1,-1):
            for ii in range(len(costs[0])):
                costs[i][ii] = costs[i][ii]+min([costs[i+1][jj] for jj in range(len(costs[0])) if jj!=ii])
        
        return min(costs[0])

#ＭＹ　　ＡＮＳＷＥＲ    
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        # dp[i][j] = up to house i,using color j's min cost
        # dp[0][j] =  costs[0][j]
        # dp[i][j] =  cost[i][j]+min(dp[i-1][k] k!=j)
        # return min(dp[-1])

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

266. Palindrome Permutation (Easy)

Given a string s, return true if a permutation of the string could form a palindrome.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        #odd occurance can not >1
        dic = collections.Counter(s)
        c=0
        for k,v in dic.items():
            if v%2==1:
                c+=1
            if c>1:
                return False
        return True

267. Palindrome Permutation II (Medium)

class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        dic = collections.Counter(s)
        c = 0
        odd_char = ''
        odd_c = 0
        for k,v in dic.items():
            if v%2==1:
                c+=1
                odd_char = k
                odd_c = v
        if c>1: return []
        if len(dic)==1:
            return [list(dic.keys())[0]*dic[list(dic.keys())[0]]]
        if odd_char:
            tmp=odd_char
            dic[odd_char]-=1
            if dic[odd_char]<=0:
                del dic[odd_char]
                 
        res = []
        def bt(dic,tmp):
            if len(tmp)==len(s):
                res.append(tmp)
                return
            
            for k,v in dic.items():
                dic_copy = dic.copy()
                tmp = k+tmp+k
                dic_copy[k]-=2
                if dic_copy[k]==0:
                    del dic_copy[k]
                #print(tmp,dic_copy)
                bt(dic_copy,tmp)
                tmp=tmp[1:-1]

            
        bt(dic,odd_char)
        return  res

backtracking 分为odd 元素存在时候，中间位置只能是odd元素，然后从中间向两边扩展。

268. Missing Number （Easy）

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n=len(nums)
        return (0+n)*(n+1)//2 - sum(nums)

269. Alien Dictionary (Hard)

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.
Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.
A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

class Solution:
     
    
    from collections import defaultdict, Counter, deque

    def alienOrder(self, words: List[str]) -> str:

        # Step 0: create data structures + the in_degree of each unique letter to 0.
        adj_list = defaultdict(set)
        in_degree = Counter({c : 0 for word in words for c in word})

        # Step 1: We need to populate adj_list and in_degree.
        # For each pair of adjacent words...
        for first_word, second_word in zip(words, words[1:]):
            for c, d in zip(first_word, second_word):
                if c != d:
                    if d not in adj_list[c]:
                        adj_list[c].add(d)
                        in_degree[d] += 1
                    break
            else: # Check that second word isn't a prefix of first word.
                if len(second_word) < len(first_word): return ""

        # Step 2: We need to repeatedly pick off nodes with an indegree of 0.
        output = []
        queue = deque([c for c in in_degree if in_degree[c] == 0])
        while queue:
            c = queue.popleft()
            output.append(c)
            for d in adj_list[c]:
                in_degree[d] -= 1
                if in_degree[d] == 0:
                    queue.append(d)

        # If not all letters are in output, that means there was a cycle and so
        # no valid ordering. Return "" as per the problem description.
        if len(output) < len(in_degree):
            return ""
        # Otherwise, convert the ordering we found into a string and return it.
        return "".join(output)

#DFS topo sorter reverse adj list and using grey black for node color

class Solution:
    def alienOrder(self, words: List[str]) -> str:

        # Step 0: Put all unique letters into the adj list.
        reverse_adj_list = {c : [] for word in words for c in word}

        # Step 1: Find all edges and put them in reverse_adj_list.
        for first_word, second_word in zip(words, words[1:]):
            for c, d in zip(first_word, second_word):
                if c != d: 
                    reverse_adj_list[d].append(c)
                    break
            else: # Check that second word isn't a prefix of first word.
                if len(second_word) < len(first_word): 
                    return ""

        # Step 2: Depth-first search.
        seen = {} # False = grey, True = black.
        output = []
        def visit(node):  # Return True iff there are no cycles.
            if node in seen:
                return seen[node] # If this node was grey (False), a cycle was detected.
            seen[node] = False # Mark node as grey.
            for next_node in reverse_adj_list[node]:
                result = visit(next_node)
                if not result: 
                    return False # Cycle was detected lower down.
            seen[node] = True # Mark node as black.
            output.append(node)
            return True

        if not all(visit(node) for node in reverse_adj_list):
            return ""

        return "".join(output)

很明显图论相关的题，没复习到还，看答案。思路：1）找到dependence rules， 2）topological sort。用queue来存indegree=0的node，然后遍历neighbors。或者DFS，revse adj list 然后为了防止有环，需要标注node color white grey black。

for item in container:
    if search_something(item):
        # Found it!
        process(item)
        break
else:
    # Didn't find anything..
    not_found_in_container()

这个语法从来没见过，for后面可以带一个else表明for loop中没有break的条件，else 来执行后续操作。

270. Closest Binary Search Tree Value （Easy）

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

# 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 closestValue(self, root: Optional[TreeNode], target: float) -> int:
        if not root.left and not root.right: return root.val
        if not root.right:
            if target<root.val:
                res=self.closestValue(root.left,target)
                return res if abs(target-res)<abs(root.val-target) else root.val
            else:
                return root.val
        if not root.left:
            if target>root.val:
                res = self.closestValue(root.right,target)
                return res if abs(target-res)<abs(root.val-target) else root.val
            else:
                return root.val
        
        if target==root.val:
            return root.val
        elif target<root.val:
            res = self.closestValue(root.left,target)
            return res if abs(target-res)<＝abs(root.val-target) else root.val
        else:
            res= self.closestValue(root.right,target)
            return res if abs(target-res)<abs(root.val-target) else root.val

#ANSWER
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val
        while root:
            closest = min(root.val, closest, key = lambda x: （abs(target - x)，ｘ)）
            root = root.left if target < root.val else root.right
        return closest