基础算法
一、快速排序
1. 快速排序例题
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
quickSort(0,n-1,nums);
for (int i=0; i<n; i++) {
System.out.print(nums[i] + " ");
}
}
public static void quickSort (int l,int r,int[] nums) {
if(l>=r) {
return;
}
int x = nums[(l+r)/2];
int i = l - 1,j = r + 1;
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quickSort(l,j,nums);
quickSort(j+1,r,nums);
}
}
2. 第k个数( 快速选择算法 )
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSortFindKthLargest(nums,k,0,nums.length-1);
}
public int quickSortFindKthLargest(int[] nums, int k, int l,int r) {
if (l >= r) {
return nums[l];
}
int i = l-1, j = r+1;
int x = nums[i+j>>1];
while (i < j) {
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
if (j+1<=nums.length-k) {
return quickSortFindKthLargest(nums,k,j+1,r);
} else {
return quickSortFindKthLargest(nums,k,l,j);
}
}
}
二、归并排序
1. 归并排序模板题
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
merge_sort(0,n-1,nums);
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " ");
}
}
public static void merge_sort (int l,int r,int[] nums) {
if (l >= r) {
return;
}
int mid = (l+r) >> 1;
int i = l,j = mid + 1;
merge_sort(l,mid,nums);
merge_sort(mid+1,r,nums);
int[] temp = new int[r - l + 1];
int k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= r) {
temp[k++] = nums[j++];
}
for (int q = l,p = 0; q <= r; q++) {
nums[q] = temp[p++];
}
}
}
2. 逆序对的数量
class Solution {
public static int ans;
public int reversePairs(int[] record) {
ans = 0;
int n = record.length;
numberOfReverseOrderPairs(0,n-1,record);
return ans;
}
public static void numberOfReverseOrderPairs(int l,int r,int[] nums){
if (l >= r) {
return;
}
int mid = (l+r)>>1;
int i = l,j = mid+1;
numberOfReverseOrderPairs(l,mid,nums);
numberOfReverseOrderPairs(mid+1,r,nums);
int[] temp = new int[r-l+1];
int k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
ans += mid - i + 1;
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= r) {
temp[k++] = nums[j++];
}
for (int q = l,p = 0; q <= r; q++) {
nums[q] = temp[p++];
}
}
}
三、二分
1. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1,-1};
}
int l = 0, r = nums.length-1;
while (l < r) {
int mid = l+r>>1;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
int ans1 = r;
l = 0; r = nums.length-1;
while (l < r) {
int mid = l+r+1>>1;
if (nums[mid] <= target) {
l = mid;
} else {
r = mid-1;
}
}
int ans2 = r;
if (nums[ans1] == target && nums[ans2] == target) {
return new int[]{ans1,ans2};
} else {
return new int[]{-1,-1};
}
}
}
2. 数的三次方根
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
四、高精度
1. 字符串相加
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算完以后的答案需要翻转过来
ans.reverse();
return ans.toString();
}
}
2. 高精度减法
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s1 = scanner.next();
String s2 = scanner.next();
List<Integer> A = new ArrayList<>();
List<Integer> B = new ArrayList<>();
for(int i = s1.length() - 1;i >= 0;i --) A.add(s1.charAt(i) - '0');
for(int i = s2.length() - 1;i >= 0; i --) B.add(s2.charAt(i) - '0');
if(!cmp(A,B)){
System.out.print("-");
}
List<Integer> C = sub(A,B);
for(int i = C.size() - 1;i >= 0; i --){
System.out.print(C.get(i));
}
}
public static List<Integer> sub(List<Integer> A,List<Integer> B){
if(!cmp(A,B)){
return sub(B,A);
}
List<Integer> C = new ArrayList<>();
int t = 0;
for(int i = 0;i < A.size();i ++){
//这里应该是A.get(i) - B.get(i) - t ，因为可能B为零，所以需要判断一下是不是存在
t = A.get(i) - t;
if(i < B.size()) t -= B.get(i);
C.add((t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
//删除指定下标下面的值
while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
return C;
}
public static boolean cmp(List<Integer> A,List<Integer> B){
if(A.size() != B.size()) return A.size() > B.size();
/* if(A.size() >= B.size()){
return true;
}else{
return false;
}
*/
for(int i = A.size() - 1;i >= 0;i --){
if(A.get(i) != B.get(i)) {
return A.get(i) > B.get(i);
}
}
return true;
}
}
3. 高精度乘法
二刷：
- 在草稿纸上演算一遍 运算过程，便知道 代码逻辑
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
String ans = "0";
int m = num1.length(), n = num2.length();
for (int i = n - 1; i >= 0; i--) {
StringBuffer curr = new StringBuffer();
int add = 0;
for (int j = n - 1; j > i; j--) {
curr.append(0);
}
int y = num2.charAt(i) - '0';
for (int j = m - 1; j >= 0; j--) {
int x = num1.charAt(j) - '0';
int product = x * y + add;
curr.append(product % 10);
add = product / 10;
}
if (add != 0) {
curr.append(add % 10);
}
ans = addStrings(ans, curr.reverse().toString());
}
return ans;
}
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
ans.reverse();
return ans.toString();
}
}
4. 高精度除法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
vector<int> A;
int B;
cin >> a >> B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = div(A, B, r);
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl << r << endl;
return 0;
}
五、前缀和S与差分a
1. 区域和检索 - 数组不可变
class NumArray {
int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
sums = new int[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
2. 子矩阵的和
class NumMatrix {
int[][] sums;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
if (m > 0) {
int n = matrix[0].length;
sums = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
}
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
}
}
3. 差分
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] nums = new int[n];
for (int[] booking : bookings) {
nums[booking[0] - 1] += booking[2];
if (booking[1] < n) {
nums[booking[1]] -= booking[2];
}
}
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
4. 差分矩阵
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int q = scanner.nextInt();
int[][] splits = new int[n+2][m+2];
int[][] sum = new int[n+2][m+2];
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sum[i][j] = scanner.nextInt();
splits[i][j] = sum[i][j] - sum[i-1][j] - sum[i][j-1] + sum[i-1][j-1];
}
}
for (int i = 0; i < q; i++) {
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
int c = scanner.nextInt();
splits[x1][y1] += c;
splits[x1][y2+1] -= c;
splits[x2+1][y1] -= c;
splits[x2+1][y2+1] += c;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = splits[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
System.out.print(sum[i][j] + " ");
}
System.out.println();
}
}
}
六、双指针
1. 无重复字符的最长子串
class Solution {
public static int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int ans = 0;
for (int l = 0,r = 0; r < s.length(); r++) {
char ch = s.charAt(r);
while (set.contains(ch) == true) {
set.remove(s.charAt(l));
l++;
}
set.add(ch);
ans = Math.max(ans,r-l+1);
}
return ans;
}
}
2. 数组元素的目标和
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int x = scanner.nextInt();
int[] A = new int[n+1];
int[] B = new int[m+1];
for (int i = 0; i < n; i++) A[i] = scanner.nextInt();
for (int i = 0; i < m; i++) B[i] = scanner.nextInt();
for (int i = 0,j = m-1; i < n && j >= 0;) {
if (A[i] + B[j] < x) {
i++;
} else if (A[i] + B[j] == x) {
System.out.print(i + " " + j);
break;
} else {
j--;
}
}
}
}
3. 判断子序列(8分钟)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[n+1];
int[] b = new int[m+1];
for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
for (int j = 0; j < m; j++) b[j] = scanner.nextInt();
boolean flag = false;
for (int i = 0,j = 0; j < m; j++) {
if (a[i] == b[j]) {
i++;
if (i == n) {
System.out.print("Yes");
flag = true;
break;
}
}
}
if (flag == false) {
System.out.print("No");
}
}
}
七、二进制
1. 位运算算法（n&n-1 n&-n）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
System.out.print(numberOfOneInBinary(nums[i]) + " ");
}
}
public static int numberOfOneInBinary(int num) {
int cnt = 0;
while (num != 0) {
num -= (num & -num);
cnt++;
}
return cnt;
}
}
八、离散化
1. 区间和
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
pair[] add = new pair[n+2];
pair[] query = new pair[m];
List<Integer> arrayMap = new ArrayList<>(n+m*2);
int[] sum = new int[n+m*2];
for (int i = 0; i < n; i++) {
add[i] = new pair();
add[i].l = scanner.nextInt();
add[i].r = scanner.nextInt();
arrayMap.add(add[i].l);
}
for (int i = 0; i < m; i++) {
query[i] = new pair();
query[i].l = scanner.nextInt();
query[i].r = scanner.nextInt();
arrayMap.add(query[i].l);
arrayMap.add(query[i].r);
}
arrayMap = new ArrayList<>(new HashSet<>(arrayMap));
Collections.sort(arrayMap);
for (int i = 0; i < n; i++) {
sum[arrayMapIndexOf(add[i].l,arrayMap)] += add[i].r;
}
for (int i = 0; i < arrayMap.size(); i++) {
if(i != 0) {
sum[i] += sum[i-1];
}
}
for (int i = 0; i < query.length; i++) {
int l = arrayMapIndexOf(query[i].l,arrayMap);
int r = arrayMapIndexOf(query[i].r,arrayMap);
if (l == 0) {
System.out.print(sum[r] + "\n");
} else {
System.out.print(sum[r]-sum[l-1] + "\n");
}
}
}
static class pair {
int l;
int r;
}
private static int arrayMapIndexOf(int k,List<Integer> arrayMap) {
int l = 0,r = arrayMap.size()-1;
while (l < r) {
int mid = (l+r+1) >> 1;
if (arrayMap.get(mid) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return r;
}
}
九、区间合并
1. 区间合并
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
pair[] range = new pair[n];
for (int i = 0; i < n; i++) {
range[i] = new pair();
range[i].l = scanner.nextInt();
range[i].r = scanner.nextInt();
}
Arrays.sort(range,new Comparator<pair>(){
@Override
public int compare(pair o1,pair o2) {
if (o1.l == o2.l) {
return o1.r - o2.r;
} else {
return o1.l - o2.l;
}
}
});
int st = (int)-2e9-1;
int ed = (int)-2e9-1;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (ed < range[i].l) {
st = range[i].l;
ed = range[i].r;
cnt++;
} else {
ed = Math.max(ed,range[i].r);
}
}
System.out.print(cnt);
}
static class pair {
int l;
int r;
}
}