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
|
输出样例:
题解: