LC

P11 . Longest Palindromic Subsequence

哇，好久没做这种dp的palindrom了。感觉好有意思，被虐得不行，不过我总觉得大佬们的O(n) space的solution大多数时候都是先用O（n^2）然后再优化出来的吧。

这道题主要是把递归公式推到出来就好做了。那个*2是为了让j-1<0的时候不要越界。

如果s[i] == s[j]:

dp[i][j] = 2 + dp[i+1][j-1] if i + 1 <= j - 1 else 2

不然的话

dp[i][j] = max(dp[i][j-1], dp[i+1][j])

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s: return 0
        n = len(s)
        dp = [[1]*n*2 for _ in range(n)]
        print(dp)

        for i in range(0, n-1)[::-1]:
            for j in range(i, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1] if i + 1 <= j - 1 else 2
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])

            print dp

        return dp[0][n/2]

s = Solution()
ans = s.longestPalindromeSubseq("bbbab")
print ans

P12. Top K Frequent Words

这道题好像可以用python的counter直接取巧。1行都可以解决

import collections
class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counter = collections.Counter(words)
        tmp = counter.most_common(k)
        return [val[0] for val in tmp]

s = Solution()
ans = s.topKFrequent(["i", "love", "leetcode", "i", "love", "coding", "i"], 2)
print ans

也可以先用counter然后再用一个heap来维护频率最高的几个单词。

import collections
import heapq
class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counter = collections.Counter(words)
        freqs = []

        for word, count in counter.items():
            heapq.heappush(freqs, (count, word))
            if len(freqs) > k:
                heapq.heappop(freqs)

        res = []
        for _ in range(k):
            res.append(heapq.heappop(freqs)[1])
        return res[::-1]

s = Solution()
ans = s.topKFrequent(["i", "love", "leetcode", "i", "love", "coding", "i"], 2)
print ans

P13. Combination Sum

我是一直觉得这道题挺好的。非常典型的一道dfs的问题。

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        return self.helper(candidates, target, [])

    def helper(self, nums, target, path, index=0, res=[]):
        # base case
        if target < 0:
            return
        if target == 0:
            res.append(path)

        # recursion body
        for i in range(index, len(nums)):
            self.helper(nums, target - nums[i], path + [nums[i]], i)

        return res


s = Solution()
ans = s.combinationSum([2, 3, 6, 7], 7)
print ans

P14. Insert Delete GetRandom O(1)

本来以为一个set就够了。结果发现python里面set不支持index。所以需要用一个array来存数，然后一个hash table来存数的位置。

import random
class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.pos = {}


    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums) - 1
            return True
        return False


    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.pos:
            ind = self.pos[val]
            self.nums[ind] = self.nums[-1]
            self.pos[self.nums[-1]] = ind
            self.nums.pop()
            self.pos.pop(val, 0)
            return True
        return False


    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.nums) if self.nums else None

val = 0
obj = RandomizedSet()
param_1 = obj.insert(val)
param_2 = obj.remove(val)
param_3 = obj.getRandom()

P15. Swap Nodes in Pairs

我觉得这道题，其实命名特别重要，不然写出来也是一团糟别人看不懂。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head and not haed.next:
            return head

        dummy = ListNode('#')
        pre_head = dummy

        while head and head.next:
            # store nodes
            first = head
            second = head.next
            new_head = second.next
            # shift order
            second.next = first
            first.next = new_head
            pre_head.next = second
            # update nodes
            pre_head = first
            head = pre_head.next
        return dummy.next


a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
e = ListNode(5)
a.next, b.next, c.next, d.next = b, c, d, e
print a.val, a.next.val, a.next.next.val, a.next.next.next.val
s = Solution()
ans = s.swapPairs(a) 
print ans.val, ans.next.val, ans.next.next.val, ans.next.next.next.val, ans.next.next.next.next.val

P16. Delete Node in a BST

这道题的递推解法的思路是，如果找到了那个node. 那么把那个node的右subtree给加到node左边subtree的right most node的right.然后再返回node的left child。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return None

        if root.val == key:
            if root.left:
                left_right_most = root.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                left_right_most.right = root.right
                return root.left
            else:
                return root.right
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
        return root

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)

b.left, b.right = a, c

so = Solution()
root = so.deleteNode(b, 1)
print root.val, root.right.val

突然想起bb当年挂我的一道题。找second largest node in BST。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def secondLargest(self, root):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        pre = None
        while root.right:
            pre = root
            root = root.right
        if not root.left:
            return pre

        cur = root.left
        while cur.right:
            cur = cur.right
        return cur

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(2.5)

b.left, b.right = a, c
c.left = d

so = Solution()
ans = so.secondLargest(b)
print ans.val

P17. Asteroid Collision

用stack来解决。好多corner case。没想到我写的一遍就过了。

class Solution(object):
    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        stack = []
        for n in asteroids:
            if not stack or n > 0:
                stack.append(n)
            else:
                # if last digit is negative we append
                if stack[-1] < 0:
                    stack.append(n)
                else:
                    # if last digit is positive we need to break as much asteroid as we can
                    while stack and stack[-1] > 0 and stack[-1] < -n:
                        stack.pop()
                    # if is equal, break both
                    if stack and stack[-1] == -n:
                        stack.pop()
                    # if last digit is negative just append.
                    elif not stack or stack[-1] < 0:
                        stack.append(n)
        return stack

so = Solution()
ans = so.asteroidCollision([5, 10, -5])
print ans

P18. Group Anagrams

hmmm, 被考到这道题的candidate前世一定是拯救了世界。

import collections
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = collections.defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            dic[key].append(s)

        return dic.values()

so = Solution()
ans = so.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
print ans

P19. Valid Sudoku

好吧，这道题写了那么多次，居然不是一次就过。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        if not board or not board[0]:
            return True

        d = set()
        n, m = len(board), len(board[0])
        for i in range(n):
            for j in range(m):
                num = board[i][j]
                if num != '.':
                    if (i, 'row', num) in d:
                        return False
                    if ('col', j, num) in d:
                        return False
                    if (i//3, j//3, num) in d:
                        return False
                    d.add((i, 'row', num))
                    d.add(('col', j, num))
                    d.add((i//3, j//3, num))
        return True

so = Solution()
ans = so.isValidSudoku(
[
[".",".","4",".",".",".","6","3","."],
[".",".",".",".",".",".",".",".","."],
["5",".",".",".",".",".",".","9","."],
[".",".",".","5","6",".",".",".","."],
["4",".","3",".",".",".",".",".","1"],
[".",".",".","7",".",".",".",".","."],
[".",".",".","5",".",".",".",".","."],
[".",".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".",".","."]])
print ans

P20. Letter Combinations of a Phone Number

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}        
        return self.dfs(digits, [''], dic)

    def dfs(self, digits, res, dic):
        if not digits:
            return res

        chars = dic.get(digits[0])
        tmp = []
        for c in chars:
            for letter in res:
                tmp.append(letter + c)
        return self.dfs(digits[1:], tmp, dic)

s = Solution()
ans = s.letterCombinations('23')
print ans

来一个大神的解法。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if '' == digits: return []
        kvmaps = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }     
        res=['']
        for c in digits:
            tmp=[]
            for x in res:
                for y in kvmaps[c]:
                    tmp.append(x+y)
            res=tmp
        return res


s = Solution()
ans = s.letterCombinations('23')
print ans