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

￡神魔★判官ぃ 2022-11-17 05:14 72阅读 0赞

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

今天是剑指Offer的第五期，

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

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

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

### 四十五、把数组排成最小的数 ###

*  问题

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

平时排数的核心思想就是把数小的放前面，数大的放后面，这样就能得到一个最小的数。

但是由于这次给的数不是一个单一的数而是一个数组，所以我们要另外定义一套大小，通过这套大小进行排序，最后按照顺序输出数。

关于大小的规则，即那个放前面得到的数小即他的权重小，即为小数。即有x,y两个数如果xy>yx那么x大于y。

class Solution {
        public String minNumber(int[] nums) {
            String[] strs = new String[nums.length];
            for (int i = 0; i < nums.length; i++)
                strs[i] = String.valueOf(nums[i]);
            Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
            StringBuilder ans = new StringBuilder();
            for (String s : strs) {
                ans.append(s);
            }
            return ans.toString();
        }
    }

### 四十六、把数字翻译成字符串 ###

*  问题

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

首先我们要明确下什么样子的数字能翻译成字母，只有单独一位或者数字在10-25之间的可以连起来翻译。

另外可以使用滚动数组来优化动态规划。

class Solution {
        public int translateNum(int num) {
            String s = String.valueOf(num);
            int p = 0, q = 0, r = 1;
            for (int i = 0; i < s.length(); i++) {
                p = q;
                q = r;
                r = 0;
                r += q;
                if (i == 0) {
                    continue;
                }
                String pre = s.substring(i - 1, i + 1);
                if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                    r += p;
                }
            }
            return r;
        }
    }

### 四十七、礼物的最大价值 ###

*  问题

在一个 m\*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

这个题目很明显就是动态规划，直接干就完事了

class Solution {
        public int maxValue(int[][] grid) {
            int row = grid.length;
            int column = grid[0].length;
            //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
            int[][] dp = new int[row + 1][column + 1];
            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= column; j++) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
                }
            }
            return dp[row][column];
        }
    }

### 四十八、最长不含重复字符的子字符串 ###

*  问题

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

这个题目在前面的思维私塾滑动数组中说过，就不在赘述了

class Solution {
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int i = -1, res = 0;
            for(int j = 0; j < s.length(); j++) {
                if(dic.containsKey(s.charAt(j)))
                    i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
                dic.put(s.charAt(j), j); // 哈希表记录
                res = Math.max(res, j - i); // 更新结果
            }
            return res;
        }
    }

### 四十九、丑数 ###

*  问题

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

PS：1是丑数

首先我们要明确除了第一个丑数一以外，其他的丑数都是由现有的丑数乘以2.3.5得来的，所以当我们确定n个数后下一个数一定是前面的数乘以2.3.5得来的，所以我们只需要比较还没有乘以2.3.5的数中乘以了以后那个最小，那个就是下一个数。结合代码和注释理解起来更加方便。

代码如下所示

class Solution {
        public int nthUglyNumber(int n) {
            int ans[] = new int[n];
            ans[0] = 1;
            //abc分别记录着乘以2.3.5乘到那个数了，因为最小值的产生之可能从这里产生
            int a = 0, b = 0, c = 0;
            for (int i = 1; i < n; i++) {
                int n2 = ans[a] * 2;
                int n3 = ans[b] * 3;
                int n5 = ans[c] * 5;
                ans[i] = Math.min(Math.min(n2, n3), n5);
                // 这里不能用if else 因为有的数可能同时是乘以2乘以三乘以五得到的。
                if (ans[i] == n2)
                    a++;
                if (ans[i] == n3)
                    b++;
                if (ans[i] == n5)
                    c++;
            }
            return ans[n - 1];
        }
    }

### 五十、只出现一次的字符 ###

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

这个题目可以使用哈希表统计一下各个字符出现的次数，然后找到只出现一次的即可，进一步优化一下就是，由于我们只关心只出现一次的，所以我们map的结构可以简单设为char-boolean。当发现已经有一个字符了，我们就将boolean设置为false

class Solution {
        public char firstUniqChar(String s) {
            HashMap<Character, Boolean> map = new HashMap();
            char[] ch = s.toCharArray();
            for (char c : ch) {
                map.put(c, !map.containsKey(c));
            }
            for (char c : ch) {
                if (map.get(c))
                    return c;
            }
            return ' ';
    
        }
    }

### 五十一、数组中的逆序对 ###

*  问题

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

这个题显而易见的方法就是暴力求解，但是时间复杂度是两个for循环嵌套。肯定是不行的，其中涉及到很多的重复计算。

重复计算的关键点是在于我们不知道当前这个元素的大小关系，以至于我们每次都是要重新for循环来遍历一遍，但是一旦我们知道了有哪些数字比我们小，我们就能简化这个过程。

所以我们需要的是一个阶段的有序，而在我们学习的排序算法中，有非常明显的阶段排序结构的算法就是归并排序。我们可以利用归并的过程来加速我们的查找。

当我们归并过程中，将两个有序数组归并成一个大的有序数组的时候，当后面的元素要进入排序数组的时候，即说明它比前面那个数组中暂存的所有数据都小，而比其后面的所有数字都大，所以这个时候，就可以很轻松的算出这个数字的逆序对有几个。一次类推来解决整个问题

class Solution {
        public int reversePairs(int[] nums) {
            int len = nums.length;
            if (len < 2)
                return 0;
            int[] copy = new int[len];
            for (int i = 0; i < len; i++) {
                copy[i] = nums[i];
            }
            int[] temp = new int[len];
            return reversePairs(copy, 0, len - 1, temp);
        }
    
        // 计算逆序对并排序
        private int reversePairs(int[] nums, int left, int right, int[] temp) {
            if (left == right)
                return 0;
            // 防止越界的常规处理
            int mid = left + (right - left) / 2;
            int leftPairs = reversePairs(nums, left, mid, temp);
            int rightPairs = reversePairs(nums, mid + 1, right, temp);
            if (nums[mid] <= nums[mid + 1])
                return leftPairs + rightPairs;
            int crossPairs = mergeAndCount(nums, left, mid, right, temp);
            return leftPairs + rightPairs + crossPairs;
        }
    
        private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
            for (int i = left; i <= right; i++)
                temp[i] = nums[i];
    
            int i = left;
            int j = mid + 1;
    
            int count = 0;
            for (int k = left; k <= right; k++) {
    
                if (i == mid + 1) {
                    nums[k] = temp[j];
                    j++;
                } else if (j == right + 1) {
                    nums[k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
                    nums[k] = temp[i];
                    i++;
                } else {
                    nums[k] = temp[j];
                    j++;
                    count += (mid - i + 1);
                }
            }
            return count;
    
    
        }
    }

### 五十二、两个链表的第一个公共节点 ###

*  问题

输入两个链表，找出它们的第一个公共节点。

看到这种找相同的就想到set来寻找，方法很见到，就是先把第一个链表的节点进行遍历，存放到set集合中，然后遍历第二个链表的节点，寻找是否在set中

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //创建集合set
        Set<ListNode> set = new HashSet<>();
        //先把链表A的结点全部存放到集合set中
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
    
        //然后访问链表B的结点，判断集合中是否包含链表B的结点，如果包含就直接返回
        while (headB != null) {
            if (set.contains(headB))
                return headB;
            headB = headB.next;
        }
        //如果集合set不包含链表B的任何一个结点，说明他们没有交点，直接返回null
        return null;
    }

第二种方法就是双指针法，设立两个指针，第一个指向A，第二个指向B，每次向后移动并判断节点是否相等。如果AB两个链表长度一样，则会相交，要是不一样，那么我们当A指针走完的时候接着走B，B走完的时候接着走A这样就能保证他们一定可以相遇。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            //如果指针tempA不为空，tempA就往后移一步。
            //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;
        }
        //tempA要么是空，要么是两链表的交点
        return tempA;
    }

### 五十三、在排序数组中查找数字 ###

*  问题

统计一个数字在排序数组中出现的次数。

查找数字，我们第一时间想到的肯定是二分查找，即先使用二分查找查找找到目标数字，然后再向两边进行查找，直到都找出来，但是这样会增加我们的时间复杂度，使我们的时间复杂度和直接遍历一样。

问题出在我们在找到目标数字后挨着两边寻找，导致了线性的时间复杂度，应该是继续采用二分查找来找寻左边界和右边界。

class Solution {
        public int search(int[] nums, int target) {
            // 搜索右边界 right
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) / 2;
                if (nums[m] <= target)
                    i = m + 1;
                else
                    j = m - 1;
            }
            int right = i;
            // 若数组中无 target ，则提前返回
            if (j >= 0 && nums[j] != target)
                return 0;
            // 搜索左边界 right
            i = 0;
            j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) / 2;
                if (nums[m] < target)
                    i = m + 1;
                else
                    j = m - 1;
            }
            int left = j;
            return right - left - 1;
        }
    }

#### 拓展：0~n中缺失的数字 ####

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

这个题目给了一个有力的条件就是有序数组，要是不是有序数组的话，那就需要求和相减了，那既然有序了我们就可以直接根据下标和数值的关系，二分查找来解决了。

class Solution {
        public int missingNumber(int[] nums) {
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                int mid = (i + j) / 2;
                if (nums[mid] == mid)
                    i = mid + 1;
                else
                    j = mid - 1;
            }
            return i;
        }
    }

### 五十四、二叉搜索树的第K大节点 ###

*  问题

给定一棵二叉搜索树，请找出其中第k大的节点。

由于二叉搜索树的中序遍历为递减序列，所以中序遍历的倒叙为递增序列，那么该题就是求中序遍历倒叙的第K个节点

class Solution {
        int res, k;
        public int kthLargest(TreeNode root, int k) {
            this.k = k;
            dfs(root);
            return res;
        }
        void dfs(TreeNode root) {
            if(root == null)
                return;
            dfs(root.right);
            if(k == 0)
                return;
            if(--k == 0)
                res = root.val;
            dfs(root.left);
        }
    }

### 五十五、二叉树的深度 ###

*  问题

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

首先先回顾一下树的遍历方式，总体来说分为两种：

*  深度优先遍历（DFS）：先序、中序、后续遍历
 *  广度优先遍历（BFS）：层次遍历

那么接下来我们就用这两种方式来解决这个题

首先是后续遍历：

class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null)
                return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }

其次是层次遍历

class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null)
                return 0;
            List<TreeNode> queue = new LinkedList<>() {
       {
                add(root);
            }};
            List<TreeNode> tmp;
            int res = 0;
            while (!queue.isEmpty()) {
                tmp = new LinkedList<>();
                for (TreeNode node : queue) {
                    if (node.left != null)
                        tmp.add(node.left);
                    if (node.right != null)
                        tmp.add(node.right);
                }
                queue = tmp;
                res++;
            }
            return res;
        }
    }

#### 拓展：平衡二叉树 ####

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

上面的题目我们构建了一个函数来判断树的深度，而平衡二叉树就是深度差不超过1即可，那么我们用上面的函数作为铺垫直接计算即可

class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null)
                return true;
            return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        
        private int depth(TreeNode root) {
            if (root == null)
                return 0;
            return Math.max(depth(root.left), depth(root.right)) + 1;
        }
    }

### 最后 ###

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

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

![image][]

[image]: /images/20221022/206b035fe6d04be091fba793fed573db.png