Day 1. 02/02/20

[tech-cow]

Day 1

• 953 Verifying an Alien Dictionary
• 215 Kth Largest Element in an Array
• 563 Binary Tree Tilt
• 15 3Sum
• 973 K Closest Points to Origin
• 125 Valid Palindrome

[tech-cow]

953. Verifying an Alien Dictionary

Time: O(n * len(longest element in arr)) | Space: O(26)

class Solution(object):
    def isAlienSorted(self, words, alphabet):
        dic = {}
        for i, num in enumerate(alphabet):
            dic[num] = i
        
        n = len(words)
        for i in range(n):
            if i + 1 == n: return True
            word1 , word2 = words[i], words[i + 1]
            if self.leftIsLarger(word1, word2, dic):
                return False
        return True
    
    def leftIsLarger(self, word1, word2, dic):
        m, n = len(word1), len(word2)
        for i in range(min(m , n)):
            if word1[i] != word2[i]:
                if dic[word1[i]] > dic[word2[i]]:
                    return True
                else:
                    return False
        return m > n

[tech-cow]

215. Kth Largest Element in an Array

'''
# Start [9:49]
# End [10:16]

Problem Solving 
    1. brute force  
        Sort and return -k   
	
	Time:
		Sort: O(nlogn) 
    
    
    2.  Max heap = o(n) + k * O(logn)
	    make a max heap
             pop max_heap_root k times
	
	Time:
		heapify a size n array: O(N)
        pop max_heap_root k times 
	        each time O(log(n))
		Total = O(N) + O(klogn)


	3. Min Heap
        Keep a minHeap of size K     
        for loop -> nums  k times
            if cur_num > minheap_root
                replace minheap_root with cur_num (minheap in the process will also change)
        return minheap_root
                
                
    Time: O(k) + nlogk
        Heapify a size k array = O(k)
        for loop the nums  O(n)
            replace top -> log(k)
'''

Brute Force

# Brute Force [9:54]
class Solution(object):
    def findKthLargest(self, nums, k): 
        nums.sort()
        return nums[-k]

MaxHeap

# Maxheap
'''
[-][9:54] reference python heapq api, completely forget 

1. heapq.heapify(x)
2. heapq.heapreplace(heap, item)¶
3. heapq.heappop(heap)

[-][9:57] forget heapq heap is min-heap, so potentially need to negative the whole heap

[10:03] Finish bug-free
'''
from heapq import heapify, heappop
class Solution(object):
    def findKthLargest(self, nums, k): 
        nums = [-num for num in nums]
        heapq.heapify(nums)
        
        k_largest = -float('inf')
        for i in range(k):
            k_largest = heapq.heappop(nums)
        return -k_largest

MinHeap

# Code [10:16] bug-free
from heapq import heapify, heappop
class Solution(object):
    def findKthLargest(self, nums, k): 
        heap = nums[:k]
        heapq.heapify(heap)
        
        for i in range(k , len(nums)):
            if nums[i] > heap[0]:
                heapq.heapreplace(heap, nums[i])
        return heap[0]

[tech-cow]

563 Binary Tree Tilt

Problem Solving

Code [10:34 - 10:38]

class Solution(object):
    def findTilt(self, root):
        if not root: return 0
        res = [0]    
        self.dfsHelper(root, res)
        return res[0]
    
    def dfsHelper(self, root, res):
        if not root: return 0
        leftSum = self.dfsHelper(root.left, res)
        rightSum = self.dfsHelper(root.right, res)
        curTilt = abs(leftSum - rightSum)
        res[0] += curTilt
        return leftSum + rightSum + root.val

[tech-cow]

15. 3Sum

Problem Solving

Code

# [Coding] 10:57
# [End]: 11:20 ->  2处Bug，没有看答案

class Solution(object):
    def threeSum(self, nums):
        if len(nums) < 3: return [] 
        nums.sort()
        print(nums)
        res = []
        
        for i in range(len(nums) - 2):
            print('Iteration---------' + str(i + 1))
            if i > 0 and nums[i] == nums[i - 1]: continue
            
            left, right = i + 1 , len(nums) - 1
            
            while left < right:
                curSum = nums[left] + nums[right] + nums[i]
                if curSum == 0:
                    res.append([nums[left] , nums[right] , nums[i]])
                    # bug 1
                        # 这前在这里写了break
                            # 我们找到一个组合，还得继续，所以要left += 1 然后 right -= 1
                    # Bug 2 
                        # Case: [-2,0,0,2,2]
                            # 这里 -2 0 2 成功以后，right - 1的话还是2， 所有有重复，必须在这里
                            # 把相同元素过滤
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    left += 1 ; right -= 1
                elif curSum < 0:
                    left += 1
                else:
                    right -= 1 
        return res

[tech-cow]

973. K Closest Points to Origin

Problem Solving

---

Buggy Code

from heapq import heapreplace, heapify
class Solution(object):
    def kClosest(self, pairs, k):
        nums = []
        dic = {}
        self.getDist(pairs, nums, dic)
        nums = [-num for num in nums]
        heap = nums[:k]
        heapq.heapify(heap)
        
              
        for i in range(k, len(nums)):
            if nums[i] > heap[0]:
                heapq.heapreplace(heap, nums[i])
        
        res = []
        for num in heap:
            res.append(dic[-num])    
        return res
        

        
        
    
    def getDist(self, pairs, nums, dic):
        for pair in pairs:
            x, y = pair
            dist = (x ** 2 + y ** 2) ** 0.5
            dic[dist] = [x, y]
            nums.append(dist)
            
Fail:    
Input
[[0,1],[1,0]]
2
Output
[[1,0],[1,0]]
Expected
[[0,1],[1,0]]

Fixed Code

from heapq import heapreplace, heapify
class Solution(object):
    def kClosest(self, pairs, k):
        nums = []
        self.getDist(pairs, nums)
        heap = nums[:k]
        heapq.heapify(heap)
        
        for i in range(k, len(nums)):
            if -nums[i][0] < -heap[0][0]:
                heapq.heapreplace(heap, nums[i])
        
        res = []
        for num, x, y in heap:
            res.append([x, y])    
        return res
        
    def getDist(self, pairs, nums):
        for pair in pairs:
            x, y = pair
            dist = (x ** 2 + y ** 2) ** 0.5
            nums.append((-dist, x, y))

[tech-cow]

125. Valid Palindrome

class Solution(object):
    def isPalindrome(self, s):
        if not s: return True
        i, j = 0, len(s) - 1
        while i < j:
            while i < j and not s[i].isalnum(): i += 1
            while i < j and not s[j].isalnum(): j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1; j -= 1
        return True