LeetCode剑指offer题目记录5

leetcode刷题开始啦, 每天记录几道题.

目录

• 剑指 Offer 11. 旋转数组的最小数字
• • 题目描述
  • 示例
  • 思路
  • • python
    • C++
• 剑指 Offer 12. 矩阵中的路径
• • 题目描述
  • 示例
  • 思路
  • • python
    • C++
• 剑指 Offer 13. 机器人的运动范围
• • 题目描述
  • 示例
  • 思路
  • • python
  • 改进
• 剑指 Offer 14- I. 剪绳子
• • 题目描述
  • 示例
  • 思路
  • • python
• 剑指 Offer 14- II. 剪绳子 II
• • 题目描述
  • 示例
  • 思路
  • • python
• 剑指 Offer 15. 二进制中1的个数
• • 题目描述
  • 示例
  • 思路
  • • python
• 剑指 Offer 16. 数值的整数次方
• • 题目描述
  • 示例
  • 思路
  • • python

剑指 Offer 11. 旋转数组的最小数字 题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。

请返回旋转数组的最小元素。

例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

示例

输入：numbers = [3,4,5,1,2]
输出：1

思路

要找到数组中满足它之前之后的都比它大的元素. 实际上, 只要找到左边的元素比它大的即可. 想一下用二分查找. 把整个数组分成左右两个升序的序列, 左边的全都大于等于右边.

二分查找, 比较中间节点和右侧节点, 如果中间比右侧小, 说明中间节点在右半截里, 更新high. 如果中间比右侧大, 说明中间节点在左半截里, 更新low. 如果中间等于右侧, 此时不能保证中间节点在哪里, 因为有重复元素, 最低点在中间节点的左边右边都有可能. 首先考虑中间节点的取法: mid = low + (high - low) // 2. 也就是说此时中间节点和右侧不是同一个节点, 所以对右侧节点来说, 如果它是最小值, 那它左边有个mid和它一样大; 如果它不是最小值, 那它向左走一步也不会越过最小值. 所以把右侧节点向左走一步.

二分法有一个比较麻烦的问题在左右节点的更新策略和返回哪个节点的值. 我们分析一下. 这个思路也可以用到别的使用二分法的情形里.

首先看一下查找的终点: low >= high. 要达到这个条件,

• 情况1: 前一步结果为low = high - 1. 此时mid = low, 先给出使循环终止的可行的更新方式.
  • num[mid] > num[high], 按之前的分析, 要更新low. 取low = mid等于什么也没做, 不行. 取low = mid + 1, 进入下一个循环就有 low == high, 终止, 返回num[low]即可.
  • num[mid] < num[high], 要更新high. 这个时候就有两种更新策略了.
    • 更新为high = mid - 1, 进入下一个循环就有 low > high, 终止, 返回 num[low]即可;
    • 更新为high = mid, 进入下一个循环就有low == high, 终止, 返回 num[low] 即可.
  • num[mid] == num[high], 之前已经分析过了, 更新high = high - 1, 进入下一个循环有high == low, 终止, 返回 num[low] 即可.

用情况2来确定情况1的第二种情形到底应该用哪个策略.

• 情况2: 前一步为low = high - 2. 此时mid = low + 1,
  • num[mid] > num[high], 更新为low = mid + 1 (=high), 返回num[low] (=num[high])为最小值, 没错;
  • num[mid] < num[high],
    • 更新为high = mid - 1(=low), 所以进入下一个循环时会终止并且返回num[low]. 这对吗? 这不对. 有可能num[low] > num[mid].
    • 更新为high = mid(=low+1), 进入下一个循环有 low = high - 1, 进入情况1. 刚刚已经分析过情况1有完备的处理方式了, 所以这样更新是可行的.
  • num[mid] == num[high], 更新high = high - 1( = mid = low + 1), 进入情况1. 所以也没错.

为什么要用mid = low + (high - low) // 2来求mid呢? 因为如果数组非常长, 用mid = (high + low) // 2可能会在加法处越界.

python

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if len(numbers) == 1:
            return numbers[0]
        low, high = 0, len(numbers) - 1
        while low < high:
            mid = low + (high - low) // 2
            if numbers[mid] < numbers[high]:
                high = mid
            elif numbers[mid] > numbers[high]:
                low = mid + 1
            else:
                high -= 1

        return numbers[low]

C++

class Solution {
public:
    int minArray(vector& numbers) {
        int low = 0; 
        int high = numbers.size() - 1;
        while (low < high){
            int mid = low + (high - low) / 2;
            if (numbers[mid] < numbers[high]){
                high = mid;
            }
            else if (numbers[mid] > numbers[high]){
                low = mid + 1;
            }
            else{
                high -= 1;
            }
        }
        return numbers[low];
    }
};

剑指 Offer 12. 矩阵中的路径 题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。

如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。

同一个单元格内的字母不允许被重复使用。

示例

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

思路

很典型的考虑深度优先, 遍历矩阵的每一个元素, 比对它和word的第一个元素. 如果匹配, 遍历这个元素上下左右是否匹配word的下一个元素, 如果没越界并且匹配就重复这个过程, 直到找到word或者遍历完矩阵都没找到. 在每一次查找时, 检查过的元素要标记好, 检查过后要复位.

python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            case1 = 0 <= i < len(board)
            case2 = 0 <= j < len(board[0])
            if not (case1 and case2):
                return False
            elif board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            board[i][j] = ''
            res = dfs(i+1, j, k+1) or dfs(i, j+1, k+1) or dfs(i-1, j, k+1) or dfs(i, j-1, k+1)
            board[i][j] = word[k]
            return res
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

C++

C++不能到处定义函数, 稍微麻烦些.

class Solution {
public:
    bool exist(vector>& board, string word) {
        row = board.size();
        col = board[0].size();
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (dfs(board, word, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
private:
    int row;
    int col;
    bool dfs(vector>& board, const string& word,
             const int& i, const int& j, const int& k){

        if (i < 0 || i >= row || j < 0 || j >= col || board[i][j] != word[k]){
            return false;
        }
        if (k == word.size() - 1){
            return true;
        }
        board[i][j] = '\0';
        bool res = dfs(board,word,i+1,j,k+1) || dfs(board,word,i-1,j,k+1) || 
                   dfs(board,word,i,j+1,k+1) || dfs(board,word,i,j-1,k+1);
        board[i][j] = word[k];
        return res;
    }
};

剑指 Offer 13. 机器人的运动范围 题目描述

地上有一个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。

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

示例

输入：m = 2, n = 3, k = 1
输出：3

思路

这又可以采用深度优先搜索. 从左上角开始, 探查四个方向, 如果没有越界, 并且行列坐标的数位和满足约束, 并且没有被标记过可达, 则标记为可达, 再继续探查四个方向. 最后统计标记的个数.

python

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def countDigit(row, col):
            res = 0
            while row:
                res += row % 10
                row = row // 10
            while col:
                res += col % 10
                col = col // 10
            return res
        
        def dfs(i, j, k):
            if i < 0 or i >= m or j < 0 or j >= n:
                return 
            elif countDigit(i, j) > k:
                return 
            elif board[i][j] == 1:
                return
            board[i][j] = 1

            dfs(i+1, j, k)
            dfs(i-1, j, k)
            dfs(i, j+1, k)
            dfs(i, j-1, k)

        if k == 0:
            return 1

        board = [[0 for j in range(n)] for i in range(m)]   
        dfs(0, 0, k)
        return sum(map(sum, board))

改进

实际上, 如果我们从左上角出发, 那并没有必要考察四个方向, 只需要看向右和向下. 改进是容易的, 在遍历函数里去掉向上和向左的函数即可.

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def countDigit(row, col):
            res = 0
            while row:
                res += row % 10
                row = row // 10
            while col:
                res += col % 10
                col = col // 10
            return res
        
        def dfs(i, j, k):
            if i < 0 or i >= m or j < 0 or j >= n:
                return 
            elif countDigit(i, j) > k:
                return 
            elif board[i][j] == 1:
                return
            board[i][j] = 1

            dfs(i+1, j, k)
            dfs(i, j+1, k)

        if k == 0:
            return 1

        board = [[0 for j in range(n)] for i in range(m)]   
        dfs(0, 0, k)
        return sum(map(sum, board))

剑指 Offer 14- I. 剪绳子 题目描述

给你一根长度为 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。

示例

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

思路

这个题好像可以动态规划, 但还是从数学的角度比较简单. m个正数相乘, 用均值不等式, 有
x 1 ⋯ x m m ≤ x 1 + ⋯ + x m m \sqrt[m]{x_1\cdots x_m}\leq\frac{x_1+\cdots+x_m}{m} mx1​⋯xm​ ​≤mx1​+⋯+xm​​
等号条件是 x 1 = ⋯ = x m x_1=\cdots=x_m x1​=⋯=xm​. 或者用求导, 也可以知道尽可能全相等时最大. 那么, n m m \frac{n}{m}^m mn​m在什么时候最大呢? n n n 是给定的, 我们对 m m m求个导, 令一阶导为零, 得到 n m = e \frac{n}{m}=e mn​=e. 就是说, 在 n n n 给定的情况下, 分 m m m 段能尽量让每段长度为 e e e 时这个乘积最大. 最靠近 e e e 的整数是 3. 所以要尽量要多的3. 但注意如果剩余的长度是1, 那拿一个3出来, 变成 2 ∗ 2 2*2 2∗2, 比直接 3 ∗ 1 3*1 3∗1要大.

python

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
            
        cut_num = n // 3
        left = n % 3
        if left == 1:
            return 3 ** (cut_num - 1) * 4
        elif left == 2:
            return 3 ** cut_num * 2
        else:
            return 3 ** cut_num

剑指 Offer 14- II. 剪绳子 II 题目描述

给你一根长度为 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。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

思路

还是和刚刚一样. 但要注意答案要取模. 和之前的处理方式一样, 我们在中间步骤取模来保证不越界.

都是整数. a   %   b = a 1 a\ \%\ b = a_1 a % b=a1​, 那 a c   %   b ac\ \%\ b ac % b 是多少呢? 显然 c a 1   %   b ca_1\ \%\ b ca1​ % b 是一个简单的答案.

python

当然, python对越界的容忍度要高不少. 所以可以在最后再取模. 但已经写成这个样子了.

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
            
        cut_num = n // 3
        left = n % 3
        if left == 1:
            res = 4
            for i in range(cut_num - 1):
                res *= 3
                res % 1000000007
        elif left == 2:
            res = 2
            for i in range(cut_num):
                res *= 3
                res % 1000000007
        else:
            res = 1
            for i in range(cut_num):
                res *= 3
                res % 1000000007
        
        return res % 1000000007

剑指 Offer 15. 二进制中1的个数 题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。

在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。

因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

思路

这个看起来用位运算比较好.

python

python中按位与运算符是 &, 如果两个值的二进制表示的相同位上都是1, 这一位的运算结果就是1. 也就是说, 我们用32个基向量去和n做按位与运算, 只有在n的对应位上是1时, 它与这个基向量才能得到非零解. 最后加一下, 就知道n有多少位上是1了.

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        for i in range(32):
            if n & (1 << i):
                res += 1
        return res

剑指 Offer 16. 数值的整数次方 题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

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

示例

输入：x = 2.10000, n = 3
输出：9.26100

思路

这个写成次方就比较哄人了. 但是把次方展开实际上是 n n n个 x x x的乘法. 那如果我先求出了 n 2 \frac{n}{2} 2n​个 x x x 的乘积, 下一步就只用一次乘法了. 这就是一种递归二分的思路. 下面就是要处理下细节.

对 n > 0 n > 0 n>0,

• 终止条件: n n n = 1 或 0. 此时不需要运算, 直接返回 x 或 1 即可.
• 循环条件:
  • n n n 为奇数: 返回 x × x n / / 2 × x n / / 2 x\times x^{n//2}\times x^{n//2} x×xn//2×xn//2
  • n n n 为偶数: 返回 x n / 2 × x n / 2 x^{n/2}\times x^{n/2} xn/2×xn/2

对 n < 0 n < 0 n<0, 返回对应相反数的次幂的导数即可.

这里有个小技巧, 判断奇偶可以判断二进制的最后一位是否为1. 这比求一次模更快. 上一个题里的技术, 按位与, 马上就用上了.

python

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def positivePow(x, n):
            if n == 0:
                return 1
            if n == 1:
                return x
            
            m = n // 2
            half_pow = positivePow(x, m)
            if n & 1: 
                return x * half_pow * half_pow
            else:
                return half_pow * half_pow
        
        if n >= 0:
            return positivePow(x, n)
        else:
            return 1 / positivePow(x, -n)