672. Bulb Switcher II

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 …, n], function of these 4 buttons are given below:

  1. Flip all the lights.
  2. Flip lights with even numbers.
  3. Flip lights with odd numbers.
  4. Flip lights with (3k + 1) numbers, k = 0, 1, 2, …

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

Note: n and m both fit in range [0, 1000].

class Solution(object):
    def flipLights(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        
        if m==0: return 1
        
        if n == 1: return 2
        
        
        def h2():
            status = [[0]*4 for _ in xrange(m+1)]
            
            status[0][3] = 1
            
            for i in range(1,m+1):
                for j,s in enumerate(status[i-1]):
                    if s: 
                        for idx in range(4):
                            if idx != j:
                                status[i][idx] = 1
                                
            return sum(status[m])
        
        def h3():
            status = [[0]*8 for _ in xrange(m+1)]
            
            status[0][7] = 1
            
            for i in range(1,m+1):
                for j,s in enumerate(status[i-1]):
                    if s:
                        status[i][j^7] = 1
                        status[i][j^5] = 1
                        status[i][j^2] = 1
                        status[i][j^1] = 1
                        
            return sum(status[m])
        
        
        if n==2: return h2()
        
        return h3()

 

 

670. Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

  1. The given number is in the range [0, 108]
class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        def helper(s):
            if not s: return ''
            d = max(s)
            if s[0] == d: return s[0]+helper(s[1:])
            
            for idx in xrange(len(s)-1,0,-1):
                if s[idx] == d:
                    return d+s[1:idx]+s[0]+s[idx+1:]
                
        
        return int(helper(str(num)))

 

669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2

Example 2:

Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1
class Solution(object):
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        def h1(r):
            if r is None: return None
            if r.val<L: 
                return h1(r.right)
            else:
                r.left = h1(r.left)
                return r
            
        def h2(r):
            if r is None: return None
            if r.val>R:
                return h2(r.left)
            else:
                r.right = h2(r.right)
                return r
            
        root = h1(root)
        root = h2(root)
        
        return root
            

671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
class Solution(object):
    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        
        Min = root.val
        ans = 1e9
        stack = [root]
        
        while stack:
            nstack = []
            
            for n in stack:
                if n.val>Min:
                    ans = min(ans,n.val)
                    
                if n.left: 
                    nstack.append(n.left)
                    nstack.append(n.right)
                    

            
            stack = nstack
        
        
        if ans<1e9: return ans
        return -1

666. Path Sum IV

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.
If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.
For each integer in this list:
  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of this node, 0 <= V <= 9.
Example 1:
Input: [113, 215, 221]
Output: 12
Explanation: 
The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.
Example 2:
Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1

The path sum is (3 + 1) = 4.

665. Non-decreasing Array

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        stack = []
        
        flag = False
        for n in nums:
            if not stack: 
                stack.append(n)
                continue
            
            if n < stack[-1]:
                if flag: return False
                
                if len(stack)<=1:
                    stack[-1] = min(n,stack[-1])
                else:
                    if n>stack[-2]:
                        stack[-1] = min(n,stack[-1])
                flag = True
            else:
                stack.append(n)
            
                
        return True

 

 

667. Beautiful Arrangement II

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, … , an], then the list [|a1 – a2|, |a2 – a3|, |a3 – a4|, … , |an-1 – an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

  1. The n and k are in the range 1 <= k < n <= 104.
class Solution(object):
    def constructArray(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        def construct(k):
            
            nums = set(range(2,k+2))
            ans = [1]
            
            for d in range(k,0,-1):
                if ans[-1] + d in nums:
                    nums.remove(ans[-1] + d)
                    ans.append(ans[-1] + d)
                else:
                    nums.remove(ans[-1] - d)
                    ans.append(ans[-1] - d)
                    
                    
            return ans
        
        return construct(k) + range(k+2,n+1)

 

668. Kth Smallest Number in Multiplication Table

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

  1. The m and n will be in the range [1, 30000].
  2. The k will be in the range [1, m * n]

awice’s solution

def findKthNumber(self, m, n, k):
    def enough(x):
        return sum(min(x / i, n) for i in xrange(1, m+1)) >= k

    lo, hi = 1, m*n
    while lo < hi:
        mi = (lo + hi) / 2
        if not enough(mi):
            lo = mi + 1
        else:
            hi = mi
    return lo

 

663. Equal Tree Partition

Given a binary tree with n nodes, your task is to check if it’s possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example 1:

Input:     
    5
   / \
  10 10
    /  \
   2   3

Output: True
Explanation: 
    5
   / 
  10
      
Sum: 15

   10
  /  \
 2    3

Sum: 15

Example 2:

Input:     
    1
   / \
  2  10
    /  \
   2   20

Output: False
Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.

Note:

  1. The range of tree node value is in the range of [-100000, 100000].
  2. 1 <= n <= 10000
class Solution(object):
    def checkEqualTree(self, root):
        
        self.total = 0
        self.ans = None
        
        def helper(r):
            if r is None: return 0
            s =  r.val +helper(r.left)+helper(r.right)
            
            if self.total == s*2 and r is not root: self.ans = True
                
            return s
        
        if not root: return False
        self.total,self.ans = helper(root),False
        
        helper(root)
        
        return self.ans

 

662. Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the nullnodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).


Note: Answer will in the range of 32-bit signed integer.

class Solution(object):
    def widthOfBinaryTree(self, root):
        
        stack = [(root,0)]
        ans = 0
        
        while stack:
            
            nstack = []
            
            left,right = None,None
            for r,idx in stack:
                if r.left: nstack.append((r.left,2*idx))
                if r.right: nstack.append((r.right,2*idx+1))
                
                if left is None:
                    left = idx 
                else:
                    left = min(left,idx)
                    
                if right is None:
                    right = idx 
                else:
                    right = max(right,idx)
            
            ans = max(right-left+1,ans)
            stack = nstack
            
        return ans