【LeetCode】《剑指Offer》第Ⅲ篇⊰⊰⊰ 20 - 31题

约定不等于承诺〃 2022-11-03 11:57 2阅读 0赞

## 【LeetCode】《剑指Offer》第Ⅲ篇⊰⊰⊰ 20 - 31题 ##

### 文章目录 ###

*   *  【LeetCode】《剑指Offer》第Ⅲ篇⊰⊰⊰ 20 - 31题
     *   *  20. 表示数值的字符串（medium）
         *  21. 调整数组顺序使奇数位于偶数前面（easy）
         *  22. 链表中倒数第k个节点（easy）
         *  24. 反转链表（easy）
         *  25. 合并两个排序的链表（easy）
         *  26. 树的子结构（medium）
         *  27. 二叉树的镜像（easy）
         *  28. 对称的二叉树（easy）
         *  29. 顺时针打印矩阵（easy）
         *  30. 包含min函数的栈（easy）
         *  31. 栈的压入、弹出序列（medium）

### 20. 表示数值的字符串（medium） ###

[剑指 Offer 20. 表示数值的字符串][Offer 20.]

【**题目**】请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

【**解题思路**】

正则表达式

class Solution {
        
        public boolean isNumber(String s) {
        
            if(s.matches("(.[\\s]+[0-9]+)|([0-9]+[\\t]+.)")){
        
                return false;
            }
            s = s.replaceAll("\\s", "");
            if(s.matches("(e[+-]?[0-9]*)|([0-9]+e)")){
        
                return false;
            }
            return s.matches("(([+-]?[0-9]+(.[0-9]*)?)|(.[0-9]+))([+-]?e[+-]?[0-9]+)?");
        }
    }

--------------------

### 21. 调整数组顺序使奇数位于偶数前面（easy） ###

[剑指 Offer 21. 调整数组顺序使奇数位于偶数前面][Offer 21.]

【**题目**】输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

**提示：**

1.  `0 <= nums.length <= 50000`
2.  `1 <= nums[i] <= 10000`

【**示例**】

输入：nums = [1,2,3,4]
    输出：[1,3,2,4] 
    注：[3,1,2,4] 也是正确的答案之一。

【**解题思路**】

双指针

class Solution {
        
        public int[] exchange(int[] nums) {
        
            if (nums.length < 2) return nums;
            int le = 0, ri = nums.length - 1;
            while (le < ri) {
        
                if (nums[le] % 2 == 0) {
        
                    while (ri > le && nums[ri] % 2 == 0) ri--;
                    int t = nums[le];
                    nums[le] = nums[ri];
                    nums[ri] = t;
                } else {
        
                    le++;
                }
            }
            return nums;
        }
    }

--------------------

### 22. 链表中倒数第k个节点（easy） ###

[剑指 Offer 22. 链表中倒数第k个节点][Offer 22. _k]

【**题目**】输入一个链表，输出该链表中倒数第`k`个节点。为了符合大多数人的习惯，本题从`1`开始计数，即链表的尾节点是倒数第`1`个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

【**示例**】

给定一个链表: 1->2->3->4->5, 和 k = 2.
    返回链表 4->5.

【**解题思路**】

快慢指针

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode getKthFromEnd(ListNode head, int k) {
        
            ListNode fast = head, slow = head;
            while (k-- > 0) fast = fast.next;
            while (fast != null) {
        
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

--------------------

### 24. 反转链表（easy） ###

[剑指 Offer 24. 反转链表][Offer 24.]

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

**限制：**

`0 <= 节点个数 <= 5000`

【**示例**】

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

【**解题思路**】

方法一：迭代

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            ListNode dummy = new ListNode(-1);
            ListNode p = null;
            while (head != null) {
        
                p = head;
                head = head.next;
                p.next = dummy.next;
                dummy.next = p;
            }
            return dummy.next;
        }
    }

方法二：递归

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null || head.next == null) return head;
            ListNode newHead = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }

--------------------

### 25. 合并两个排序的链表（easy） ###

[剑指 Offer 25. 合并两个排序的链表][Offer 25.]

【**题目**】输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

**注意**：`0 <= 链表长度 <= 1000`

【**示例**】

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

【**解题思路**】

方法一：迭代

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (l1 != null && l2 != null) {
        
                if (l1.val < l2.val) {
        
                    cur.next = l1;
                    l1 = l1.next;
                } else {
        
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }

方法二：递归

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            if (l1 == null) {
        
                return l2;
            } else if (l2 == null) {
        
                return l1;
            } else if (l1.val < l2.val) {
        
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
        
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }

--------------------

### 26. 树的子结构（medium） ###

[剑指 Offer 26. 树的子结构][Offer 26.]

【**题目**】  
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

**注意**：`0 <= 节点个数 <= 10000`

【**示例**】

树A:              树B:
         3             4
       /   \          /
      4     5        1
     / \
    1   2
    返回true

【**解题思路**】

class Solution {
        
        public boolean isSubStructure(TreeNode A, TreeNode B) {
        
            if (B == null) return false;
            return f(A, B);
        }
    
        private boolean f(TreeNode A, TreeNode B) {
        
            if (A == null) return false;
            if (A.val == B.val && isSame(A, B)) return true;
            return f(A.left, B) || f(A.right, B);
        }
    
        private boolean isSame(TreeNode a, TreeNode b) {
        
            if (b == null) return true;
            if (a == null || a != null && a.val != b.val) return false;
            return isSame(a.left, b.left) && isSame(a.right, b.right); 
        }
    }

--------------------

### 27. 二叉树的镜像（easy） ###

[剑指 Offer 27. 二叉树的镜像][Offer 27.]

【**题目**】请完成一个函数，输入一个二叉树，该函数输出它的镜像。

【**示例**】

输入：root = [4,2,7]
    输出：[4,7,2]
    如            4                   4
                /  \       镜像为    /  \
               2    7              7    2

【**解题思路**】

class Solution {
        
        public TreeNode mirrorTree(TreeNode root) {
        
            if (root == null) return null;
            TreeNode node = root.left;
            root.left = mirrorTree(root.right);
            root.right = mirrorTree(node);
            return root;
        }
    }

--------------------

### 28. 对称的二叉树（easy） ###

[剑指 Offer 28. 对称的二叉树][Offer 28.]

【**题目**】请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

**限制：**

`0 <= 节点个数 <= 1000`

【**示例**】

如      1
          /  \
         2    2
        /      \
       3        3     是一棵对称二叉树

【**解题思路**】

方法一：

联系上一题二叉树的镜像，先求出镜像，然后判断是否相等即可

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            TreeNode mirror = mirrorTree(root);
            return isSame(root, mirror);
        }
        
        private TreeNode mirrorTree(TreeNode root) {
        
            if (root == null) return null;
            TreeNode node = new TreeNode(root.val);
            node.right = mirrorTree(root.left);
            node.left = mirrorTree(root.right);
            return node;
        }
    
        private boolean isSame(TreeNode root, TreeNode mirror) {
        
            if (root == null && mirror == null) return true;
            if (root == null || mirror == null) return false;
            if (root.val != mirror.val) return false;
            return isSame(root.left, mirror.left) && isSame(root.right, mirror.right);
        }
    }

方法二：

观察发现并不需要特意求出其对应的镜像树，只需按不同的顺序遍历即可

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) return true;
            return isSame(root.left, root.right);
        }
        private boolean isSame(TreeNode t1, TreeNode t2) {
        
            if (t1 == null && t2 == null) return true;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            return isSame(t1.left, t2.right) && isSame(t1.right, t2.left);
        }
    }

--------------------

### 29. 顺时针打印矩阵（easy） ###

[剑指 Offer 29. 顺时针打印矩阵][Offer 29.]

【**题目**】输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

**限制：**

*  `0 <= matrix.length <= 100`
 *  `0 <= matrix[i].length <= 100`

【**示例**】

输入：matrix = [[1,2,3],
                   [4,5,6],
                   [7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]

【**解题思路**】

class Solution {
        
        public int[] spiralOrder(int[][] matrix) {
        
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        
                return new int[]{
        };
            }
            List<Integer> list = new ArrayList<>();
            int left = 0, right = matrix[0].length - 1;
            int top = 0, bottom = matrix.length - 1;
            int [] res = new int[matrix.length * matrix[0].length];
            int k = 0;
    
            while (left <= right && top <= bottom) {
        
                for (int i = left; i <= right; i++)     res[k++] = matrix[top][i];
                for (int i = top + 1; i <= bottom; i++) res[k++] = matrix[i][right];
                if (left < right && top < bottom) {
        
                    for (int i = right - 1; i > left; i--)  res[k++] = matrix[bottom][i];
                    for (int i = bottom; i > top; i--)      res[k++] = matrix[i][left];
                }
                top++;
                bottom--;
                left++;
                right--;
            }
            return res;
        }
    }

--------------------

### 30. 包含min函数的栈（easy） ###

[剑指 Offer 30. 包含min函数的栈][Offer 30. _min]

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

**提示：**

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

‘【**示例**】

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

【**解题思路**】

单调栈

class MinStack {
        
    
        private Stack<Integer> valStack;
        private Stack<Integer> minStack;
        
        /** initialize your data structure here. */
        public MinStack() {
        
            this.minStack = new Stack<>();
            this.valStack = new Stack<>();
        }
        
        public void push(int x) {
        
            if(minStack.isEmpty()){
        
                minStack.push(x);
            }else{
        
                if(x <= this.min()){
        
                    minStack.push(x);
                }
            }
            valStack.push(x);
        }
        
        public void pop() {
        
            if(valStack.isEmpty()){
        
                throw new RuntimeException("stack is empty");
            }
            if(valStack.peek() == this.min()){
        
                minStack.pop();
            }
            valStack.pop();
        }
        
        public int top() {
        
            return valStack.peek();
        }
        
        public int min() {
        
            if(minStack.isEmpty()){
        
                throw new RuntimeException();
            }
            return minStack.peek();
        }
    }

--------------------

### 31. 栈的压入、弹出序列（medium） ###

[剑指 Offer 31. 栈的压入、弹出序列][Offer 31.]

【**题目**】输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 \{1,2,3,4,5\} 是某栈的压栈序列，序列 \{4,5,3,2,1\} 是该压栈序列对应的一个弹出序列，但 \{4,3,5,1,2\} 就不可能是该压栈序列的弹出序列。

提示：

*  `0 <= pushed.length == popped.length <= 1000`
 *  `0 <= pushed[i], popped[i] < 1000`
 *  `pushed` 是 `popped` 的排列。

【**示例**】

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出：true
    解释：我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

【**解题思路**】

模拟

class Solution {
        
        public boolean validateStackSequences(int[] pushed, int[] popped) {
        
            Stack<Integer> stack = new Stack<>();
            int pushI = 0, popI = 0;
            while (pushI < pushed.length) {
        
                stack.push(pushed[pushI++]);
                while (!stack.isEmpty() && stack.peek() == popped[popI]) {
        
                    stack.pop();
                    popI++;
                }
            }
            return stack.isEmpty();
        }
    }

[Offer 20.]: https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
[Offer 21.]: https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
[Offer 22. _k]: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[Offer 24.]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[Offer 25.]: https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[Offer 26.]: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
[Offer 27.]: https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
[Offer 28.]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[Offer 29.]: https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
[Offer 30. _min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[Offer 31.]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/