By Long Luo

Leetcode 22. 括号生成 题解。

方法一：暴力法

思路与算法：

直接生成所有 \(2^{2n}\) 个’(‘和’)’字符构成的序列，然后我们检查每一个是否有效即可。

为了生成所有序列，我们可以使用递归。长度为 \(n\) 的序列就是在长度为 \(n-1\) 的序列前加一个’(‘或’)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量 \(balance\) 表示左括号的数量减去右括号的数量。如果在遍历过程中 \(balance\) 的值小于零，或者结束时 \(balance\) 的值不为零，那么该序列就是无效的，否则它是有效的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public List<String> generateParenthesis(int n) {
	if (n < 1) {
		return new ArrayList<>();
	}

	List<String> ans = new ArrayList<>();
	generateAll(new char[2 * n], 0, ans);
	return ans;
}

public void generateAll(char[] current, int pos, List<String> result) {
	if (pos == current.length) {
		if (valid(current)) {
			result.add(new String(current));
		}
	} else {
		current[pos] = '(';
		generateAll(current, pos + 1, result);
		current[pos] = ')';
		generateAll(current, pos + 1, result);
	}
}

public boolean valid(char[] current) {
	int balance = 0;
	for (char c : current) {
		if (c == '(') {
			++balance;
		} else {
			--balance;
		}
		if (balance < 0) {
			return false;
		}
	}
	return balance == 0;
}

复杂度分析

• 时间复杂度：\(O(2^{2n}n)\)，对于 \(2^{2n}\) 个序列中的每一个，我们用于建立和验证该序列的复杂度为 \(O(n)\)。
• 空间复杂度：\(O(n)\)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 \(O(1)\) 的空间，最多递归 \(2n\) 层，因此空间复杂度为 \(O(n)\)。

By Long Luo

Grep 是什么？

grep, g/re/p , (Global / Regular Expression(RE) search / and Print Out the line) ，全面搜索正则表达式并把行打印出来 ，是一种强大的文本搜索工具，它能使用正则表达式搜索文本，并把匹配的行打印出来。用于过滤/搜索的特定字符。可使用正则表达式能配合多种命令使用，使用上十分灵活。

grep searches each FILE for PATTERNS. PATTERNS is a string that contains one or more patterns separated by newline characters, and grep prints each line that matches a pattern. When using grep in a shell command, PATTERNS should usually be quoted.

A FILE of “-” denotes standard input. If no FILE is specified, recursive searches examine the working directory, while nonrecursive searches read standard input.

Furthermore, the variant programs egrep, fgrep, and rgrep are equivalent to grep -E, grep -F, and grep -r, respectively. These variants are obsolete, but remain available for backward compatibility.

Grep 用法

grep [OPTION…] PATTERNS [FILE…]

grep [OPTION…] -e PATTERNS … [FILE…]

grep [OPTION…] -f PATTERN_FILE … [FILE…]

WILDCARDS

QUANTIFIERS

CHARACTER CLASSES

[A-Za-z] Any lower and upper case letters [0-9] Any Number [0-9A-Za-z] Any lower and upper case letter or digits

POSITIONS

By Long Luo

Sed Commands Options Description Exit sed without processing any more commands or input. Delete the pattern space; immediately start next cycle. Print out the pattern space (to the standard output). Appending text after a line. insert text before a line. = Print out the current input line number (with a trailing newline). Replaces the line(s) with text. w Write the pattern space to filename. Empty the content of the pattern space. Delete text in the pattern space up to the first newline , restart cycle if pattern space contains newlines. Execute the command that is found in the pattern space. F Print the file name of the current input file. Reads file filename. n N Read/append the next line of input into the pattern space. W Write the first line of the current pattern space to filename Exchange the contents of the hold and pattern spaces. Transliterate any characters in the pattern space.

Command Options Options Description -i[SUFFIX] Edit files in place (make backup if SUFFIX supplied). -n Suppress automatic printing of pattern space. -f add the contents of script-file to the commands to be executed -e Execute multiple sed commands -r or -E Use extended regular expressions (supports ‘+’, ‘(’, ‘)’)■ -s Consider files as separate rather than as a single, continuous stream. -c Copy the input to the standard output. -I pecify the desired line-wrap length for the I command. Command Flags Flags Description g Global substitution - Replace all occurrences in each line. Execute shell command after substitution. w Save only the substituted lines to a specified file. Perform case-insensitive pattern matching. p Print only the substituted lines. 1,2,4,… Substitute the nth occurrence- Replace specific occurrence of a pattern.

BASIC EXAMPLES

$ seq |sed $ seq | sed -n $ sed ‘/warning/i # This is a warning’ logfile $ cod -o ‘<c/corvor/now-corvor/;c/port/8080/;}’ config.-conf

REPLACING TEXT $ sed s/old/new/g file.txt $ sed ‘4 s/old/new/’ file.txt $ sed s/old/new/3 file.txt $ sed ‘s/A//’ file.txt $ sed -n 7important/w important_lines.txt’ logfile $ sed 7hello/s/world/universe/’ file.txt

APPEND AND PREPEND TEXT $ sed -n 7hello/p’ file.txt $ sed -n 7hello/lp’ file.txt $ sed -n 7hellQ/lp’ file,txt $ sed ‘2a Text after line 2’ file.txt $ sed ‘\(a THE END!' file.txt\) sed ’s/old/new/’ config.conf

• • • DELETING LINES $ sed 1,4d’ file.txt $ sed ‘6~4d’ file.txt $ sed ‘\(d' file.txt\) sed 7 AErrors/d’ file.txt $ sed 7 A\(/d' file.txt\) sed 7 A#/d’ file.txt $ sed ’3d’file t¥t

• • • OPTIONS EXAMPLES $ sed -n 7error/p’ syslog.log $ sed -e ‘s/server-01/server-02/’ -e ‘s/port=8080/port=9090/’ app.conf $ sed -i.bak ‘s/v3.3.2/3.4.1/’ app.conf $ sed .r ‘s/(error|warning)/info/’ syslog Ing $ bed -b ‘b/liubuidiiie/bei vei/1 /eiu/Luunf $ sed -n -e ’1,5C' -e’ I his is a new line.’ source.txt destination.txt $ seo -T repiace_pauerns.sea conng.ixi sysxplore.com $ sed -I long_text.txt

参考文献

1. SED
2. DevOps

By Long Luo

AWK 是一种强大的文本处理工具，广泛用于 Linux/Unix 系统中对文本文件或数据流进行操作。它能够基于条件筛选、统计字段、重新排列数据等。主要特点包括：

• 基于模式匹配： 根据条件筛选数据。
• 列操作能力： 简单高效地处理文本列数据。
• 轻量编程语言： 提供内置变量、循环、条件语句等编程功能。

AWK 程序的结构

AWK 程序的结构:

1

awk 'pattern { action }' file

• pattern： 指定操作的匹配规则，例如正则表达式、逻辑判断等。
• action： 指满足条件时要执行的操作，用 {} 包围，例如打印、统计、替换等。
• file： 要处理的文本文件名称

常用内置变量

以下是 常用内置变量 的补充说明：

变量说明：

1. NR 和 FNR 的区别：

• NR：累计行号，处理多个文件时行号会累加。
• FNR：当前文件的行号，处理多个文件时每个文件的行号从 1 开始重新计数。

2. FS 和 OFS 的作用：

• FS：指定输入字段的分隔符，默认是空格。
• OFS：指定输出字段的分隔符，默认是空格。

3. RS 和 ORS 的作用：

• RS：指定输入记录的分隔符，默认是换行符。
• ORS：指定输出记录的分隔符，默认是换行符。

4. ENVIRON 的使用：

• ENVIRON 是一个关联数组，用于访问环境变量。例如：

1

awk 'BEGIN { print ENVIRON["HOME"] }'

5. RSTART 和 RLENGTH：

• 这两个变量与 match 函数配合使用，用于获取匹配字符串的起始位置和长度。例如：

1

awk 'BEGIN { str = "hello world"; match(str, /world/); print RSTART, RLENGTH }'

6. SUBSEP：

• 用于多维数组的下标分隔符，默认是 \034（非打印字符）。例如：

1

awk 'BEGIN { arr["a", "b"] = 10; print arr["a", "b"] }'

7. ARGIND 和 ARGC：

• ARGIND：当前处理的文件在命令行参数中的索引（从 1 开始）。
• ARGC：命令行参数的数量。例如：

1

awk 'BEGIN { print ARGIND, ARGC }' file1.txt file2.txt

8. FILENAME：

• 当前正在处理的文件名。例如：

1

awk '{ print FILENAME, $0 }' file1.txt file2.txt

9. 1,2, …, $NF：

• $1 表示第 1 列，$2 表示第 2 列，依此类推。
• $NF 表示当前行的最后一列。

10. NF：

• 当前行的字段数（列数）。例如：

1

awk '{ print NF }' file.txt

11. RS 和 ORS 的高级用法：

• 可以修改 RS 和 ORS 来处理非标准格式的文件。例如，将 RS 设置为空字符串，以处理多行记录：

1

awk 'BEGIN { RS = "" } { print $0 }' file.txt

12. SUBSEP 的高级用法：

• 可以修改 SUBSEP 来定义多维数组的下标分隔符。例如：

1

awk 'BEGIN { SUBSEP = ":"; arr["a", "b"] = 10; print arr["a", "b"] }'

13. RSTART 和 RLENGTH 的高级用法：

• 结合 match 函数，可以提取匹配的子字符串。例如：

1

awk 'BEGIN { str = "hello world"; match(str, /world/); print substr(str, RSTART, RLENGTH) }'

14. ENVIRON 的高级用法：

• 可以遍历 ENVIRON 数组，打印所有环境变量。例如：

1

awk 'BEGIN { for (key in ENVIRON) print key, ENVIRON[key] }'

15. FILENAME 的高级用法：

• 在处理多个文件时，可以根据文件名执行不同的操作。例如：

1

awk '{ if (FILENAME == "file1.txt") print "File1:", $0; else print "File2:", $0 }' file1.txt file2.txt

运行 AWK 程序

AWK 程序可以通过以下方式运行：

1. 命令行直接运行：

1

awk 'pattern { action }' file

• pattern：匹配条件（可选）。
• action：满足条件时执行的操作。
• file：要处理的文件。

2. 脚本文件运行：

1

awk -f script.awk file

示例：假设 script.awk 内容如下：

1

{ print $1 }

运行命令：

1

awk -f script.awk file.txt

• script.awk：包含 AWK 程序的脚本文件。
• file：要处理的文件。

注意事项： - 未指定文件时，AWK 从标准输入读取数据； - 可同时处理多个文件；

AWK 基本输出

• 打印文件的所有内容：

1

awk '{ print $0 }' file.txt

• 打印文件的第 1 列和第 3 列：

1

awk '{ print $1, $3 }' file.txt

AWK 高级输出

printf 格式化输出 printf 可以格式化输出内容，例如：

1

awk '{ printf "Name: %s, Age: %d\n", $1, $2 }' file.txt

排序输出 结合 sort 命令对输出进行排序：

1

awk '{ print $1 }' file.txt | sort

选择/过滤行

按某列的值

• 打印第 2 列大于 50 的行：

1

awk '$2 > 50 { print }' file.txt

按某几列值的计算结果

• 打印第 1 列和第 2 列之和大于 100 的行：

1

awk '$1 + $2 > 100 { print }' file.txt

按字符串匹配

• 打印包含 “error” 的行：

1

awk '/error/ { print }' file.txt

不同方式的组合

• 打印第 2 列大于 50 且包含 “error” 的行：

awk ‘$2 > 50 && /error/ { print }’ file.txt BEGIN 和 END - BEGIN 块在处理输入前执行，END 块在处理输入后执行：

awk ‘BEGIN { print “Start” } { print } END { print “End” }’ file.txt

计算

统计数量：工时超过 15 小时的员工人数

1

awk '$3 > 15 { count++ } END { print count }' file.txt

求和、求平均：平均工资

1

awk '{ sum += $2 } END { print "Average:", sum/NR }' file.txt

处理文本：打印时薪最高的员工信息

1

awk '$4 > max { max = $4; line = $0 } END { print line }' file.txt

字符串拼接（concatenation）：在一行内打印所有员工名

1

awk '{ names = names $1 " " } END { print names }' file.txt

打印最后一行

1

awk '{ last = $0 } END { print last }' file.txt

内置函数

• 统计行数、单词数、字符数：

1

awk '{ chars += length($0); words += NF } END { print "Lines:", NR, "Words:", words, "Chars:", chars }' file.txt

控制流

If-Else

1

awk '{ if ($1 > 50) print "High"; else print "Low" }' file.txt

While

1

awk '{ i = 1; while (i <= NF) { print $i; i++ } }' file.txt

For

1

awk '{ for (i = 1; i <= NF; i++) print $i }' file.txt

数组

统计每列的总和：

1

awk '{ for (i = 1; i <= NF; i++) sum[i] += $i } END { for (i in sum) print "Column", i, "Sum:", sum[i] }' file.txt

AWK 示例速查表

以下是常见 AWK 功能及其对应程序和类似命令：

参考文献

1. AWK
2. AWK 简明教程

By Long Luo

建筑是凝固的音乐，斑驳的外墙演绎着历史的旋律。

布鲁日是一座被时间静止的美丽小城。漫步在布鲁日的小巷中，脚踏着青石板路，仿佛走入了中世纪。满眼是砖红色屋顶，哥特式的长窗，高高伫立的钟楼，还有墙壁上随处可见的洛可可画作，你依然能感受到当年布鲁日的繁荣和富庶。