Day 10 | 7/10

[tech-cow]

刷题任务

热身重刷

• 15 3Sum
• 16 3Sum Closest

Leetcode

• 3. Longest Substring Without Repeating Characters
• 763. Partition Labels
• 80. Remove Duplicates from Sorted Array II

[tech-cow]

3. Longest Substring Without Repeating Characters

第一次尝试

类型：滑动窗口
Time Complexity O(n)
Space Complexity O(n)

以下为第一次尝试，思路是利用滑动窗口原理。
子方程 isValid用来检测双指针区间是否有重复，这里运用了一个Python的小窍门，set(s)可以去重，去完重的String如果和原String长度一样，说明原来String没有重复。
回到主方程：只要没有重复(isValid == True)，那就增加快指针r，直到找到重复以后更新返回值，这里注意的是要比较原有最大值，和目前最大值: max(cnt, r-l)。
假如有重复的话，l += 1，滑动窗口然后继续重复。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        cnt, l, r = 0, 0, 0
        while r < len(s):
            if self.isValid(s[l:r+1]):
                r += 1
                cnt = max(cnt, r-l)
            else:
                l += 1
        return cnt
    
    
    def isValid(self, s):
        return len(set(s)) == len(s)

---

可优化的地方

做完题想了想，这个方法还有很多优化空间因为

1. 子方程 isValid开辟的空间过多
2. l指针的增值可以优化。因为重复多次，举例：'pousase', 这里s出现重复，但我们每次对l增值的时候，进行了多次无必要计算，l增值一次对应的String为ousase，这时候我们又走了一遍String，然而结果反而会更小，所以l应该增加到重复字符第一次出现的位置 + 1的下标。

---

优化代码

类型：滑动窗口
Time Complexity O(n)
Space Complexity O(n)

以下代码原理是用一个字典计算重复，免去了每次迭代用set的重复操作。
然后利用字典value储存下标的优势，每次区间出现重复，l的下标增加到重复字符第一次出现的位置 + 1的下标

class Solution:
    def lengthOfLongestSubstring(self, s):
        dic, cnt, l = {}, 0, 0       

        for r in range(len(s)):
            if s[r] in dic and l <= dic[s[r]]:
                l = dic[s[r]] + 1
            else:
                cnt = max(cnt, r - l + 1)
            dic[s[r]] = r
        return cnt

优化代码参考链接

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