OJ基本技巧记录

2017-09-12 本文已影响220人青年马土豆

OJ基本技巧记录

OJ平台代码基本格式

import java.util.Scanner;

/**
 * Created by ml on 2017/9/11.
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String n = in.nextLine();//读一个字符串
            int m = in.nextInt();//读一个整数
            long l = in.nextLong();//读一个长整数
            double t = in.nextDouble();//读一个浮点数
            System.out.println(cal(n));//具体处理逻辑
        }
        in.close();
    }
}

OJ输入输出技巧

输入数据有多行，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一个由字母和数字组成的字符串。

Scanner in = new Scanner(System.in);
int n = in.nextInt();
//可以创建数组
int[] n = new int[n];
String[] str = new String[n];
for(int i=0;i<n;i++) {
    n[i] = in.nextInt();
    String str = in.nextLine();
}

读入字符串的分割

例如：Input输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成

Scanner in = new Scanner(System.in);
while (in.hasNext()) {
    String str =in.nextLine();
    String[] date = str.split("/");
    int y = Integer.parseInt(date[0]);
    int m = Integer.parseInt(date[1]);
    int d = Integer.parseInt(date[2]);
}
in.close();

不同类型相互转换

int转为String：
- String s = Integer.toString(i);
- String s = String.valueOf(i);
- String s = "" + i;
- 三种效率排序：Integer.toString(int i) > String.valueOf(int i) > i+"";
String转为int
- int i = Integer.parseInt(s);
- int i = Integer.valueOf(s).intValue()
- 这两种都会抛出异常（NumberFormatException）

Java输出

System.out.print(); //输出不换行
System.out.println(); //输出换行
System.out.format();
- double d = 345.678;
- System.out.printf("%9.2f", d);// "9.2"中的9表示输出的长度，2表示小数点后的位数。
- System.out.printf("%+-9.3f", d);// "+-"表示输出的数带正负号且左对齐。
System.out.printf(); //与上相同
DecimalFormat。DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度。0 表示如果位数不足则以 0 填充，# 表示只要有可能就把数字拉上这个位置。
- NumberFormat formatter = new DecimalFormat( "0.00");
- String s = formatter.format(-.567); // -0.57
- System.out.println(s);

矩阵如何按行输出

//输出int[n][m]，判断是否是每一行的最后一个，输出换行。
for(int i = 0; i < n ; i++) {
    for(int j = 0; j < m; j++>) {
        if(j == m - 1){
            system.out.println(i);
        } else {
            system.out.print(i + " ");
    }
}

不定长度类型

对于整形等数据在处理中不能确定长度的情况，使用ArrayList<Integer>等形式来存储数据。
对于char或者String类型可以使用StingBuffer等形式来存储。

集合遍历

数组以及List：遍历

List<String> list = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

Map类

Map<String, String> map = new HashMap<String, String>();

//1
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, String> entry = it.next();
    System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//2
for (Map.Entry<String, String> entry : map.entrySet()) {
    entry.getKey();
}
//3
for (String key : map.keySet()) {
    String value = (String) map.get(key);
}

传统的for循环遍历，基于计数器。遍历整个集合的平均时间复杂度为O(n^2)。
迭代器遍历，Iterator。
foreach循环遍历。实现原理同Iterator。

排序

如果要对数组排序，请使用java.util.Arrays.sort()方法。
如果对list排序，请使用java.util.Collections.sort()方法。
自定义排序：对于要排序的类实现Comparable接口。

class S1 implements Comparable{  
    int x;  
    int y;  
    S1(int x, int y){  
        this.x = x;  
        this.y = y;  
    }  
    //实现排序方法。先比较x，如果相同比较y  
    @Override  
    public int compareTo(Object o) {  
        S1 obj = (S1) o;  
        if(x != obj.x)  
        {  
            return x - obj.x;  
        }  
        return y - obj.y;  
    }  
    //重写toStirng方法，改变println时的显示效果  
    public String toString(){  
        return "("+x+", "+y+")";  
    }

OJ常用函数

不同类型长度：
- 数组：int len = n.length;//int[] n = new int[10];
- 字符串：int len = s.length();//String s = "hello";
- List：int len = list.size();//List<String> list = new ArrayList<String>();

String类：

字符串某一位置字符,charAt。

String str = new String("asdfzxc");
char ch = str.charAt(4);//ch = z

转化为char数组。toCharArray方法。

String str1 = new String("abc");
char[] c = str1.toCharArray();

判断相等。equals方法。

String str1 = new String("abc");
String str2 = new String("ABC");
boolean c = str1.equals(str2);//c=false

提取子串。substring方法：一个参数：该方法从beginIndex位置起，出剩余的字符作为一个新的字符串返回。两个参数：左闭右开原则[beginIndex,endIndex)，即[beginIndex,endIndex - 1]

String str1 = new String("asdfzxc");
String str2 = str1.substring(2);//str2 = "dfzxc"
String str3 = str1.substring(2,5);//str3 = "dfz"

字符串比较。compareTo方法是对字符串内容按字典顺序进行大小比较，通过返回的整数值指明当前字符串与参数字符串的大小关系。若当前对象比参数大则返回正整数，反之返回负整数，相等返回0。

String str1 = new String("abc");
String str2 = new String("ABC");
int a = str1.compareTo(str2);//a>0
int b = str1.compareTo(str2);//b=0

是否包含字符。contains方法判断参数s是否被包含在字符串中，并返回一个布尔类型的值.

String str = "student";
str.contains("stu");//true
str.contains("ok");//false

字符串字符替换。replace、replaceFirst、replaceAll方法。

String str = "asdzxcasd";
String str1 = str.replace('a','g');//str1 = "gsdzxcgsd"
String str2 = str.replace("asd","fgh");//str2 = "fghzxcfgh"
String str3 = str.replaceFirst("asd","fgh");//str3 = "fghzxcasd"
String str4 = str.replaceAll("asd","fgh");//str4 = "fghzxcfgh"

字符查找。indexOf、lastIndexOf方法。

String str = "I am a good student";
int a = str.indexOf('a');//a = 2
int b = str.indexOf("good");//b = 7
int c = str.indexOf("w",2);//c = -1
int d = str.lastIndexOf("a");//d = 5
int e = str.lastIndexOf("a",3);//e = 2

StringBuffer类

添加。append方法。

StringBuffer sb = new StringBuffer(“abc”);
sb.append(true);//"abctrue"

插入。insert方法。

StringBuffer sb = new StringBuffer(“TestString”);
sb.insert(4,false);//"TestfalseString"

删除。deleteCharAt方法。

StringBuffer sb = new StringBuffer(“Test”);
sb. deleteCharAt(1);//"Tst"

转换为字符串

StringBuffer sb = new StringBuffer(“Test”);
String s1 = sb.toString(); //StringBuffer转换为String

ArrayList类
- 添加：add方法
- 插入：insert方法
- 删除：remove方法
- 清空：clear方法
- 包含：contains方法

OJ常用算法

自己的初步阶段：理清思路，暴力求解，再逐步改进！

OJ基本技巧记录

OJ基本技巧记录

OJ平台代码基本格式

OJ输入输出技巧

OJ常用函数

OJ常用算法

猜你喜欢

热点阅读