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]