【直通BAT】剑指Offer-经典试题整理(3)

青旅半醒 2022-02-15 13:07 197阅读 0赞

### 22 链表中倒数第k个节点 ###

来源：AcWing

题目描述  
输入一个链表，输出该链表中倒数第k个结点。

解法  
pre 指针走 k-1 步。之后 cur 指针指向 phead，然后两个指针同时走，直至 pre 指针到达尾结点。

当用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些。

此题需要考虑一些特殊情况。比如 k 的值小于 0 或者大于链表长度。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        /** * 找出链表倒数第k个节点，k从1开始 * @param head 链表头部 * @param k 第k个节点 * @return 倒数第k个节点 */
        public ListNode FindKthToTail(ListNode head,int k) { 
            if (head == null || k < 1) { 
                return null;
            }
    
            ListNode pre = head;
            for (int i = 0; i < k - 1; ++i) { 
                if (pre.next != null) { 
                    pre = pre.next;
                } else { 
                    return null;
                }
            }
    
            ListNode cur = head;
            while (pre.next != null) { 
                pre = pre.next;
                cur = cur.next;
            }
            return cur;
        }
    }

### 23 链表中环的入口结点 ###

来源：AcWing

题目描述  
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解法  
先利用快慢指针。若能相遇，说明存在环，且相遇点一定是在环上；若没有相遇，说明不存在环，返回 null。

固定当前相遇点，用一个指针继续走，同时累积结点数。计算出环的结点个数 cnt。

指针 p1 先走 cnt 步，p2 指向链表头部，之后 p1,p2 同时走，相遇时，相遇点一定是在环的入口处。因为 p1 比 p2多走了环的一圈。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    public class Solution { 
    
        /** * 求链表环的入口，若没有环，返回null * @param pHead 链表头 * @return 环的入口点 */
        public ListNode EntryNodeOfLoop(ListNode pHead) { 
            if (pHead == null || pHead.next == null) { 
                return null;
            }
            ListNode fast = pHead;
            ListNode slow = pHead;
            boolean flag = false;
            while (fast != null && fast.next != null) { 
                slow = slow.next;
                fast = fast.next.next;
                if (fast == slow) { 
                    flag = true;
                    break;
                }
            }
    
            // 快指针与慢指针没有相遇，说明无环，返回 null
            if (!flag) { 
                return null;
            }
    
            ListNode cur = slow.next;
            // 求出环中结点个数
            int cnt = 1;
            while (cur != slow) { 
                cur = cur.next;
                ++cnt;
            }
    
            // 指针p1先走cnt步
            ListNode p1 = pHead;
            for (int i = 0; i < cnt; ++i) { 
                p1 = p1.next;
            }
    
            // p2指向链表头，然后p1/p2同时走，首次相遇的地方就是环的入口
            ListNode p2 = pHead;
            while (p1 != p2) { 
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }

### 24 反转链表 ###

来源：AcWing

题目描述  
输入一个链表，反转链表后，输出新链表的表头。

解法  
解法一  
利用头插法解决。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode reverseList(ListNode head) { 
            if (head == null || head.next == null) { 
                return head;
            }
            ListNode dummy = new ListNode(-1);
            ListNode p = head;
            ListNode q = head.next;
            while (q != null) { 
                p.next = dummy.next;
                dummy.next = p;
                p = q;
                q = p.next;
            }
            p.next = dummy.next;
            return p;
        }
    }

**解法二：递归**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode reverseList(ListNode head) { 
            if (head == null || head.next == null) { 
                return head;
            }
            ListNode node = reverseList(head.next);
            ListNode cur = node;
            while (cur.next != null) { 
                cur = cur.next;
            }
            cur.next = head;
            head.next = null;
            return node;
        }
    }

### 25 合并两个排序的链表 ###

来源：AcWing

题目描述  
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

样例

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

**解法**  
解法一  
同时遍历两链表进行 merge。

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

**解法二：递归**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode merge(ListNode l1, ListNode l2) { 
            if (l1 == null) { 
                return l2;
            }
            if (l2 == null) { 
                return l1;
            }
            if (l1.val < l2.val) { 
                l1.next = merge(l1.next, l2);
                return l1;
            }
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }

### 26 树的子结构 ###

来源：AcWing

题目描述  
输入两棵二叉树 A、B，判断 B 是不是 A 的子结构。

我们规定空树不是任何树的子结构。

样例

树 A：

8
        / 
       8   7
      / 
     9   2
        / 
       4   7

树 B：

8
      / 
     9   2

返回 true ,因为 B 是 A 的子结构。

**解法**  
递归方式遍历：

*  在树 A 中找到和树 B 的根结点值一样的结点 R；
 *  判断树 A 以 R 为根结点的子树是否包含与树 B 一样的结构。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) { 
            boolean res = false;
            if (pRoot1 != null && pRoot2 != null) { 
                if (pRoot1.val == pRoot2.val) { 
                    res = isSame(pRoot1, pRoot2);
                }
                if (!res) { 
                    res = hasSubtree(pRoot1.left, pRoot2);
                }
                if (!res) { 
                    res = hasSubtree(pRoot1.right, pRoot2);
                }
            }
            return res;
            
        }
        
        private boolean isSame(TreeNode root1, TreeNode root2) { 
            if (root2 == null) { 
                return true;
            }
            if (root1 == null || root1.val != root2.val) { 
                return false;
            }
            return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
        }
    }

### 27 二叉树的镜像 ###

来源：AcWing

题目描述  
输入一个二叉树，将它变换为它的镜像。

样例

输入树：

8
         / 
        6  10
       /  / 
      5  7 9 11

\[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null\]  
输出树：

8
         / 
        10  6
       /  / 
      11 9 7  5

\[8,10,6,11,9,7,5,null,null,null,null,null,null,null,null\]  
**解法**  
将根结点的左右孩子互换，之后递归左右孩子。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public void mirror(TreeNode root) { 
            if (root == null || (root.left == null && root.right == null)) { 
                return;
            }
            TreeNode t = root.left;
            root.left = root.right;
            root.right = t;
            mirror(root.left);
            mirror(root.right);
        }
    }

### 28 对称的二叉树 ###

来源：AcWing

题目描述  
请实现一个函数，用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样，那么它是对称的。

样例

如下图所示二叉树\[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null\]为对称二叉树：

1
       / 
      2   2
     /  / 
    3  4 4  3

如下图所示二叉树\[1,2,2,null,4,4,3,null,null,null,null,null,null\]不是对称二叉树：

1
       / 
      2   2
        / 
       4 4  3

解法  
比较二叉树的前序遍历序列和对称前序遍历序列是否一样，若是，说明是对称的。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            return isSymmetric(root, root);
        }
        
        private boolean isSymmetric(TreeNode root1, TreeNode root2) { 
            if (root1 == null && root2 == null) { 
                return true;
            }
            if (root1 == null || root2 == null || root1.val != root2.val) { 
                return false;
            }
            return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
        }
    }

### 29 顺时针打印矩阵 ###

来源：AcWing

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

样例

> 输入：  
> \[  
> \[1, 2, 3, 4\],  
> \[5, 6, 7, 8\],  
> \[9,10,11,12\]  
> \]
> 
> 输出：\[1,2,3,4,8,12,11,10,9,5,6,7\]

**解法**  
由外往里，一圈圈打印矩阵即可。

class Solution { 
        public int[] printMatrix(int[][] matrix) { 
            if (matrix == null || matrix.length < 1) { 
                return new int[] { };
            }
            int m = matrix.length, n = matrix[0].length;
            int[] res = new int[m * n];
            int[] index = new int[1];
            index[0] = 0;
            int i = 0, j = 0, p = m - 1, q = n - 1;
            while (i <= p && j <= q) { 
                add(matrix, res, index, i++, j++, p--, q--);
            }
            return res;
        }
        
        private void add(int[][] matrix, int[] res, int[] index, int i, int j, int p, int q) { 
            if (i == p) { 
                for (int m = j; m <= q; ++m) { 
                    res[index[0]++] = matrix[i][m];
                }
            } else if (j == q) { 
                for (int m = i; m <= p; ++m) { 
                    res[index[0]++] = matrix[m][j];
                }
            } else { 
                for (int m = j; m < q; ++m) { 
                    res[index[0]++] = matrix[i][m];
                }
                for (int m = i; m < p; ++m) { 
                    res[index[0]++] = matrix[m][q];
                }
                for (int m = q; m > j; --m) { 
                    res[index[0]++] = matrix[p][m];
                }
                for (int m = p; m > i; --m) { 
                    res[index[0]++] = matrix[m][j];
                }
            }
            
        }
    }

### 30 包含min函数的栈 ###

来源：AcWing

题目描述  
设计一个支持 push，pop，top 等操作并且可以在 O(1) 时间内检索出最小元素的堆栈。

*  push(x)–将元素x插入栈中
 *  pop()–移除栈顶元素
 *  top()–得到栈顶元素
 *  getMin()–得到栈中最小元素

样例

MinStack minStack = new MinStack();
    minStack.push(-1);
    minStack.push(3);
    minStack.push(-4);
    minStack.getMin();   --> Returns -4.
    minStack.pop();
    minStack.top();      --> Returns 3.
    minStack.getMin();   --> Returns -1.

**解法**  
定义两个stack。

压栈时，先将元素 x 压入 stack1。然后判断 stack2 的情况：

*  stack2 栈为空或者栈顶元素大于 x，则将 x 压入 stack2 中。
 *  stack2 栈不为空且栈定元素小于 x，则重复压入栈顶元素。

获取最小元素时，从 stack2 中获取栈顶元素即可。

class MinStack { 
    
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;
    
        /** initialize your data structure here. */
        public MinStack() { 
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }
        
        public void push(int x) { 
            stack1.push(x);
            if (stack2.isEmpty() || stack2.peek() > x) { 
                stack2.push(x);
            } else { 
                stack2.push(stack2.peek());
            }
        }
        
        public void pop() { 
            stack1.pop();
            stack2.pop();
        }
        
        public int top() { 
            return stack1.peek();
        }
        
        public int getMin() { 
            return stack2.peek();
        }
    }
    
    /** * 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.getMin(); */

31 栈的压入、弹出序列  
来源：AcWing

题目描述  
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

注意：若两个序列为空或长度不等则视为并不是一个栈的压入、弹出序列。

样例

> 输入：\[1,2,3,4,5\]  
> \[4,5,3,2,1\]
> 
> 输出：true

**解法**  
判断下一个要弹出的元素：

*  如果刚好是栈顶元素，直接弹出。
 *  如果不在栈顶，则把压栈序列中还没有入栈的数字压入栈，直到待弹出的数字压入栈顶。
 *  如果所有数字都压入栈顶后依然没有后找到下一个弹出的数字，则不可能是弹出序列。

import java.util.Stack;
    
    public class Solution { 
        /** * 判断是否是弹出序列 * @param pushA 压栈序列 * @param popA 弹栈序列 * @return 是否是弹出序列 */
        public boolean IsPopOrder(int[] pushA,int[] popA) { 
            if (pushA == null || popA == null || pushA.length != popA.length) { 
                return false;
            }
    
            Stack<Integer> stack = new Stack<>();
            int i = 0;
            int n = pushA.length;
            boolean flag = false;
            for (int val : popA) { 
                while (stack.isEmpty() || stack.peek() != val) { 
                    if (i >= n) { 
                        flag = true;
                        break;
                    }
                    stack.push(pushA[i++]);
                }
                if (flag) { 
                    break;
                }
                stack.pop();
            }
    
            return stack.isEmpty();
        }
    }

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

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号\*\*`菜鸟名企梦`**后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“资料”:即可领取**5T精品学习资料\*\*、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

**推荐阅读**

[☞【直通BAT】剑指Offer-经典试题整理(1)][BAT_Offer-_1]

[☞【直通BAT】剑指Offer-经典试题整理(2)][BAT_Offer-_2]

[1240]: /images/20220215/e2a67ae3e2ec40ad8f49033c46a439f0.png
[BAT_Offer-_1]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247485255&idx=2&sn=b2f9cf433469bde8523c1185810313e9&chksm=eb5124b3dc26ada549ab0b2d61b3422087228511dfd39166c8bc4e2e2e241fa61e58f8f6e6b4&scene=21#wechat_redirect
[BAT_Offer-_2]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247485276&idx=2&sn=784ebaf30c07033fc1384b7752d2c754&chksm=eb5124a8dc26adbe159439e22bc1049f84658ff255697e5d13754769abdb0cc2e4ef2c3089cf&scene=21#wechat_redirect