441. Arranging Coins （Easy）

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        r=0
        while n>0:
            r+=1
            n-=r
        return r-1 if n<0 else r

class Solution:
    def arrangeCoins(self, n: int) -> int:
        
        # (1+ x) x /2 <= n
        #      (1+x)x <= 2n
        # max x which (1+x)x <=2n
        
        l, r = 0, n
        
        while l <= r:
            
            m = (l + r) // 2
            
            if (m+1)*m <= 2*n and (m+2)*(m+1) > 2*n:
                return m
            
            if (m+1)*m < 2*n:
                l = m + 1
            else:
                r = m - 1
    

答案是binary search啊。。

442. Find All Duplicates in an Array （Medium）

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        # 0 1 2 3 4 5 6 7
        # 4 3 2 7 8 2 3 1
        
        # -4 3 2-7    -3-1 
        
        n=len(nums)
        
        for i in range(n):
            ind=(abs(nums[i])%n-1)
            nums[ind] =   abs(nums[ind])+n if nums[ind]<0 else -abs(nums[ind])-n
        
        #print(nums)
        res=[]
        for i in range(n):
            if nums[i]>n:
                res.append(i+1)
        return res

#ANSWER BEST
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res=[]
        for n in nums:
            if nums[abs(n)-1]<0: #seen before
                res.append(abs(n))
            
            nums[abs(n)-1]*=-1
        
        return res

#MY ANSWER
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:

        # nums from 1 to n, length is n
        # nums index from 0 to n-1
        res = []
        s = set(nums)
        for i in range(len(nums)):
            idx = abs(nums[i])-1
            nums[idx] *= -1

        for i in range(len(nums)):
            if nums[i]>0:
                if i+1 in s:
                    res.append(i+1)
        return res 

特殊的bookkeeping。 答案写的更好

443. String Compression （Medium）

Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.

class Solution:
    def compress(self, chars: List[str]) -> int:

        pos = 0
        pre = None
        c=0
        chars.append(' ')# for reduce corner case  ch != pre
        for i,ch in enumerate(chars):
            if i!=0 and ch!=pre:
                #add to result
                if c==1:
                    chars[pos]=pre
                    pos+=1
                else:
                    chars[pos]=pre
                    pos+=1
                    for char in str(c):
                        chars[pos] = char
                        pos+=1

                c=1
            else:
                c+=1
            
            pre = ch
        

        print(chars[:pos])
        return pos
#ANSWER 更简单
 
class Solution:
    def compress(self, chars: List[str]) -> int:
        walker, runner = 0, 0
        while runner < len(chars):
		
            chars[walker] = chars[runner]
            count = 1
			
            while runner + 1 < len(chars) and chars[runner] == chars[runner+1]:
                runner += 1
                count += 1
			
            if count > 1:
                for c in str(count):
                    chars[walker+1] = c
                    walker += 1
            
            runner += 1
            walker += 1
        
        return walker

two pointer 写出来了，但是cornercase很多边test边写的。。。。答案很简单。。。。

444. Sequence Reconstruction (Medium)

You are given an integer array nums of length n where nums is a permutation of the integers in the range [1, n]. You are also given a 2D integer array sequences where sequences[i] is a subsequence of nums.
Check if nums is the shortest possible and the only supersequence. The shortest supersequence is a sequence with the shortest length and has all sequences[i] as subsequences. There could be multiple valid supersequences for the given array sequences.
For example, for sequences = [[1,2],[1,3]], there are two shortest supersequences, [1,2,3] and [1,3,2].
While for sequences = [[1,2],[1,3],[1,2,3]], the only shortest supersequence possible is [1,2,3]. [1,2,3,4] is a possible supersequence but not the shortest.
Return true if nums is the only shortest supersequence for sequences, or false otherwise.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        values = {x for seq in sequences for x in seq}
        graph = {x: [] for x in values}
        indegrees = {x: 0 for x in values}
        for seq in sequences:
            for i in range(len(seq) - 1):
                s = seq[i]
                t = seq[i+1]
                graph[s].append(t)
                indegrees[t] += 1
        queue = collections.deque()
        for node, count in indegrees.items():
            if count == 0:
                queue.append(node)
        res = []
        while queue:
            if len(queue) != 1:
                return False
            source = queue.popleft()
            res.append(source)
            for target in graph[source]:
                indegrees[target] -= 1
                if indegrees[target] == 0:
                    queue.append(target)
        return len(res) == len(values) and res == nums

#MY ANSWER
class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        # a<-b
        # topo sort dependency
        # nums is topo sort
        
        if len(nums)==1: return sequences==[[nums[0]]]
        dic = collections.defaultdict(set)
        indegree = collections.defaultdict(int)
        visited = set()
        for seq in sequences:
            for a, b in zip(seq,seq[1:]):
                if (a,b) not in visited:
                    visited.add((a,b))
                    indegree[a]+=1
                    dic[b].add((a,b))
        
        while nums:
            val = nums.pop()
            if val not in dic:
                return False
            c=0
            for aa,bb in  dic[val]:
                indegree[aa]-=1
                if indegree[aa]==0:
                    c+=1
                    del indegree[aa]
            del dic[val]
            if c!=1: return False
            if len(nums)==1: return True
        
        return True

。。。topological sort... 第一步建立dependency graph， 第二部toposort，每一步检查是否只有一个node的可能性，如果比一个多，return False。 第三步，在得到toposortlist 后，检查长度是否和sequence中所有unique 元素个数一样而且 是input nums。
解释：
TopSort order exists
Whether the TopSort order is the only one (Uniqueness of Topological sort, Hamilton path, see https://en.wikipedia.org/wiki/Topological_sorting#Uniqueness).如果不是，那么说明有些pair只有偏序关系，没有全序关系，这样不能完全确定元素之间的顺序
the only top sort order constructed should be equal to the org.

index == org.length (check condition 3) && index == map.size() (check all the vertex in the graph has been visited, so the top sort order exists, check condition 1)

How to check only one order? queue.size() should always be one, then only one element at a time has indegree to be 0, so you only have one choice (check condition 2)

445. Add Two Numbers II （Medium）

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def rev(node):
            pre=None
            while node:
                nodenext=node.next
                node.next=pre
                pre=node
                node=nodenext
            return pre
        
        l1=rev(l1)
        l2=rev(l2)
        
        carry=0
        head=ListNode(val=None)
        savehead=head
        while l1 or l2:
            v1= l1.val if l1 else 0
            v2= l2.val if l2 else 0
            val=(v1+v2+carry)%10
            carry=(v1+v2+carry)//10
            head.next=ListNode(val)
            head=head.next
            
            l1=l1.next if l1 else None
            l2=l2.next if l2 else None
            
        if carry:
            head.next=ListNode(carry)
            head=head.next
        
        return rev(savehead.next)

#
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        
        s1=[]
        s2=[]
        
        cur=l1
        while cur:
            s1.append(cur.val)
            cur=cur.next
            
        cur=l2
        while cur:
            s2.append(cur.val)
            cur=cur.next
            
        
        head=None
        carry=0
        while s1 or s2:
            x = s1.pop() if s1 else 0
            y = s2.pop() if s2 else 0
            sum_=x+y+carry
            cur=ListNode(sum_%10)
            cur.next=head
            head=cur
            carry=sum_//10
        
        if carry:
            cur=ListNode(carry)
            cur.next=head
            head=cur
        return head
        
 #####
 class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        
        s1=[]
        s2=[]
        
        cur=l1
        while cur:
            s1.append(cur.val)
            cur=cur.next
            
        cur=l2
        while cur:
            s2.append(cur.val)
            cur=cur.next
            
        
        head=None
        carry=0
        while s1 or s2:
            x = s1.pop() if s1 else 0
            y = s2.pop() if s2 else 0
            sum_=x+y+carry
            cur=ListNode(sum_%10)
            cur.next=head
            head=cur
            carry=sum_//10
        
        if carry:
            cur=ListNode(carry)
            cur.next=head
            head=cur
        return head
               

followup 是不revlist能否。。。那就用stack。

446. Arithmetic Slices II - Subsequence (Hard)

Given an integer array nums, return the number of all the arithmetic subsequences of nums.
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.
A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].
The test cases are generated so that the answer fits in 32-bit integer.

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        
        #f[i][d] denotes the number of weak arithmetic subsequences that ends with A[i] and its common difference is d.
        #Now the state transitions are quite straightforward:

        # for all j < i, f[i][A[i] - A[j]] += (f[j][A[i] - A[j]] + 1).
        # The 1 appears here because we can form a new weak arithmetic subsequence for the pair (i, j)
        
        #when we are appending new elements to existing weak arithmetic subsequences, we are forming arithmetic subsequences. So the first part, f[j][A[i] - A[j]] is the number of new formed arithmetic subsequences, and can be added to the answer.

        
        n=len(nums)
        res=0
        cnt=dict()
        for i in range(n):
            cnt[i]=dict()
            for j in range(i):
                delta=nums[i]-nums[j]
                
                diff=delta
                sum_=cnt[j].get(diff,0)
                origin=cnt[i].get(diff,0)
                cnt[i][diff]=origin+sum_+1
                res+=sum_
        return res


#MY ANSWER
#cnt[i][d] denotes the number of weak arithmetic subsequences that ends with A[i] and its common difference is d.
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        cnt =dict()
        # j  i #
        for i in range(n):
            cnt[i] = defaultdict(int)
            for j in range(i):
                diff = nums[i]-nums[j]
                cnt[i][diff] +=  cnt[j][diff]  +1
                res+=cnt[j][diff]
        return res

是应该用DP但看答案。。。答案这个DP解法不是一般的DP。。。先dp【i】【diff】是以ith nums为最终位置的weak arithmetic subsequences的个数，这个weak值2个元素也能形成subsequence。 要想得到真正的3个元素的arithmetic subsequences个数，每次可以把nums【i】添加到dp【j】【diff】时候这个dp【j】【diff】个数就是arithmetic subsequences个数。很难想到这个方法啊。。。
backtracking 方法超时

class Solution {
    private int n;
    private int ans;
    private void dfs(int dep, int[] A, List<Long> cur) {
        if (dep == n) {
            if (cur.size() < 3) {
                return;
            }
            long diff = cur.get(1) - cur.get(0);
            for (int i = 1; i < cur.size(); i++) {                
                if (cur.get(i) - cur.get(i - 1) != diff) {
                    return;
                }
            }
            ans ++;
            return;
        }
        dfs(dep + 1, A, cur);
        cur.add((long)A[dep]);
        dfs(dep + 1, A, cur);
        cur.remove((long)A[dep]);
    }
    public int numberOfArithmeticSlices(int[] A) {
        n = A.length;
        ans = 0;
        List<Long> cur = new ArrayList<Long>();
        dfs(0, A, cur);
        return (int)ans;        
    }
}

447. Number of Boomerangs (Medium)

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Return the number of boomerangs.

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        
        def dis(p1,p2):
            return (p1[0]-p2[0])**2+(p1[1]-p2[1])**2
        
        
        dic=collections.defaultdict(set)
        
        for i,p1 in enumerate(points):
            for j,p2 in enumerate(points):
                if i!=j:
                    dic[dis(p1,p2)].add((i,j))
                    dic[dis(p1,p2)].add((j,i))
        #print(dic)
        res=0
        for k, s in dic.items():
            #find i,j i,k
            d=dict()
            for t in s:
                d[t[0]]=d.get(t[0],0)+1
            
            #print(d)
            
            for key,val in d.items():
                res+= val*(val-1) if val>1 else 0
        
        return res
#ANSWER 同样思路但超级简单
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        for p in points:
            cmap = {}
            for q in points:
                f = p[0]-q[0]
                s = p[1]-q[1]
                cmap[f*f + s*s] = 1 + cmap.get(f*f + s*s, 0)
            for k in cmap:
                res += cmap[k] * (cmap[k] -1)
        return res


#MY ANSWER
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        #dp[i][dist] 以i为顶点的长度为diff的 个数 i-j i-k  （i，j，k） 也可以是 i k j
        
        def distance(i,j):
            a,b = points[i]
            x,y = points[j]
            return (a-x)**2+(b-y)**2
        
        n = len(points)
        res = 0
        #   j ... i  #
        for i in range(n):
            dic = defaultdict(int)
            for j in range(n):
                if i!=j:
                    dist = distance(i,j)
                    dic[dist]+=1
            #以i为顶点的，第一个边有n种选择，第二个边有n-1 种选择
            for dist in dic:
                res+=  dic[dist]*(dic[dist]-1)  
        
        return res

pass了 hashmap先按照距离分类， 然后每个距离下按照起始点分类，比如距离为1下 其实点为0的edge总共有n个，那么组成三角形能组成n*n-1个。

448. Find All Numbers Disappeared in an Array (Easy)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        #
        n=len(nums)
        
        for i in range(n):
            ind = abs(nums[i])-1
            nums[ind]=-abs(nums[ind])
        
        res=[]
        for i in range(n):
            if nums[i]>0:
                res.append(i+1)
        return res

449. Serialize and Deserialize BST (Medium)

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        res=[]
        def pre(root):
            if not root: 
                res.append('#')
                return
            res.append(str(root.val))
            pre(root.left)
            pre(root.right)
        pre(root)
        return ','.join(res)
        

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        data=data.split(',')
        def pre(data):
            if not data: return None
            cur=data.pop(0) 
            root=None
            if cur!='#':
                root=TreeNode(int(cur))
            
            if root and data:
                root.left=pre(data)
            if root and data:
                root.right=pre(data)
            return root
        return pre(data)
#MY ANSWER
class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not root: return '#'
        rootval = str(root.val)
        l = self.serialize(root.left)
        r = self.serialize(root.right)
        return ','.join([rootval,l,r])

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if data=='#': return None
        data = data.split(',')
        print(data)
        def decode(data):
            val = data.pop(0)
            if val=='#': return None
            root = TreeNode(int(val))
            root.left = decode(data)
            root.right = decode(data)
            return root
        #print(data)
        
        return decode(data)

#答案用postorder compressed string 更好
class Codec:
    def serialize(self, root):
        """
        Encodes a tree to a single string.
        """
        def postorder(root):
            return postorder(root.left) + postorder(root.right) + [root.val] if root else []
        return ' '.join(map(str, postorder(root)))

    def deserialize(self, data):
        """
        Decodes your encoded data to tree.
        """
        def helper(lower = float('-inf'), upper = float('inf')):
            if not data or data[-1] < lower or data[-1] > upper:
                return None
            
            val = data.pop()
            root = TreeNode(val)
            root.right = helper(val, upper)
            root.left = helper(lower, val)
            return root
        
        data = [int(x) for x in data.split(' ') if x]
        return helper()

450. Delete Node in a BST （Medium）

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.

class Solution:
    def successor(self, root):
        """
        One step right and then always left
        """
        root = root.right
        while root.left:
            root = root.left
        return root.val
    
    def predecessor(self, root):
        """
        One step left and then always right
        """
        root = root.left
        while root.right:
            root = root.right
        return root.val
        
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        
        # delete from the right subtree
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        # delete from the left subtree
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        # delete the current node
        else:
            # the node is a leaf
            if not (root.left or root.right):
                root = None
            # the node is not a leaf and has a right child
            elif root.right:
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)
            # the node is not a leaf, has no right child, and has a left child    
            else:
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)
                        
        return root

#MY SOLUTION
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        def successor(root):
            root =root.right
            while root.left:
                root = root.left
            return root.val
        
        def predecessor(root):
            root = root.left
            while root.right:
                root =root.right
            return root.val
        

        if not root: return None
        
        # del from right
        if key>root.val:
            root.right = self.deleteNode(root.right,key)
        elif key<root.val:
            root.left = self.deleteNode(root.left,key)
        else:
            #key==root.val

            if not  root.left and not root.right:
                root = None
            
            elif root.right:
                # the node is not a leaf and has a right child
                root.val = successor(root)
                root.right = self.deleteNode(root.right,root.val)
            else:
                root.val = predecessor(root)
                root.left = self.deleteNode(root.left,root.val)
        
        return root

这个是很经典的一个题目。recursion方法很经典。