By Long Luo

148. 排序链表 。

暴力 + ArrayList

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;

    List<Integer> nodeList = new ArrayList<>();
    while (pNode != null) {
        nodeList.add(pNode.val);
        pNode = pNode.next;
    }

    Collections.sort(nodeList);

    ListNode dummyNode = new ListNode(-1);
    pNode = dummyNode;
    for (int i = 0; i < nodeList.size(); i++) {
        pNode.next = new ListNode(nodeList.get(i));
        pNode = pNode.next;
    }

    return dummyNode.next;
}

123

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

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;

    List<ListNode> nodeList = new ArrayList<>();
    while (pNode != null) {
        nodeList.add(pNode);
        pNode = pNode.next;
    }

    nodeList.sort(Comparator.comparingInt(o -> o.val));

    ListNode dummyNode = new ListNode(-1);
    ListNode preNode = dummyNode;
    for (int i = 0; i < nodeList.size(); i++) {
        pNode = nodeList.get(i);
        preNode.next = pNode;
        pNode.next = null;
        preNode = pNode;
    }

    return dummyNode.next;
}

复杂度分析

• 时间复杂度：\(O(n \log n + n)\)
• 空间复杂度：\(O(n)\)

归并排序

1
2
3

复杂度分析

• 时间复杂度：\(O(n \log n + n)\)
• 空间复杂度：\(O(n)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

Leetcode 230. 二叉搜索树中第K小的元素 题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点root，和一个整数$k$，请你设计一个算法查找其中第$k$个最小元素（从$1$开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
 
提示：
树中的节点数为 n 。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4
 
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第$k$小的值，你将如何优化算法？

方法一：中序遍历 + 递归

思路与算法：

二叉搜索树具有如下性质：

• 结点的左子树只包含小于当前结点的数。
• 结点的右子树只包含大于当前结点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。

因为二叉搜索树和中序遍历的性质，所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是，我们可以通过中序遍历找到第\(k\)个最小元素。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int kthSmallest(TreeNode root, int k) {
	List<Integer> nums = new ArrayList<>();
	inOrder(root, nums);
	return nums.get(k - 1);
}

public void inOrder(TreeNode root, List<Integer> numberList) {
	if (root == null) {
		return;
	}

	inOrder(root.left, numberList);
	numberList.add(root.val);
	inOrder(root.right, numberList);
}

复杂度分析：

• 时间复杂度：\(O(N)\)，其中\(N\)是树的节点数。
• 空间复杂度：\(O(N)\)，需要额外存储每个节点的值。

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