[数据结构与算法]【剑指Offer】数据结构

励志

Being yourself, that is a magic stronger than any wish.
坚守本心，远胜祈愿。

题目来源：
https://leetcode-cn.com/leetbook/detail/illustration-of-algorithm/

配合学习文档：
https://www.kancloud.cn/alex_wsc/dataalg/1853982

书籍推荐：

《漫画算法》

视频推荐：
https://www.bilibili.com/video/BV1E4411H73v

目录

一、剑指 Offer 05. 替换空格

题：

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

解：

解题思路：遍历添加
AC代码：

class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        for(char s1 : s.toCharArray()){
            if(s1 == ' '){
                sb.append("%20");
            }else{
                sb.append(s1);
            }
        }
        return sb.toString();
    }
}

二、剑指 Offer 06. 从尾到头打印链表

题：

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

解：

解题思路：辅助栈
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        while(head != null){
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = stack.removeLast();
        }
        return res;
    }
}

解题思路：递归
AC代码：

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

三、剑指 Offer 09. 用两个栈实现队列

题：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

解：

图解：

AC代码：

class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }	
}

四、剑指 Offer 20. 表示数值的字符串

题：

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

1. 若干空格
2. 一个 小数 或者 整数
3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
4. 若干空格

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（’+’ 或 ‘-’）

2. 下述格式之一：

   至少一位数字，后面跟着一个点 ‘.’
   至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
   一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（’+’ 或 ‘-’）
2. 至少一位数字

部分数值列举如下：

• ["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下：

• [“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

示例 4：

输入：s = "    .1  "
输出：true

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

解：

思路：有限状态自动机

状态定义：

按照字符串从左到右的顺序，定义以下 9 种状态。

1. 开始的空格
2. 幂符号前的正负号
3. 小数点前的数字
4. 小数点、小数点后的数字
5. 当小数点前为空格时，小数点、小数点后的数字
6. 幂符号
7. 幂符号后的正负号
8. 幂符号后的数字
9. 结尾的空格
   

结束状态：

合法的结束状态有 2, 3, 7, 8 。

AC代码：

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

五、剑指 Offer 24. 反转链表

题：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

解：

图解：

Ps：链表松手前一定要保存好下一个val







AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
        	// 跳棋法
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre; 
    }
}

另解：递归
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return dfs(null, head);
    }
    ListNode dfs(ListNode pre, ListNode cur){
        if(cur == null) return pre; // 出口
        // 过程
        ListNode res = dfs(cur, cur.next); // 递归下一个
        cur.next = pre; // 修改节点指向
        return res; // 返回下一个节点
    }
}

六、剑指 Offer 30. 包含 min 函数的栈

题：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

解：

思路：两个栈，一个实现pop，push，另一个储存最小值（非严格升序）

采用 “非严格” 降序原因：
在栈 A 具有 重复 最小值元素时，非严格降序可防止栈 B 提前弹出最小值元素，示例如下：

AC代码：

class MinStack {
    LinkedList<Integer> A, B;
    public MinStack() {
        A = new LinkedList();
        B = new LinkedList();
    }
    public void push(int x) {
        A.add(x); 
        if(B.isEmpty() || B.getLast() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.removeLast().equals(B.getLast()))
            B.removeLast();
    }
    public int top() {
        return A.isEmpty() ? -1 : A.getLast() ;
    }
    public int min() {
        return B.isEmpty() ? -1 : B.getLast();
    }
}


/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

七、剑指 Offer 35. 复杂链表的复制

题：

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

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

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

解：

思路：哈希映射Node，然后复制对应next 和 random 引用指向
AC代码：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head; // 指针
        Map<Node, Node> map = new HashMap();
        while(cur != null){
            // Node一一映射（映射头）
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head; // 指针归零
        while(cur != null){
            // 修改指向（让头带好他们的小弟）
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);   
    }
}

思路：拼接+拆分（注意指向对应）
图解：

AC代码：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head; // 指针
        // 合并
        while(cur != null){
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = temp.next; 
        } 
        // random指向
        cur = head; // 归零
        while(cur != null){
            if(cur.random != null){
                // 要指向各自的链的指向
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 拆分
        cur = head.next;
        Node res = head.next, pre = head;
        while(cur.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;

    }
}

八、剑指 Offer 58 - II. 左旋转字符串

题：

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

1 <= k < s.length <= 10000

解：

解题思路：

字符串切片 注意 substring [ ) 范围区间

AC代码：

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n,s.length()) + s.substring(0,n);
    }
}

• 时间复杂度 O(N) ： 其中 N 为字符串 s 的长度，字符串切片函数为线性时间复杂度。
• 空间复杂度 O(N)： 两个字符串切片的总长度为 N 。
  

解题思路：

字符串遍历添加

AC代码：

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for(int i = n; i < len; i++){
            sb.append(s.charAt(i));
        }
        for(int i = 0; i < n; i++){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

• 时间复杂度 O(N) ： 线性遍历 s 并添加，使用线性时间。
• 空间复杂度 O(N) ： 新建的辅助 sb 使用 O(N) 大小的额外空间。

解题思路：

三次翻转（C++） c++中字符串可变

AC代码：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverseString(s, 0, n - 1);
        reverseString(s, n, s.size() - 1);
        reverseString(s, 0, s.size() - 1);
        return s;
    }
private:
    void reverseString(string& s, int i, int j) {
        while(i < j) swap(s[i++], s[j--]);
    }
};

或者直接使用库函数

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

九、剑指 Offer 59 - I. 滑动窗口的最大值

题：

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 

解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

解：

解题思路：单调递减队列 – 双端队列

AC代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(len <= 1 || nums == null) return nums;
        // 储存最大值
        LinkedList<Integer> deque = new LinkedList<>();
        int[] res = new int[len - k + 1];
        for(int i = 0; i < len; i++){
            // 从后往前匹配，保证非严格递减
            while(!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
                deque.removeLast();
            }
            deque.addLast(i);
            if(deque.getFirst() <= i-k){
                deque.removeFirst();
            }
            // 窗口是否完全进入
            if(i+1 >= k){
                res[i + 1 - k] = nums[deque.getFirst()];
            }
        }
        return res;
    }
}

• 时间复杂度 O(n)： 其中 n 为数组 numsnums 长度；线性遍历 nums占用 O(n)；每个元素最多仅入队和出队一次，因此单调队列 deque 占用 O(2n) 。
• 空间复杂度 O(k) ： 双端队列 deque 中最多同时存储 k 个元素（即窗口大小）。

十、剑指 Offer 59 - II. 队列的最大值

题：

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

解：

解题思路：单调递减队列 – 双端队列
AC代码：

class MaxQueue {

    LinkedList<Integer> A;
    LinkedList<Integer> B;
    
    public MaxQueue() {
        A = new LinkedList<>();
        B = new LinkedList<>();
    }
    
    public int max_value() {
        return B.isEmpty() ? -1 : B.getFirst();
    }
    
    public void push_back(int value) {
        A.addLast(value);
        while(!B.isEmpty() && value > B.getLast()){
            B.removeLast();
        }
        B.addLast(value);
    }
    
    public int pop_front() {
        if(A.isEmpty()) return -1;
        if(A.getFirst().equals(B.getFirst())){
            B.removeFirst();
        }
        return A.removeFirst();
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

十一、剑指 Offer 67. 把字符串转换成整数

题：

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [?231, 231 ? 1]。如果数值超过这个范围，请返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
 因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
 因此返回 INT_MIN (?231) 。

解：

解题思路：
图解：

AC代码：

class Solution {
    public int strToInt(String str) {
        // 去除空格
        str = str.trim();

        int len = str.length();
        // 空字符串去除
        if(len == 0) return 0;
        
        int index = 0; // 遍历指针
        int sign = 1; // 默认为正
        // 符号位判断
        if(str.charAt(index) == '-' || str.charAt(index) == '+'){
            sign = str.charAt(index) == '+' ? 1 : -1;
            index ++;
        }       
        int res = 0;
        for(; index < len; index++){
            // 字符转数字
            int digit = str.charAt(index) - '0';
            // 遇到非数字
            if(digit < 0 || digit > 9) break;
            // 越界处理
            if(res > Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && digit > Integer.MAX_VALUE%10){
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + digit;
        }
        return sign * res;
    }
}

解题思路：有限状态机
AC代码：

class Solution {
    public int myAtoi(String s) {
        // 状态机规定：' '空格 's'符号 'n'数字 '？'字母 
        Map[] states = {
            new HashMap<>(){{put(' ',0); put('s',1); put('n',2);}} // 空格
            ,new HashMap<>(){{put('n',2);}} // 符号
            ,new HashMap<>(){{put('n',2);}} // 数字
        };
        // 合法结束状态：2,3
        int p = 0;
        char t;
        // 符号，结果，符号是否出现
        int sign = 1, res = 0;
        boolean flag = false;
        for(char c : s.toCharArray()){
            if(c >= '0' && c <= '9'){
                t = 'n';
                flag = true;
                int digit = c - '0';
                if(res > Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && digit > Integer.MAX_VALUE%10){
                    return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }
                res = res * 10 + digit;
            } 
            else if(c == '+' || c == '-' ){
                t = 's';
                if(flag == false){
                    sign = c == '+' ? 1 : -1;
                    flag = true;
                }               
            } 
            else if(c == ' ') t = ' ';
            else t = '?';
            if(!states[p].containsKey(t)) break;
            p = (int)states[p].get(t);
        }
        return res;
    }
}

总结

• LinkedList 真香！
• 单调栈 真香！
• 总结 真香！