第5章 字符串

笔记

字符与整数的联系——ASCII码

常用ASCII值：'A'- 'Z'是65~ 90，'a' - 'z'是97 - 122，0 - 9是 48 - 57。

每个常用字符都对应一个-128 ~ 127的数字，二者之间可以相互转化。注意：目前负数没有与之对应的字符。

字符可以参与运算，运算时会将其当做整数。

String类

初始化

String a = "Hello World";
String b = "My name is ";
String x = b;  // 存储到了相同地址
String c = b + "yxc";  // String可以通过加号拼接
String d = "My age is " + 18;  // int会被隐式转化成字符串"18"
String str = String.format("My age is %d", 18);  // 格式化字符串，类似于C++中的sprintf
String money_str = "123.45";
double money = Double.parseDouble(money_str);  // String转double

String不能修改指向的字符串内容，但可以修改指向的字符串。

访问String中的字符可通过charAt(i)实现。

常用字符串API

length()：返回长度
split(String regex)：分割字符串
indexOf(char c)、indexOf(String str)、lastIndexOf(char c)、lastIndexOf(String str)：查找，找不到返回-1
equals()：判断两个字符串是否相等，注意不能直接用==
compareTo()：判断两个字符串的字典序大小，负数表示小于，0表示相等，正数表示大于
startsWith()：判断是否以某个前缀开头
endsWith()：判断是否以某个后缀结尾
trim()：去掉首尾的空白字符
toLowerCase()：全部用小写字符
toUpperCase()：全部用大写字符
replace(char oldChar, char newChar)：替换字符
replace(String oldRegex, String newRegex)：替换字符串
substring(int beginIndex, int endIndex)：返回[beginIndex, endIndex)中的子串
toCharArray()：将字符串转化成字符数组

字符串输入与输出

Scanner sc = new Scanner(System.in);
String str1 = sc.next();  // 输入字符串，遇到空格、回车等空白字符时停止输入
String str2 = sc.nextLine();  // 输入一整行字符串，遇到空格不会停止输入，遇到回车才会停止

System.out.println(str1);  // 可以直接输出
System.out.printf("%s\n", str2);  // 也可以格式化输出，用 %s 表示字符串

字符串构造

String不能被修改，如果打算修改字符串，可以使用StringBuilder和StringBuffer。

StringBuffer线程安全，速度较慢；StringBuilder线程不安全，速度较快。可用reverse()快速翻转字符串。

StringBuilder sb = new StringBuilder("Hello ");  // 初始化
sb.append("World");  // 拼接字符串
System.out.println(sb);

习题

AcWing 760. 字符串长度

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        scanner.close();

        System.out.println(line.length());
    }
}

AcWing 761. 字符串中的数字个数

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        scanner.close();

        int cnt = 0;
        for (char c: line.toCharArray()) {
            if (Character.isDigit(c))
                cnt++;
        }
        System.out.println(cnt);
    }
}

AcWing 763. 循环相克令

import java.util.Scanner;

public class Main {

    public static int get(String a) {
        if (a.equals("Hunter")) return 0;
        else if (a.equals("Gun")) return 1;
        else return 2;
    }

    public static void judge(String a, String b) {
        int x = get(a);
        int y = get(b);
        if (x == y) System.out.println("Tie");
        else if ((x + 1) % 3 == y) System.out.println("Player1");
        else System.out.println("Player2");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-- > 0) {
            String a = scanner.next();
            String b = scanner.next();
            judge(a, b);
        }
        scanner.close();
    }
}

AcWing 765. 字符串加空格

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        scanner.close();

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < line.length(); i++) {
            stringBuilder.append(line.charAt(i));
            if (i < line.length() - 1) stringBuilder.append(' ');
        }
        System.out.println(stringBuilder);
    }
}

AcWing 769. 替换字符

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String c = scanner.nextLine();
        scanner.close();

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < line.length(); i++) {
            if (line.charAt(i) != c.charAt(0)) stringBuilder.append(line.charAt(i));
            else stringBuilder.append('#');
        }
        System.out.println(stringBuilder);
    }
}

AcWing 773. 字符串插入

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            String str = scanner.next();
            String sub = scanner.next();

            int k = 0;
            for (int i = 1; i < str.length(); i++)
                if (str.charAt(i) > str.charAt(k))
                    k = i;

            System.out.println(str.substring(0, k + 1) + sub + str.substring(k + 1));
        }
        scanner.close();
    }
}

AcWing 772. 只出现一次的字符

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        scanner.close();

        int[] cnt = new int[26];
        for (char c : s.toCharArray())
            cnt[c - 'a']++;

        for (char c : s.toCharArray())
            if (cnt[c - 'a'] == 1) {
                System.out.println(c);
                return;
            }

        System.out.println("no");
    }
}

AcWing 762. 字符串匹配

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double k = scanner.nextDouble();
        String s1 = scanner.next();
        String s2 = scanner.next();
        scanner.close();

        int cnt = 0;
        for (int i = 0; i < Math.min(s1.length(), s2.length()); i++)
            if (s1.charAt(i) == s2.charAt(i)) cnt++;

        double res = (double)cnt / s1.length();
        if (res >= k) System.out.println("yes");
        else System.out.println("no");
    }
}

AcWing 768. 忽略大小写比较字符串大小

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        scanner.close();

        s1 = s1.toLowerCase();
        s2 = s2.toLowerCase();
        int res = s1.compareTo(s2);
        if (res == 0) System.out.println("=");
        else if (res < 0) System.out.println("<");
        else System.out.println(">");
    }
}

AcWing 766. 去掉多余的空格

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder stringBuilder = new StringBuilder();
        while(scanner.hasNext()) {
            String s = scanner.next();
            stringBuilder.append(s);
            stringBuilder.append(' ');
        }
        scanner.close();

        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        System.out.println(stringBuilder);
    }
}

AcWing 767. 信息加密

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        StringBuilder stringBuilder = new StringBuilder();
        char ch;
        for (char c : s.toCharArray()) {
            if (Character.isLowerCase(c)) ch = (char) ('a' + (c - 'a' + 1) % 26);
            else if (Character.isUpperCase(c)) ch = (char) ('A' + (c - 'A' + 1) % 26);
            else ch = c;

            stringBuilder.append(ch);
        }

        System.out.println(stringBuilder);
    }
}

AcWing 764. 输出字符串

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        StringBuilder stringBuilder = new StringBuilder();
        int n = s.length();
        char ch;
        for (int i = 0; i < n; i++) {
            ch = (char) (s.charAt(i) + s.charAt((i + 1) % n));
            stringBuilder.append(ch);
        }

        System.out.println(stringBuilder);
    }
}

AcWing 770. 单词替换

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        String a = scanner.nextLine();
        String b = scanner.nextLine();
        scanner.close();

        for (int i = 0; i < s.length; i++) {
            if (s[i].equals(a)) System.out.printf("%s", b);
            else System.out.printf("%s", s[i]);

            if (i < s.length - 1) System.out.print(" ");
        }
        System.out.println("");
    }
}

笔记

不能直接用replace()替换旧字符串，题目要求是单词符合才行，而不是字符满足。因此在测试用例把a替换成b时，直接使用replace()就会出错。

AcWing 771. 字符串中最长的连续出现的字符

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-- > 0) {
            String s = scanner.next();
            char c = ' ';
            int cnt = 0;
            for (int i = 0; i < s.length();) {
                int j = i + 1;
                while(j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                if (j - i > cnt) {
                    c = s.charAt(i);
                    cnt = j - i;
                }
                i = j;
            }
            System.out.printf("%c %d\n", c, cnt);
        }
        scanner.close();
    }
}

笔记

双指针算法优化时间复杂度。

读取输入时，如果先用nextInt()读取n，则再调用nextLine()会读取到当前行的换行符，达不到预期效果。

AcWing 774. 最长单词

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        s = s.substring(0, s.length() - 1);
        String[] arr = s.split(" ");
        int maxIndex = 0;
        for (int i = 0; i < arr.length; i++)
            if (arr[i].length() > arr[maxIndex].length())
                maxIndex = i;
        System.out.println(arr[maxIndex]);
    }
}

AcWing 775. 倒排单词

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        String[] arr = s.split(" ");
        for (int i = arr.length - 1; i >= 0; i--) {
            System.out.print(arr[i]);
            if (i > 0) System.out.print(" ");
        }
        System.out.println("");
    }
}

AcWing 776. 字符串移位包含问题

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.next();
        String s2 = scanner.next();
        scanner.close();

        if (s1.length() < s2.length()) {
            String tmp = s1;
            s1 = s2;
            s2 = tmp;
        }

        boolean success = false;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.contains(s2)) {
                success = true;
                break;
            }
            s1 = s1.substring(1) + s1.charAt(0);
        }

        if (success) System.out.println("true");
        else System.out.println("false");
    }
}

笔记

假设字符串s1的长度不小于s2，如果满足题意，则s2一定是s1所有循环移位结果之一的子串。查找子串可用contains()

AcWing 777. 字符串乘方

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(true) {
            String s = scanner.nextLine();
            if (s.equals(".")) break;

            int n = s.length(), j = 1;
            while(j <= n) {
                if (n % j == 0) {
                    String sub = s.substring(0, j);
                    StringBuilder stringBuilder = new StringBuilder();
                    for (int i = 0; i < n / j; i++) stringBuilder.append(sub);
                    if (s.equals(stringBuilder.toString())) break;
                }
                j++;
            }
            System.out.println(n / j);
        }
        scanner.close();
    }
}

笔记

题意可理解为：枚举子串substring(0, j)，找到最小的j，使得以子串substring(0, j)重复$\frac{n}{j}$次拼接后得到原串。其中$1 \leqslant j \leqslant n$，$n$是原串字符串长度。

由于$j$和$\frac{n}{j}$都是整数，因此$j$必定是$n$的约数。因此可从小到大枚举j，一方面能保证一旦找到满足的就是最大的$\frac{n}{j}$，另一方面当$j=n$时，一定成立，即原串。

AcWing 778. 字符串最大跨距

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(",");
        scanner.close();

        String a = s[0], b = s[1], c = s[2];
        int i = a.indexOf(b), j = a.lastIndexOf(c);
        if (i == -1 || j == -1) System.out.println(-1);
        else if (i + b.length() > j) System.out.println(-1);
        else System.out.println(j - (i + b.length()));
    }
}

AcWing 779. 最长公共字符串后缀

import java.util.Scanner;

public class Main {

    public static String f(String[] s) {
        int n = s.length;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s[0].length(); i++) {
            char c = s[0].charAt(s[0].length() - i - 1);
            boolean success = true;
            for (int j = 1; j < n; j++) {
                int index = s[j].length() - i - 1;
                if (index < 0 || s[j].charAt(index) != c) {
                    success = false;
                    break;
                }
            }
            if (success) stringBuilder.append(c);
            else break;
        }
        return stringBuilder.reverse().toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(true) {
            int n = scanner.nextInt();
            if (n == 0) break;
            String[] s = new String[n];
            for (int i = 0; i < n; i++) s[i] = scanner.next();

            System.out.println(f(s));
        }
        scanner.close();
    }
}