文章目錄
- 雙指針
- 字符串序列判定
- 字符串所有整數最小和
- 服務交換接口失敗率分析
- 分披薩
- 最多團隊
雙指針
- 雙指針是指在解決問題時使用兩個指針，通常分別指向數組或字符串中的不同位置，通過移動這兩個指針來解決問題的一種技巧。雙指針技巧常用于解決數組、鏈表或字符串相關的問題。
- 雙指針常見的應用題型包括：
- 快慢指針：用于解決鏈表中的環檢測、鏈表中間節點查找等問題。快慢指針可以幫助判斷鏈表是否有環、找到鏈表的中間節點等。
- 對撞指針：又稱為雙指針夾逼法，通常用于解決數組或字符串中的查找問題。例如在有序數組中查找兩數之和、三數之和等問題。
- 左右指針：使用兩個指針分別從數組的兩端開始向中間移動，用于解決數組或字符串中的問題，如判斷是否存在某個目標值、查找滿足條件的子數組等。
- 滑動窗口：雙指針技巧在滑動窗口算法中有廣泛應用。滑動窗口是一種解決字符串或數組子串問題的技巧，通過維護一個窗口來解決問題。
- 兩數之和：給定一個數組和一個目標值，找到數組中的兩個數使得它們的和等于目標值。雙指針技巧可以用于解決這類問題。
- 雙指針技巧通常能夠提高問題的解決效率，減少時間復雜度，并且可以解決一些復雜的數據處理問題。根據具體問題的要求和特點，選擇合適的雙指針技巧來解決問題會更加高效。
字符串序列判定
-
題目描述
輸入兩個字符串 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 -
題解：雙指針
- 使用雙指針 i 和 j，分別指向字符串 S 和 L 的開頭。
- 遍歷字符串L，對于 L 的每個字符：
- 如果當前字符等于 S 的當前字符（即S[i] == L[j]），則移動 S 的指針 i，繼續比較下一個字符
- 如果當前字符不等于 S 的當前字符，繼續遍歷 L 下一個字符
- 如果 S 的指針 i 移動到了末尾（即 i == len(S)），則說明 S 是 L 的有效子串，輸出當前 L 的指針位置 j
- 如果遍歷完 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);}} }
