【剑指Offer】解题思路拆解Java版——第四期

た入场券 2022-11-15 15:49 68阅读 0赞

下面这段时间带来的是对于剑指Offer（第二版）一书中的算法题目进行阅读并分享。原书中一共66道题目，我们就一天11道，用六天的时间来进行讲解，最后一天来个总结，争取在一周的时间内介绍完这66道经典题目。要是喜欢的欢迎关注公众号《Java冢狐》来追更！

今天是剑指Offer的第四期，

另外由于原书是C++代码编写而成，这边我们用Java来实现一遍，顺便说一下相关的面试知识点，一起进行面试前的复习。希望大家能够喜欢。

另外有些地方的讲解可能并不是十分到位，在此更推荐更大家去看原书。

那么话不多少，让我们开始今天的解题之路吧！

### 三十四、二叉树中和为某一值的路径 ###

*  问题

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

就挨着遍历，遍历过程中记录一下当前的值，然后只要满足就加入，最后直接返回即可。

LinkedList<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
    
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            recur(root, sum);
            return res;
        }
    
        void recur(TreeNode root, int tar) {
            if (root == null)
                return;
            path.add(root.val);
            tar -= root.val;
            if (tar == 0 && root.left == null && root.right == null)
                res.add(new LinkedList(path));
            recur(root.left, tar);
            recur(root.right, tar);
            path.removeLast();
        }

### 三十五、复杂链表的复制 ###

*  问题

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

public class Solution {
    
        HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();
    
        public Node copyRandomList(Node head) {
    
            if (head == null) {
                return null;
            }
    
    
            if (this.visitedHash.containsKey(head)) {
                return this.visitedHash.get(head);
            }
    
            Node node = new Node(head.val, null, null);
    
    
            this.visitedHash.put(head, node);
    
            node.next = this.copyRandomList(head.next);
            node.random = this.copyRandomList(head.random);
    
            return node;
        }
    }

### 三十六、二叉搜索树与双向链表 ###

*  问题

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

这个问题的难点在于不能创建任何新的节点，只能调整节点指向。

class Solution {
        Node head, pre;
    
        public Node treeToDoublyList(Node root) {
            if (root == null)
                return null;
            dfs(root);
            // 进行头尾节点的互指
            pre.right = head;
            head.left = pre;
            return head;
        }
    
        public void dfs(Node cur) {
            if (cur == null)
                return;
            dfs(cur.left);
    
            // pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur，当pre==null时，即cur左侧没有节点，此时cur为双向链表中的头结点
            if (pre == null)
                head = cur;
                // 反之则cur左侧存在节点pre，需要进行pre.right=cur的操作
            else
                pre.right = cur;
            cur.left = pre;
            pre = cur;
            dfs(cur.right);
        }

### 三十七、序列化二叉树 ###

*  问题

请实现两个函数，分别用来序列化和反序列化二叉树。

我们通常使用的前序、中序、后序亦或是层次遍历记录的二叉树信息都不是很完整的，即一个输出序列可能对应着多种二叉树的可能，但是题目要求序列化和反序列化是可逆操作，所以我们的序列化信息要携带完整的二叉树信息。

通过题目中给的示例提示我们可以使用记录了null节点的层次遍历来完整还原二叉树

public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null)
                return "[]";
            StringBuilder ans = new StringBuilder("[");
            Queue<TreeNode> queue = new LinkedList<>() {
       {
                add(root);
            }};
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node != null) {
                    ans.append(node.val + ",");
                    queue.add(node.left);
                    queue.add(node.right);
                } else {
                    ans.append("null,");
                }
            }
            ans.deleteCharAt(ans.length() - 1);
            ans.append("]");
            return ans.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]"))
                return null;
            String[] ans = data.substring(1, data.length() - 1).split(",");
            TreeNode root = new TreeNode(Integer.parseInt(ans[0]));
            Queue<TreeNode> queue = new LinkedList<>() {
       {
                add(root);
            }};
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (!ans[i].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(ans[i]));
                    queue.add(node.left);
                }
                i++;
                if (!ans[i].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(ans[i]));
                    queue.add(node.right);
                }
                i++;
            }
            return root;
        }
    }

### 三十八、字符串的排列 ###

*  问题

输入一个字符串，打印出该字符串中字符的所有排列。

这个问题麻烦的地方在于字符中的字符有重复的，需要我们去重，不过核心思想还是一个位置一个位置的固定来最终输出所有的元素。

class Solution {
        List<String> ans = new LinkedList<>();
        char[] c;
    
        public String[] permutation(String s) {
            c = s.toCharArray();
            dfs(0);
            return ans.toArray(new String[ans.size()]);
        }
    
        void dfs(int x) {
            if (x == c.length - 1) {
                // 添加排列方案
                ans.add(String.valueOf(c));
                return;
            }
            HashSet<Character> set = new HashSet<>();
            for (int i = x; i < c.length; i++) {
                if (set.contains(c[i]))
                    continue;
                set.add(c[i]);
                // 交换
                swap(i, x);
                // 固定下一位元素
                dfs(x + 1);
                // 恢复交换
                swap(i, x);
            }
        }
    
        void swap(int a, int b) {
            char temp = c[a];
            c[a] = c[b];
            c[b] = temp;
        }
    }

### 三十九、数组中出现次数超过一半的元素 ###

*  问题

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

这个题目一上手首先会想到哈希表法和排序法：

*  哈希表法：

遍历数组，利用哈希统计每个数组的数量，最多的即为众数

*  数组排序法

将数组排序，那么中间的数一定为众数

除此之外，还要介绍一种方法，即为摩尔投票法，其核心思想是票数正负抵消即：

*  当众数的票数即为1，非众数的票记为-1，那么所有的票数和一定大于0
 *  当数组的前a个数的票数和为0，则剩余（n-a）个数字的票数和一定大于0，即后（n-a）个数的众数仍为x

所以我们假设数组的首个元素为众数遍历统计票数，当票数和为0时剩余数组的众数一定不变，所以当票数为n的时候可以缩短剩余的数组区间，当遍历完成后，最后剩余的数字即为众数。

class Solution {
        public int majorityElement(int[] nums) {
            int ans = 0;
            int temp = 0;
            for (int c : nums) {
                if (temp == 0)
                    ans = c;
                temp += c == ans ? 1 : -1;
            }
            return ans;
    
        }
    }

### 四十、最小k个数 ###

*  问题

输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

这个题目算是面试中考察的热点，在前面的思维私塾系列文章中有所涉及，可以使用快排、大小根堆、二叉搜索树来解决。

class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            int[] ans = new int[k];
            if (k == 0)
                return ans;
            // 默认实现是小根堆，但是对于最小k个数需要的是大根堆，即需要重写一下比较器
            Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
            for (int num : arr) {
                if (pq.size() < k) {
                    pq.offer(num);
                } else if (num < pq.peek()) {
                    pq.poll();
                    pq.offer(num);
                }
            }
    
            for (int i = 0; i < k; ++i) {
                ans[i] = pq.poll();
            }
            return ans;
    
    
        }
    }

### 四十一、数据流中的中位数 ###

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如：

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

*  void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 *  double findMedian() - 返回目前所有元素的中位数。

本题的思路十分的简单，不知道Leetcode为啥给了一个困难难度。简单思路就是用一个链表来实现插入和查找，插入的时候使用二分查找来加快速度

class MedianFinder {
        List<Integer> list
    
        public MedianFinder() {
            list = new ArrayList<>();
        }
    
        public void addNum(int num) {
            int left = 0;
            int right = list.size();
            while(left<right){
                int mid = (right+left)>>1;
                if(list.get(mid)<num){
                    left = mid+1;
                }else{
                    right = mid;
                }
            }
            list.add(left,num);
        }
    
        public double findMedian() {
            if(list.size() == 0) return 0.0;
            int k = list.size();
            if(k%2==0){
                return ((double)list.get(k / 2 - 1) + list.get(k / 2)) / 2;
            }else{
                return (double)list.get(k / 2);
            }
        }
    }

或者可以借助堆来进一步来优化时间复杂度：

建立一个小顶堆A和大顶堆B各保存列表的一半元素

class MedianFinder {
        Queue<Integer> A, B;
        public MedianFinder() {
            A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
            B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
        }
        public void addNum(int num) {
            if(A.size() != B.size()) {
                A.add(num);
                B.add(A.poll());
            } else {
                B.add(num);
                A.add(B.poll());
            }
        }
        public double findMedian() {
            return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
        }
    }

### 四十二、连续子数组的最大和 ###

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

属于动态规划中一类十分经典的题目，只要明确转移方程即可，即dp\[i-1\]<0即表示产生负贡献，直接舍弃即可，重新开始取值即可。

class Solution {
        public int maxSubArray(int[] nums) {
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
                nums[i] += Math.max(nums[i - 1], 0);
                res = Math.max(res, nums[i]);
            }
            return res;
        }
    }

### 四十三、1~n整数中1出现的次数 ###

输入一个整数 `n` ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

这种题目盲目的去数肯定是不可以的，肯定是要找寻规律，我们就看一个数的各个位置出现1的次数。

我们把当前位记为cur，那么：

*  cur=0时

1出现的次数只由高位决定，即：高位\*位因子

*  cur=1时

1出现的次数比cur=0时要多出低位+1，即高位\*位因子+低位+1；

*  cur=2,3，...9时

1出现的次数相比于cur=0时要多出一次的位因子即高位\* 位因子+位因子

class Solution {
        public int countDigitOne(int n) {
            int digit = 1;
            int ans = 0;
            int high = n / 10;
            int cur = n % 10;
            int low = 0;
            while (high != 0 || cur != 0) {
                if (cur == 0)
                    ans += high * digit;
                else if (cur == 1)
                    ans += high * digit + low + 1;
                else
                    ans += (high + 1) * digit;
                low += cur * digit;
                cur = high % 10;
                high /= 10;
                digit *= 10;
            }
            return ans;
        }
    }

### 四十四、数字序列中某一位的数字 ###

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

我们要找出数字排序的规律从而能够更快的解决这个题目。

我们知道的是数位的数量等于9*位数*数字数量。

这个问题分为三步：

*  先筛选

通过位数和数量的关系，确定是在几位数

*  确定是第几个数字

然后通过剩余的数量除以位数得到是该位的第几个数字

*  返回具体的数字

确定了是第几个数字，然后确定是那个数字

class Solution {
        public int findNthDigit(int n) {
            if (n == 0)
                return 0;
            // 排除0后开始我们的计数
            // 位数
            int digit = 1;
            // 起始数字
            int start = 1;
            // 总共的数字
            long count = 9;
            // 缩小范围
            while (n > count) {
                n = (int) (n - count);
                digit++;
                start = start * 10;
                // 前面的公式
                count = (long) start * 9 * digit;
            }
            // 确定是第几个数字
            int num = start + (n - 1) / digit;
            // 确定是这个数字的第几位
            int index = (n - 1) % digit;
            // 到目前确定了是num的第index位（从高位到低位）
            while (index < (digit - 1)) {
                num = num / 10;
                digit--;
            }
            return num % 10;
    
        }
    }

### 最后 ###

*  如果觉得看完有收获，希望能关注一下，顺便给我点个赞，这将会是我更新的最大动力，感谢各位的支持
 *  欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
 *  求一键三连：点赞、转发、在看。
 *  如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。

——我是冢狐，和你一样热爱编程。

> 欢迎关注公众号“ Java冢狐”，获取最新消息