。

[tech-cow]

刷题任务

http://pythontutor.com/visualize.html#mode=display

重刷题目:

• 15 3Sum
• 16 3Sum Closest
• 3. Longest Substring Without Repeating Characters

Lintcode

• 607 Two Sum III - Data Structure Design
• 143 Sort Colors II

Leetcode

• 532 K-diff Pairs in an Array
• 18 4Sum
• 76 Minimum Window Substring
• 763. Partition Labels
• 828. Unique Letter String
• 80. Remove Duplicates from Sorted Array II
• 11. Container With Most Water

刷题状况：
15 3Sum : 细小的Bug, l初始值设置错位

[tech-cow]

Leetcode

763. Partition Labels

类型：窗口+斗鸡眼
Time Complexity O(n)
Space Complexity O(n)

首先用字典存储char出现最后的下标。
在每次迭代的时候更新r的区间，在这里i作为我们的runner，l则保持在左区间的位置。直到当i和r相等的时候，得到最长区间r-l+1并加入到数组。

class Solution(object):
    def partitionLabels(self, s):
        dic = {}
        for i, char in enumerate(s):
            dic[char] = i
        
        res = []
        l , r = 0, 0
        for i, char in enumerate(s):
            r = max(r, dic[char])
            if i == r:
                res.append(r-l+1)
                l = r + 1
        return res

80. Remove Duplicates from Sorted Array II

类型：龟兔赛跑
Time Complexity O(n)
Space Complexity O(1)

在Remove Duplicates from Sorted Array I的基础上加了一个Edge Case用来判断重复字符:
(nums[fast] == nums[slow] and nums[fast] != nums[slow - 1])

class Solution:
    def removeDuplicates(self, nums):
        if len(nums) <= 2: return len(nums) 
        slow , fast = 1, 2
        while fast < len(nums):
            if nums[fast] != nums[slow] or (nums[fast] == nums[slow] and nums[fast] != nums[slow - 1]):
                nums[slow+1] = nums[fast]
                slow += 1
            fast += 1
        return slow + 1