L1-011 A-B(Java)

题目

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。

输入格式：
输入在2行中先后给出字符串A和B。两字符串的长度都不超过10的四次方，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。
输出格式：
在一行中打印出A−B的结果字符串。

输入样例：
I love GPLT!  It's a fun game!
aeiou
输出样例：
I lv GPLT!  It's  fn gm!

解题思路

1. 这个题目的关键在于如何有效地检查和删除字符！我这边是标记B中的字符，你可以使用布尔数组或者HashSet，遍历B，将出现的字符在布尔数组或HashSet标记为true(HashSet不是标记为true，口语化是标记，其实是add而已)。
2. 然后遍历A并创建StringBuilder，被布尔数组标记过的字符就不会被append进去(被hashet添加过的字符在进行contains时就不会被append)。

解题过程中遇到的问题

1. 一开始我是用的HashSet，我以为运行超时是因为如果字符串A很长的话，遍历A时时间成本就会很高，所以我就改为了布尔数组，因为布尔数组访问时间为O(1)，但是它比HashSet在空间上更加高效一点，而且是直接映射ASCII码。
2. 问题的根本是Scanner scanner = new Scanner(System.in); 将其更改为BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

代码

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;/*** 最终优化版* 用BufferedReader和BufferedWriter：相比于Scanner和System.out.println，这些类在处理大量数据时更加高效。* 直接操作原始字符数组：减少对StringBuilder的依赖，直接在输入的字符数组上操作，减少了内存复制的开销。* 使用布尔数组而非整数数组：这可以减少内存占用，尽管在这种情况下影响可能不大。*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));char[] A = br.readLine().toCharArray();char[] B = br.readLine().toCharArray();boolean[] ascii = new boolean[128]; // 使用布尔数组而非整数数组for (char c : B) {ascii[c] = true;}int len = 0;for (char c : A) {if (!ascii[c]) {A[len++] = c; // 直接在原数组上操作}}bw.write(A, 0, len);bw.flush();bw.close();br.close();}
}

import java.util.HashSet;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 写法二
*/
public class Main {public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String A = br.readLine();String B = br.readLine();HashSet<Character> setB = new HashSet<>();for (char ch : B.toCharArray()) {setB.add(ch);}StringBuilder result = new StringBuilder();for (char ch : A.toCharArray()) {if (!setB.contains(ch)) {result.append(ch);}}System.out.print(result.toString());br.close();}
}