solutions2


Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list.

In [ ]:
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return None
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
        return None

Integer to Roman

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

In [ ]:
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        C = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        V = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

        ans = ""
        for v, c in zip(V, C):
            if num >= v:
                counts = num / v
                num = num % v
                ans += c*counts
        return ans

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".

In [21]:
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        dp = [True]
        L = len(s)
        for i in xrange(L):
            dp.append(False)
            for j in xrange(i, -1, -1):
                if dp[j] and s[j:i+1] in wordDict:
                    dp[-1] = True
                    break
        return dp[L]

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique.

In [ ]:
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        total, left, start = 0, 0, 0
        for i in xrange(len(gas)):
            diff = gas[i] - cost[i]
            total += diff
            left += diff
            if left < 0:
                left = 0
                start = i+1
        if total < 0:
            return -1
        else:
            return start

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

In [ ]:
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dic = {}
    def cloneGraph(self, node):
        if node is None:
            return None
        if node.label in self.dic:
            return self.dic[node.label]
        root = UndirectedGraphNode(node.label)
        self.dic[node.label] = root
        for node in node.neighbors:
            root.neighbors.append(self.cloneGraph(node))
        return root

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]

In [ ]:
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        def isPalindrome(s):
            L = len(s)
            mid = L/2
            if L % 2 == 0:
                return s[:mid] == s[:mid-1:-1]
            else:
                return s[:mid] == s[:mid:-1]
        
        ans = []
        def search(s, parent):
            if s == "":
                ans.append(parent)
            else:
                for i in xrange(1, len(s)+1):
                    c = s[:i]
                    if isPalindrome(c):
                        search(s[i:], parent+[c])
        search(s, [])
        return ans

Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X

In [ ]:
class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        rows = len(board)
        if rows == 0:
            return
        cols, queue = len(board[0]), []
        def fill(row, col):
            if row >=0 and row < rows and col >= 0 and col < cols and board[row][col] == 'O':
                board[row][col] = 'D'
                queue.append((row+1,col))
                queue.append((row-1,col))
                queue.append((row,col+1))
                queue.append((row,col-1))
        
        def bfs(row, col):
            queue.append((row, col))
            while queue:
                pos = queue.pop()
                fill(pos[0], pos[1])
                
        for col in xrange(cols):
            bfs(0, col)
            bfs(rows-1, col)
        
        for row in xrange(1, rows-1):
            bfs(row, 0)
            bfs(row, cols-1)
            
        for row in xrange(rows):
            for col in xrange(cols):
                if board[row][col] == 'D':
                    board[row][col] = 'O'
                elif board[row][col] == 'O':
                    board[row][col] = 'X'

In [18]:
s = 'aba'
for i in xrange(len(s)):
    print s[:idd]


a
ab

Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

In [ ]:
class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max1, max2, max3 = [None]*3
        L = len(nums)
        while L > 0:
            L -= 1
            v = nums[L]
            if max1 is None:
                max1 = v
            elif v > max1:
                max1, max2, max3 = v, max1, max2
            elif v == max1:
                continue
            else:
                if max2 is None:
                    max2 = v
                elif v > max2:
                    max2, max3 = v, max2
                elif v == max2:
                    continue
                else:
                    if max3 is None or v > max3:
                        max3 = v
        return max1 if max3 is None else max3

Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example: Input: "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

In [ ]:
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        counts = {}
        ans, carry = 0, 0
        for c in s:
            if c in counts:
                counts[c] += 1
            else:
                counts[c] = 1
        for _, v in counts.items():
            if v > 1:
                if v % 2 == 0:
                    ans += v
                else:
                    ans += (v-1)
                    carry  = 1
            else:
                carry = 1
        return ans+carry

Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Example: n = 15, Return: [ "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz" ]

In [ ]:
class Solution(object):
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []
        for v in xrange(1, n+1):
            if v % 3 == 0 and v % 5 == 0:
                ans.append("FizzBuzz")
            elif v % 3 == 0:
                ans.append("Fizz")
            elif v % 5 == 0:
                ans.append("Buzz")
            else:
                ans.append(str(v))
        return ans

Add Strings

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2. Note: The length of both num1 and num2 is < 5100. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly.

In [ ]:
class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        i, j, carry = len(num1), len(num2), 0
        ans = ''
        while i or j or carry:
            digit = carry
            if i:
                i -= 1
                digit += int(num1[i])
            if j:
                j -= 1
                digit += int(num2[j])
            ans += str(digit%10)
            carry = digit/10
        return ans[::-1]

Sum of Left Leaves

Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

In [ ]:
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        def isLeave(node):
            return node.left is None and node.right is None
        def leftLeave(node):
            if node:
                if node.left and isLeave(node.left):
                    self.ans += node.left.val
                leftLeave(node.left)
                leftLeave(node.right)
        leftLeave(root)
        return self.ans

Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent. Example: Input: n = 1 Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"] Note: The order of output does not matter. The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00". The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

In [ ]:
class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        def convert(n, nums):
            L = len(nums)
            if n > L:
                return []
            if n == 0:
                return [0]
            if n == 1:
                return nums
            else:
                ans = []
                for i in xrange(len(nums)):
                    for v in convert(n-1, nums[i+1:]):
                        ans.append(nums[i]+v)
                return ans
        times = []
        for h in xrange(num+1):
            m = num - h
            minutes = convert(m, [1,2,4,8,16,32])
            for hour in convert(h, [1,2,4,8]):
                if hour < 12:
                    for minute in minutes:
                        if minute < 60:
                            if minute > 9:
                                times.append("{}:{}".format(hour, minute))
                            else:
                                times.append("{}:0{}".format(hour, minute))
        return times

Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231). Example 1: Input: 3 Output: 3 Example 2: Input: 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

In [ ]:
class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        L, cnt, start = 1, 9, 1
        while n > L * cnt:
            n -= L * cnt
            L += 1
            cnt *= 10
            start *= 10
        start += (n-1) / L
        return int(str(start)[(n-1)%L])

Rotate Function

Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow: F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. Calculate the maximum value of F(0), F(1), ..., F(n-1). Note: n is guaranteed to be less than 105. Example: A = [4, 3, 2, 6] F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

In [ ]:
class Solution(object):
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        def F(nums):
            S = 0
            for i in xrange(len(nums)):
                S += i * nums[i]
            return S
        S, L = sum(A), len(A)
        ans = F(A)
        last = ans
        for n in A[::-1]:
            now = last + S - L*n
            if now > ans:
                ans = now
            last = now
        return ans

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2.

In [ ]:
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        counts = {}
        for c in s:
            if c in counts:
                counts[c] += 1
            else:
                counts[c] = 1
        for i in xrange(len(s)):
            if counts[s[i]] == 1:
                return i
        return -1

Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used. Note: All letters in hexadecimal (a-f) must be in lowercase. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character. The given number is guaranteed to fit within the range of a 32-bit signed integer. You must not use any method provided by the library which converts/formats the number to hex directly.

In [ ]:
class Solution(object):
    def toHex(self, num):
        """
        :type num: int
        :rtype: str
        """
        hexs = '0123456789abcdef'
        if num < 0:
            num += 0x100000000
        ans = []
        while num > 0:
            ans.append(hexs[num%16])
            num /= 16
        return ''.join(ans[::-1]) if ans else '0'

Find the Difference

Given two strings s and t which consist of only lowercase letters. String t is generated by random shuffling string s and then add one more letter at a random position. Find the letter that was added in t.

In [ ]:
import collections
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        counts = collections.Counter(s)
        for c in t:
            if c in counts and counts[c] > 0:
                counts[c] -= 1
            else:
                return c

Ransom Note


In [ ]:
import collections
class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        counts = collections.Counter(magazine)
        for c in ransomNote:
            if c in counts and counts[c] > 0:
                counts[c] -= 1
            else:
                return False
        return True

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!

In [ ]:
class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            mid = (left+right)/2
            val = guess(mid)
            if val is 0:
                return mid
            elif val is 1:
                left = mid+1
            else:
                right = mid-1

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order.

In [ ]:
import collections
class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        count = collections.Counter(nums1)
        join = []
        for n in nums2:
            if n in count and count[n] > 0:
                join.append(n)
                count[n] -= 1
        return join

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. Note: Each element in the result must be unique. The result can be in any order.

In [ ]:
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1)&set(nums2))

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Given s = "hello", return "holle". Example 2: Given s = "leetcode", return "leotcede".

In [ ]:
class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = [c for c in s]
        vowels = 'aeiouAEIOU'
        left, right = 0, len(s)-1
        while True:
            while left < right and s[left] not in vowels:
                left += 1
            while left < right and s[right] not in vowels:
                right -= 1
            if left >= right:
                return ''.join(s)
            else:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1

Reverse String

Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh".

In [ ]:
class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s[::-1]

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Follow up: Could you solve it without loops/recursion?

In [ ]:
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        cur = 0
        while num > 3:
            cur += num&3
            num = num >> 2
        return num == 1 and cur == 0

Power of Three

Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion?

In [ ]:
class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and 1162261467 % n == 0

Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap. For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

In [ ]:
class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n%4 != 0

Word Pattern

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str. Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false. Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

In [ ]:
class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        S = str.split()
        pre, vals = {}, set()
        if len(S) != len(pattern):
            return False
        for p, s in zip(pattern, S):
            if p in pre:
                if pre[p] != s:
                    return False
            else:
                if s in vals:
                    return False
                else:
                    pre[p] = s
                    vals.add(s)
        return True

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to sumRange function.

In [ ]:
class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.pre = []
        S = 0
        for n in nums:
            S += n
            self.pre.append(S)

    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.pre[j]
        else:
            return self.pre[j] - self.pre[i-1]

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. For example: Secret number: "1807" Friend's guess: "7810" Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.) 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. In the above example, your function should return "1A3B". Please note that both secret number and friend's guess may contain duplicate digits, for example: Secret number: "1123" Friend's guess: "0111" In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".

In [ ]:
class Solution(object):
    def getHint(self, secret, guess):
        """
        :type secret: str
        :type guess: str
        :rtype: str
        """
        pre = {}
        for n in guess:
            if n in pre:
                pre[n] += 1
            else:
                pre[n] = 1
        A, B = 0, 0
        for n1, n2 in zip(secret, guess):
            if n1 == n2:
                A += 1
                if pre[n1] > 0:
                    pre[n1] -= 1
                else:
                    B -= 1
            elif n1 in pre and pre[n1] > 0:
                B += 1
                pre[n1] -= 1
        return "{}A{}B".format(A, B)

Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.

In [ ]:
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count, pos = 0, 0
        for n in nums:
            if n == 0:
                count += 1
            else:
                nums[pos] = n
                pos += 1
        while count > 0:
            nums[pos] = 0
            pos += 1
            count -= 1

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.

In [ ]:
class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = (left+right)/2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        if isBadVersion(right):
            return right
        else:
            return right+1

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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number.

In [ ]:
class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        while num > 1:
            if num % 2 == 0:
                num /= 2
            elif num % 3 == 0:
                num /= 3
            elif num % 5 == 0:
                num /= 5
            else:
                return False
        return num == 1

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime?

In [ ]:
class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0:
            return 0
        return (num-1)%9+1

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: ["1->2->5", "1->3"]

In [ ]:
class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        paths = []
        def helper(node, path):
            if node:
                val = str(node.val)
                if node.left is None and node.right is None:
                    paths.append("->".join(path+[val]))
                else:
                    helper(node.left, path+[val])
                    helper(node.right, path+[val])
        helper(root, [])
        return paths

Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time Each intermediate word must exist in the word list For example, Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

In [ ]:
import string
import collections
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        wordList.add(endWord)
        queue = collections.deque([(beginWord, 1)])
        
        while queue:
            word, steps = queue.popleft()
            if word == endWord:
                return steps
            for i in xrange(len(word)):
                left, right = word[:i], word[i+1:]
                for c in string.lowercase:
                    if c is not word[i]:
                        newWord = left+c+right
                        if newWord in wordList:
                            queue.append((newWord, steps+1))
                            wordList.remove(newWord)
        return 0

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false. Note: You may assume the string contains only lowercase alphabets.

In [ ]:
class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        pre = {}
        for c in s:
            if c in pre:
                pre[c] += 1
            else:
                pre[c] = 1
        for c in t:
            if c in pre:
                if pre[c] > 0:
                    pre[c] -= 1
                else:
                    return False
            else:
                return False
        return sum(pre.values()) == 0

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

In [ ]:
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        def findMiddle(node):
            fast, slow = node, node
            while fast and fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverseNode(node):
            if node is None or node.next is None: return node
            node = node.next
            prev = None
            cur = node
            while cur:
                temp = cur
                cur = cur.next
                temp.next = prev
                prev = temp
            return prev
        mid = findMiddle(head)
        tail = reverseNode(mid)
        while head and tail:
            if head.val != tail.val:
                return False
            head = head.next
            tail = tail.next
        return True

Implement Queue using Stacks

Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.

In [ ]:
class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        self.stack = self.stack[1:]

    def peek(self):
        """
        :rtype: int
        """
        return self.stack[0]

    def empty(self):
        """
        :rtype: bool
        """
        return self.stack == []

Power of Two

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

In [ ]:
class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        while n > 1:
            if n % 2 == 1:
                return False
            n /= 2
        return n == 1

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

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

Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1

In [ ]:
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return root
        temp = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(temp)
        return root

Implement Stack using Queues

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.


In [ ]:
class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.Q = []

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.Q = [x] + self.Q

    def pop(self):
        """
        :rtype: nothing
        """
        self.Q = self.Q[1:]

    def top(self):
        """
        :rtype: int
        """
        return self.Q[0]

    def empty(self):
        """
        :rtype: bool
        """
        return self.Q == []

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure. Rectangle Area Assume that the total area is never beyond the maximum possible value of int.

In [ ]:
class Solution(object):
    def computeArea(self, A, B, C, D, E, F, G, H):
        width = [A, E, C, G]
        height = [B, D, F, H]
        width.sort()
        height.sort()
        total = (C-A)*(D-B) + (G-E)*(H-F)
        if E > C or A > G or B > H or F > D:
            return total
        else:
            if (A == width[1] and C == width[2]) and (B == height[1] and D == height[2]):
                return (G-E)*(H-F)
            if (E == width[1] and G == width[2]) and (F == height[1] and H == height[2]):
                return (C-A)*(D-B)
            w = width[1] - width[2]
            h = height[1] - height[2]
            return total - w * h

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

In [ ]:
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        L = len(nums)
        index = {}
        for i in xrange(L):
            if nums[i] in index:
                for j in index[nums[i]]:
                    if i - j <= k:
                        return True
                index[nums[i]].append(i)
            else:
                index[nums[i]] = [i]
        
        return False

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” _______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5 For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

In [ ]:
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root in (None, p, q):
            return root
        left, right = (self.lowestCommonAncestor(node, p, q) for node in (root.left, root.right))
        if left and right:
            return root
        elif left:
            return left
        else:
            return right

Reverse Linked List

Reverse a singly linked list.

In [ ]:
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        tail = head
        head = head.next
        tail.next = None
        while head:
            temp = head
            head = head.next
            temp.next = tail
            tail = temp
        return tail

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. For example, Given "egg", "add", return true. Given "foo", "bar", return false. Given "paper", "title", return true.

In [ ]:
class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        Ls, Lt = len(s), len(t)
        if Ls != Lt:
            return False
        i, j = 0, 0
        code = {}
        vals = set()
        while i < Ls and j < Lt:
            if s[i] in code:
                if code[s[i]] != t[j]:
                    return False
            else:
                if t[j] in vals:
                    return False
                else:
                    code[s[i]] = t[j]
                    vals.add(t[j])
                    
            i += 1
            j += 1
        return True

Count Primes

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

In [ ]:
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [True] * max(n, 2)
        isPrime[0], isPrime[1] = False, False
        x = 2
        while x * x < n:
            if isPrime[x]:
                p = x * 2
                while p < n:
                    isPrime[p] = False
                    p += x
            x += 1
        return sum(isPrime)