力扣算法系列文章

一、判断子序列

题目如下：

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数，表示 a1,a2,…,an。
第三行包含 m 个整数，表示 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

代码如下：

import java.util.Scanner;public class Main {    public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] arr1 = new int[n]; int[] arr2 = new int[m]; for(int i = 0; i < n; ++i){     arr1[i] = sc.nextInt(); } for(int i = 0; i < m; ++i){     arr2[i] = sc.nextInt(); } int p1 = 0; for(int i = 0; i < m; ++i){     if(p1 < n && arr1[p1] == arr2[i]){  ++p1;     } } if(p1 == n) {     System.out.println("Yes"); }else{     System.out.println("No"); }    }}

运行结果：

二、二进制中1的个数

题目如下：

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。

输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围
1≤n≤100000,
0≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2

代码如下：

import java.util.*;public class Main{    public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while(n -- > 0){     int num = sc.nextInt();     int cnt = 0;     while(num != 0){  int rightOne = num & (-num);  num ^= rightOne;  cnt++;     }     System.out.print(cnt + " "); }    }}

运行结果：

三、区间和

题目如下：

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。

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

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

代码如下：

import java.util.*;public class Main {    public static class Pair{ int first; int second; public Pair(int o1, int o2){     this.first = o1;     this.second = o2; }    }    public static final int N = 300010;    public static int n;    public static int m;    public static int[] CoordinateAxes = new int[N];    public static int[] sum = new int[N];    public static List<Integer> alls = new ArrayList<>();    public static List<Pair> add = new ArrayList<>();    public static List<Pair> query = new ArrayList<>();    public static int unique(List<Integer> list) { int j = 0; for (int i = 0; i < list.size(); i++) {     if (i == 0 || list.get(i) != list.get(i - 1)) {  list.set(j, list.get(i));  j++;     } } return j;    }    public static int find(int x){ int l = 0; int r = alls.size() - 1; while(l < r){     int mid = l + ((r - l) >> 1);     if(alls.get(mid) >= x){  r = mid;     }else{  l = mid + 1;     } } return r + 1;    }    public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for(int i = 0; i < n; ++i){     int x = sc.nextInt();     int c = sc.nextInt();     add.add(new Pair(x, c));     alls.add(x); } for(int i = 0; i < m; ++i){     int l = sc.nextInt();     int r = sc.nextInt();     query.add(new Pair(l, r));     alls.add(l);     alls.add(r); } Collections.sort(alls); int unique = unique(alls); alls = alls.subList(0, unique); for(Pair item : add){     int x = find(item.first);     CoordinateAxes[x] += item.second; } for(int i = 1; i <= alls.size(); ++i){     sum[i] = sum[i - 1] + CoordinateAxes[i]; } for(Pair item : query){     int l = find(item.first);     int r = find(item.second);     System.out.println(sum[r] - (l -1 < 0 ? 0 : sum[l - 1])); }    }}

运行结果：

四、区间合并

题目如下：

给定 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

代码如下：

import java.util.*;public class Main {     public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] arr = new int[n][2]; for(int i = 0; i < n; ++i){     arr[i][0] = sc.nextInt();     arr[i][1] = sc.nextInt(); } final int[][] merge = merge(arr); System.out.println(merge.length);    }     public static int[][] merge(int[][] intervals) { int len=intervals.length; if (len==0)     return new int[0][2]; Arrays.sort(intervals, new Comparator<int[]>() {     public int compare(int[] o1, int[] o2) {  return o1[0]-o2[0];     } }); List<int[]> list=new ArrayList<int[]>(); for(int i=0;i<len;i++){     int start=intervals[i][0];     int end=intervals[i][1];     if(list.size()==0 || start > list.get(list.size()-1)[1]){  list.add(new int[]{start,end});     }else {  list.get(list.size()-1)[1]=Math.max(end,list.get(list.size()-1)[1]);     } } return list.toArray(new int[list.size()][]);    } }

运行结果：