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

向右看齐 2022-02-15 12:58 183阅读 0赞

## 13 机器人的运动范围 ##

### 题目描述 ###

地上有一个 m 行和 n 列的方格。

一个机器人从坐标 `0,0` 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例1

输入：k=7, m=4, n=5
    输出：20

样例2

输入：k=18, m=40, n=40
    
    输出：1484
    
    解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
          但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

注意:

1.  0<=m<=50
2.  0<=n<=50
3.  0<=k<=100

### 解法 ###

从坐标(0, 0) 开始移动，当它准备进入坐标(i, j)，判断是否能进入，如果能，再判断它能否进入 4 个相邻的格子 (i-1, j), (i+1, j), (i, j-1), (i, j+1)。

class Solution { 
    
        /** * 计算能到达的格子数 * * @param threshold 限定的数字 * @param rows 行数 * @param cols 列数 * @return 能到达的格子数 */
        public int movingCount(int threshold, int rows, int cols) { 
            boolean[][] visited = new boolean[rows][cols];
            return getCount(threshold, rows, cols, 0, 0, visited);
        }
    
        private int getCount(int threshold, int rows, int cols, int i, int j, boolean[][] visited) { 
            if (check(threshold, rows, cols, i, j, visited)) { 
                visited[i][j] = true;
                return 1 + getCount(threshold, rows, cols, i + 1, j, visited)
                        + getCount(threshold, rows, cols, i - 1, j, visited)
                        + getCount(threshold, rows, cols, i, j + 1, visited)
                        + getCount(threshold, rows, cols, i, j - 1, visited);
            }
            return 0;
        }
    
        private boolean check(int threshold, int rows, int cols, int i, int j, boolean[][] visited) { 
            return i >= 0 && i < rows && j >= 0 && j < cols
                    && !visited[i][j] && (getDigitSum(i) + getDigitSum(j) <= threshold);
        }
    
        private int getDigitSum(int val) { 
            int sum = 0;
            while (val > 0) { 
                sum += (val % 10);
                val /= 10;
            }
            return sum;
        }
    }

## 14 剪绳子 ##

来源：AcWing

### 题目描述 ###

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，n>1 并且 m≥1）。

每段的绳子的长度记为 `k[0]、k[1]、……、k[m]`。`k[0]k[1] … k[m]`可能的最大乘积是多少？

例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。

样例

输入：8
    输出：18

### 解法 ###

#### 解法一：动态规划法 ####

时间复杂度`O(n²)`，空间复杂度`O(n)`。

f(n) = max{f(n), f(i) * f(n - i)}, i = 1,2..n-1

*  长度为 2，只可能剪成长度为 1 的两段，因此 f(2)=1
 *  长度为 3，剪成长度分别为 1 和 2 的两段，乘积比较大，因此 f(3) = 2
 *  长度为 n，在剪第一刀的时候，有 n-1 种可能的选择，剪出来的绳子又可以继续剪，可以看出，原问题可以划分为子问题，子问题又有重复子问题。

class Solution { 
    
        /** * 剪绳子求最大乘积 * * @param length 绳子长度 * @return 乘积最大值 */
        public int maxProductAfterCutting(int length) { 
            if (length < 4) { 
                return length - 1;
            }
    
            int[] res = new int[length + 1];
            res[1] = 1;
            res[2] = 2;
            res[3] = 3;
            for (int i = 4; i <= length; ++i) { 
                for (int j = 1; j < i / 2 + 1; ++j) { 
                    res[i] = Math.max(res[i], res[j] * res[i - j]);
                }
            }
            return res[length];
        }
    }

#### 贪心算法 ####

时间复杂度`O(1)`，空间复杂度`O(1)`。

贪心策略：

*  当 n>=5 时，尽可能多地剪长度为 3 的绳子
 *  当剩下的绳子长度为 4 时，就把绳子剪成两段长度为 2 的绳子。

证明：

*  当 n>=5 时，可以证明 2(n-2)>n，并且 3(n-3)>n。也就是说，当绳子剩下长度大于或者等于 5 的时候，可以把它剪成长度为 3 或者 2 的绳子段。
 *  当 n>=5 时，3(n-3)>=2(n-2)，因此，应该尽可能多地剪长度为 3 的绳子段。
 *  当 n=4 时，剪成两根长度为 2 的绳子，其实没必要剪，只是题目的要求是至少要剪一刀。

class Solution { 
    
        /** * 剪绳子求最大乘积 * * @param length 绳子长度 * @return 乘积最大值 */
        public int maxProductAfterCutting(int length) { 
            if (length < 4) { 
                return length - 1;
            }
    
            int timesOf3 = length / 3;
            if (length % 3 == 1) { 
                --timesOf3;
            }
            int timesOf2 = (length - timesOf3 * 3) >> 1;
            return (int) (Math.pow(2, timesOf2) * Math.pow(3, timesOf3));
        }
    }

## 15 二进制中1的个数 ##

来源：AcWing

### 题目描述 ###

输入一个 32 位整数，输出该数二进制表示中 1 的个数。

注意：

*  负数在计算机中用其绝对值的补码来表示。

样例1

输入：9
    输出：2
    解释：9的二进制表示是1001，一共有2个1。

样例2

输入：-2
    输出：31
    解释：-2在计算机里会被表示成11111111111111111111111111111110，
          一共有31个1。

### 解法 ###

#### 解法一 ####

利用整数 1，依次左移每次与 n 进行与运算，若结果不为0，说明这一位上数字为 1，++cnt。

此解法 i 需要左移 32 次。

不要用 n 去右移并与 1 进行与运算，因为 n 可能为负数，右移时会陷入死循环。

class Solution { 
    
        /** * 求二进制中1的个数 * * @param n 整数 * @return 该整数的二进制中1的个数 */
        public int NumberOf1(int n) { 
            int i = 1;
            int cnt = 0;
            while (i != 0) { 
                if ((n & i) != 0) { 
                    ++cnt;
                }
                i <<= 1;
            }
            return cnt;
        }
    }

#### 解法二（推荐） ####

运算 `(n - 1) & n`，直至 n 为 0。运算的次数即为 n 的二进制中 1 的个数。

因为 n-1 会将 n 的最右边一位 1 改为 0，如果右边还有 0，则所有 0 都会变成 1。结果与 n 进行与运算，会去除掉最右边的一个 1。

举个栗子：

若 n = 1100，
    n - 1 = 1011
    n & (n - 1) = 1000
    
    即：把最右边的 1 变成了 0。

> 把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。

class Solution { 
    
        /** * 求二进制中1的个数 * * @param n 整数 * @return 该整数的二进制中1的个数 */
        public int NumberOf1(int n) { 
            int cnt = 0;
            while (n != 0) { 
                ++cnt;
                n &= (n - 1);
            }
            return cnt;
        }
    }

#### 解法三 ####

利用 Java API。

class Solution { 
    
        /** * 求二进制中1的个数 * * @param n 整数 * @return 该整数的二进制中1的个数 */
        public int NumberOf1(int n) { 
            return Integer.bitCount(n);
        }
    }

## 16 数值的整数次方 ##

来源：AcWing

### 题目描述 ###

实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。

不得使用库函数，同时不需要考虑大数问题。

注意：

*  不会出现底数和指数同为 0 的情况。

样例1

输入：10 ，2
    输出：100

样例2

输入：10 ，-2  
    输出：0.01

### 解法 ###

注意判断值数是否小于 0。另外 0 的 0 次方没有意义，也需要考虑一下，看具体题目要求。

#### 解法一 ####

时间复杂度 `O(N)`。

class Solution { 
    
        /** * 计算数值的整数次方 * * @param base 底数 * @param exponent 指数 * @return 数值的整数次方 */
        public double Power(double base, int exponent) { 
            if (exponent == 0) { 
                return 1;
            }
            if (exponent == 1) { 
                return base;
            }
    
            double res = 1;
            for (int i = 0; i < Math.abs(exponent); ++i) { 
                res *= base;
            }
    
            return exponent > 0 ? res : 1 / res;
        }
    }

#### 解法二 ####

![.gif][]

递归求解，每次 exponent 缩小一半，时间复杂度为 `O(log N)`。

class Solution { 
    
        /** * 计算数值的整数次方 * * @param base 底数 * @param exponent 指数 * @return 数值的整数次方 */
        public double Power(double base, int exponent) { 
            if (exponent == 0) { 
                return 1;
            }
            if (exponent == 1) { 
                return base;
            }
    
            double res = Power(base, Math.abs(exponent) >> 1);
            res *= res;
            if ((exponent & 1) == 1) { 
                res *= base;
            }
            return exponent > 0 ? res : 1 / res;
        }
    }

## 17 打印从1到最大的n位数 ##

来源：无

### 题目描述 ###

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

### 解法 ###

此题需要注意 n 位数构成的数字可能超出最大的 int 或者 long long 能表示的范围。因此，采用字符数组来存储数字。

#### 解法一 ####

*  对字符数组表示的数进行递增操作；
 *  输出数字（0开头的需要把0去除）。

class Solution { 
    
        /** * 打印从1到最大的n位数 * * @param n n位数 */
        public void print1ToMaxOfNDigits(int n) { 
            if (n < 1) { 
                return;
            }
            char[] chars = new char[n];
            Arrays.fill(chars, '0');
            while (increment(chars)) { 
                printNumber(chars);
            }
        }
    
    
        /** * 打印字符数组表示的数字（需要省略前n个0） * * @param chars 字符数组 */
        private void printNumber(char[] chars) { 
            int i = 0, n = chars.length;
            for (; i < n; ++i) { 
                if (chars[i] != '0') { 
                    break;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (; i < n; ++i) { 
                sb.append(chars[i]);
            }
            System.out.println(sb.toString());
        }
    
        private boolean increment(char[] chars) { 
            int n = chars.length;
            int carry = 1;
            for (int i = n - 1; i >= 0; --i) { 
                int sum = chars[i] - '0' + carry;
                if (sum > 9) { 
                    if (i == 0) { 
                        return false;
                    }
                    chars[i] = '0';
                } else { 
                    ++chars[i];
                    break;
                }
            }
            return true;
        }
    }

#### 解法二 ####

利用递归全排列，设置每一位，设置完之后，打印出来。

class Solution { 
    
        /** * 打印从1到最大的n位数 * * @param n n位数 */
        public void print1ToMaxOfNDigits(int n) { 
            if (n < 1) { 
                return;
            }
            char[] chars = new char[n];
            print1ToMaxOfNDigits(chars, n, 0);
        }
    
        private void print1ToMaxOfNDigits(char[] chars, int n, int i) { 
            if (i == n) { 
                printNumber(chars);
                return;
            }
    
            // 每一位分别设置从0到9
            for (int j = 0; j < 10; ++j) { 
                chars[i] = (char) (j + '0');
                print1ToMaxOfNDigits(chars, n, i + 1);
            }
        }
    
    
        /** * 打印字符数组表示的数字（需要省略前n个0） * * @param chars 字符数组 */
        private void printNumber(char[] chars) { 
            int i = 0, n = chars.length;
            for (; i < n; ++i) { 
                if (chars[i] != '0') { 
                    break;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (; i < n; ++i) { 
                sb.append(chars[i]);
            }
            System.out.println(sb.toString());
        }
    }

## 18.1 在O(1)时间删除链表节点 ##

来源：AcWing

### 题目描述 ###

给定单向链表的一个节点指针，定义一个函数在 `O(1)` 时间删除该节点。

假设链表一定存在，并且该节点一定不是尾节点。

样例

输入：链表 1->4->6->8
          删掉节点：第2个节点即6（头节点为第0个节点）
    
    输出：新链表 1->4->8

### 解法 ###

判断要删除的节点是否是尾节点：

*  若是，那么需要遍历链表，找到节点的前一个节点，让前一个节点指向 `null`，时间复杂度为 `O(n)`；
 *  若不是，把下一个节点的值赋给该节点，该节点指向下下个节点，时间复杂度为 `O(1)`。

题目中说明了节点不是尾节点，那么符合第二种情况。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
    
        /** * 删除链表的节点 * * @param node 要删除的节点 */
        public void deleteNode(ListNode node) { 
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

## 18.2 删除链表中重复的节点 ##

来源：AcWing

### 题目描述 ###

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例1

输入：1->2->3->3->4->4->5
    
    输出：1->2->5```
    
    样例2

输入：1->1->1->2->3

输出：2->3

### 解法
    
    #### 解法一：递归
    
    
    ```java
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        /**
         * 删除链表重复的节点
         *
         * @param head 链表头节点
         * @return 删除重复节点后的链表
         */
        public ListNode deleteDuplication(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
    
            if (head.next.val == head.val) {
                if (head.next.next == null) {
                    return null;
                }
                if (head.next.next.val == head.val) {
                    return deleteDuplication(head.next);
                }
                return deleteDuplication(head.next.next);
            }
            head.next = deleteDuplication(head.next);
            return head;
        }
    }

#### 解法二：非递归 ####

pre 始终指向下一个不重复的节点。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
    
        /** * 删除链表重复的节点 * * @param head 链表头节点 * @return 删除重复节点后的链表 */
        public ListNode deleteDuplication(ListNode head) { 
            if (head == null || head.next == null) { 
                return head;
            }
    
            ListNode pre = null, cur = head;
            while (cur != null) { 
                if (cur.next != null && cur.next.val == cur.val) { 
                    int val = cur.val;
                    while (cur.next != null && cur.next.val == val) { 
                        cur = cur.next;
                    }
                    if (pre == null) { 
                        head = cur.next;
                    } else { 
                        pre.next = cur.next;
                    }
                } else { 
                    pre = cur;
                }
                cur = cur.next;
            }
            return head;
        }
    }

## 19 正则表达式匹配 ##

来源：AcWing

### 题目描述 ###

请实现一个函数用来匹配包括 `'.'` 和 `'*'` 的正则表达式。

模式中的字符 `'.'` 表示任意一个字符，而 `'*'` 表示它前面的字符可以出现任意次（含 0 次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串 `"aaa"` 与模式 `"a.a"` 和 `"ab*ac*a"` 匹配，但是与 `"aa.a"` 和 `"ab*a"` 均不匹配。

样例

输入：
    
    s="aa"
    p="a*"
    
    输出:true

### 解法 ###

判断模式中第二个字符是否是 `*`：

*  若是，看如果模式串第一个字符与字符串第一个字符是否匹配：
 *  若不匹配，在模式串上向右移动两个字符`j+2`，相当于 a\* 被忽略。
 *  若匹配，字符串后移`i+1`。此时模式串可以移动两个字符`j+2`，也可以不移动`j`。
 *  若不是，看当前字符与模式串的当前字符是否匹配，即 `str[i] == pattern[j] || pattern[j] == '.'`：
 *  若匹配，则字符串与模式串都向右移动一位，`i+1`，`j+1`。
 *  若不匹配，返回 false。

class Solution { 
    
        /** * 判断字符串是否与模式串匹配 * * @param s 字符串 * @param p 模式串 * @return 是否匹配 */
        public boolean isMatch(String s, String p) { 
            if (s == null || p == null) { 
                return false;
            }
            char[] str = s.toCharArray();
            char[] pattern = p.toCharArray();
            return match(str, 0, str.length, pattern, 0, pattern.length);
        }
    
        private boolean match(char[] str, int i, int len1, char[] pattern, int j, int len2) { 
            if (i == len1 && j == len2) { 
                return true;
            }
    
            // pattern已经走到最后，而str还有未匹配的
            // str走到最后，而pattern还没走完，此时是允许的
            if (j == len2) { 
                return false;
            }
    
            if (j + 1 < len2 && pattern[j + 1] == '*') { 
                if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) { 
                    return match(str, i, len1, pattern, j + 2, len2)
                            || match(str, i + 1, len1, pattern, j, len2)
                            || match(str, i + 1, len1, pattern, j + 2, len2);
                }
                return match(str, i, len1, pattern, j + 2, len2);
            }
    
            if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) { 
                return match(str, i + 1, len1, pattern, j + 1, len2);
            }
            return false;
    
        }
    }

## 20 表示数值的字符串 ##

来源：AcWing

### 题目描述 ###

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如，字符串`"+100"`,`"5e2"`,`"-123"`,`"3.1416"`和`"-1E-16"`都表示数值。

但是`"12e"`,`"1a3.14"`,`"1.2.3"`,`"+-5"`和`"12e+4.3"`都不是。

注意:

*  小数可以没有整数部分，例如.123等于0.123；
 *  小数点后面可以没有数字，例如233.等于233.0；
 *  小数点前面和后面可以有数字，例如233.666;
 *  当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
 *  当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4;

样例：

输入: "0"
    
    输出: true

### 解法 ###

利用正则表达式匹配即可。

[]  ： 字符集合
    ()  ： 分组
    ?   ： 重复 0 ~ 1
    +   ： 重复 1 ~ n
    *   ： 重复 0 ~ n
    .   ： 任意字符
    \. ： 转义后的 .
    \d ： 数字

public class Solution { 
        /** * 判断是否是数字 * @param str * @return */
        public boolean isNumeric(char[] str) { 
            return str != null 
                    && str.length != 0 
                    && new String(str).matches("[+-]?\d*(\.\d+)?([eE][+-]?\d+)?");
        }
    }

## 21 调整数组顺序使奇数位于偶数前面 ##

来源：AcWing

### 题目描述 ###

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

### 解法 ###

#### 解法一 ####

计算出奇数的个数，就很容易写出来了。

import java.util.Arrays;
    
    public class Solution { 
        /** * 调整数组元素顺序，使得奇数元素位于偶数元素前面，且保证奇数和奇数，偶数和偶数之间的相对位置不变。 * @param array 数组 */
        public void reOrderArray(int [] array) { 
            if (array == null || array.length < 2) { 
                return;
            }
    
            int numsOfOdd = 0;
            for (int val : array) { 
                if (val % 2 == 1) { 
                    ++numsOfOdd;
                }
            }
            int[] bak = Arrays.copyOf(array, array.length);
            int i = 0, j = numsOfOdd;
            for (int val : bak) { 
                if (val % 2 == 1) { 
                    array[i++] = val;
                } else { 
                    array[j++] = val;
                }
            }
        }
    
    }

#### 解法二 ####

import java.util.Arrays;
    
    public class Solution { 
        public void reOrderArray(int [] array) { 
            if (array == null || array.length < 2) { 
                return;
            }
            Integer[] bak = new Integer[array.length];
            Arrays.setAll(bak, i -> array[i]);
            Arrays.sort(bak, (x, y) -> (y & 1) - (x & 1));
            Arrays.setAll(array, i -> bak[i]);
        }
        
    }

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

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

**推荐阅读**

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

[.gif]: https://upload-images.jianshu.io/upload_images/14326004-6bf275a799dbd596.gif?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
[1240]: /images/20220215/17dcb4d07a154d81a76044f0a93e8044.png
[BAT_Offer-_1]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247485255&idx=1&sn=73cba8342196c477b85b42195546d95f&chksm=eb5124b3dc26ada5070b85eaa005a52d43127f4a09d8138706ae018ef305435a27801d81494c&scene=21#wechat_redirect