《剑指 offer》刷题记录之二：字符串 & 链表

发表于 分类于 ， 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

本篇博客为《剑指 offer》一书的刷题笔记（第二部分）。

面试题 5：替换空格

题目：请实现一个函数，把字符串 s 中的每个空格替换成 "%20"。

示例

输入：s = "We are happy."
输出："We%20are%20happy."

限制：\(0 \le s \le 100000\)

思路及代码

这道题的关键在于如何执行替换操作，如果我们使用常规的从前往后遍历字符串替换空格，由于需要将 1 个字符替换为 3 个字符，因此替换时需要将当前字符后面的所有字符整体后移，这会导致总的时间复杂度达到 \(O(n^2)\)，显然并不是我们想要的结果（上述思考是原书中针对 C++ 提出的，实际上 java 和 python 中字符串不可更改，会自然而然地想到创建新的字符串）。

为了减小时间复杂度，我们可以创建一个辅助数组，提前预留出位置用于替换。数组的长度设为原字符串长度的 3 倍。遍历字符串，将其依次填入数组中，发现空格就替换，记录当前替换后字符串的总长度，最后将数组转化为新的字符串。

上述解法的 java 实现如下：

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) { // 也可以用 char c : s.toCharArray()
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}

上述方法用 StringBuilder 也可以实现。而对于 python，可以通过 list 实现，如下所示：

class Solution:
    def replaceSpace(self, s: str) -> str:
        list_s = []
        for c in s:
            if c == ' ': 
                list_s.append('%20')
            else: 
                list_s.append(c)
        return "".join(list_s) # python 可以直接 s.replace(" ", "%20")

本方法的时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)。实际上，原书中针对 C++ 给出的解法为先按照空格数扩展原字符串，再从后往前遍历，这样可以避免多次移动。

PS：%20 是 URL 的空格编码，表示一个普通空格（本质是 ASCII 码），而 &nbsp; 则是一种 HTML 的字符实体编码，表示 Non-breaking space，即不被折断的空格，一般用来占位，其 Unicode 码对应为 U+00A0（无 ASCII 码，UTF-8 码为 C2A0），更详细的说明请查看维基百科。

面试题 6：从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例

输入：head = [1,3,2]
输出：[2,3,1]

限制：\(0 \le 链表长度 \le 100000\)

思路及代码

在不改变链表结构的前提下，如果我们遍历链表，遍历的顺序是从头到尾，而要求的输出顺序是从尾到头。即第一个遍历到的节点在最后一个输出，最后一个遍历到的节点在第一个输出，这是典型的“后进先出”，我们可以使用栈来实现这种顺序。

上述方法的 java 实现如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

上述方法的时间复杂度为 \(O(n)\)，因为正向遍历一遍链表，栈弹出相当于反向遍历一遍链表，空间复杂度为 \(O(n)\)，因为额外使用了一个栈来存储链表中的每个节点。python 可以使用 list 和其切片特性实现栈的操作。

除了栈，我们还可以使用递归来解决上述问题，因为递归本质上就是一个栈结构。每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身，这样链表的输出结果就反过来了。

上述解法的 python 实现如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

该方法的时间复杂度和空间复杂度同样为 \(O(n)\)。需要注意，由于该递归并非尾递归，所以当链表非常长的时候，会导致函数调用的层级很深，可能导致函数调用栈溢出。相比较而言基于栈实现的代码的鲁棒性要更好一些。