双指针技巧的应用

Posted on In

这里对笔试题中常用到的「双指针技巧」进行简单的归纳，后续遇到会继续补充。

LeetCode 文章 「常用的双指针技巧」

数组相关问题

  • 调整数组顺序使得满足某种条件的数（如奇数）位于不满足条件的前面
  • 排序数组中和为 s 的两个数字
  • 排序数组中和为 s 的所有子数组
  • 和为 s 的连续正数序列
  • 接雨水问题
  • 颜色排序问题

笔试题记录

  • 网易游戏笔试题 (190811）：

    你可以最多改变两个大写字母，使得字符串所包含的连续的 N 串的长度最长，求最长长度

    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
    """
    5
    NNTN
    NNNNGGNNNN
    NGNNNNGNNNNNNNNSNNNN
    TNT
    T

    4
    10
    18
    3
    1
    """


    def main():
        # two pointers solution
        n_cases = int(input())
        while n_cases > 0:
            n_cases -= 1
            s = input().strip()
            length = len(s)

            le = ri = 0
            max_length = 0
            cnt = 0  # the count of non-'N's in current [le, ri] window
            while ri < length:
                if cnt > 2:
                    if s[le] != 'N':
                        cnt -= 1
                    le += 1
                else:
                    if s[ri] != 'N':
                        cnt += 1
                    ri += 1
                    max_length = max(max_length, ri-le)

            print(max_length)


    if __name__ == "__main__":
        main()

  • 网易云音乐面试题（190817）

    给定一个字符串，请你找出其中不含有重复字符的最长子串

    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
    """
    输入：原始字符串
    输出：最长子串

    input: abcabcaa
    output: abc
    input: ddddddd
    output: d
    input: skkwek
    output: kwe
    """


    s = input()
    length = len(s)

    le = ri = 0
    window = set()
    ans = [0, 0]
    while ri < length:
        while s[ri] in window:
            window.remove(s[le])
            le += 1
        window.add(s[ri])
        ri += 1
        if len(window) > ans[1] - ans[0] + 1:
            ans[0], ans[1] = le, ri

    print(s[ans[0]:ans[1]+1])

  • 字节跳动面试题（190818）

    求 arr[j] - arr[i] 的最大值， j >= i

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


    def main():
        arr = list(map(int, input().split()))
        i = j = 0
        ans = 0
        while j < len(arr):
            if arr[j] <= arr[i]:
                i = j
            ans = max(ans, arr[j] - arr[i])
            j += 1
        print(ans)


    if __name__ == "__main__":
        main()