1、快速排序
给定你一个长度为 nn 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 nn。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 nn 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
输出样例：
题解：
快速排序的本质思想是分治。
时间复杂度：O (n*log n)
步骤：
1、将问题分解成一个个子问题：先把数组按照中点分为两组，对两个数组内的数字按照下标从小到大与中点分别进行比较，如果左边的数组数值比中点小则下标加1更新，右边的比中点大则下标减1，不满足条件则暂停下标更新。
2、当左边或者右边的数组值都暂停更新时，将左右数组两个数互换，这一步的目标是将比中点大的换到数组右边，小的放到左边。
3、每个子问题通过递归完成，由于都是在原数组中进行操作，所以最后数组就是排序好的数组。
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
| var buf = ""
let arr = []
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split(" ").filter(s => s !== "").map(x => parseInt(x))
}
process.stdin.on("end",function(){
buf.split("\n").forEach((line,index) => {
if(index === 1){
let arr = getInputArgs(line)
quickSort(rr,0,arr.length - 1)
console.log(arr.join(" "))
}
})
})
function quickSort(arr,l,r){
if(l >= r) return
let i = l - 1
let j = r + 1
let t = arr[r + l >> 1]
while(i < j){
do {i++} while(arr[i] < t)
do {j--} while(arr[j] > t)
if(i < j){
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
quickSort(arr,l,j)
quickSort(arr,j + 1,r)
}
|
2、第k个数
给定一个长度为 nn 的整数数列，以及一个整数 kk，请用快速选择算法求出数列从小到大排序后的第 kk 个数。
输入格式
第一行包含两个整数 nn 和 kk。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 kk 小数。
数据范围
1≤n≤1000001≤n≤100000,
1≤k≤n1≤k≤n
输入样例：
输出样例：
题解：
使用快排的代码进行排序，由于是输出从小到大第k个数，基于这个条件约束可以对代码进行调整，每一个只快速排序有k的一边即可。
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
| var buf = ""
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
let getInputArgs = line => {
return line.split(" ").filter(s => s !== "").map(x => parseInt(x))
}
var arr = []
let k = 0
function quickSort(l,r,k){
buf.split("\n").forEach((line,index) => {
if(index === 0){
k = getInputArgs(line)[1]
}
else if(index === 1){
arr = getInputArgs(line)
console.log(quickSort(0,arr.length - 1,k))
})
})
function quickSort(l,r,k){
if(l >= r) return arr[r]
let i = l - 1
let j = r + 1
let t = arr[r + l >> 1]
while(i < j){
do {i++} while(arr[i] < t)
do {j--} while(arr[j] > t)
if(i < j){
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
if(j >= k - 1){
return quickSort(l.j,k)
}
else return quickSort(j + 1,r,k)
}
|
3、归并排序
给定你一个长度为 nn 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 nn。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 nn 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
输出样例：
题解：
归并排序的主要思想也是分治。
时间复杂度：O（nlogn）
步骤：
1、与快排最后才递归不同，归并一上来先用中点将数组分为左右两个数组，然后用递归将问题分解为一个个子问题，
2、处理子问题：左右两个数组分别从左往右比较，如果左边数组的值比右边的小则将左边的数推进（push）新建的数组中，并更新左边数组下标（加1），反之则将右边的数存进新数组。
3、当左边的数组或者右边的数组没有数可以进行比较时，将剩下数组的数全部存进新数组中（由于 先递归，所以数组会被一直分割到最小长度，然后从最小长度数组进行比较，所以第三步剩下数组后面的数都是具有单调性的）
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
| var buf = ""
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
let getInputArgs = line => {
return line.split(" ").filter(s => s !== "").map(x => parseInt(x))
}
process.stdin.on("end",function(){
buf.split("\n").forEach(function(line,lineIdx){
if(lineIdx === 1){
let arr = getInputArgs(line)
mergeSort(arr,0,arr.length-1)
console.log(arr.join(" "))
}
})
})
function mergeSort(arr,l,r){
if(l >= r) return
let mid = r + l >> 1
mergeSort(arr,l,mid)
meergeSort(arr,mid + 1,r)
let t = 0
let i = l
let j = mid + 1
let temp = new Array(r - l + 1)
while(i <= mid && j <= r){
if(arr[i] <= arr[j]) temp[t++] = arr[i++]
else temp[t++] = arr[j++]
}
while(i <= mid) temp[t++] = arr[i++]
while(j <= r) temp[t++] = arr[j++]
for(let i = l,t = 0;i <= r;i++,t++){
arr[i] = temp[t]
}
}
|
4、逆序对的数量
给定一个长度为 nn 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 ii 个和第 jj 个元素，如果满足 i<ji<j 且 a[i]>a[j]a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 nn，表示数列的长度。
第二行包含 nn 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤1000001≤n≤100000，
数列中的元素的取值范围 [1,109][1,109]。
输入样例：
输出样例：
题解：
由于归并排序先递归，所以是先将数组分割为很多最小长度数组，然后从最小长度数组（即数组要么只有一个数，要么只有两个数）开始排序，所以当每一次回溯的时候，序列两边其实是排好序的，具有单调性，所以我们可以从这一点思考。将序列从中间分开，那么逆序对只能是这种情况：两个元素一个在左，一个在右。
比如：4 5 6 | 1 2 3 ，我们将4与1进行比较，发现这两个数构成逆序对，由于左右两边数组都具有单调性，那么我们就知道5和6也是与1构成逆序对的，这个时候就可以直接跳过1与5、6 比较的情形。
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
| let n = 0
function mergeSort(arr,l,r){
if(l >= r) return
let mid = Math.floor((l+r)/2)
mergeSort(arr,l,mid)
mergeSort(arr,mid+1,r)
let i = l
let j = mid + 1
let temp = new Array(r-l+1)
let t = 0
while(i <= mid && j <= r ){
if(arr[i] <= arr[j]) temp[t++] = arr[i++]
else{
n += (mid-i+1)
temp[t++] = arr[j++]
}
}
while(i <= mid) temp[t++] = arr[i++]
while(j <= r) temp[t++] = arr[j++]
for(let i = l,t = 0;t < temp.length;i++,t++){
arr[i] = temp[t]
}
}
var buf = '';
process.stdin.on('readable', function () {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => {
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
}
process.stdin.on('end', function () {
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 1) {
let arr = getInputArgs(line);
mergeSort(arr, 0, arr.length-1);
console.log(n);
}
});
});
|
5、数的范围
给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 nn 和 qq，表示数组长度和询问个数。
第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。
输出格式
共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
输出样例：
题解：
由于输入的样例是升序的，并且是要查找某一个数的范围，那么我们就应该考虑用二分法。
步骤：
1、根据要查找的目标值对数组样例进行二分查找，即用数组中间的值与目标值进行比较，如果比目标值小说明目标值位于数组中点右边，反之说明在数组中点左边。
2、由于是查找目标值在数组中的范围，所以我们可以用两种二分的方法，一种是将最终结果逐渐逼近数组较左边的目标值下标，另一种是逼近数组较右边目标值下标。（如下代码）
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
| var buf = ""
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split(" ").filter(s => s !== "").map(x => parseInt(x))
}
process.stdin.on("end",function(){
let k = 0
let arr = []
buf.split("\n").forEach((line,index) => {
if(index === 0){
k = getInputArgs(line)[1]
}
else if(index === 1){
arr = getInputArgs(line)
}
else if(k > 0){
target = getInputArgs(line)[0]
console.log(fn(arr,target)[0],fn(arr,target)[1])
k--
}
})
})
function fn(arr,target){
let l = 0
let r = arr.length - 1
let left = null
let right = null
while(l < r){
const mid = r + l >>> 1
if(arr[mid] >= target) r = mid
else l = mid + 1
}
left = arr[l] === target ? l : -1
l = 0
r = arr.length - 1
while(l < r){
const mid = r + l + 1 >>> 1
if(arr[mid] <= target) l = mid
else r = mid - 1
}
right = arr[l] === target ? l : -1
return [left,right]
}
|
6、高精度加法
给定两个正整数（不含前导 00），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤1000001≤整数长度≤100000
输入样例：
输出样例：
题解：
将两个数的每一位数依次存放进两个数组中，然后我们用这两个数组模拟两个数的竖式相加，就是小学学的列竖式。
由于相加是从个位数开始的，所以我们可以从个位数开始将数存进数组，这是为了方便计算。
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
| var buf = ""
let a,b,c = []
let d = ""
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split("").map(Number).reverse()
}
process.stdin.on("end",function(){
buf.split("\n").forEach((line,index) => {
if(index === 0){
a = getInputArgs(line)
}
else if(index === 1){
b = getInputArgs(line)
add(a,b)
for(let i = c.length - 1;i >= 0;i--){
d += c[i] + ""
}
console.log(d)
}
})
})
function add(a,b){
let t = 0
for(let i = 0;i < a.length || i < b.length;i++){
if(i < a.length) t += a[i]
if(i < b.length) t += b[i]
c.push(t % 10)
t = Math.floor(t / 10)
}
if(t) c.push(t)
}
|
7、高精度减法
给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤1051≤整数长度≤105
输入样例：
输出样例：
题解：
同高精度减法~
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
| var buf = ""
let a,b = []
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split("").map(x => parseInt(x)).reverse()
}
process.stdin.on("end",function(){
let m = 0
buf.split("\n").forEach((line,index) => {
if(m === 0){
a = getInputArgs(line)
m++
}
else{
b = getInputArgs(line)
if(cmp(a,b)){
console.log(fn(a,b).reverse().join(""))
}
else{
console.log("-" + fn(b,a).reverse().join(""))
}
m --
}
})
})
function fn(a,b){
let c = []
let t = 0
for(let i = 0;i < a.length || i < b.length;i++){
if(i < a.length) t += a[i]
if(i < b.length) t -= b[i]
c.push((t + 10) % 10)
if( t < 0) t =-1
else t = 0
}
while(c.length > 1 && c[c.length - 1] === 0) c.pop()
return c
}
function cmp(a,b){
if(a.length !== b.length) return a.length > b.length
else if(a.length === b.length){
for(let i = a.length - 1;i >= 0;i--){
if(a[i] !== b[i]) return a[i] > b[i]
}
}
return true
}
|
8、高精度乘法
给定两个非负整数（不含前导 00） AA 和 BB，请你计算 A×BA×B 的值。
输入格式
共两行，第一行包含整数 AA，第二行包含整数 BB。
输出格式
共一行，包含 A×BA×B 的值。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
0≤B≤100000≤B≤10000
输入样例：
输出样例：
题解：
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
| var buf = ""
let a,b = []
process.stdin.on("readable",function(){
let chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split("").map(x => parseInt(x)).reverse()
}
process.stdin.on("end",function(){
let m = 0
buf.split("\n").forEach((line) => {
if(m ===0){
a = getInputArgs(line)
m++
}
else{
b = line.trim()
console.log(fn(a,b).reverse().join(""))
m--
}
})
})
function fn(a,b){
let c = []
let t = 0
for(let i = 0;i < a.length;i++){
if(i < a.length) t += a[i] * b
c.push(t % 10)
t = Math.floor(t / 10)
}
if(t) c.push(t)
while(c.length > 1 && c[c.length - 1] === 0) c.pop()
return c
}
|
9、高精度除法
给定两个非负整数（不含前导 00） A，BA，B，请你计算 A/BA/B 的商和余数。
输入格式
共两行，第一行包含整数 AA，第二行包含整数 BB。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
1≤B≤100001≤B≤10000,
BB 一定不为 00
输入样例：
输出样例：
题解：
由于除法与上面三个题的计算不一样，除法需要从最高位开始除，如果我们依然从各位数开始存数的话，那么就应该从数组最后一位从后往前计算。
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
| var buf = ""
let a,b = []
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split("").map(x => parseInt(x)).reverse()
}
process.stdin.on("end",function(){
let m = 0
buf.split("\n").forEach(line => {
if(m === 0){
a = getInputArgs(line)
m++
}
else{
b = line
fn(a,b)
m--
}
})
})
function fn(a,b){
let c = []
let t = 0
for(let i = a.length - 1;i >= 0;i--){
t = t * 10 + a[i]
c.push(Math.floor(t / b))
t = t % b
}
c = c.reverse()
while(c.length > 1 && c[c.length - 1] === 0) c.pop()
console.log(c.reverse().join(""))
console.log(t)
}
|
10、前缀和
输入一个长度为 nn 的整数序列。
接下来再输入 mm 个询问，每个询问输入一对 l,rl,r。
对于每个询问，输出原序列中从第 ll 个数到第 rr 个数的和。
输入格式
第一行包含两个整数 nn 和 mm。
第二行包含 nn 个整数，表示整数数列。
接下来 mm 行，每行包含两个整数 ll 和 rr，表示一个询问的区间范围。
输出格式
共 mm 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000
输入样例：
1
2
3
4
5
| 5 3
2 1 3 6 4
1 2
1 3
2 4
|
输出样例：
题解：
如果使用暴力算法，那么我们每一次查询都需要遍历数组然后计算对应范围的前缀和，然后相减，这太费劲了。如果我们一次性把数组所有下标的前缀和直接存放进一个数组，以后每一次查询都可以根据范围，直接从前缀和数组中查询出两个下标的前缀和然后相减即可。
*注意：由于数据范围是从1开始的，所以前缀和数组也需要从下标1开始存储，下标0存储0即可。
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
|
function fn(arr,l,r){
return arr[r] - arr[l - 1]
}
var buf = ""
let arr = []
process.stdin.on("readable",function(){
var chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
function getInputArgs(line){
return line.split(" ").filter(s => s !== "").map(x => parseInt(x))
}
process.stdin.on("end",function(){
let m,n = 0
buf.split("\n").forEach((line,index) => {
if(index === 0){
m = getInputArgs(line)[0]
n = getInputArgs(line)[1]
}
else if(index === 1){
arr = getInputArgs(line)
for(let i = 1;i < m;i++){
arr[i] += arr[i - 1]
}
arr.unshift(0)
}
else{
if(n > 0){
let l = getInputArgs(line)[0]
let r = getInputArgs(line)[1]
console.log(fn(arr,l,r))
}
n--
}
})
})
|
11、子矩阵的和
输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个询问，每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，qn，m，q。
接下来 nn 行，每行包含 mm 个整数，表示整数矩阵。
接下来 qq 行，每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一组询问。
输出格式
共 qq 行，每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例：
1
2
3
4
5
6
7
| 3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
|
输出样例：
题解：
