sc

P1.从东北往西南打印矩阵

input:

1 2 3 4
5 6 7 8

output:

1
2 5
3 6
4 7
8

class Solution(object):
    def so(self, matrix):
        """
        :type matrix: List[List[int]]
        :retype: List[List[int]]
        """
        if not matrix or not matrix[0]:
            return

        end = len(matrix) + len(matrix[0])-1
        res = []

        for num in range(end):
            tmp = []
            for i in range(num+1):
                if i<len(matrix) and (num-i)<len(matrix[0]):
                    tmp.append(matrix[i][num-i])
            res.append(tmp)
        return  res


so = Solution()
print so.so([[1,2,3,4],[5,6,7,8]])

P2. Merge K sorted list https://leetcode.com/problems/merge-k-sorted-lists/

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

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(None)
        head = dummy
        q = []

        for node in lists:
            if node:
                heapq.heappush(q, (node.val, node))

        while q:
            tmp = heapq.heappop(q)
            dummy.next = tmp[1]
            dummy = dummy.next
            if tmp[1].next:
                heapq.heappush(q, (dummy.next.val, dummy.next))

        return head.next

P3.valid sudoku https://leetcode.com/problems/valid-sudoku/

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        res = set()
        for row in range(len(board)):
            for col in range(len(board)):
                if board[row][col]=='.': continue

                num = board[row][col]
                if (row,'row', num) in res: return False
                else: res.add((row, 'row', num))

                if (col,'col',num) in res: return False
                else: res.add((col, 'col', num))

                if (row//3, col//3, num) in res: return False
                else: res.add((row//3, col//3,num))


        return True

p4. 给定数组，只有正数，使用＋和＊和（）。求最大值。 使用DP解决。dp[j] = max(dp[m - 1] + dp[m][j], dp[m - 1] * dp[m][j]);

class Solution(object):
    def findmax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.memo = {}
        res = self.dfs(nums, 0, len(nums)-1)
        return res

    def dfs(self, nums, l, r):

        if (l, r) in self.memo:
            return self.memo[l, r]

        if l == r:
            return nums[l]

        res = 0
        for i in range(l, r):
            left = self.dfs(nums, l, i)
            right = self.dfs(nums, i+1, r)
            tmp = max(left + right, left * right)
            res = max(res, tmp)

        self.memo[(l, r)] = res
        return res


nums = [1,2,3]
so = Solution()
a = so.findmax(nums)
print(a)

P5. 有序的rotated array 二分查找 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l, r = 0, len(nums)-1

        while l<r:

            mid = (l+r)//2

            if nums[mid]<nums[r]:
                r = mid
            else:
                l = mid+1

        return nums[l]

nums = [3, 1, 2]
so = Solution()
a = so.findMin(nums)
print(a)

如过有重复的数字的话，那么要判断mid是不是跟右边相等，相等的话,l-=1

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l<r:
            mid = (l+r)//2
            if nums[mid]<nums[r]:
                r = mid
            elif nums[mid]>nums[r]:
                l = mid+1
            else:
                r -= 1
        return nums[l]

P6. 实现一个trie leetcode

https://leetcode.com/problems/implement-trie-prefix-tree/

class node(object):
    def __init__(self):
        self.dic = {}
        self.isword = False

class Solution(object):

    def __init__(self):
        self.root = node()

    def buildTrie(self, words):
        for word in words:
            tmp = self.root
            for c in word:
                if c not in tmp.dic:
                    tmp.dic[c] = node()
                tmp = tmp.dic[c]

            tmp.isword = True
        return self.root



words = ['abc', 'ab', 'abcd']
so = Solution()
root = so.buildTrie(words)
print root.dic['a'].dic['b'].isword

P7. 用Binary Search Tree实现实现Map，包括以下操作： put(key, value), get(key), size()。其实就是实现BST的insert和get。然后让我写test case测试自己的代码。然后问了下用BST实现Map的好处，跟HashMap比的话

Delete实在不想写了。如果考到了，那我就跪地求饶好了。

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

class BST(object):

    def __init__(self):
        self.root = None

    def insert(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: None
        """
        node = TreeNode(val)
        if not root:
            self.root = node
        else:
            if root.val < val:
                if not root.right:
                    root.right = node
                else:
                    self.insert(root.right, val)
            else:
                if not root.left:
                    root.left = node
                else:
                    self.insert(root.left, val)

    def delete(self, val):
        """
        :type val: int
        :rtype: None
        """
        pass


    def search(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return False

        if root.val == val:
            return True

        if root.val > val:
            return self.search(root.left, val)
        else:
            return self.search(root.right, val)




bst = BST()
bst.insert(bst.root, 2)
bst.insert(bst.root, 1)
bst.insert(bst.root, 3)
bst.insert(bst.root, 4)
print bst.root.val
print bst.search(bst.root, 6)

今天心情好，再写一遍，感觉这个版本代码风格更好一点。

class Hash(object):

    def __init__(self):
        self.root = None

    def add(self, key, val):
        node = TreeNode(key, val)
        if not self.root:
            self.root = node
        else:
            self.addHelper(self.root, node)

    def addHelper(self, root, node):
        if node.key < root.key:
            if not root.left:
                root.left = node
            else:
                self.addHelper(root.left, node)
        elif node.key > root.key:
            if not root.right:
                root.right = node
                return
            else:
                self.addHelper(root.right, node)

    def get(self, key):
        return self.getHelper(self.root, key)


    def getHelper(self, root, key):
        if not root:
            return
        elif root.key==key:
            return root.val
        elif key<root.key:
            return self.getHelper(root.left, key)
        else:
            return self.getHelper(root.right, key)

h = Hash()
h.add(2,'haha')
h.add(1,'heihei')
h.add(3,'hoho')
print h.get(1)

P8. Given a list of integers: {4, 3, 1}; // assume no duplicates and a target sum: 5 print out all sequences of integers from the list that sum to target

https://leetcode.com/problems/combination-sum/

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

    def dfs(self, nums, target, path, res):
        if target < 0:
            return  # backtracking
        if target == 0:
            res.append(path)
            return 
        for i in xrange(len(nums)):
            self.dfs(nums[i:], target-nums[i], path+[nums[i]], res)

P9 实现ArrayList。

class ArrayList(object):
    def __init__(self, capa):
        """
        :type capa: int
        :rtype: None
        """
        self.array = []
        self.capa = capa

    def add(self, val):
        """
        :type val: int
        :rtype: None
        """
        if len(self.array) == self.capa:
            self.capa = 2*self.capa
        self.array.append(val)
        return 

    def delete(self, val):
        """
        :type val: int
        :rtype: None
        """
        if val in self.array:
            self.array.remove(val)
            if len(self.array) == self.capa/2:
                self.capa = self.capa/2
        return 

a = ArrayList(5)
a.add(1)
a.add(2)
a.add(3)
print a.array, a.capa
for i in range(10):
    a.add(1)
print a.array, a.capa
for i in range(10):
    a.delete(1)
print a.array, a.capa

P10 问了一个字符串比较问题，说很多用户名都会重复，通过后面的数字来区分，但是在排序的时候严格按照字符串排序就会出现 abc10 排在 abc2 前面（因为‘1’比‘2’要小），但是事实上他们想要达到的效果是 abc10 排在 abc2 后面（10比2要大），于是让写一个字符串比较函数.

先写一个version number compare吧。

https://leetcode.com/problems/compare-version-numbers/

class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1 = self.helper(version1)
        v2 = self.helper(version2)

        if v1==v2:
            return 0
        return 1 if v1>v2 else -1

    def helper(self, v):
        res = map(int, v.split('.'))
        while len(res)>1 and res[-1]==0:
            res.pop()
        return res

so = Solution()
v1 = '0.1'
v2 = '11.2'
print so.compareVersion(v1,v2)

再写一个字符串compare。

class Solution(object):
    def compareVersion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        v1 = self.splitstr(s1)
        v2 = self.splitstr(s2)

        if v1==v2:
            return 0
        return 1 if v1>v2 else -1

    def splitstr(self, s):
        res = []
        index = 0
        while index<len(s):
            index += 1
            if s[index] in '0123456789':
                break
        return [s[:index],int(s[index:])]

s1 = 'abc10'
s2 = 'abc1'

so = Solution()
print so.compareVersion(s1, s2)