sc 11-20

P11: Trapping rain water。

https://leetcode.com/problems/trapping-rain-water/

思路：左右两个pointer 然后每次动矮的那一个。然后分别记录左右最高的

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height or len(height)<3:
            return 0

        l ,r = 0, len(height)-1
        left_h, right_h = height[l], height[r]

        res = 0
        while l<r:
            if left_h<right_h:
                res += max(0, left_h-height[l+1])
                l = l+1
                left_h = max(left_h, height[l])
            else:
                res += max(0, right_h-height[r-1])
                r = r-1
                right_h = max(right_h, height[r])
        return res

P12: 给定字符串A，B， 判断A中是否存在子串是B的anagram 。

https://leetcode.com/problems/valid-anagram/

leet有道简单版的。再上一道难的。

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return collections.Counter(s) == collections.Counter(t)

难的版本

class Solution(object):
    def isAnagram(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: bool
        """
        if len(b)> len(a):
            return False

        b = sorted(b)

        for i in range(len(a)-len(b)+1):
            if sorted(a[i:i+len(b)]) == b:
                return True

        return False

s = "sadaanagramsad"
t = "nagaram"
so = Solution()
print so.isAnagram(s,t)

更优化的版本用sliding window + hash来做。

import collections
class Solution(object):
    def isAnagram(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: bool
        """
        da = collections.defaultdict(int)
        db = collections.defaultdict(int)
        if len(b)> len(a):
            return False

        for c in b:
            db[c] += 1

        for i in range(len(b)):
            da[a[i]] += 1

        if da == db:
            return True

        for i in range(1, len(a) - len(b) + 1):
            da[a[i-1]] -= 1
            da[a[i+len(b)-1]] += 1
            if self.compare(db, da):
                return True

        return False 

    def compare(self, d1, d2):
        for k in d1:
            if k not in d2 or d1[k]!=d2[k]:
                return False
        return True



s = "sadaanagramsad"
s = "aasdadnagaram"
t = "nagaram"
so = Solution()
print so.isAnagram(s,t)

P13. 第一轮是一个妹子, 好像是某硬件组的, 具体不记得了, 就记得妹子长得还不错lol 我记得开始就问了下我背景和做过什麽, 看起来很有兴趣的样子。然后做题, 先是建一个event, 里面有start time和end time, 然后check这两个event有没有conflict, 各种if else, 然后升级, 给一个list of events, 直接sort他们。再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的。

leetcode meeting room I//meeting room II

https://leetcode.com/problems/meeting-rooms/

https://leetcode.com/problems/meeting-rooms-ii/

思路： 写了下难的那道。扫描线算法。然后存avaliable和房间数。

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        # put all the times together and sort them.
        times = []
        for i in intervals:
            times.append((i[0], 1))
            times.append((i[1], 0))
        times.sort()

        count = 0
        availiable = 0
        for t in times:
            # if we need a room
            # avaliabe room -1.
            if t[1]:
                availiable -= 1
                if availiable<0:
                    availiable += 1
                    count += 1
            # if end a meeting
            # avaliable + 1
            else:
                availiable += 1  
        return count

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

P14. 首先， 一个array的range是1-N，这个array里有1+N个数, 找出这个array里的duplicate。(ex. [1, 1, 3, 5]) HashMap 解决然后条件升级, 问不能用extra space. 想了一下, 先sort, 再找再升级, 不能改变array, 不能有extra space。

287 Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/

最后跟linked list 找circle一样的。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow = nums[0]
        fast = nums[nums[0]]
        while (slow != fast):
            slow = nums[slow]
            fast = nums[nums[fast]]

        fast = 0;
        while (fast != slow):
            fast = nums[fast]
            slow = nums[slow]

        return slow

P15. binary tree to doubly linked list.

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

思路：这道题是数flatten成单项链表，面试题目相当于是加强版。就是preorder里面加点料。需要注意的地方是我们这个 self.pre = root这里很精妙，相当于在flatten右边树之前，把左树的最后一个节点给存起来了。

class Solution(object):
    pre = None
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void 
        """
        if root:
            self.pre = root
            self.flatten(root.left)

            tmp = root.right
            root.right = root.left
            root.left = None
            self.pre.next = root.right

            self.flatten(tmp)

加强版：因为我们需要双向链表。所以要记录这个node的parent.因为Input变成了2个，所以我们需要新写一个helper function呢。

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

class Solution(object):
    pre = None
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void 
        """
        self.helper(root, None)


    def helper(self, root, p):

        if root:

            self.pre = root
            self.helper(root.left, root)

            tmp = root.right
            root.right = root.left
            root.left = p
            self.pre.next = root.right

            self.helper(tmp, self.pre)


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

a.left, a.right = b, c

so = Solution()
so.flatten(a)
print a.val, a.right.val, a.right.left.val

P16. search in rotated array 。

https://leetcode.com/problems/search-in-rotated-sorted-array/

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

思路：这道题跟一般的之前那个rotated sorted array找最小的值不一样，这个是要search。先找出带顺序的那一半，然后再判断在不在里面。 (睡了一觉刚醒，起来做这个就是思路清晰，corner case毫无破绽！

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1

        l, r = 0, len(nums)-1

        while l<r:
            mid = (l+r)//2

            if nums[mid] == target:
                return mid

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

        return l if nums[l]==target else -1

nums = [4, 5, 6, 7, 0, 1, 2]
so = Solution()
print so.search(nums, 0)

再写个加强版，带重复的，其实就是多了一个如果mid == r 然后r--而已。 跟P5的思想一样。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if not nums:
            return -1

        l, r = 0, len(nums)-1

        while l<r:
            mid = (l+r)//2

            if nums[mid] == target:
                return True

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

        return True if nums[l]==target else False

P17.上来面试官先介绍了一下他做的工作，人很nice，中国帅哥，然后让我介绍了我的projects 和 背景。之后出了一道题目： // Give a stream of numbers // Write a method to return the medium of the numbers you have received // void add(int num); // int getMedium();

https://leetcode.com/problems/find-median-from-data-stream/

import heapq
class MedianFinder:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.min_heap = []
        self.max_heap = []


    def addNum(self, num):
        """
        Adds a num into the data structure.
        :type num: int
        :rtype: void
        """
        if len(self.min_heap)==len(self.max_heap):
            heapq.heappush(self.min_heap, num)
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
        else:
            heapq.heappush(self.max_heap, -num)
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))


    def findMedian(self):
        """
        Returns the median of current data stream
        :rtype: float
        """
        if len(self.min_heap)==len(self.max_heap):
            return (self.min_heap[0] - self.max_heap[0])/2.0
        else:
            return -self.max_heap[0]

P18. 我一开始就想当然的用了个二维int矩阵做参数。 然后他memory overhead是什么，我就说我mn4。 问能不能省，我就说其实不需要用int存状态，用两个bit就可以了。 又问如果还要再省一点呢？我就说，如果要操作的点不太多的话，那就不要存矩阵了，就存存要修改的点的坐标。 然后又问怎么做，我才意识到他是想说参数其实不必用矩阵，就用一个list of coordinates，然后就说如果是sparse矩阵的话就只扫一下live的点，然后看看它和它neighbor在下一轮是什么状态就好了。 但是这个时候时间已经差不多了，就没有再写实现。

https://leetcode.com/problems/game-of-life/

前天才写了一遍，今天就不写了。

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return

        for i in range(len(board)):
            for j in range(len(board[0])):
                cnt = 0
                for m, n in [[i-1, j],[i+1, j], [i, j-1], [i, j+1], [i-1, j-1], [i+1, j+1], [i+1, j-1], [i-1, j+1]]:
                    if 0<=m<len(board) and 0<=n<len(board[0]):
                        if board[m][n]&1 ==1:
                            cnt += 1

                if board[i][j]==1:
                    if 3<=board[i][j]+cnt<=4:
                        board[i][j] = board[i][j]^2
                else:
                    if cnt==3:
                        board[i][j] = board[i][j]^2
                print cnt

        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] = board[i][j]>>1

P19. 1. permutation i。leetcode原题，没有任何改变。

https://leetcode.com/problems/permutations-ii/

Permutation I 太简单，我们还是写permutaiont II好了

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        self.size=len(nums)
        nums.sort()
        self.dfs(nums,[],res)
        return res

    def dfs(self,nums,cur,res):
        if len(cur)==self.size:
            res.append(cur)
            return
        for i in range(len(nums)):
            if i and nums[i]==nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], cur+[nums[i]], res)

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

P20. 24点游戏。给你几个数字，判断他们做加减乘除运算是否可以得到24，顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节，每次计算得到新的数之后最好加入数组做下一次搜索，不然容易出错。

class Solution(object):
    def game24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return self.dfs(nums, 0, '')


    def dfs(self, nums, cur, path):
        """
        :type nums: List[int]
        :type cur: int
        :type path: str
        :rtype: bool
        """

        if not nums and cur==24:
            print path
            return True


        for i in range(len(nums)):
            if self.dfs(nums[:i]+nums[i+1:], cur+nums[i], path+'+'+str(nums[i])):
                return True

            if self.dfs(nums[:i]+nums[i+1:], cur-nums[i], path+'-'+str(nums[i])):
                return True

            if self.dfs(nums[:i]+nums[i+1:], cur*nums[i], path+'*'+str(nums[i])):
                return True

            if self.dfs(nums[:i]+nums[i+1:], cur/nums[i], path+'/'+str(nums[i])):
                return True

        return False



nums = [4,2,1,3]
so = Solution()
print so.game24(nums)