双指针算法

图形

image.png

题目一

描述：
提取字符串中 用 单个空格隔开的单词
输入：
i am boy；
输出：
i
am
boy
代码实现

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  4. public class ForSubstring {
  5.     public static void main(String[] args) throws Exception {
  6.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7.         String[] strs = br.readLine().split("");
  8.         String str;
  9.         for (int i = 0; i < strs.length; i++) {
  10.             int j = i;
  11.             while( j < strs.length && !" ".equals(strs[j])) j ++;
  12.             for (int k = i; k < j; k++) {
  13.                 System.out.print(strs[k]);
  14.             }
  15.             System.out.println();
  16.             i = j;
  17.         }
  18.     }
  19. }

题目二

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼1e5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1e5
输入样例：
5 1 2 2 3 5
输出样例：
3
代码实现：

  1. //hashmap 实现 
  2. for ( int i = 0,j = 0; i < n;i ++) {
  3.     while(map.containsKey(arr[i])) map.remove(arr[j++]);
  4.     map.put(arr[i],1);
  5.     res = Math.max(map.size(),res);
  6. }
  7. //数组实现 比hashmap快
  8. for ( int i = 0,j = 0 ; i < n;i ++) {
  9.     b[arr[i]] ++ ;
  10.     while (b[arr[i]] > 1) b[arr[j++]] --;
  11.     res = Math.max(res,i-j+1);
  12. }

题目三

题目描述
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
代码实现：

  1. int n = Integer.parseInt(strs[0]),
  2. m = Integer.parseInt(strs[1]),
  3. x = Integer.parseInt(strs[2]);
  4. int[] a = new int[n];
  5. int[] b = new int[m];
  6. strs = br.readLine().split( " ");
  7. String[] strings = br.readLine().split( " ");
  9. Map<Integer,Integer> map = new HashMap<>();
  10.     //因为n与m可大可小，所以有个取最大值
  11.     //只要i < n 就可以处理a数组
  12.     //只要i < m 就可以处理b数组
  13.     //以a数组为例 存入map
  14.     for (int i = 0; i < (n > m ? n : m) ; i++) {
  15.         if (i < n) {
  16.             a[i] = Integer.parseInt(strs[i]);
  17.             map.put(a[i],i);
  18.         }
  19.         if (i < m) b[i] = Integer.parseInt(strings[i]);
  20.     }
  21.     //循环判断，只要x - b[i] 存在于map中 即为所得
  22.     for (int i = 0; i < m; i++) {
  23.         if (map.containsKey(x-b[i])) System.out.println(map.get(x-b[i])+" "+i);
  24.     }
  25. }

题目四

给定一个长度为 nn 的整数序列 a1,a2,…,an以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5}是序列 {a1,a2,a3,a4,a5}的一个子序列。
输入格式
第一行包含两个整数 n,m
第二行包含 nn 个整数，表示 a1,a2,…,an
第三行包含 mm 个整数，表示 b1,b2,…,bm
输出格式
如果 a 序列是 b 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1≤n≤m≤105
−109≤ai,bi≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes
代码实现：

  1. for (int i = 0; i < m ; i++) {
  2.     if (i < n) a[i] = Integer.parseInt(strs[i]);
  3.     if (i < m) b[i] = Integer.parseInt(strings[i]);
  4. }
  5. int j = 0;
  6. for (int i = 0; i < m; i ++) {
  7.     if (b[i] == a[j]) j++;
  8.     if(j == n) {
  9.         System.out.println("Yes");
  10.         break;
  11.     }
  12.     if(i == m -1 ) System.out.println("No");
  13. }

位运算

求 n 的第 k 位数 n >> k & 1 ;
返回n的最后一位1 lowbit( n ) = n & (-n)

题目

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n个整数，表示整个数列。
输出格式
共一行，包含 n 个整数，其中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000
0≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
代码实现：

  1. int i = 0;
  2. while (n-- != 0) {
  3.     int res = 0;
  4.     while(arr[i] != 0) {
  5.         arr[i] -= (arr[i] & -arr[i]);
  6.         res++;
  7.     }
  8.     i++;
  9.     System.out.print(res+" ");
  10. }

离散化

图形

image.png

题目

题目描述
假定有一个无限长的数轴，数轴上每个坐标上的数都是00。

现在，我们首先进行nn次操作，每次操作将某一位置 xx 上的数加 cc 。

接下来，进行 mm 次询问，每个询问包含两个整数 ll 和 rr，你需要求出在区间 [l,r][l,r] 之间的所有数的和。

输入格式
第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式
共m行，每行输出一个询问中所求的区间内数字和。

数据范围
−109≤x≤109−109≤x≤109
1≤n,m≤1051≤n,m≤105
−109≤l≤r≤109−109≤l≤r≤109
−10000≤c≤10000−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
代码实现：

  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  5.     final static int N = 300100;
  7.     public static void main(String[] args) throws Exception {
  9.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  11.         String[]  strs = br.readLine().split(" ");
  12.         int n = Integer.parseInt(strs[0]),
  13.                 m = Integer.parseInt(strs[1]);
  14.         int[] q = new int[N];
  15.         int[] s = new int[N];
  17.         List<Integer> alls = new ArrayList<>();
  18.         List<Node> add = new ArrayList<>();
  20.         List<Node> query = new ArrayList<>();
  21.         for (int i = 0; i < n; i++) {
  22.             strs = br.readLine().split(" ");
  23.             int x = Integer.parseInt(strs[0]);
  24.             int c = Integer.parseInt(strs[1]);
  25.             add.add(new Node(x,c));
  26.             alls.add(x);
  27.         }
  28.         for (int i = 0; i < m; i++) {
  29.             strs = br.readLine().split(" ");
  30.             int l = Integer.parseInt(strs[0]);
  31.             int r = Integer.parseInt(strs[1]);
  32.             alls.add(l);
  33.             alls.add(r);
  34.             query.add(new Node(l,r));
  35.         }
  36.         Collections.sort(alls);
  37.         int unique = unique(alls);
  38.         alls = alls.subList(0,unique);
  39.         for (Node node : add) {
  40.             int index = find(node.first,alls);
  41.             q[index] = 0;
  42.             q[index] += node.last;
  43.         }
  44.         for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + q[i];
  46.         for (Node node : query) {
  47.             int l = find(node.first,alls);
  48.             int r = find(node.last,alls);
  49.             System.out.println(s[r] - s[l - 1]);
  50.         }
  51.         br.close();
  52.     }
  53.     private static int unique(List<Integer> list) {
  54.         int j = 0;
  55.         for (int i = 0; i < list.size() - 1; i++) {
  56.             if(i == 0 || list.get(i) != list.get(i - 1)) {
  57.                 list.set(j,list.get(i));
  58.                 j++;
  59.             }
  60.         }
  61.         return j;
  62.     }
  63.     private static int find (int x ,List<Integer> list) {
  64.         int l = 0;
  65.         int r = list.size() - 1;
  66.         while (l < r) {
  67.             int mid = l + r >> 1;
  68.             if (list.get(mid) >= x) r = mid;
  69.                 else l = mid + 1;
  70.         }
  71.         return l + 1;
  72.     }
  73. }
  74. class Node {
  75.     public int first;
  76.     public int last;
  77.     public Node(int first, int last) {
  78.         this.first = first;
  79.         this.last = last;
  80.     }
  81. }

区间合并

图形

image.png

题目

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n
接下来n行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
代码实现：

  1. List<Node> megs  = new ArrayList<>();
  2. while (n-- != 0) {
  3.     String[] strs = br.readLine().split(" ");
  4.     int l = Integer.parseInt(strs[0]),
  5.     r = Integer.parseInt(strs[1]);
  6.     megs.add(new Node(l,r));
  7. }
  8. System.out.println(mergeInterval(megs));
  10. private static int mergeInterval(List<Node> megs) {
  11.     megs.sort(new Comparator<Node>() {
  12.         @Override
  13.         public int compare(Node o1, Node o2) {
  14.             return o1.first - o2.first;
  15.         }
  16.     });
  17.     int r = Integer.MIN_VALUE,k = 0;
  18.     for (Node node : megs) {
  19.         if(node.first > r) k++;
  20.         r = r > node.last ? r : node.last;
  21.     }
  22.     return k;
  23. }