算法思想之双指针

双指针

• 双指针是指在解决问题时使用两个指针，通常分别指向数组或字符串中的不同位置，通过移动这两个指针来解决问题的一种技巧。双指针技巧常用于解决数组、链表或字符串相关的问题。
• 双指针常见的应用题型包括：
  • 快慢指针：用于解决链表中的环检测、链表中间节点查找等问题。快慢指针可以帮助判断链表是否有环、找到链表的中间节点等。
  • 对撞指针：又称为双指针夹逼法，通常用于解决数组或字符串中的查找问题。例如在有序数组中查找两数之和、三数之和等问题。
  • 左右指针：使用两个指针分别从数组的两端开始向中间移动，用于解决数组或字符串中的问题，如判断是否存在某个目标值、查找满足条件的子数组等。
  • 滑动窗口：双指针技巧在滑动窗口算法中有广泛应用。滑动窗口是一种解决字符串或数组子串问题的技巧，通过维护一个窗口来解决问题。
  • 两数之和：给定一个数组和一个目标值，找到数组中的两个数使得它们的和等于目标值。双指针技巧可以用于解决这类问题。
• 双指针技巧通常能够提高问题的解决效率，减少时间复杂度，并且可以解决一些复杂的数据处理问题。根据具体问题的要求和特点，选择合适的双指针技巧来解决问题会更加高效。

字符串序列判定

• 题目描述

  输入两个字符串 S 和 L，都只包含英文小写字母。S 长度 <=100，L 长度 <=500,000。判定 S 是否是 L 的有效子串。

  判定规则：

  S 中的每个字符在 L 中都能找到（可以不连续），且 S 在Ｌ中字符的前后顺序与 S 中顺序要保持一致。

  （例如，S=”ace”是 L=”abcde”的一个子序列且有效字符是 a、c、e，而”aec”不是有效子序列，且有效字符只有 a、e）

  输入描述

  输入两个字符串 S 和 L，都只包含英文小写字母。S 长度<=100，L 长度<=500,000。先输入 S，再输入 L，每个字符串占一行。

  输出描述

  S 串最后一个有效字符在 L 中的位置。（首位从 0 开始计算，无有效字符返回 -1）

• 示例1

  输入：
  ace
  abcde
  输出：4
  

  示例2

  输入：
  fgh
  abcde
  输出：-1
  

• 题解：双指针

  1. 使用双指针 i 和 j，分别指向字符串 S 和 L 的开头。
  2. 遍历字符串L，对于 L 的每个字符：
     • 如果当前字符等于 S 的当前字符（即S[i] == L[j]），则移动 S 的指针 i，继续比较下一个字符
     • 如果当前字符不等于 S 的当前字符，继续遍历 L 下一个字符
  3. 如果 S 的指针 i 移动到了末尾（即 i == len(S)），则说明 S 是 L 的有效子串，输出当前 L 的指针位置 j
  4. 如果遍历完 L 后，仍然没有找到有效子串，则输出 -1

  import java.util.Scanner;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String S = sc.nextLine();String L = sc.nextLine();int sIndex = 0;int lastPos = -1;for (int i = 0; i < L.length(); i++) {if (sIndex == S.length()) {break;}if (S.charAt(sIndex) == L.charAt(i)) {lastPos = i;sIndex++;}}System.out.println(sIndex == S.length() ? lastPos : -1);}}
  }
  

字符串所有整数最小和

• 题目描述

  输入字符串 s，输出 s 中包含所有整数的最小和。

  说明：

  字符串 s，只包含 a-z A-Z + -

  合法的整数包括

  • 正整数：一个或者多个0-9组成，如 0 2 3 002 102
  • 负整数：负号 – 开头，数字部分由一个或者多个0-9组成，如 -0 -012 -23 -00023

  输入要求

  包含数字的字符串

  输出要求

  所有整数的最小和

• 用例1

  输入：bb1234aa
  输出：10
  

  用例2

  输入：bb12-34aa
  输出：-31
  说明：1+2+（-34） = -31
  

• 题解1

  import java.util.Scanner;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String str = sc.nextLine();str += " "; // 处理字符串末尾为负数情况int sum = 0;int num = 0; // 数字前方为符号时拼接数字boolean flag = false; // 数字前方是否为负号char[] arr = str.toCharArray();for (int i = 0; i < arr.length; i++) {char c = arr[i];if (!Character.isDigit(c)) {if (flag) {sum -= num;num = 0;}flag = '-' == c;} else {if (flag) num = num * 10 + c - '0';else sum += c - '0';}}System.out.println(sum);}}
  }
  

  题解2：双指针

  从左到右扫描字符串，遇到数字时累加到结果中，遇到负号时将后面的负数减去。具体做法是使用两个指针 i 和 r，i 指向当前字符，r 指向负数的末尾。每次遇到负号时，将 r 移动到负数的末尾，将负数转换为整数后减去即可。

   import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String str = sc.nextLine();int sum = 0;int r = 0;char[] arr = str.toCharArray();for (int i = 0; i < arr.length; i++) {char c = arr[i];if (Character.isDigit(c)) sum += c - '0';else if ('-' == c) {r = i + 1;while (r < arr.length && Character.isDigit(arr[r])) {r++; // 右指针指向负数后一个字符}sum -= i + 1 == r ? 0 : Integer.parseInt(str.substring(i + 1, r));i = r; // 计算完毕，移动左指针}}System.out.println(sum);}}}
  

服务交换接口失败率分析

• 题目描述

  服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，数组中的数值为 0 ~ 100 的整数，给定一个数值（minAverageLost）表示某个时间段内平均失败率容忍值，即平均失败率小于等于 minAverageLost，找出数组中最长时间段，如果未找到则直接返回 。

  输入要求

  输入有两行内容，

  第一行为 minAverageLost

  第二行为（数组），数组元素通过空格(“ “)分隔。

  minAverageLost 及数组中元素取值范围为 0−100 的整数，数组元素的个数不会超过 100 个

  输出要求

  找出平均值小于等于 minAverageLost 的最长时间段，输出数组下标对，格式 (beginindex) - (endindx)（下标从0开始），如果同时存在多个最长时间段，则输出多个下标对与下标对之间使用空格(” ”)拼接，多个下标对按下标对从小到大排序。

  如果不存在满足条件的时间段，则输出 NULL。

• 用例1

  输入：
  1
  0 1 2 3 4
  输出：0-2
  

  用例2

  输入：
  2
  0 0 100 2 2 99 0 2
  输出：0-1 3-4 6-7
  

• 题解1

  import java.util.*;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNextLine()) {int k = Integer.parseInt(sc.nextLine());String[] arr = sc.nextLine().split(" ");ArrayList<String> list = new ArrayList<>();int l = 0; int maxLen = 0; int sum = 0;for (int r = 0; r < arr.length; r++) {sum += Integer.parseInt(arr[r]);int len = r - l + 1; // 左右指针长度，指向同一个位置时长度为1if ((double) sum / len > k) {sum = 0; // 重置左右指针间的数值和l = r + 1; // 移动左指针指向下一个数字} else {if (len > maxLen) list.clear(); // 新的最大长度，清空小于该长度的时间段if (len >= maxLen) list.add(l + "-" + r);maxLen = Math.max(maxLen, len); // 更新最大长度}}if (list.isEmpty()) System.out.println("NULL");for (int i = 0; i < list.size(); i++) {if (i == list.size()-1) System.out.println(list.get(i));else System.out.print(list.get(i) + " ");}}}
  }
  

分披萨

• 题目描述

  "吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块都完全不同奇数块，且肉眼能分辨出大小。

  由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口选。

  他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。

  已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。

  输入要求

  第 1 行为一个正整数奇数 N，表示披萨小块数量，其中 3 ≤ N < 500。接下来的第 2 行到第 N + 1 行（共 N 行），每行为一个正整数，表示第 i 块披萨的大小，其中 1 ≤ i ≤ N。

  披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ∼ N，每块披萨的大小范围为 [1, 2147483647]

  输出要求

  "吃货"能分得到的最大的披萨大小的总和。

• 用例1

  输入：
  5
  8
  2
  10
  5
  7
  输出：19
  说明：
  此例子中，有 5 块披萨。每块大小依次为 8、2、10、5、7。
  按照如下顺序拿披萨，可以使"吃货"拿到最多披萨：
  “吃货” 拿大小为 10 的披萨
  “馋嘴” 拿大小为 5 的披萨
  “吃货” 拿大小为 7 的披萨
  “馋嘴” 拿大小为 8 的披萨
  “吃货” 拿大小为 2 的披萨
  至此，披萨瓜分完毕，"吃货"拿到的披萨总大小为 10 +7 + 2 = 19
  可能存在多种拿法，以上只是其中一种。
  

• 题解

  import java.util.*;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < n; i++) {list.add(sc.nextInt());}Integer max = Collections.max(list); // 先拿最大的一块int maxIndex = list.indexOf(max);int ret = max, l = check(maxIndex - 1, n), r = check(maxIndex + 1, n);for (int i = 0; i < (n-1) / 2; i++) { // 除去最大一块后，轮流拿(n-1)/2次ret += Math.min(list.get(l), list.get(r));l = check(l - 1, n);r = check(r + 1, n);}System.out.println(ret);}}public static int check(int i, int n) {if (i < 0) return n - 1;else if (i > n - 1) return 0;else return i;}
  }
  

最多团队

• 题目描述

  用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为 N，每个团队可以由 1 人或者 2 人组成，且 1 个人只能参加 1 个团队，计算出最多可以派出多少只符合要求的团队。

  输入要求

  第一行代表总人数，范围 1-500000

  第二行数组代表每个人的能力

  数组大小，范围 1-500000

  元素取值，范围 1-500000

  第三行数值为团队要求的最低能力值，范围 1-500000

  输出要求

  最多可以派出的团队数量

• 用例1

  输入：
  5
  3 1 5 7 9
  8
  输出：3
  说明：说明 3、5组成一队 1、7一队 9自己一队 输出3
  

  用例2

  输入：
  7
  3 1 5 7 9 2 6
  8
  输出：4
  说明：3、5组成一队，1、7一队，9自己一队，2、6一队，输出4
  

  用例3

  输入：
  3
  1 1 9
  8
  输出：1
  说明：9自己一队，输出1
  

• 题解1

  import java.util.*;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) arr[i] = sc.nextInt();int k = sc.nextInt();Arrays.sort(arr);int l = 0; int r = n - 1; int count = 0;while (r >= l) {if (arr[r] >= k) { // 单人参赛count++; r--;} else if (arr[l] + arr[r] >= k) {count++; l++; r--;} else if (arr[l] + arr[r] < k) {l++; // 能力太差，要么不参赛，要么跟可以单人参赛的人一起参赛}}System.out.println(count);}}
  }