sc onsite 11-20

P11 Alien dict

具体参考 Topo Sort 其实可以试下另外一种写法的，有点懒，就算了哈。

import collections
class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """

        # build graph
        indegree = collections.defaultdict(set)
        outdegree = collections.defaultdict(set)
        for i in range(len(words)-1):
            x, y = words[i], words[i+1]
            index = 0
            while index<min(len(x),len(y)) and x[index]==y[index]:
                index +=1
            if index<min(len(x),len(y)):
                indegree[y[index]].add(x[index])
                outdegree[x[index]].add(y[index])

        s = [k for k in outdegree if k not in indegree]
        res = []
        while s:
            tmp = s.pop()
            res.append(tmp)
            chidren = outdegree[tmp]
            for c in chidren:
                indegree[c].remove(tmp)
                if not indegree[c]:
                    s.append(c)

        chars = set(''.join(words))
        if len(res) == len(chars):
            return ''.join(res)
        else:
            return ''

words = [
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
so = Solution()
so.alienOrder(words)

P12 ugly number 写一个臭数字全家福 哈哈哈

https://leetcode.com/problems/ugly-number/

class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        for p in 2,3,5:
            while num!=0 and num%p==0:
                num = num//p
        return num==1

so = Solution()
a = so.isUgly(6)
print(a)

https://leetcode.com/problems/ugly-number-ii/

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """

        res = [1]
        i2, i3, i5= 0, 0 ,0
        while len(res)<n:
            n2, n3, n5 = 2*res[i2], 3*res[i3], 5*res[i5]
            val = min([n2, n3, n5])
            if val==n2:
                i2 += 1
            if val==n3:
                i3 += 1
            if val==n5:
                i5 += 1
            res.append(val)

        return res[-1]

n = 10
so = Solution()
ans = so.nthUglyNumber(n)
print(ans)

https://leetcode.com/problems/super-ugly-number/

import heapq
class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        res = [1]
        q = []
        for p in primes:
            heapq.heappush(q, (p, 0, p))

        while len(res)<n:
            val, i, p = q[0]
            res.append(val)
            while q and q[0][0]==val:
                val, i, p = heapq.heappop(q)
                heapq.heappush(q, (p*res[i+1], i+1, p))
        return res[-1]

P13 merge k sorted list

# Definition for singly-linked list.
# 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 = [(n.val ,n) for n in lists if n]
        heapq.heapify(q)

        while q:
            val, n = heapq.heappop(q)
            head.next = n
            head = head.next
            if n.next:
                heapq.heappush(q, (n.next.val,n.next))

        return dummy.next

好像这里用heapreplace要快一点。不过也没快多少。

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

        dummy =  ListNode(None)
        head = dummy
        q = [(n.val ,n) for n in lists if n]
        heapq.heapify(q)

        while q:
            val, n = q[0]
            head.next = n
            head = head.next
            if not n.next:
                heapq.heappop(q)
            else:
                heapq.heapreplace(q, (n.next.val, n.next))

        return dummy.next

P14 8*8的棋盘 走K步从一个点走到另一个点有多少不同路径，之前在地里看到过但下面的都不对，先写了个dfs， 然后说简化，我说两头dfs， 然后说再简化，然后经他提示用dp做出来了， 思路是第K步走到一个格子一共有多少不同路径， 那么K+1步走到他周围八个点就是多少路径，解法类似Game of life开个buff数组

怎么越做他们家的题越觉得他们家的bar越低啊。什么菜题都拿出来考人。快把我招进去，我帮他们出两道酷酷的题目。我觉得这道题dp也没有简化复杂度。只是优化了空间。

class Solution(object):
    def UniquePath(self, size, start, end, k):

        res = []
        self.dfs(start, end, [], k, size, res)
        return res

    def dfs(self, cur, end, path, k, size, res):

        if not k:
            if cur==end:
                res.append(path)
            return

        for dp in [(1,0) ,(-1,0), (0,1), (0,-1)]:
            i, j = cur[0]+dp[0], cur[1]+dp[1]
            if 0<=i<size and 0<=j<size:
                self.dfs((i,j), end, path+[(i,j)], k-1, size, res)

boardsize = 8
start = (0,0)
end = (3,3)
so = Solution()
ans = so.UniquePath(boardsize, start, end, 6)
print(ans)

P15 安排会议室 又是瞬间秒掉 https://leetcode.com/problems/meeting-rooms-ii/

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        times = []
        for s, e in intervals:
            times.append((s,1))
            times.append((e,0))

        times.sort()

        rooms, avaliable = 0, 0
        for t in times:
            if t[1]:
                if not avaliable:
                    rooms += 1
                else:
                    avaliable -= 1
            else:
                avaliable += 1
        return rooms

intervals = [[0, 30],[5, 10],[15, 20]]
so = Solution()
print so.minMeetingRooms(intervals)

我们加强一下这道题。除了计算房间的个数，还要给每个会议室分配房间号码。

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        times = []
        room_num = {}
        for s, e in intervals:
            times.append((s,1,e))
            times.append((e,0,s))

        times.sort()

        rooms, avaliable = 0, []
        for t in times:
            if t[1]:
                if not avaliable:  # make a new room num
                    rooms += 1
                    room_num[t[0]] = rooms
                else: # use a empty room num
                    room_num[t[0]] = avaliable.pop(0)
            else:   # return a room
                avaliable.append(room_num[t[2]])

        return room_num

intervals = [[0, 30],[5, 10],[15, 20]]
so = Solution()
print so.minMeetingRooms(intervals)

P16 感觉是word search 简易版，一个字典，给个单词，判断单词在不在字典里。和第二轮一样，一下子就觉得应该用trie做，本来以为没啥问题，结果写search的时候脑抽了，写了个bug，改了一下，又跑了另一个test case，结果还有一个bug，还好及时改好了，估计这里减分了。follow up就是如果单词里有问号，代表任意字母，判断字典里是不是有这个pattern的单词。用dfs挺快写好了，跑了几个test case也没啥问题。他好像说挺好的，具体也没听清了，估计也是安慰安慰我。后来就聊了聊天，我问了问在这里和大公司的区别之类的。

那我们就先写一个简单的版本吧。

class Node(object):
    def __init__(self):
        self.dic = {}
        self.isWord = False

class Solution(object):
    def findWords(self, words, s):

        root = Node()
        # Build trie
        for w in words:
            tmp = root
            for c in w:
                if c not in tmp.dic:
                    tmp.dic[c] = Node()
                tmp = tmp.dic[c]
            tmp.isWord = True

        ans = [i for i in root.dic]
        print(ans)

        tmp = root
        for c in s:
            if c not in tmp.dic:
                return False
            tmp = tmp.dic[c]

        return tmp.isWord


words = ["oath","pea","eat","rain"]
s = "oath"
so = Solution()
ans = so.findWords(words, s)
print(ans)

然后我们再写一个带星号的。

class Node(object):
    def __init__(self):
        self.dic = {}
        self.isWord = False

class Solution(object):
    def findWords(self, words, s):

        root = Node()
        # Build trie
        for w in words:
            tmp = root
            for c in w:
                if c not in tmp.dic:
                    tmp.dic[c] = Node()
                tmp = tmp.dic[c]
            tmp.isWord = True

        res = []
        self.findAll(root, s, '', res)
        return res

    def findAll(self, node, s, path, res):

        if not s:
            if node.isWord==True:
                res.append(path)
            return

        if s[0]=='*':
            for n in node.dic:
                self.findAll(node.dic[n], s[1:], path+n, res)
        else:
            if s[0] in node.dic:
                self.findAll(node.dic[s[0]], s[1:], path+s[0], res)

words = ["oath","pea","eat","rain"]
s = "*a*h"
so = Solution()
ans = so.findWords(words, s)
print(ans)

P17 给inorder和postorder建树

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            num = postorder.pop()
            root = TreeNode(num)
            index = inorder.index(num)
            root.right = self.buildTree(inorder[index+1:], postorder)
            root.left = self.buildTree(inorder[:index], postorder)
            return root

P18 lc Word Search II word search变形，输出字典里面每一个单词出现的次数。follow up是怎么scale，都要求把代码写下来然后运行 https://leetcode.com/problems/word-search-ii/

class Node(object):
    def __init__(self):
        self.dic = {}
        self.isWord = False

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        root = Node()

        for w in words:
            cur = root
            for c in w:
                if c not in cur.dic:
                    cur.dic[c] = Node()
                cur = cur.dic[c]
            cur.isWord = True

        res = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.bt(i, j, board, '', root, res)
        return res

    def bt(self, i, j, board, path, root, res):
        if root.isWord:
            res.append(path)
            root.isWord = False

        if 0<=i<len(board) and 0<=j<len(board[0]):
            c  = board[i][j]
            if c in root.dic:
                board[i][j]='#'
                self.bt(i-1, j, board, path+c, root.dic[c], res)
                self.bt(i+1, j, board, path+c, root.dic[c], res)
                self.bt(i, j+1, board, path+c, root.dic[c], res)
                self.bt(i, j-1, board, path+c, root.dic[c], res)
                board[i][j]=c

P19
317 Shortest Distance from All Buildings
今天状态好，居然又写了一个更简单的版本，鼓掌！撒花！

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return -1

        cost = [[0]*len(grid[0]) for _ in range(len(grid))]
        cnt = 0 # count how many building we have visited
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    self.bfs((i,j), grid, cost, cnt)
                    cnt -= 1

        res = [cost[i][j] for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]==cnt]
        return min(res) if res else -1

    def bfs(self, start, grid, cost, cnt):

        q = [(start, 0)]
        while q:
            p, dist = q.pop(0)
            for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
                i, j = p[0]+dp[0], p[1]+dp[1]
                # only the position be visited by cnt times will append to queue
                if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]==cnt:
                    cost[i][j] += dist+1
                    q.append(((i,j), dist+1))
                    grid[i][j] -= 1

296 Best Meeting Point 原来直接算meduim就行了？我觉得自己是个傻逼啊！

class Solution(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return

        cost = [[0]*len(grid[0]) for _ in range(len(grid))]

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    self.bfs((i,j), cost, grid)
        res = [i for row in cost for i in row if i!=0]
        return min(res) if res else -1

    def bfs(self, start, cost, grid):

        q = [(start, 0)]
        visited = {start}

        while q:
            po, dist = q.pop(0)
            for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
                i, j = po[0]+dp[0], po[1]+dp[1]
                if 0<=i<len(grid) and 0<=j<len(grid[0])\
                and (i,j) not in visited:
                    cost[i][j] += dist+1
                    q.append(((i, j),dist+1))
                    visited.add((i,j))

grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
so = Solution()
ans = so.minTotalDistance(grid)
print ans

大神的解法

class Solution(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        r, c = len(grid), len(grid[0])
        sumr = [i for i in xrange(r) for j in xrange(c) if grid[i][j]]
        sumc = [j for i in xrange(r) for j in xrange(c) if grid[i][j]]
        sumr.sort()
        sumc.sort()
        mid_row = sumr[len(sumr)/2]
        mid_col = sumc[len(sumc)/2]
        return sum([abs(r-mid_row) for r in sumr]) + sum([abs(c-mid_col) for c in sumc])

P20 Big Integer加减，可正可负，听他描述完，有点想抽自己，看到有人说了类似题目的面经，但是说的是电面，就没准备，没想撞上了。题目大意： 传入一个String, 自己定定义BigInteger class的内部变量, 实现加减； 想了一下，本来想直接char arrar处理，发现把符号信息单独拿出来会简单很多， 所以就是BigInteger{int sign, int[] nums}, 然后就是实现， 两个数的符号 ++, --, +-, -+, 分情况写，没有全部写完，就写好了＋＋， －－, 小哥说没时间了，你写几个testcase 先跑一下这个吧，testcase 通过， done.

不带小数的加法和乘法。

class Solution(object):
    def add(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = list(num1)[::-1]
        num2 = list(num2)[::-1]

        if len(num1)<len(num2):
            num1, num2 = num2, num1

        carry = 0
        index = 0
        while index<len(num1):
            n2 = int(num2[index]) if index<len(num2) else 0
            tmp = n2 + int(num1[index]) + carry
            cur = tmp%10
            carry = tmp//10
            num1[index] = str(cur)
            index += 1

        if carry: num1.append('1')

        return ''.join(num1[::-1])

    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = num1[::-1]
        num2 = num2[::-1]

        res = [0]*(len(num1) + len(num2))
        for i in range(len(num2)):
            for j in range(len(num1)):
                tmp = int(num2[i])*int(num1[j])
                res[j+i] += tmp
                res[j+i+1] += res[j+i]//10
                res[j+i] = res[j+i]%10

        while len(res)>1 and res[-1]==0:
            res.pop()

        return ''.join(map(str,res))[::-1]

num1 = '124'
num2 = '5679'
so = Solution()
a = so.add(num1, num2)
print(a)
a = so.multiply(num1, num2)
print(a)