排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

查找

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l ;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

LeetCode.35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target)
return mid;
if (nums[mid] >= target)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
}

浮点数二分法解题模板

1
2
3
4
5
6
double l=a,r=b;
while(r-l>c){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}

不考虑mid-1mid+1的边界问题模板

1
2
3
4
5
6
7
8
9
int L=-1,R=n;
while(L+1!=R)
{
int mid=L+R>>1;
if(check()) L=mid;
else R=mid;
//最后根据你所分左右两边区间的结果
//选取L或者R作为结果
}

高精度

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);

vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}

if (t) C.push_back(t);
return C;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

高精度乘低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;

int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();

return C;
}

高精度除低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// A / b = C ... r, A >= 0, b > 0
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;
}

java版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package basic.highPrecision;

import java.io.*;
import java.math.BigInteger;


public class highPrecision {

public static void main(String[] args) {

}

/**
* 791.高精度加
*/
public static void add() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
System.out.println(a.add(b));
br.close();
}

/**
* 792.高精度减
*/
public static void subtract() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
System.out.println(a.subtract(b));
br.close();
}

/**
* 793.高精度乘
*/
public static void multiply() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
System.out.println(a.multiply(b));
br.close();
}

/**
* 795.高精度除
*/
public static void divideAndReminder() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
BigInteger[] c = a.divideAndRemainder(b);
System.out.println(c[0]); //a/b
System.out.println(c[1]); //a%b
br.close();
}

/**
* 高精度取mod
*/
public static void mod() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
BigInteger c = a.mod(b);
System.out.println(c);
br.close();
}
}