实践是检验真理的唯一标准！！！
-------------认识与实践
目录
由以下的测试可以看出，使用BufferedReader和BufferedInputStream速度接近，可能是因为数据量比较小，但是它们的速度均比Scanner要快很多。
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class FindFastest {
public static void main(String[] args) {
FindFastest ff = new FindFastest();
// 测试数据
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
ff.testScanner();
// 测试结果如下：
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用Scanner读取耗时：252微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用Scanner读取耗时：230微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用Scanner读取耗时：271微秒
// ff.testScannerWithBufferedInputStream();
// 测试结果如下：
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用带BufferedInputStream的Scanner读取耗时：75微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用带BufferedInputStream的Scanner读取耗时：7微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用带BufferedInputStream的Scanner读取耗时：5微秒
// ff.testBufferedReader();
// 测试结果如下：
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用BufferedReader读取耗时：95微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用BufferedReader读取耗时：3微秒
// 苹果公司计划于9月9日召开新闻发布会，届时苹果将发布新一代iPhone。而苹果iPhone发布会一般于9月初至9月中旬召开，这次传闻的召开时间与近几年基本吻合。
// 使用BufferedReader读取耗时：3微秒
}
public void testScanner() {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
long start = System.nanoTime();
in.next();
// 返回用第二个参数指定基数表示的第一个参数的字符串表示形式。
// System.out.println(Integer.toString(in.nextInt(), 10));
long end = System.nanoTime();
System.out.println("使用Scanner读取耗时：" + (end - start) / 1000 + "微秒");
}
}
public void testScannerWithBufferedInputStream() {
Scanner in = new Scanner(new BufferedInputStream(System.in));
while (in.hasNext()) {
in.next();
long start = System.nanoTime();
System.out.println("使用带BufferedInputStream的Scanner读取耗时：" + (System.nanoTime() - start) / 1000 + "微秒");
}
}
public void testBufferedReader() {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
try {
String str = null;
while ((str = buf.readLine()) != null) {
if (!"".equals(str)) {
long start = System.nanoTime();
System.out.println("使用BufferedReader读取耗时：" + (System.nanoTime() - start) / 1000 + "微秒");
}
}
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
/**
*
* @param num
* @param base
* @return 该函数是将十进制数字转化成指定的任意进制的数
*/
public static String baseString(int num, int base) {
String str = "", digit = "0123456789abcdef";
if (num == 0) {
return "";
} else {
str = baseString(num / base, base);
return str + digit.charAt(num % base);
}
}
}
例3：读入字符串【杭电2005 第几天？】
给定一个日期，输出这个日期是该年的第几天。 Input 输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成
1985/1/20
2006/3/12
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] dd = {0,31,28,31,30,31,30,31,31,30,31,30,31};
while(sc.hasNext()){
int days = 0;
String str = sc.nextLine();
String[] date = str.split("/");
int y = Integer.parseInt(date[0]);
int m = Integer.parseInt(date[1]);
int d = Integer.parseInt(date[2]);
if((y%400 == 0 || (y%4 == 0 && y%100 !=0)) && m>2) days ++;
days += d;
for(int i=0;i<m;i++){
days += dd[i];
}
System.out.println(days);
}
}
} 快速排序
给定你一个长度为 nn 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 nn。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 nn 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5 3 1 2 4 5输出样例：
1 2 3 4 5
import java.util.Scanner;
import java.io.BufferedInputStream;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
int n= sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]= sc.nextInt();
}
quickSort(arr,0,n-1);
for(int i=0;i<n;i++){
System.out.print(arr[i]+" ");
}
}
private static void quickSort(int[] arr,int left,int right){
if(left>=right)return;
int x=arr[(left+right)/2],i=left-1,j=right+1;
while(i<j){
do{
i++;
}while(arr[i]<x);
do{
j--;
}while(arr[j]>x);
if(i<j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
quickSort(arr,left,j);
quickSort(arr,j+1,right);
}
}给定一个长度为 nn 的整数数列，以及一个整数 kk，请用快速选择算法求出数列从小到大排序后的第 kk 个数。
输入格式
第一行包含两个整数 nn 和 kk。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 kk 小数。
数据范围
1≤n≤1000001≤n≤100000,
1≤k≤n1≤k≤n输入样例：
5 3 2 4 1 5 3输出样例：
3
import java.util.Scanner;
public class Main{
static int N=100010;
static int[] A=new int[N];
static int n,k;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n= sc.nextInt();
k= sc.nextInt();
for(int i=0;i<n;i++){
A[i]= sc.nextInt();
}
System.out.println(quickSort(0,n-1,k-1));
}
public static int quickSort(int l,int r,int k){
if(l>=r)return A[k];
int x=A[l],i=l-1,j=r+1;
while(i<j){
do i++;while(A[i]<x);
do j--;while(A[j]>x);
if(i<j){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
if(k<=j)return quickSort(l,j,k);
else return quickSort(j+1,r,k);
}
}归并排序
给定你一个长度为 nn 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 nn。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 nn 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5 3 1 2 4 5输出样例：
1 2 3 4 5
import java.util.*;
public class Main{
private static int N = 100010;
private static int[] a= new int[N];
private static int[] t= new int[N];
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int i = 0;i < n;i++){
a[i] = scanner.nextInt();
}
int l = 0,r = n-1;
mergeSort(a,l,r);
for(int i = 0;i < n;i++){
System.out.print(a[i] + " ");
}
}
public static void mergeSort(int[] a,int l,int r){
if(l >= r){
return;
}
int m = l + r >> 1;
mergeSort(a,l,m);
mergeSort(a,m+1,r);
//i和j指针谁小动谁
int i = l,j = m + 1,k = 0;
while(i <= m && j <= r){
t[k++] = a[i] < a[j] ? a[i++] : a[j++];
}
while(i <= m){
t[k++] = a[i++];
}
while(j <= r){
t[k++] = a[j++];
}
//辅助数组重新填充回原数组l,r区间
for(i = l,k = 0;i <= r;i++,k++){
a[i] = t[k];
}
}
}
给定一个长度为 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]。输入样例：
6 2 3 4 5 6 1输出样例：
5
import java.io.*;
public class Main {
static int N = 100010; // 数据规模为 10w
static int[] arr = new int[N];
public static void main(String[] args) throws IOException {
// 输入数据进行初始化
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
String[] arrStr = reader.readLine().split(" ");
for (int i = 0; i < n; i++)
arr[i] = Integer.parseInt(arrStr[i]);
// 打印结果
System.out.println(mergeSort(0, n - 1));
// 关闭输入流
reader.close();
}
// 语义: 对 [l, r]进行排序, 并计算 [l,r]中逆序对的数量
private static long mergeSort(int l, int r) {
// 递归结束, 只有一个元素, 逆序对为 0
if (l >= r) return 0;
int mid = l + r >> 1;
long res = 0;
// 情况一和情况二, 并对左右数组进行排序
res += mergeSort(l, mid) + mergeSort(mid + 1, r);
// 归并排序
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else {
tmp[k++] = arr[j++];
// 情况三
res += mid - i + 1;
}
}
// 扫尾
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
// tmp -> arr
for (i = l, j = 0; i <= r; i++, j++) {
arr[i] = tmp[j];
}
return res;
}
}
二分
给定一个按照升序排列的长度为 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输入样例：
6 3 1 2 2 3 3 4 3 4 5输出样例：
3 4 5 5 -1 -1
难度：简单 时/空限制：1s / 64MB 总通过数：95466 总尝试数：156147 来源：模板题,AcWing 算法标签
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 获取输入值
int n = in.nextInt(); // 数组大小
int count = in.nextInt(); // 查询个数
// 获取完整数组
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
// 查询 count轮
while (count-- != 0) {
int target = in.nextInt(); // 本轮查询的目标值
// 初始化 l和 r, 查找左边界
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= target) // 如果 mid满足, 需要向左寻找
r = mid;
else
l = mid + 1;
}
// 跳出循环时, l == r, 如果数组中不存在 target
if (arr[l] != target) {
System.out.println("-1 -1");
} else {
System.out.print(l + " "); // 注意输出值为下标
// 初始化 l和 r, 查找右边界
l = 0;
r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1; // 使用第二个模板
if (arr[mid] <= target) // 如果 mid满足, 需要向右寻找
l = mid;
else
r = mid - 1;
}
System.out.println(l);
}
}
}
}
给定一个浮点数 nn，求它的三次方根。
输入格式
共一行，包含一个浮点数 nn。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 66 位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
1000.00输出样例：
10.000000
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double n = in.nextDouble();
double l = 0, r = Math.abs(n); // 考虑 n为负数的情况
while (r - l > 1e-8) { // // 精度比所求精度高 2位
double mid = (l + r) / 2;
if (mid * mid * mid >= Math.abs(n)) // 不需要考虑边界问题
r = mid;
else
l = mid;
}
if (n >= 0)
System.out.println(String.format("%.6f", l)); // 保留 6位小数
else
System.out.println("-" + String.format("%.6f", l));
}
}
高精度
给定两个正整数（不含前导 00），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤1000001≤整数长度≤100000
输入样例：
12 23输出样例：
35
import java.text.DecimalFormat;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
public class Main{
static final int c=100009;
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
String a=sc.next();
String b=sc.next();
List<Integer> res=add(a,b);
for(int i=res.size()-1;i>=0;i--) System.out.print(res.get(i));
}
public static List<Integer> add(String a,String b){
int i=a.length()-1;
int j=b.length()-1;
List<Integer> temp=new ArrayList<>();
int t=0;
for(;i>=0||j>=0;i--,j--){
t+=(i>=0?a.charAt(i)-'0':0)+(j>=0?b.charAt(j)-'0':0);
temp.add(t%10);
t=t/10;
}
if(t>0) temp.add(t);
return temp;
}
}
给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤1051≤整数长度≤105
输入样例：
32 11输出样例：
21
import java.util.*;
public class Main{
static int N=100010;
static int[] c=new int[N];//0下标表示个位，这样好进位
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String a=sc.next();
String b=sc.next();
System.out.println(minus(a,b));
}
static String minus(String a,String b){
if(a.length() < b.length() || a.length() == b.length() && a.compareTo(b) < 0){
return "-"+minus(b,a);
}
int k=0,n=a.length(),m=b.length(),t=0;
for(int i=n-1,j=m-1;i>=0;i--){
t=a.charAt(i)-'0'-t;
if(j>=0){
t-=b.charAt(j--)-'0';
}
c[k++]=(t+10)%10;
if(t<0){
t=1;
}else{
t=0;
}
}
while(k>0 && c[k]==0){//去掉前导0
k--;
}
StringBuilder sb=new StringBuilder();
for(int i=k;i>=0;i--){
sb.append((char)(c[i]+'0'));
}
return sb.toString();
}
}
给定两个非负整数（不含前导 00） AA 和 BB，请你计算 A×BA×B 的值。
输入格式
共两行，第一行包含整数 AA，第二行包含整数 BB。
输出格式
共一行，包含 A×BA×B 的值。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
0≤B≤100000≤B≤10000输入样例：
2 3输出样例：
6
import java.util.Scanner;
public class Main{
public static void main(String[] args){
String a;
int b;
Scanner sc = new Scanner(System.in);
a = sc.next();
b = sc.nextInt();
char[] A = new char[a.length()];
for(int i = a.length() - 1; i >= 0; i --) A[a.length() - 1 - i] = a.charAt(i);
String s = mul(A, b);
System.out.println(s);
}
public static String mul(char[] A, int b){
int t = 0;
StringBuffer sb = new StringBuffer();
for(int i = 0; i < A.length || t != 0; i++){
if(i < A.length) t += (A[i] - '0') * b;
sb.append(t % 10);
t /= 10;
}
String s = sb.reverse().toString();
int i = 0;
for(; i < A.length - 1; i ++) {
if(s.charAt(i) != '0') break;
}
return s.substring(i, s.length());
}
}
给定两个非负整数（不含前导 00） A，BA，B，请你计算 A/BA/B 的商和余数。
输入格式
共两行，第一行包含整数 AA，第二行包含整数 BB。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
1≤B≤100001≤B≤10000,
BB 一定不为 00输入样例：
7 2输出样例：
3 1
import java.util.Scanner;
public class Main{
static int r;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String a = sc.next();
int b = sc.nextInt();
char[] A = new char[a.length()];
for(int i = a.length() - 1; i >= 0; i --) A[a.length() - 1 - i] = a.charAt(i);
String res = div(A, b);
System.out.println(res);
System.out.println(r);
}
public static String div(char[] A, int b){
StringBuffer sb = new StringBuffer();
r = 0;
for(int i = A.length - 1; i >= 0; i --){
r = r * 10 + A[i] - '0';
sb.append(r / b);
r %= b;
}
String s = sb.toString();
int i = 0;
for(; i < s.length()- 1; i++){
if(s.charAt(i) != '0') break;
}
return s.substring(i, s.length());
}
}
本文含有隐藏内容，请 开通VIP 后查看