1. 替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

思路:

  • 获取数组长度，遍历数组中的字符

  • 以一个char数组作为容器装载新的数据，并设计一个指针作为索引

    • 如果字符为空格，那么以size++作为索引进行三次添加，‘%’，‘2’，‘0’
    • 如果不为空格，那么以size++作为做索引进行添加当前字符串索引的字符
    • size的目的，一方面作为char数组长度，一方面进行添加操作（由于是size++，先以size索引执行操作，后再进行自增）
      1. class Solution {
      2. public String replaceSpace(String s) {
      3.    // 字符串长度
      4.    int length = s.length();
      5.    // char类型数组作为容器
      6.    // 初始化长度为3，表示极端情况下， 字符串里面全为空格，则需要所有三倍于字符串长度的字符数组"%20"为三个字符
      7.    char[] chs = new char[length*3];
      8.    int size = 0;
      9.    for(int i=0;i<length;i++){
      10.        char c = s.charAt(i);
      11.        if(c==' '){
      12.            chs[size++] = '%';
      13.            chs[size++] = '2';
      14.            chs[size++] = '0';
      15.        }else{
      16.            chs[size++] = c;
      17.        }
      18.    }
      19.    String newStr = new String(chs,0,size);
      20.    return newStr;
      21. }
      22. }

      复杂度分析：

  • 时间复杂度：O(n)。遍历字符串 s 一遍。

  • 空间复杂度：O(n)。额外创建字符数组，长度为 s 的长度的 3 倍。

2. 从尾到头打印链表

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

思路：

  • 问题实质：实现倒序，或者说是排序反转。
  • 最好的解决方式：
    • 使用栈，栈的最大特性：先进后出

  • 步骤：

    • 遍历节点，获取val，push入栈中
    • 遍历节点，使用int[]进行装载pop出来的数据
      1. class Solution {
      2. // 使用栈  (先进后出的原则，实现倒叙)
      3. public int[] reversePrint(ListNode head) {
      4.    Stack<ListNode> stack = new Stack<>();
      5.    ListNode temp = head;
      6.    while(temp!=null){
      7.        stack.push(temp);
      8.        temp = temp.next;
      9.    }
      10.    int size = stack.size();
      11.    int[] answer = new int[size];
      12.    for(int i=0;i<size;i++){
      13.        answer[i] = stack.pop().val;
      14.    }
      15.    return answer;
      16. }
      17. }

      复杂度分析：

  • 时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。

  • 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。