• LeetCode Cookbook 双指针 上篇 难点

    LeetCode Cookbook 双指针 上篇 难点1

       双指针这一部分真的挺难，昨天参加了一下周赛，基础还是太薄弱了，最小堆、线段树都不会用，或者根本想不到，有关区域间处理的问题确实是一个薄弱点，一步一步来吧，急也没有用！这一部分的内容确实脑壳疼，有点做不动，我想分为上下两篇，上篇 中等难度，下篇 hard 难度。厚积薄发，继续，努力，奋斗！

    3. 无重复字符的最长子串

    题目链接：3. 无重复字符的最长子串
    题目大意：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

    例如：

    输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    解题思路：典型 滑动窗口 其实称为 双指针比较恰当一些。这一行代码 seen.remove(s[L]) 很重要，如果涉及到判断是否存在的操作，一定要进行remove操作。

    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 建立窗口 维持窗口 保持窗口稳定
        L,n = 0,len(s)
        tmp_len,max_len  = 0,0 
        seen = set()
        for i in range(n):
            tmp_len += 1
            while s[i] in seen:
                seen.remove(s[L])
                L += 1
                tmp_len -= 1
            max_len = max(max_len,tmp_len)
            seen.add(s[i])
        return max_len

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    424. 替换后的最长重复字符 （model-I）

    题目链接：424. 替换后的最长重复字符
    题目大意：给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。在执行上述操作后，返回包含相同字母的最长子字符串的长度。

    例如:

    输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    解题思路：两个重点：

    • （1）学习 这种数组的创建方法，专门针对 小写字母的字符串；
    • （2）循环的建立以及循环内部的处理方法，左边指针的处理。
    class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        nums = [0]*26
        L,maxn = 0,0
        for R in range(n):
            idR = ord(s[R])-ord("A")
            nums[idR] += 1
            maxn = max(maxn,nums[idR])
            if R-L+1-maxn>k:
                idL = ord(s[L])-ord("A")
                nums[idL] -= 1
                L += 1
        return R-L+1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    438. 找到字符串中所有字母异位词（model-I）

    题目链接：438. 找到字符串中所有字母异位词
    题目大意：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

    例如：

    输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    解题思路：注意观察左右窗口移动的结果。

    ----------------------------
L= 0 R= 0
s_cnt [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 0 R= 0
s_cnt [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 0 R= 1
s_cnt [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 0 R= 1
s_cnt [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 0 R= 2
s_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 0 R= 2
s_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------

# 有变化 这句话神了 while s_cnt[cur_R] > p_cnt[cur_R] 真的哎！
# 注意是如何 吐出去的 是因为由新的元素进入 就要全部吐出去
L= 0 R= 3
s_cnt [1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 4 R= 3
s_cnt [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 4 R= 4
s_cnt [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 4 R= 4
s_cnt [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 4 R= 5
s_cnt [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 4 R= 5
s_cnt [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------

# 注意这里 L由4到5的变化 弹出匹配元素多余的个数
L= 4 R= 6
s_cnt [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 5 R= 6
s_cnt [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 5 R= 7
s_cnt [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 6 R= 7
s_cnt [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------
L= 6 R= 8
s_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 6 R= 8
s_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------

L= 6 R= 9
s_cnt [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L= 10 R= 9
s_cnt [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
p_cnt [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_cnt,p_cnt = [0]*26,[0]*26
        n,m,ans = len(s),len(p),[]
        
        for ch in p:
            idx = ord(ch)-ord('a')
            p_cnt[idx] += 1

        L = 0
        for R in range(n):
            cur_R = ord(s[R])-ord('a')
            s_cnt[cur_R] += 1
            # print('----------------------------')
            # print('L=',L,'R=',R)
            # print('s_cnt',s_cnt)
            # print('p_cnt',p_cnt)
            while s_cnt[cur_R] > p_cnt[cur_R]:
                cur_L = ord(s[L]) - ord('a')
                s_cnt[cur_L] -= 1
                L += 1
            # print('L=',L,'R=',R)
            # print('s_cnt',s_cnt)
            # print('p_cnt',p_cnt)
            if R-L+1 == m:
                ans.append(L)
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    567. 字符串的排列 （model-I)

    题目链接：567. 字符串的排列
    题目大意：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。

    例如：

    输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

输入：s1= "ab" s2 = "eidboaoo"
输出：false

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    解题思路： 与 424. 替换后的最长重复字符 ，438. 找到字符串中所有字母异位词
    一样的思路

    class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_cnt,s2_cnt = [0]*26,[0]*26
        m,n,L = len(s1),len(s2),0
        for ch in s1:
            idx = ord(ch)-ord('a')
            s1_cnt[idx] += 1

        for R in range(n):
            cur_R = ord(s2[R])-ord('a')
            s2_cnt[cur_R] += 1
            while s2_cnt[cur_R] > s1_cnt[cur_R]:
                cur_L = ord(s2[L])-ord('a')
                L += 1
                s2_cnt[cur_L] -= 1
            if R-L+1 == m:
                return True
        return False

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    763. 划分字母区间（model-I）

    题目链接：763. 划分字母区间
    题目大意： 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

    例如：

    输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    解题思路： 同567. 字符串的排列

    class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        s_cnt = [0]*26
        L,n = 0,len(s)
        stop,ans = 0,[]
        # 每一个字母所能行走到的最远距离
        for i,ch in enumerate(s):
            idx = ord(ch)-ord('a')
            s_cnt[idx] = i

        for R in range(n):
            cur_R = ord(s[R])-ord('a')
            stop = max(stop,s_cnt[cur_R])
            # print(R,stop)
            if R == stop:
                # print(s[L:R+1])
                # print(stop)
                ans.append(R-L+1)
                L = R+1
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    826. 安排工作以达到最大收益

    题目链接：826. 安排工作以达到最大收益
    题目大意：你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

    • difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
    • worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。
    • 每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。
      举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

    例如：

    输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    解题思路 ：

    • difference between bisect.bisect_left() and bisect_right()
    • (1) 列表中没有查询元素x时，两者返回相同的值，即插入的位置；
    • (2) 只有1个元素x时，left 返回该值所在位置，right 对应位置+1
    • (3) 多个元素x时，left 返回元素x最左面的元素位置 right 最右端元素x的位置+1
    #  字典排序
'''
>>> people = {3: "Jim", 2: "Jack", 4: "Jane", 1: "Jill"}

>>> # Sort by key
>>> dict(sorted(people.items()))
{1: 'Jill', 2: 'Jack', 3: 'Jim', 4: 'Jane'}

>>> # Sort by value
>>> dict(sorted(people.items(), key=lambda item: item[1]))
{2: 'Jack', 4: 'Jane', 1: 'Jill', 3: 'Jim'}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    # zip 排序
'''
>>> a = [3, 9, 2, 24, 1, 6]
>>> b = ['a', 'b', 'c', 'd', 'e']
>>> sorted(zip(a, b))
[(1, 'e'), (2, 'c'), (3, 'a'), (9, 'b'), (24, 'd')]
>>> sorted(zip(a, b), key=lambda x: x[1])
[(3, 'a'), (9, 'b'), (2, 'c'), (24, 'd'), (1, 'e')]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        ans,i,best = 0,0,0
        n = len(difficulty)
        difficulty,profit = zip(*sorted(zip(difficulty,profit)))
        difficulty,profit = list(difficulty),list(profit)
        maxn = float('-inf')
        for i in range(n):
            if profit[i] < maxn:
                profit[i] = maxn
            else:
                maxn = profit[i]
        for skill in sorted(worker):
            i = bisect.bisect_right(difficulty,skill)
            ans += profit[i-1] if i>0 else 0
        return ans
'''

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    838. 推多米诺（model-I）

    题目链接：838. 推多米诺
    题目大意： n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

    • dominoes[i] = ‘L’，表示第 i 张多米诺骨牌被推向左侧，
    • dominoes[i] = ‘R’，表示第 i 张多米诺骨牌被推向右侧，
    • dominoes[i] = ‘.’，表示没有推动第 i 张多米诺骨牌。
    • 返回表示最终状态的字符串。

    例如：
    在这里插入图片描述

    输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

    • 1
    • 2

    解题思路：

                # 四种情况：
            # 1）R . . . R -> R R R R R
            # 2）L . . . L -> L L L L L
            # 3）R . . . L -> R R . L L and R . . . . L -> R R R L L L
            # 4）L . . . R and L . . . . R -> no change

    • 1
    • 2
    • 3
    • 4
    • 5
    class Solution:
    def pushDominoes(self, d: str) -> str:
        
        # 这一步预处理 绝了！！！
        d = 'L' + d + 'R'
        n = len(d)
        L,ans = 0,[]
        for R in range(1,n):
            if d[R] == '.': continue
            num = R-L-1

            if L:
                ans.append(d[L])
            if d[L] == d[R]:
                ans.append(d[L]*num)
            elif d[L] == 'R' and d[R] == 'L':
                ans.append('R'*(num//2)+'.'*(num%2)+'L'*(num//2))
            else:
                ans.append('.'*num)
            L = R
        return ''.join(ans)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    845. 数组中的最长山脉（model-II）

    题目链接：845. 数组中的最长山脉
    题目大意：
    把符合下列属性的数组 arr 称为 山脉数组 ：

    • arr.length >= 3
    • 存在下标 i（0 < i < arr.length - 1），满足 arr[0] < arr[1] < … < arr[i - 1] < arr[i]， arr[i] > arr[i + 1] > … > arr[arr.length - 1]
    • 给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

    例如：

    输入：arr = [2,1,4,7,3,2,5]
输出：5
解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

    • 1
    • 2
    • 3

    解题思路：while 循环 省力气！

    class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans,L = 0,0
        # while 还是非常有用的 省了不少时间！！！
        while L < n-1:
            if arr[L] < arr[L+1]:
                R=L
                up,down = False,False
                while R<n-1 and arr[R]<arr[R+1]:
                    up = True
                    R += 1
                while R<n-1 and arr[R]>arr[R+1]:
                    down = True
                    R += 1
                if R-L+1>ans and up and down:
                    ans = R-L+1
                L=R 
            else:
                L += 1
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    881. 救生艇（model-II）

    题目链接：881. 救生艇
    题目大意：给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回 承载所有人所需的最小船数 。

    例如：

    输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    解题思路： 循环中控制 船的个数。

    class Solution:
    def numRescueBoats(self, p: List[int], limit: int) -> int:
        n,ans = len(p),0
        L,R,cnt = 0,n-1,0
        p.sort()
        while cnt < n:
            if L<n-1 and p[L]+p[R] <= limit:
                L += 1
                R -= 1
                cnt += 2
            elif R>0 and p[R]+p[R-1] <= limit:
                R -= 2
                cnt += 2
            else:
                R -= 1
                cnt += 1
            ans += 1
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    904. 水果成篮

    题目链接：904. 水果成篮
    题目大意：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

    • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
    • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
    • 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

    例如：

    输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    解题思路： 注意 del 非常重要！

    class Solution:
    def totalFruit(self, f: List[int]) -> int:
        n = len(f)
        L,ans = 0,0
        counter = collections.Counter()
        for R in range(n):
            counter[f[R]] += 1
            while len(counter) > 2:
                counter[f[L]] -= 1
                #  因为 while 判断的是 字典中的个数 所以为0 后必须删除
                if counter[f[L]] == 0: del counter[f[L]]
                L += 1
            ans = max(ans,R-L+1)
        return ans



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    930. 和相同的二元子数组 **

    题目链接：930. 和相同的二元子数组
    题目大意：给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。

    例如：

    输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

输入：nums = [0,0,0,0,0], goal = 0
输出：15

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    解题思路：不好想啊 这道题的 做法 有点赖。

    class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        ans,total = 0,0
        L1,L2 = 0,0
        sum1,sum2 = 0,0
        for R in range(n):
            sum1 += nums[R]
            while L1<=R and sum1>goal:
                sum1 -= nums[L1]
                L1 += 1
            sum2 += nums[R]
            while L2<=R and sum2>=goal:
                sum2 -= nums[L2]
                L2 += 1
            ans += L2-L1
        return ans


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    986. 区间列表的交集（model-II）

    题目链接：986. 区间列表的交集
    题目大意：给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。返回这 两个区间列表的交集 。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

    例如：
    在这里插入图片描述

    输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

    • 1
    • 2

    解题思路：典型的区间题目，难一点的话就必须使用 最小堆了。

    class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        m,n = len(A),len(B)
        ans = []
        if m==0 or n==0: return []
        i,j = 0,0
        while i<m and j<n:
            lo = max(A[i][0],B[j][0])
            hi = min(A[i][1],B[j][1])
            if lo <= hi:
                ans.append([lo,hi])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return ans


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    1004. 最大连续1的个数 III （model-I）

    题目链接：1221. 分割平衡字符串
    题目大意：
    给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

    例如：

    输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    解题思路： 双指针 + 计数

    class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        n = len(nums)
        counter = collections.Counter(nums)
        if counter[0] <= k: return n
        L,ans,cnt = 0,0,0
        for R in range(n):
            if nums[R] == 0:
                cnt += 1
            while cnt > k:
                if nums[L] == 0:
                    cnt -= 1
                L += 1
            if cnt == k:
                ans = max(ans,R-L+1) 
        return ans


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    1040. 移动石子直到连续 II

    题目链接：1040. 移动石子直到连续 II
    题目大意：在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。

    • 值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。-
    • 当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

    例如：

    输入：[7,4,9]
输出：[1,2]
解释：我们可以移动一次，4 -> 8，游戏结束。或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

输入：[6,5,4,3,10]
输出：[2,3]
解释：我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    解题思路：

    class Solution:
    def numMovesStonesII(self, s: List[int]) -> List[int]:
        n = len(s)
        if n == 0: return [0,0]
        s.sort()
        # 注意 端点石子 移动后 不能是端点石子
        maxS = max(s[-2]-s[0],s[-1]-s[1])+2-n
        minS,L,R = float('inf'),0,0
        while L<n:
            if R+1<n and s[R]-s[L]<n:
                R += 1
            else:
                if s[R]-s[L] >= n: R -= 1
                if R-L+1 == n-1 and s[R]-s[L]+1 == n-1: 
                    minS = min(minS,2)
                else:
                    minS = min(minS,n-(R-L+1))
                if R == n-1 and s[R]-s[L]<n:
                    break
                L += 1
        return [minS,maxS]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    1052. 爱生气的书店老板

    题目链接：1052. 爱生气的书店老板
    题目大意：有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

    • 在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
    • 当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
      请你返回 这一天营业下来，最多有多少客户能够感到满意 。

    例如：

    输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    解题思路： 需要读懂题意 才能搞明白如何设计 动态变化的中间量

    class Solution:
    def maxSatisfied(self, c: List[int], g: List[int], m: int) -> int:
        n = len(c)
        total = sum(c for c,g in zip(c,g) if g==0)
        curVal = 0
        for i in range(m):
            curVal += c[i]*g[i]
        ansVal = curVal
        for i in range(m,n):
            curVal = curVal + c[i]*g[i] - c[i-m]*g[i-m]
            ansVal = max(ansVal,curVal)
        return ansVal+total

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    1093. 大样本统计

    题目链接：1093. 大样本统计
    题目大意：
    我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。计算以下统计数据:

    • minimum ：样本中的最小元素。
    • maximum ：样品中的最大元素。
    • mean ：样本的平均值，计算为所有元素的总和除以元素总数。
    • median ：如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
    • mode ：样本中出现次数最多的数字。保众数是 唯一 的。
    • 以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。

    例如：

    输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
解释：用count表示的样本为[1,2,2,2,3,3,3,3,3]。
最小值和最大值分别为1和3。
均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。
因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。
众数为3，因为它在样本中出现的次数最多。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    解题思路： 很多啊！

    class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        mi = 225.0
        ma = 0.0
        me = 0.0
        mode = [0,0]
        med = 0
        n = sum(count)
        t = 0
        half = [n//2+1] if n%2 else [n//2,n//2+1]
        flag = 0
        for i in range(256):
            if count[i]:
                mi=min (i,mi)
                ma = max(i,ma)
                if mode[1] < count[i]:
                    mode[0],mode[1] = i,count[i]
                me += count[i]*i
                flag += count[i]
                while(half):
                    if flag >= half[0]:
                        med += i
                        t +=1
                        half.remove(half[0])
                    else:break
            else:
                pass
        return [mi,ma,me/n,med/t,mode[0]]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    1208. 尽可能使字符串相等 （model-II）

    题目链接：1208. 尽可能使字符串相等
    题目大意：给你两个长度相同的字符串，s 和 t。将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

    例如：

    输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    解题思路： 很多啊！

    class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        diff = [abs(ord(sc) - ord(tc)) for sc, tc in zip(s, t)]
        ans,L,R = 0,0,0
        total = 0

        for R in range(n):
            total += diff[R]
            while total > maxCost:
                total -= diff[L]
                L += 1
            ans = max(ans, R-L+1)

        return ans


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    总结

      滑动窗口或双指针这一部分的大半算整完了,当然这些题还是比较少的,这周继续参加积分竞赛,希望能可以拿下三道题，加油!

  • 相关阅读:
    Flink实时计算中台Kubernates功能改造点
    面试题整理
    从零开始的LINUX(一)
    【MATLAB教程案例52】SVM支持向量机学习——使用matlab实现基于SVM的数据二分类
    Flask框架初学-05-命令管理Manager及数据库的使用
    用Androidstudio 开发一个学生作业管理系统
    合成数据: 利用开源技术节约资金、时间和减少碳排放
    debian 已安装命令找不到 解决方法
    Hadoop -- 分布式文件系统
    CF1527D MEX Tree
  • 原文地址：https://blog.csdn.net/weixin_42269028/article/details/126813463