001.算法笔试中处理输入和输出

前置知识：无

核心代码模式 VS. ACM 模式 §

核心代码模式和 ACM 模式

高效 IO §

ACM 模式的题目要自己处理数据的输入输出，使用语言不同的方法，IO 的效率相差很大

词和行 §

• 词：按空白分割（包括空格、回车换行、制表符等空白字符串）
• 行：按换行分割

如，有如下内容：

1      2
abc -28 uvw

按词读：

共读 5 次，每次读到：
1
2
abc
-28
uvw

按行读：

共读 2 次，每次读到：
1      2
abc -28 uvw

Java §

• 低效 IO：Scanner、System.out
• 高效 IO：BufferedReader、StreamTokenizer、PrintWriter

按词读 §

package main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
 
public class Main {
  public static void main(String[] args) throws IOException {
    // 带缓存的读（输入），很高效
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // 一个词一个词的读
    StreamTokenizer in = new StreamTokenizer(br);
    // 带缓存的写（输出），很高效
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) { // 输入流没有结束
      int n = (int) in.nval; // 读一个词的内容，转成 int 类型
      in.nextToken(); // 读下一个词
      int m = (int) in.nval; // 读一个词的内容，转成 int 类型
	  // ...
      out.println(n, m); // 输出
    }
 
    out.flush(); // 将缓存区的内容刷到标准输出
 
    // 关流
    br.close();
    out.close();
  }
}

按行读 §

package main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
 
public class Main {
  public static String line;
 
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while ((line = in.readLine()) != null) { // 按行读，输入流没有结束
	  // ...
      out.println("...");
    }
    out.flush();
    in.close();
    out.close();
  }
}

Go §

• 低效 IO：fmt.Scan*、fmt.Print*
• 高效 IO：bufio.NewScanner、bufio.NewReaderSize、bufio.NewWriterSize、strings.Builder

以 这道题 为例

低效 IO §

当频繁地对少量数据读写时会占用 IO，造成性能问题

package main
 
import (
    "fmt"
)
 
func main() {
    var a, b int
    for {
        _, err := fmt.Scan(&a, &b) // 低效读
        if err != nil {
            break
        }
        fmt.Println(a + b) // 低效写
    }
}

高效读 §

Scanner §

package main
 
import (
    "bufio"
    "os"
    "strings"
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() { // input.Scan(): 读一行; input.Text(): 拿这行的内容
        line := input.Text() // string
        words := strings.Fields(line) // 分割这一行中的词，[]string
    }
}

指定缓冲区 §

bufio.NewScanner 缓冲区默认为 64*1024 字节，当一行数据多于缓冲区大小时会 panic，使用 Scanner.Buffer 方法进行设置，如：这道题

package main
 
import (
    "bufio"
    "os"
)
 
func main() {
	input := bufio.NewScanner(os.Stdin)
	// 缓冲区大小为8192字节，使用bufio.MaxScanTokenSize来设置最大扫描令牌的大小
	input.Buffer(make([]byte, 8192), bufio.MaxScanTokenSize)
    for input.Scan() {
        line := input.Text() // string，读一行
        // ...
    }
}

或者使用 bufio.NewReaderSize

package main
 
import (
    "bufio"
    "os"
)
 
func main() {
    reader := bufio.NewReaderSize(os.Stdin, 1 << 20) // 指定缓冲区大小
    for {
        line, _, err := reader.ReadLine() // 读一行, []byte
        if err != nil {
            break
        }
        // ...
    }
}

按词读 §

已过时

Go 中没有像 Java 中 StreamTokenizer 那么方便的 API 直接来使用，而是要自己写分割函数（函数是固定的，背会或者现场拷贝都可以）

package main
 
import (
    "bufio"
    "os"
    "unicode"
)
 
func main() {
	input := bufio.NewScanner(os.Stdin)
	// 设置自定义的分隔函数
	input.Split(splitWithSpace)
 
	for input.Scan() {
		word := input.Text() // string
		// ...
	}
}
 
func splitWithSpace(data []byte, atEOF bool) (advance int, token []byte, err error) {
	// 跳过连续的空白字符
	start := 0
	for start < len(data) && unicode.IsSpace(rune(data[start])) {
		start++
	}
 
	// 使用 unicode.IsSpace 来判断是否是空白字符
	for i := start; i < len(data); i++ {
		if unicode.IsSpace(rune(data[i])) {
			return i + 1, data[start:i], nil
		}
	}
 
	// 如果未找到空白字符，且已经到达文件末尾，返回剩余的内容
	if atEOF && len(data[start:]) > 0 {
		return len(data), data[start:], nil
	}
 
	// 如果未找到空白字符且未到达文件末尾，则要求继续读取更多数据
	return 0, nil, nil
}

package main
 
import (
	"bufio"
	"fmt"
	"strings"
)
 
func main() {
	s := `1      2
       abc -28 uvw`
	in := bufio.NewScanner(strings.NewReader(s))
	in.Split(bufio.ScanWords)
	for in.Scan() {
		fmt.Println(in.Text())
	}
}

输出：

1
2
abc
-28
uvw

这道题 用到了按词读

高效写 §

带缓冲区的写 §

package main
 
import (
    "strings"
    "strconv"
    "bufio"
    "os"
    "fmt"
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    output := bufio.NewWriterSize(os.Stdout, 1 << 20)
    for input.Scan() {
        arr := strings.Split(input.Text(), " ")
        a, _ := strconv.Atoi(arr[0])
        b, _ := strconv.Atoi(arr[1])
        fmt.Fprintln(output, a + b) // 先写出到缓冲区
        // 或
        // output.WriteString(strconv.Itoa(a + b))
        // output.WriteByte('\n')
    }
    output.Flush() // 将缓存区的内容刷到标准输出
}

一次写出 §

package main
 
import (
    "fmt"
    "strings"
    "strconv"
    "bufio"
    "os"
)
 
func main() {
    var builder strings.Builder
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        arr := strings.Split(input.Text(), " ")
        a, _ := strconv.Atoi(arr[0])
        b, _ := strconv.Atoi(arr[1])
        builder.WriteString(strconv.Itoa(a + b)) // 先写进 strings.Builder
        builder.WriteByte('\n')
    }
    fmt.Print(builder.String()) // 之后一次写出到标准输出
}

临时动态空间 VS. 全局静态空间 §

ACM 模式的题目要使用全局静态空间，每组测试都公用这些全局静态空间；不要用临时动态空间，如动态 new、make。因为测试平台算你代码的空间占用是算代码中所有申请空间的总和，不会管你有没有释放