LeetCode 307. Range Sum Query - Mutable

'''
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
'''
#764ms, 15.8MB
class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
     

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: None
        """
        self.nums[i] = val
     

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

LeetCode 200. Number of Islands

'''
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

'''
class Solution:
    def findANDsink(self, i, j):
        if self.grid[i][j] == '1':
            self.grid[i][j] = '0'
            if not i == 0:
                self.findANDsink(i-1, j)
            if i < self.n-1:
                self.findANDsink(i+1, j)
            if not j == 0:
                self.findANDsink(i, j-1)
            if j < self.m-1:
                self.findANDsink(i, j+1)
       
   
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
       
        self.grid = grid
        self.n = len(grid)
        self.m = len(grid[0])
       
        i = 0
        j = 0
        self.count = 0
        for i in range(0, self.n):
            for j in range(0, self.m):
                if self.grid[i][j] == '1':
                    self.count += 1
                    self.findANDsink(i,j)
           
        return self.count

LeetCode 343. Integer Break

'''
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
'''
'''
first a few integers:
1: 0 (not available)
2: 1*1=1
3: 1*2=2
4: 2*2=4
5: 2*3=6
6: 3*3=9
7: 3*4=12

for n >= 4, can be break into 2s and 3s to max the product
proof:
if break into multiple numbers and one of it >= 5: it can be broken to get a larger product
so the max single number is 4, which is also 2*2   
   
'''

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 0
        elif n == 2: return 1
        elif n == 3: return 2
        elif n == 4: return 4
        else:
            result = 1
            while n > 4:
                result *= 3
                n -=3
            result *= n
            return result

LeetCode 338. Counting Bits

'''
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
'''
'''
Solution;
when n = 2k: count(n) = n/2
when n = 2k+1: count(n) = count(n/2) +1
'''

#76ms, 16MB
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num == 0: return [0]
        elif num == 1: return [0,1]
       
        result = [0, 1]
        for i in range(2, num+1):
            if i%2 == 0:
                result.append(result[i/2])
            else:
                result.append(result[(i-1)/2]+1)
       
        return result

LeetCode 303. Range Sum Query - Immutable

'''
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Key is the calculation efficiency.
'''

class NumArray1(object):
#1088 ms, 15.3 MB
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

class NumArray(object):
#144ms, 15.3MB
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.list = []
        total = 0
        for i in nums:
            total += i
            self.list.append(total)
           
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.list[j]
        else:
            return self.list[j] - self.list[i-1]

LeetCode 326. Power of Three

'''
Given an integer, write a function to determine if it is a power of three.
'''

class Solution(object):
    #120ms, 11.8MB
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0: return False
        if n == 1: return True
        else:
            while n % 3 == 0:
                n = n//3
                if n == 1: return True
            return False

LeetCode 268. Missing Number

'''
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
'''
class Solution(object):
    #256ms, 12.6MB
    def missingNumber1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x = 0       
        s = sum(nums)       
        return (len(nums)+1)*len(nums)/2 - s

LeetCode 299. Bulls and Cows

'''
You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows.

Please note that both secret number and friend's guess may contain duplicate digits.
'''


class Solution(object):
    #60ms, 11.9MB
    def getHint1(self, secret, guess):
        """
        :type secret: str
        :type guess: str
        :rtype: str
        """
        A = []
        C = {}
        D = {}
     
        for i in range(len(guess)):
            if guess[i] == secret[i]:
                A.append(i)
     
        def addtodict(dic, key):
            if key in dic:
                dic[key] += 1
            else:
                dic[key] = 1
     
        B = 0
        for i in range(len(guess)):
            if i not in A:
                addtodict(C, secret[i])
                addtodict(D, guess[i])
     
        for i in D:
            if i in C:
                B += min(D[i], C[i])
         
        return str(len(A))+'A'+str(B)+'B'

LeetCode 257. Binary Tree Paths

'''
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
'''

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

#20ms, 11MB
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if not root: return []
        if not root.left and not root.right: return [str(root.val)]
       
        connector = '->'
        self.result = []
       
        def pathstr(root, current):
            if not root:
                pass
            elif not root.left and not root.right:
                current += '->'+str(root.val)
                self.result.append(current[2:])
            else:
                current += '->'+str(root.val)
                pathstr(root.left, current)
                pathstr(root.right, current)
       
        pathstr(root, '')
       
        return self.result

LeetCode 658. Find K Closest Elements

'''
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
'''
class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        if k > len(arr): return arr
        if k == 0: return []
     
        subarr = []
        for i in arr:
            if i > x:
                subarr.append([i,i-x])
            else:
                subarr.append([i,x-i])
     
        subarr = sorted(subarr, key = lambda y: y[1])
        result = [i[0] for i in subarr[:k]]
        result.sort()
        return result

    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        if k > len(arr): return arr
        if k == 0: return []
       
        arr = sorted(arr, key = lambda y: abs(y-x))
        arr = arr[:k]
        arr.sort()
        return arr

LeetCode 374. Guess Number Higher or Lower

'''
We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!
'''
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        i = 1
        while n > i+1:
            j = (i+n)//2
            if guess(j) == -1:
                n = j
            elif guess(j) == 1:
                i = j
            else:
                return j
        if guess(i) == 0:
            return i
        else:
            return n

LeetCode 278. First Bad Version

'''
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
'''
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        i = 1
        while n > i+1:
            if isBadVersion((i+n)//2):
                n = (i+n)//2
            else:
                i = (i+n)//2
        if isBadVersion(i): return i
        else: return n
       

LeetCode 264. Ugly Number II

'''
Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
'''
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # target = 2**i * 3**j * 5**k
        i = j = k = 0
        l = [1]
        while n > 1:
            n_next = min(2*l[i], 3*l[j], 5*l[k])
            if n_next == 2*l[i]:
                i+=1
            elif n_next == 3*l[j]:
                j+=1
            else:
                k+=1
            if n_next not in l:
                l.append(n_next)
                n-=1
           
        return l[-1]

LeetCode 263. Ugly Number

'''
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
'''
class Solution:
    #52ms, 13.3MB
    def isUgly(self, num: int) -> bool:
        if num < 1: return False
       
        while num%2 == 0:
            num /= 2
       
        while num%3 == 0:
            num /= 3
       
        while num%5 == 0:
            num /=5
       
        if num == 1: return True
        else: return False

LeetCode 172. Factorial Trailing Zeroes

'''
Given an integer n, return the number of trailing zeroes in n!.
'''
class Solution:
    #seems working, but exceeds time
    def trailingZeroes1(self, n: int) -> int:
        if n == 0: return 0
        count = 0
        i = 1
        while i <= n:
            temp = i
            while temp % 10 == 0 or temp % 10 == 5:
                count += 1
                temp /= 5
            i += 1
        return count
   
    #improve from the above methods
    #60ms, 13.1MB
    def trailingZeroes(self, n: int) -> int:
        if n == 0: return 0
       
        count = 0
        i = 1
        #obtain min count for 5^count > n
        while i <= n:
            i *= 5
            count += n//i
       
        return count

LeetCode 206. Reverse Linked List

'''
Reverse a singly linked list.
'''
class Solution(object):
   
    #24ms, 92.92%, 13.1MB, 26.08%
    def reverseList1(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #try O(N) strorage
        l = []
        if not head: return None
        while head:
            l.append(head)
            head = head.next
        for i in range(-1, -len(l), -1):
            l[i].next = l[i-1]
        l[0].next = None
        return l[-1]

    #24ms, 12.8MB
    def reverseList2(self, head):
        #O(1) strorage
        if not head: return None
       
        p1 = head
        p2 = p1.next
        p1.next = None
        while p2:
            dump = p2
            p2 = p2.next
           
            dump.next = p1
            p1 = dump
       
        return p1

    #recursive, 24ms, 16.4MB
    def reverseList3(self, head):
        #recursive
        if not head or not head.next:
            return head
        else:
            dump = self.reverseList(head.next)
            head.next.next = head
            head.next = None
            return dump

LeetCode 205. Isomorphic Strings

'''
Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
'''
class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        ht1 = {}
        ht2 = {}
        for i in range(len(s)):
            if s[i] not in ht1:
                ht1[s[i]] = t[i]
            elif not ht1[s[i]] == t[i]:
                return False
            if t[i] not in ht2:
                ht2[t[i]] = s[i]
            elif not ht2[t[i]] == s[i]:
                return False
           
        return True

LeetCode 226. Invert Binary Tree

'''

Invert a binary tree.

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

#16ms, 11MB
class Solution1(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def invert(root):
            if root:
                temp = root.left
                root.left = root.right
                root.right = temp
                if root.left: invert(root.left)
                if root.right: invert(root.right)
     
        dump = root
        invert(dump)
        return root

#28ms, 10.7MB
class Solution2(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        dump = root
     
        if root:
            temp = root.left
            root.left = root.right
            root.right = temp
            if root.left: self.invertTree(root.left)
            if root.right: self.invertTree(root.right)
     
        return dump

LeetCode 204. Count Primes

'''
Count the number of prime numbers less than a non-negative number, n.

'''
#1248ms, 69.9MB
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        nl = [i for i in range(n)]
       
        for i in nl:
            if i > 1:
                j = i*2
                while j < n:
                    if not nl[j] == 1: nl[j] = 1
                    j += i
                   
        result = [k for k in nl if k > 1]
        return len(result)

LeetCode 202. Happy Number

'''
Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
'''

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        mem = {}
        while True:
            if n == 1:
                return True
            elif n in mem:
                return False
            else:
                mem[n]=1
                temp = 0
                for i in str(n):
                    temp += int(i)**2
                n = temp

LeetCode 190. Reverse Bits

'''
Reverse bits of a given 32 bits unsigned integer.

'''

#learned demical to binary and reverse

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        sn = bin(n)[2:]
        sn = '0'*(32-len(sn)) + sn
        sn = sn[::-1]
        return int(sn,2)

LeetCode 179. Largest Number

'''
Given a list of non negative integers, arrange them such that they form the largest number.

'''

'''
learned:
the use of build-in function sorted() including order and key
the customization of __lt__
'''

class cf(str):
    def __lt__(a, b):
        return a+b < b+a

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(i) for i in nums]
        result = ''.join(sorted(strs, reverse=True, key=cf))
        if result[0] == '0':
            return '0'
        else:
            return result
       

LeetCode 199. Binary Tree Right Side View

'''
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
       
        nodes = [root]
        result = []
        while nodes:
            result.append(nodes[-1].val)
            temp = []
            for i in nodes:
                if i.left: temp.append(i.left)
                if i.right: temp.append(i.right)
            nodes = temp
        return result

LeetCode 717. 1-bit and 2-bit Characters

'''
We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).
Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.
'''

'''
Key learning: the use of xor (or ^)
'''

class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        parity = bits.pop()
        while bits and bits.pop(): parity ^= 1
        return parity == 0

LeetCode 229. Majority Element II

'''
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.
'''

class Solution(object):
    #24ms, 11.6MB
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ht = {}
        for i in nums:
            if i in ht:
                ht[i] += 1
            else:
                ht[i] = 1
        return [i for i in ht if ht[i] > len(nums)//3]
       

LeetCode 169. Majority Element

'''
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
'''

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[len(nums)//2]

LeetCode 125. Valid Palindrome

'''
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.

'''
class Solution:
    #80ms, 13.6MB
    def isPalindrome1(self, s: str) -> bool:
           
        digits = '1234567890'
        lower = 'qwertyuiopasdfghjklzxcvbnm'
        upper = 'QWERTYUIOPASDFGHJKLZXCVBNM'
        ht = {i:j for i, j in zip(upper, lower)}
       
        ss= ''
        for i in s:
            if i in digits:
                ss += i
            elif i in lower:
                ss += i
            elif i in upper:
                ss += ht[i]
       
        n = len(ss)//2
        if n == 0: return True
        print (ss,'-', ss[:n],'-', ss[-n:][::-1])
        return ss[:n] == ss[-n:][::-1]

    #60ms, 13.6MB
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
       
        ss= ''
        for i in s:
            if i.isalnum(): ss += i
           
        n = len(ss)//2
        if n == 0: return True
        return ss[:n] == ss[-n:][::-1]

LeetCode 61. Rotate List

''' Given a linked list, rotate the list to the right by k places, where k is non-negative. ''' # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def rotateRight1(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ #problem: when k is too large, the direct method cannot work, thus need to obtain the length of the list first if not head or not head.next: return head else: p1 = p2 = head dump = None for i in range(k): p2 = p2.next if not p2.next: dump = p2 p2.next = p1 if dump: dump = p2.next p2.next = None return dump else: while p2.next: p1 = p1.next p2 = p2.next p2.next = head dump = p1.next p1.next = None return dump #24ms, 10.9MB def rotateRight(self, head, k): if not head or not head.next: return head else: n = 1 p1 = head while p1.next: p1 = p1.next n += 1 p1.next = head k = k%n p2 = ListNode(0) p2.next = head for i in range(n-k): p2 = p2.next p3 = p2.next p2.next = None return p3

LeetCode 189. Rotate Array

'''
Given an array, rotate the array to the right by k steps, where k is non-negative.

'''
class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            temp = nums.pop()
            nums.insert(0, temp)

LeetCode 94. Binary Tree Inorder Traversal

'''
Given a binary tree, return the inorder traversal of its nodes' values.

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

class Solution(object):
    #recursive
    def inorderTraversal1(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def inorder(node):
            if node.left:
                inorder(node.left)
            self.result.append(node.val)
            if node.right:
                inorder(node.right)
       
        self.result = []
        if root:
            inorder(root)
        return self.result

    #iterative
    def inorderTraversal(self, root):
        res, stack = [], []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            node = stack.pop()
            res.append(node.val)
            root = node.right

LeetCode 173. Binary Search Tree Iterator

'''
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#Runtime: 88 ms, Memory Usage: 20 MB
#next() can use pop(0)
class BSTIterator1(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.i = -1
        self.vals = []
       
        def add_val(root):
            if root:
                self.vals.append(root.val)
                add_val(root.left)
                add_val(root.right)
       
        add_val(root)
        self.vals.sort()

    def next(self):
        """
        @return the next smallest number
        :rtype: int
        """
        self.i += 1
        if self.i < len(self.vals):
            return self.vals[self.i]
        else:
            return None
       

    def hasNext(self):
        """
        @return whether we have a next smallest number
        :rtype: bool
        """
        return self.i < len(self.vals)-1

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

LeetCode 434. Number of Segments in a String

'''
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
'''

class Solution(object):
    def countSegments1(self, s):
        """
        :type s: str
        :rtype: int
        """
        return len(s.split())
   
    def countSegments(self, s):
        temp = ''
        count = 0
        for i in s:
            if i != ' ':
                temp += i
            else:
                if temp: count += 1
                temp = ''
        if temp: count += 1
        return count

LeetCode 165. Compare Version Numbers

'''
Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the .character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.
'''
class Solution1(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        s1 = version1.split('.')
        s2 = version2.split('.')
       
        n = min(len(s1), len(s2))
       
        for i in range(n):
            if int(s1[i]) > int(s2[i]):
                return 1
            elif int(s1[i]) < int(s2[i]):
                return -1
       
        if len(s1) > len(s2) and int(''.join(s1[n:])) > 0:
            return 1
        elif len(s1) < len(s2) and int(''.join(s2[n:])) > 0:
            return -1
        else:
            return 0

#without built-in functions (specially split() and join())
class Solution(object):
    def sp(self, string, splitter=' '):
        #split string into a list splitted by the splitter
        temp = ''
        sl = []
        for i in string:
            if i != splitter:
                temp += i
            else:
                if temp:
                    sl.append(temp)
                    temp = ''
        if temp:
            sl.append(temp)
            temp = ''
        return sl
   
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        s1 = self.sp(version1, '.')
        s2 = self.sp(version2, '.')
       
        n = min(len(s1), len(s2))
       
        for i in range(n):
            if int(s1[i]) > int(s2[i]):
                return 1
            elif int(s1[i]) < int(s2[i]):
                return -1
       
        s3sum = 0
        if n == len(s1):
            for i in s2[n:]:
                s3sum += int(i)
                if s3sum > 0: break
        else:
            for i in s1[n:]:
                s3sum += int(i)
                if s3sum > 0: break
           
        if len(s1) > len(s2) and s3sum > 0:
            return 1
        elif len(s1) < len(s2) and s3sum > 0:
            return -1
        else:
            return 0

LeetCode 142. Linked List Cycle II

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

#use list, 1172ms
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None       
        else:
            nodes = []
            while True:
                if not head in nodes:
                    nodes.append(head)
                    head = head.next
                    if not head: return None
                else:
                    return head

#use dictionary (hash-table), 40ms
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None       
        else:
            nodes = {}
            while True:
                if not head in nodes:
                    nodes[head] = None
                    head = head.next
                    if not head: return None
                else:
                    return head

LeetCode 141. Linked List Cycle

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

class Solution1(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
       
        result = []
        while head:
            if head in result:
                return True
            result.append(head)
            head = head.next
       
        return False

class Solution(object):
    def hasCycle(self, head):
        if not head:
            return False
       
        p1 = ListNode(0)
        p1.next = head
        p2 = head
       
        while True:
            if p2 != p1:
                p2 = p2.next
                if not p2: return False
            else:
                return True
           
            if p2 != p1:
                p2 = p2.next
                if not p2: return False
            else:
                return True
           
            p1 = p1.next
           
        return False
           

LeetCode 129. Sum Root to Leaf Numbers

'''
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def helper(i, node):
            if node:
                if not node.left and not node.right:
                    self.result += i*10+node.val
                if node.left: helper(i*10+node.val, node.left)
                if node.right: helper(i*10+node.val, node.right)
       
        self.result = 0
        helper(0, root)
        return self.result

LeetCode 559. Maximum Depth of N-ary Tree

'''
Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
'''
"""

# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""

class Solution:
    def maxDepth(self, root: 'Node') -> 'int':
        if not root:
            return 0
        elif not root.children:
            return 1
        else:
            return 1 + max([self.maxDepth(i) for i in root.children])

LeetCode 104. Maximum Depth of Binary Tree

'''
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
'''

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

class Solution:
    def maxDepth(self, root: 'TreeNode') -> 'int':
        if not root:
            return 0
        else:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

LeetCode 111. Minimum Depth of Binary Tree

'''
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def helper(self, i, root):
        if self.result == 0 or i < self.result:
            if not root.left and not root.right:
                self.result = i
            else:
                if root.left: self.helper(i+1, root.left)
                if root.right: self.helper(i+1, root.right)
   
    def minDepth(self, root: 'TreeNode') -> 'int':
        self.result = 0
        if root:
            self.helper(1, root)
        return self.result

LeetCode 102. Binary Tree Level Order Traversal

'''

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

'''

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

class Solution:
    def levelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
        if not root:
            return []
       
        result = [[root.val]]
        current = [root]
       
    while True:
            node = []
            for i in current:
                if i.left: node.append(i.left)
                if i.right: node.append(i.right)
            if node == []:
                break
            vals = [j.val for j in node]
            result.append(vals)
            current = node
     
        return result

LeetCode 107. Binary Tree Level Order Traversal II

'''

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

'''


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None


class Solution:

    def levelOrderBottom(self, root: 'TreeNode') -> 'List[List[int]]':

        if not root:

            return []

       

        def btt(i, root):

            if root:

                n = len(self.result)

                if i < -n:

                    self.result.insert(-n, [])

                self.result[i].append(root.val)

                if root.left:

                    btt(i-1, root.left)

                if root.right:

                    btt(i-1, root.right)

       

        self.result = []

        btt(-1,root)



        return self.result

LeetCode 145. Binary Tree Postorder Traversal

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

# Postorder (Left, Right, Root)

class Solution1:
    #recursive
    def postorderTraversal(self, root: 'TreeNode') -> 'List[int]':
       
        def addToList(root):
            if root:
                self.result.insert(0, root.val)
                addToList(root.right)
                addToList(root.left)
       
        self.result = []
        addToList(root)
        return self.result

class Solution:
    #iterative
    def postorderTraversal(self, root: 'TreeNode') -> 'List[int]':
       
        if not root:
            return []
       
        i = -1
        result = [root]
        while i >= -len(result):
            temp = result[i]
            if temp.left:
                result.insert(i, temp.left)
            if temp.right:
                result.insert(i, temp.right)
            i -= 1

        vals = [i.val for i in result]
        return vals

LeetCode 144. Binary Tree Preorder Traversal

'''
Given a binary tree, return the preorder traversal of its nodes' values.
'''
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution_1:

    #recursive

    def travel(self, root):

        if root:

            self.result.append(root.val)

            self.travel(root.left) 

            self.travel(root.right)        

    

    def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':

        self.result = []        

        if not root:

            return self.result

        else:

            self.travel(root)

            return self.result

'''

some thoughts:

preorder = root, left, right

the iterative method:

the key is that the length of the list changes at every iteration

for loop may not work this case, change to while loop and calculate the length of the list every time

every insert left and right to root, if any
first create list of all node, then val

'''

class Solution_2:

    #iterative

    def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':

        if not root:

            return []

        else:

            l = [root]

            i = 0

            while i < len(l):

                n = len(l)

                if l[i].right:                    

                    l.insert(i+1, l[i].right)

                if l[i].left:

                    l.insert(i+1, l[i].left)

                i += 1

            

            result = [j.val for j in l]

            return result