231. Power of Two (Easy)

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

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<0: return False
        c=0
        while n:
            lastbit= n%2
            if lastbit==1:
                c+=1
            n=n>>1
        return c==1

#answer is great
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0: return False
        # 1 000 000 000
        #    111 111 111
        return n&(n-1)==0

232. Implement Queue using Stacks (Easy)

class MyQueue:

    def __init__(self):
        self.s1=[]
        self.s2=[]
        

    def push(self, x: int) -> None:
        self.s1.append(x)

    def pop(self) -> int:
        # 1 2 3
        # 3 2 1
        while self.s1:
            self.s2.append(self.s1.pop())
        val=self.s2.pop()
        while self.s2:
            self.s1.append(self.s2.pop())
        
        return val

    def peek(self) -> int:
        pre=None
        while self.s1:
            cur=self.s1.pop()
            self.s2.append(cur)
            pre=cur
        while self.s2:
            self.s1.append(self.s2.pop())
        
        return pre
        

    def empty(self) -> bool:
        return len(self.s1)==0


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity?

class MyQueue:

    def __init__(self):
        self.s1=[]
        self.s2=[]
        self.front=None

    def push(self, x: int) -> None:
        if self.s1==[]:
            self.front=x
        self.s1.append(x)

    def pop(self) -> int:
        if self.s2==[]:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()

    def peek(self) -> int:
        if self.s2:
            return self.s2[-1]
        
        return self.front
          
        
    def empty(self) -> bool:
        return self.s1==[] and self.s2==[]

follow up的思路挺有意思，push: 数字保存在s1，但是当s1为空时候，保存front。 pop：如果s2有元素，pop s2， 否则 把s1 push到s2 peek: 若s2 有元素，peek s2 否则 就是 front。

233. Number of Digit One （Hard）

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example：
Input: n = 13
Output: 6
1，10， 11，12，13

class Solution:
    def countDigitOne(self, n: int) -> int:
        c=0
        i=1
        while i<=n:
            divider = i*10
            c += (n//divider)*i + min(max(n%divider -i+1,0),i)
            i*=10
        return c

完全不是考算法，对于个位来说，存在1的位置有，1，11，21，31，41，51，61，71 ... 基本10个一循环，比如 1到13的个位为1的有1，11，总共2个。 所以是 13//10 + (13%10)!=0。 对于十位来说存在1的有， 10，11，12，。。。19 | 110，111，112，113，。。。119| 210,...，每100个一循环，比如1到113的十位， (113/ 100) * 10 + min(max(113%100-10+1,0),10) 同理千位100,101,...199| 1100,1101....1199|.... 千位中1的个数 (n/1000)*100 + min(max(n%1000-100+1,0),100) 具体的循环截断1的个数是在 0到 100之间， 具体多少是n%1000-100+1.

234. Palindrome Linked List (Easy)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        
        fast=slow=head
        
        while slow and fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        
        if fast:
            mid=slow.next
        else:
            mid=slow
            
        
        def rev(node):
            pre=None
            while node:
                nodenext=node.next
                node.next=pre
                pre=node
                node=nodenext
            return pre
        
        revmid  = rev(mid)
        
        while revmid:
            if revmid.val!=head.val:
                return False
            revmid=revmid.next
            head=head.next
        return True
        #1 2 3 4 5
        #    s m
        #        f
                
        #1 2 3 4
        #    s
        #    m   f  

235. Lowest Common Ancestor of a Binary Search Tree （Medium）

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 
        #    all left ,  all right,    p mid q
        #
        
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

。。。没仔细看题，忽略了这个是个BST，得用BST性质。

236. Lowest Common Ancestor of a Binary Tree （Medium）

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

class Solution:
    dic=dict()
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def find(root,node):
            if not root: return False
            if (root.val,node.val) in self.dic:
                return self.dic[(root.val,node.val)]
          
            if root.val==node.val:
                self.dic[(root.val,node.val)]=True
                return True
            if find(root.left,node):
                self.dic[(root.left.val,node.val)]=True
                return True
            if find(root.right,node):
                if root.right:
                    self.dic[(root.right.val,node.val)]=True
                return True
            return False
        
        if find(root.left,p) and find(root.left,q):
            return self.lowestCommonAncestor(root.left,p,q)
        elif find(root.right,p) and find(root.right,q):
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root
#answer way of writting
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        if root in [p,q,None]: return root
        
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        
        
        if left and right: 
            return root
        if left: 
            return left
        if right:
            return right

第一次尝试Time limit exceeded...，得找到p，q是在root的同侧还是异侧。 由于是递归调用，find funciton call了太多次，所以用memerization 方法， pass了。答案思路： 如果root 是{p,q,None} 就返回root， left=从root.left找p，q共同祖先， right=从root.right 找p，q共同祖先。

237. Delete Node in a Linked List (Easy)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        
      if node.next:
            node.val=node.next.val
            node.next=node.next.next

把下一位数字覆盖到当前node， 然后跳过这个node。

238. Product of Array Except Self （Medium）

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        prefix_left = [1]*len(nums)
        prefix_right= [1]*len(nums)
        
        for i in range(1,len(nums)):
            prefix_left[i] = prefix_left[i-1]*nums[i-1]
        for j in range(len(nums)-2,-1,-1):
            prefix_right[j] = prefix_right[j+1]*nums[j+1]
        res = []    
        for (l,r) in zip(prefix_left,prefix_right):
            res.append(l*r)
        return res

239. Sliding Window Maximum (Hard)

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        
        #if k==1: return nums
        
        stack_max = []
        queue = []
        res = []
        for n in nums:
            queue.append(n)
            
            
            while stack_max and n>stack_max[-1]:
                stack_max.pop()
            if not stack_max or  n>stack_max[-1]:
                stack_max.append(n)
            
            if len(queue)>k:
                expired = queue.pop(0)
                if expired == stack_max[-1]:
                    stack_max.pop()
            
            if len(queue)==k:
                #print(queue,stack_max)
                if stack_max:
                    res.append(stack_max[-1])
                else:
                    #the expired one is the max and poped out
                    newmax=max(queue)
                    res.append(newmax)
                    stack_max.append(newmax)
            
        return res
#answer way of writting
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        
        queue = collections.deque()
        res = []
        for i, n in enumerate(nums):
            while queue and n> nums[queue[-1]]:
                queue.pop()
            queue.append(i)
            #expire
            if queue[0] == i - k:
                queue.popleft()
            #can add to result
            if i >= k - 1:
                res.append(nums[queue[0]])
        return res
    
#         if not nums:
#             return []
#         start=0
#         r=[]
#         while start+k<=len(nums):
#             r.append(max(nums[start:start+k]))
#             start+=1
            
#         return r

初次尝试， time limit exceeded。QUEUE 是FIFO结构，适合sliding window，如果当前大，queue 要pop掉末尾元素， 如果过期，踢掉， queue中保存最大值位置。

240. Search a 2D Matrix II （Medium)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        
        def search(rowl,rowr,coll,colr,target):
            if rowl==rowr and coll==colr:
                return matrix[rowl][coll]==target
            elif rowl==rowr:
                return target in matrix[rowl]
            elif coll==colr:
                return target in [row[coll] for row in matrix]
            
            if  rowr-rowl==1 and colr-coll==1:    
                if matrix[rowl][coll]==target or matrix[rowr][colr]==target or matrix[rowr][coll]==target or matrix[rowl][colr]==target:
                    return True
                return False
            
            
            rowmid = (rowl+rowr)//2
            colmid = (coll+colr)//2
            if matrix[rowmid][colmid]==target:
                return True
            elif target<matrix[rowmid][colmid]:
                return search(rowl,rowmid,coll,colmid,target) or search(rowl,rowmid,colmid,colr,target) or search(rowmid,rowr,coll,colmid,target)
            else:
                return search(rowmid,rowr,colmid,colr,target) or search(rowl,rowmid,colmid,colr,target) or search(rowmid,rowr,coll,colmid,target)
            
        
        return search(0,len(matrix)-1,0,len(matrix[0])-1,target)

用了分治法，虽然写出来了，但感觉写了陀X。 答案分治法

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # an empty matrix obviously does not contain `target`
        if not matrix:
            return False

        def search_rec(left, up, right, down):
            # this submatrix has no height or no width.
            if left > right or up > down:
                return False
            # `target` is already larger than the largest element or smaller
            # than the smallest element in this submatrix.
            elif target < matrix[up][left] or target > matrix[down][right]:
                return False

            mid = left + (right-left) // 2

            # Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid]
            row = up
            while row <= down and matrix[row][mid] <= target:
                if matrix[row][mid] == target:
                    return True
                row += 1
            
            return search_rec(left, row, mid - 1, down) or \
                   search_rec(mid + 1, up, right, row - 1)

        return search_rec(0, 0, len(matrix[0]) - 1, len(matrix) - 1)

class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

    m = len(matrix)
    n = len(matrix[0])

    cur = [m-1,0]

    def valid(li):
        r,c = li
        if m>r>=0 and n>c>=0:
            return True
        return False
    
    while valid(cur):
        if matrix[cur[0]][cur[1]]==target: return True

        if target>matrix[cur[0]][cur[1]]:
            cur = [cur[0],cur[1]+1]
        else:
            cur = [cur[0]-1,cur[1]]

    return False

最佳答案 思路 ： 从左下角开始，如果target大于cur, 列+1， 如果targe 小于cur，行-1.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # an empty matrix obviously does not contain `target` (make this check
        # because we want to cache `width` for efficiency's sake)
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        # cache these, as they won't change.
        height = len(matrix)
        width = len(matrix[0])

        # start our "pointer" in the bottom-left
        row = height - 1
        col = 0

        while col < width and row >= 0:
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else: # found it
                return True
        
        return False