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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

思路

1. O($n^2$)遍历字符串，找到一个空格，替换成 %20，后面的字符后移。
2. O(n)
   构建新字符串，长度为原始的+空格数*2，遍历并构建。

代码

// Java
class Solution {
    public String replaceSpace(String s) {
        int rawLength = s.length();
        StringBuilder newString = new StringBuilder();
        for (int i = 0; i < rawLength; ++i) {
            if (s.charAt(i) == ' ')
                newString.append("%20");
            else
                newString.append(s.charAt(i));
        }
        return newString.toString();
    }
}

面试题06. 从尾到头打印链表

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

思路

问面试官是否可以改变原始数据，如果可以，翻转链表。
不可以的话，使用 Stack或者 递归

代码

// 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) {
        ListNode p = head;
        Stack<Integer> s = new Stack<>();
        while(p != null) {
            s.push(p.val);
            p = p.next;
        }
        int[] ans = new int[s.size()];
        int i = 0;
        while(!s.empty()) {
            ans[i] = s.pop();
            ++i;
        }
        return ans;
    }
}

其他解法

版权属于：moluuser

本文链接：https://moluuser.com/archives/34/

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。