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

刺骨的言语ヽ痛彻心扉 2022-11-13 04:23 67阅读 0赞

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

今天是剑指Offer的第二期，

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

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

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

### 十二、矩阵中的路径 ###

*  问题

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

\[\["a","**b**","c","e"\],

\["s","**f**","**c**","s"\],

\["a","d","**e**","e"\]\]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

不要被这个问题给吓到了，其实很简单，程序就是擅长来执行一些循环的命令。只要我们掌握好边界就没问题了

这个题目属于回溯法的典型应用，本质就是使用递归实现，在递归结束后需要返回值或者还原现场条件。

需要注意的是，我们搜索的范围是整个矩阵，所以需要注意边界问题，另外搜索过程中我们需要记录已经搜索过的地方，不然容易陷入到无限循环和重复匹配的问题中。

public boolean exist(char[][] board, String word) {
            // 二维网格的长和宽
            int h = board.length, w = board[0].length;
            // 设置一个二维数组用于标记节点是否被访问过
            boolean[][] visited = new boolean[h][w];
            // 对二维网格中的每个结点都进行搜索
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 在二维网格中判断board[i][j] 是否等于 s[k]
        // 参数分别是原数组、已访问数组、要访问的左边xy、查找的单词组，目标单词的位置。
        public boolean check(char[][] board, boolean[][] visited, int x, int y, String word, int index) {
            // 如果搜索的点与字符串中的第k个字符不相同
            if (board[x][y] != word.charAt(index)) {
                return false;
            }
            // 整个字符串都已经找到了，返回true
            else if (index == word.length() - 1) {
                return true;
            }
            // 标记已访问，并继续搜索
            visited[x][y] = true;
            // 继续搜索的四个方向（上下左右）
            int[][] directions = {
       {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            // 用于标识接下来的搜索是否成功
            boolean result = false;
            for (int[] dir : directions) {
                int newx = x + dir[0], newy = y + dir[1];
                // 判断新坐标是否越界
                if (newx >= 0 && newx < board.length && newy >= 0 && newy < board[0].length) {
                    if (!visited[newx][newy]) {
                        boolean flag = check(board, visited, newx, newy, word, index + 1);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            // 回溯的返回过程
            visited[x][y] = false;
            return result;
        }

### 十三、机器人的运动范围 ###

地上有一个m行n列的方格，从坐标 `[0,0]` 到坐标 `[m-1,n-1]` 。一个机器人从坐标 `[0, 0]`的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 \[35, 37\] ，因为3+5+3+7=18。但它不能进入方格 \[35, 38\]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

这个题目和上个题目一样都是很经典的搜索题目，对于此种问题我们要使用广度优先搜索或者深度优先搜索来进行解决，这里介绍广度优先搜索：

public int movingCount(int m, int n, int k) {
            if (k == 0) {
                return 1;
            }
            Queue<int[]> queue = new LinkedList<int[]>();
            // 向右和向下的方向数组，因为新增的只会出现在下面或者右边，所以只需要向下或者向右进行搜索，
            int[] dx = {0, 1};
            int[] dy = {1, 0};
            boolean[][] vis = new boolean[m][n];
            queue.offer(new int[]{0, 0});
            vis[0][0] = true;
            int ans = 1;
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 2; ++i) {
                    int tx = dx[i] + x;
                    int ty = dy[i] + y;
                    if (tx >= m || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                        continue;
                    }
                    queue.offer(new int[]{tx, ty});
                    vis[tx][ty] = true;
                    ans++;
                }
            }
            return ans;
        }
    
        // 计算位数
        private int get(int x) {
            int res = 0;
            while (x != 0) {
                res += x % 10;
                x /= 10;
            }
            return res;
        }

### 十四、剪绳子 ###

给你一根长度为 `n` 的绳子，请把绳子剪成整数长度的 `m` 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 `k[0],k[1]...k[m-1]` 。请问 `k[0]*k[1]*...*k[m-1]` 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

这个问题说到底就是动态规划，只要找到动态转移方程就可以了

*  动态规划

public int cuttingRope(int n) {
            if (n <= 0)
                return 0;
            if (n == 1)
                return 1;
            if (n == 2)
                // 因为至少且一刀
                return 1;
            int[] ans = new int[n + 1];
            ans[0] = 0;
            ans[1] = 1;
            ans[2] = 1;
            for (int i = 3; i < n + 1; i++) {
                for (int j = 2; j < i; j++) {
                    // 这里需要注意的是在最后别忘了j * ans[i - j]和j * (i - j)进行比较，因为最少一刀的
                    ans[i] = Math.max(ans[i], Math.max(j * ans[i - j], j * (i - j)));
                }
            }
            return ans[n];
        }

*  贪心算法

书中除了动态规划还提到一个算法就是贪心算法，这个了解一下就好，感觉还是动态规划算是一个常规算法，这个贪心算法有点数学的味道。即可以通过数学推导得知，切分规则如下最优：

*   *  最优三：

绳子尽可能的切成三的片段，留下来最后一段绳子的长度可能为0,1,2三种情况

*   *  次优二：

若最后一段绳子是2，则保留，不再拆为1+1

*   *  最差一：

若最后一段绳子是1，则把一份3+1拆成2+2

class Solution {
        public int cuttingRope(int n) {
            if(n <= 3) return n - 1;
            int a = n / 3, b = n % 3;
            if(b == 0) return (int)Math.pow(3, a);
            if(b == 1) return (int)Math.pow(3, a - 1) * 4;
            return (int)Math.pow(3, a) * 2;
        }
    }

### 十五、二进制中一的个数 ###

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

看到二进制，无脑位移操作即可。简单的很

public int hammingWeight(int n) {
            if (n == 0)
                return 0;
    
            int count = 0;
            while (n != 0) {
                if ((int) (n & 1) == 1)
                    count++;
                n = n >>> 1;
            }
            return count;
        }

### 十六、数值的整数平方 ###

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

由于不需要考虑大数问题所以来说算法实现起来相对来说较为简单，唯一需要考虑的就是特殊值和如何更快的算出平方问题。

就是对于特殊值0和负数需要在方法入口处进行处理，后面就正常操作就可以了。

而对于快速算出平方就要采用类似折半的算法来减少乘法的次数。这个题目在面阿里二面的时候的原题，印象还是很深的。

public double myPow(double x, int n) {
            if (x == 0) 
                return 0;
            long b = n;
            double res = 1.0;
            if (b < 0) {
                x = 1 / x;
                b = -b;
            }
            while (b > 0) {
                if ((b & 1) == 1) 
                    res *= x;
                x *= x;
                b >>= 1;
            }
            return res;
        }

### 十七、打印从1到最大的n位数 ###

输入数字 `n`，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

这个题目看起来很简单，在面试中考察的时候主要是考察对于特殊情况的处理，即在于输入的n很大的时候容易溢出，所以无论是使用short还是int亦或是long都是会越界的，所以要使用字符串来代替。

但是使用字符串的时候仅为操作效率低下，也不是一个很好的办法，所以需要转换思路。

仔细分析生成的列表其实是n位的0-9的全排序，这样就不用进位操作了。

private List<Integer> list;
    
        public int[] printNumbers(int n) {
            list = new ArrayList<>();
            dfs(n, 0, new StringBuilder());
            int[] res = new int[list.size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = list.get(i);
            }
            return res;
        }
    
        private void dfs(int n, int i, StringBuilder sb) {
            if (i == n) {
                while (sb.length() != 0 && sb.charAt(0) == '0') {
                    sb.deleteCharAt(0);
                }
                if (sb.length() != 0) {
                    list.add(Integer.valueOf(sb.toString()));
                }
                return;
            }
            for (int j = 0; j < 10; j++) {
                sb.append(j);
                dfs(n, i + 1, sb);
                if (sb.length() != 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }

### 十八、删除链表的节点 ###

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

这个题目很简单就不再赘述了

public ListNode deleteNode(ListNode head, int val) {
            if(head.val==val)
                return head.next;
            ListNode p=head;
            // 找到下一个节点就是要删除的节点
            while(p.next.val!=val){
                p=p.next;
            }
            p.next=p.next.next;
            return head;
        }

### 十九、正则表达式匹配 ###

请实现一个函数用来匹配包含`'.'`和`'*'`的正则表达式。模式中的字符`'.'`表示任意一个字符，而`'*'`表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串`"aaa"`与模式`"a.a"`和`"ab*ac*a"`匹配，但与`"aa.a"`和`"ab*a"`均不匹配。

这个题目的关键就是匹配的过程，第一次看的时候真的是感觉麻烦的一批，但是只要你仔细的去分类去看，还是很简单的。

题目中的匹配是逐步匹配的过程，我们每次从p中取出元素，有三种可能：

*  是字符

要判断和s中的是否一致

*  是‘.’

一定可以匹配成功

*  是‘\*’
 *   *  匹配0次
     *  匹配1次
     *  匹配多次

用动态规划来表示的话就是：

*  如果 pattern\[j\] == str\[i\] || pattern\[j\] == '.', 此时dp\[i\]\[j\] = dp\[i-1\]\[j-1\];
 *  如果 pattern\[j\] == '\*' 分两种情况:
 *   *  如果pattern\[j - 1\] != str\[i\] && pattern\[j - \] != '.', 此时dp\[i\]\[j\] = dp\[i\]\[j - 2\] //a\*匹配0次
     *  如果pattern\[j - 1\] == str\[i\] || pattern\[j - 1\] == '.'
 *   *   *  此时 dp\[i\]\[j\] = dp\[i\]\[j - 2\] // a\*匹配0次
         *  或者dp\[i\]\[j\] = dp\[i\]\[j - 1\] // a\*匹配1次
         *  或者 dp\[i\]\[j\] = dp\[i - 1\]\[j\] // a\*匹配多次

代码如下所示

public boolean isMatch(String s, String p) {
            int slen = s.length();
            int plen = p.length();
            boolean[][] ans = new boolean[slen + 1][plen + 1];
            ans[0][0] = true;
            for (int i = 1; i <= plen; i++) {
                if (p.charAt(i - 1) == '*' && i >= 2)
                    ans[0][i] = ans[0][i - 2];
            }
            for (int i = 1; i <= slen; i++) {
                for (int j = 1; j <= plen; j++) {
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                        ans[i][j] = ans[i - 1][j - 1];
                    else if (p.charAt(j - 1) == '*' && j >= 2) {
                        if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.')
                            ans[i][j] = ans[i][j - 2];
                        else
                            ans[i][j] = ans[i][j - 2] || ans[i][j - 1] || ans[i - 1][j];
    
                    } else ans[i][j] = false;
                }
            }
            return ans[slen][plen];
        }

### 二十、表示数值的字符串 ###

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

做这个题目首先要明确哪些属于数值：

*  '.'出现正确情况：只出现一次，且在e前面
 *  'e'出现正确情况：只出现一次，且出现前有数字
 *  '+','-'出现正确情况：只能出现在开头和e的后一位

public boolean isNumber(String s) {
            if (s == null || s.length() == 0) return false;
            //去掉首位空格
            s = s.trim();
            boolean numFlag = false;
            boolean dotFlag = false;
            boolean eFlag = false;
            for (int i = 0; i < s.length(); i++) {
                //判定为数字，则标记numFlag
                if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    numFlag = true;
                    //判定为.  需要没出现过.并且没出现过e
                } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                    dotFlag = true;
                    //判定为e，需要没出现过e，并且出过数字了
                } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                    eFlag = true;
                    numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
                    //判定为+-符号，只能出现在第一位或者紧接e后面
                } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {
    
                    //其他情况，都是非法的
                } else {
                    return false;
                }
            }
            return numFlag;
        }

### 二十一、调整数组顺序使得奇数位于偶数前面 ###

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

这个题目用双指针或者快慢指针来做都很简单，其核心就是找到要移动的元素，然后使之交换

public int[] exchange(int[] nums) {
            int len = nums.length;
            int left =0;
            int right = len-1;
            while(left<right){
                while(left<right&&nums[left]%2==1){
                    left++;
                }
                while(left<right&&nums[right]%2==0){
                    right--;
                }
                int temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
                left++;
                right--;
            }
            return nums;
        }

### 二十二、链表中倒数第k个节点 ###

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

这个题目在以前的快慢指针那一期中就有过介绍，在此就不过多赘述，直接使用快慢指针即可。

public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode slow =head;
            ListNode fast = head;
            while(fast!=null){
                fast =fast.next;
                if(k==0){
                    slow=slow.next;
                }else{
                    k--;
                }
            }
            return slow;
        }

这一期的11道题就给大家介绍完了，这一部分主要是一些搜索问题和动态规划的问题，另外加了几个面试中常见的题目，注入链表中倒数第K个节点这样的问题。有些题目初步看起来真的是感觉没有思路，其实当你仔细分析的时候，你会发现其实没有那么的复杂，只要把大问题拆成小问题，逐步去解决，你就会发现其实问题没有那么困难。

### 最后 ###

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

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

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