8月刷题/Mock interview接龙活动（缺米刷题的来）

刷了三道dp题。日常打卡

report for duty

8.8 打卡三道binary search。index细节太多还需要学习

#34. Find first and last position of element in sorted array
run binary search twice to find lower bound and upper bound
        idx1 = helper(nums, target)
        idx2 = helper(nums, target + 1) - 1
        if idx1 < len(nums) and nums[idx1] == target:
            return [idx1, idx2]
        else:
            return [-1, -1]

The tip for this method is that if target is not in the array, for example in this case, [5,7,7,8,8,10] with target 6 will give us index [1, 0], but since nums[idx1] != target it will output [-1, -1]

Another tricky way:
        double left = target - 0.5, right = target + 0.5;
        int l = bs(nums, left), r = bs(nums, right);
        if(l == r) return new int[]{-1, -1};
        return new int[]{l, r-1};

#33. Search in rotated sorted array
Determine whether mid point is on the left side of the pivot or the right side. Plot the array as a 分段函数。
if nums[low] <= nums[mid]: binary search left
else: binary search right

#81. Search in rotated sorted array II
Mid is a floor of (l+r)/2, so it can be equal to l. We want to make sure that the equal sign in condition nums[i] <= nums[mid] only happens when l = mid, so you have to remove the duplicates for the left.  ex: [3,3,3,3,3,3,4,5,3]
However for the right, it's not necessary, and it can make the calculation slower. For example find 2 in [0, 1, 2, 3, 3, 3, 3, 3, 3, 3], all the 3s can be skipped in a O(logN) manner if you don't do the r -=1, if you do, it will be O(N)

和上面一题同样的分段，但是多了一个dedup的条件：
while l < mid and nums[l] == nums[mid]: # tricky part
            l += 1

TimLee 发表于 2020-8-7 10:42
今天闹肚子，只打一道题卡
442. Find All Duplicates in an Array

八月day7:
remove element
merge sorted array
duplicate zeros
如果用python的built in function就非常容易，但是感觉还是需要不用function也能写出来
啊不好意思，应该回复主题帖的，按错了

Take away: 用的dp track 一个string的substring 是 palindrome 还是非palindrome 和对于每一个substring所需要改动的字母数 把他变成一个palindrome 然后用在用一层dp 来minCut 和 min number changes

先上今天的第一题： LeetCode 279 完全平方数

今天做了三类题，Kth element, K-way merge, DP Knapsack
DP 的题需要更加深入的理解和练习～

复习了一下heap的实现 + 打卡两道heap题
heapifyDown的时候要注意左右子元素选最大(maxHeap)/小(minHeap)

8/8 打卡第三天，今天复习了4道top k的题

8.8 day8 August LeetCoding Challenge