剑指offer刷题记录（一）

0x00 前言

寒假赋闲在家，搞科研的同时希望提升一下自己的代码水平，于是回到阔别已久的LeetCode平台开始刷题。这次选择了剑指offer系列题目，编程语言采用Java。话不多说，直接开刷。

0x01 数组中重复的数字

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

算法详解

题目仅要求输出一个多次出现的数字，故自然联想到使用哈希表。完成建表之后对题目提供的数组进行一次遍历即可。该方法时间复杂度为O(N)，空间复杂度为哈希表所占的额外空间O(N)。

注意题目给出的特殊条件：长度为n的数组里所有数字在0—n-1范围内。该条件说明若数组中不包含重复元素，则数组下标与元素值是一一对应的关系，即nums[i]==i成立。于是引入原地置换的算法，提升程序运行效率，具体算法如下：

遍历数组nums，设置初始索引为i=0：

• 若nums[i] == i，说明数字与索引位置正确对应，无需交换，跳过该索引；
• 若nums[nums[i]] == nums[i]，说明索引nums[i]及索引i处元素值相同，返回该重复值即可；
• 否则交换索引为i和nums[i]的元素值，将此数字交换至对应索引的位置。

若遍历完毕尚未返回任何值，则返回-1表示元素与索引一一对应。

解题代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            int temp = 0;
            while(nums[i] != i){
                int m = nums[i];
                if(nums[m] == m){
                    return m;
                }
                else{
                    temp = nums[m];
                    nums[m] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度$O(N)$。
• 空间复杂度$O(1)$：该算法提供原地置换，无需开辟新的存储空间。

0x02 二维数组中的查找

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回true。

给定 target = 20，返回false。

限制：

0 <= n <= 1000

0 <= m <= 1000

算法详解

该题目将普通元素查找扩展至二维数组，最简单的方法为两次循环遍历，时间复杂度为O(N*M)，其中N，M分别为二维数组的行数与列数。显然该解法没有用到矩阵从上至下递增，从左至右递增的特点，故不是最优解。

我们将矩阵逆时针旋转45°，可以发现其结构类似二叉搜索树，对每个元素来说，左分支元素更小而右分支元素更大。因此我们从根节点开始搜索，遇到大于目标元素的元素则向左继续搜索，反之则向右继续搜索，最终获得目标元素。

结合以上思想，我们进行合理转化：根节点对应矩阵右上角的元素。具体算法如下：

• 从矩阵右上角元素开始遍历，同时与目标值target进行对比；
• 若matrix[row_index][column_index] > target，消去第column_index列元素；
• 若matrix[row_index][column_index] < target，消去第row_index行元素；
• 若matrix[row_index][column_index] == target，找到目标。

该算法选择从右上角开始遍历，需要注意下标范围及二维数组空判断问题。

解题代码

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length==0){
            return false;
        }
        int row_index = 0;
        int column_index = matrix[0].length-1;
        while(row_index>=0&&row_index<matrix.length&&column_index>=0&&column_index<matrix[0].length){
            if(matrix[row_index][column_index]== target){
                return true;
            }else if(matrix[row_index][column_index] > target){
                column_index--;
            }else if(matrix[row_index][column_index] < target){
                row_index++;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度$O(M+N)$：其中N和M分别代表矩阵的行数和列数，算法最多循环N+M次；
• 空间复杂度$O(1)$：i，j指针使用常数大小的额外空间。

0x03 替换空格

题目描述

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

限制：

0 <= s 的长度 <= 10000

算法详解

根据题目要求，最简单的方法是采用String类自带的替换函数replaceAll()，当然面试官肯定不会允许。于是就需要自己研究替换函数。注意到Java中String类型使用final关键词修饰，即String对象是不可修改的，从而考虑两种方法：

• 方法一：引入可修改的数据类型StringBuilder，最后使用toString()函数转换成String类型输出即可。
• 方法二：引入静态数组char[]，首先确定数组的长度为原始字符串的三倍（假设原始字符串全部由空格组成），随后采用双指针法循环遍历原始字符串和新的字符串，完成比较与添加字符的操作。

解题代码

Method 1

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(char c: s.toCharArray()){
            if(c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

Method 2

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] final_result = new char[3*length];
        int j = 0;
        for(int i = 0;i<length;i++){
            if(s.charAt(i) == ' '){
                final_result[j++] = '%';
                final_result[j++] = '2';
                final_result[j++] = '0';
            }else{
                final_result[j++] = s.charAt(i);
            }
        }
        return new String(final_result, 0, j);
    }
}

复杂度分析

• Method1

  • 时间复杂度$O(N)$。
  • 空间复杂度$O(N)$：Java新建StringBuilder使用了线性大小的额外空间。

• Method2

  • 时间复杂度$O(N)$。
  • 空间复杂度$O(1)$：由于是原地扩展字符串s的长度，因此使用$O(1)$的额外空间。

0x04 从尾到头打印链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

算法详解

本题目为最基础的链表逆序问题，可采用两种不同的数据结构辅助完成：

• 方法一：不引入栈而仅使用定长数组。由于Java中数组具有长度固定的特点，故首先需要遍历链表以获得结果数组的长度。建立对应长度数组后，采用从后向前逐位填充的方法完成逆序输出。
• 方法二：引入栈这一数据结构。由于栈具有LIFO的特点，只需通过进出操作就能实现链表逆序输出，将输出结果按序存入结果数组即可。

解题代码

Method 1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        // First get the length of the list
        int count = 0;
        ListNode current = head;
        while(current != null){
            count++;
            current = current.next;
        }
        // Then create a result array with fixed length
        int[] result_array = new int[count];
        // Lastly reverse the linkedlist
        for(int j = count-1;j>=0;j--){
            result_array[j] = head.val;
            head = head.next;
        }
        return result_array;
    }
}

Method 2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        // First create stack needed
        Stack<Integer> tmp_stack = new Stack<Integer>();
        ListNode temp = head;
        while(temp != null){
            tmp_stack.push(temp.val);
            temp = temp.next;
        }
        // Then create result array with fixed length
        int[] result_array = new int[tmp_stack.size()];
        // Lastly pop all the elements in this stack
        for(int j = 0;j < result_array.length;j++){
            result_array[j] = tmp_stack.pop();
        }
        return result_array;
    }
}

复杂度分析

两种方法的时间复杂度与空间复杂度均为$O(N)$。

0x05 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

限制：

0 <= 节点个数 <= 5000

算法详解

题目中给出前序遍历和中序遍历的结果数组。树结构中前序遍历遵循根节点—>左节点—>右节点的遍历顺序，中序遍历遵循左节点—>根节点—>右节点的遍历顺序，我们需要结合两次遍历的结果数组完成二叉树重构。基本方法如下：

递归函数将前序遍历结果数组preorder[]和中序遍历结果数组inorder[]作为输入参数，显然preorder[0]必为根节点。随后获取根节点对应元素在inorder[]数组中的位置（可通过构造函数和采用哈希表存储的方法），设为target_index。则在中序遍历数组中，inorder[:target_index]即为左子树，inorder[target_inex:]即为右子树；在前序遍历数组中，preorder[1: 1+target_index-0]为左子树（其中target_index-0表示从inorder[]数组中获取的左子树的长度），preorder[target_index+1:]为右子树。通过以上方法可以确定更新后的preorder[]数组和inorder[]数组，随后递归调用即可。

结合基本方法的分析，我们引入分治算法，通过递归对所有子树进行划分：

• 递推参数：根节点在前序遍历的索引root_index，子树在中序遍历的左边界left_bound，子树在中序遍历的右边界right_bound；

• 终止条件：当left_bound > right_bound，代表已经越过叶节点，此时返回null；

• 递推流程

  • 建立根节点node，节点值为preorder[root_index]；

  • 划分左右子树：查找根节点在中序遍历结果数组inorder[]中的索引target_index_in_inorder；

  • 开启左右子树递归，关键参数如下表所示：
    

• 返回值：回溯返回node，作为上一层递归中根节点的左/右子节点

值得注意的是，参数列表中target_index_in_inorder - left_bound + root_index + 1含义为：根节点索引+左子树长度+1，在中序遍历中该位置表示右子树的根节点。

解题代码

Method1 Fundational Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // This function is defined to get the index of root node in inorder-list
    public int findIndex(int[] orderlist, int target_value){
        for(int i = 0;i<orderlist.length;i++){
            if(orderlist[i] == target_value){
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if((preorder.length != inorder.length)||(preorder.length == 0 || inorder.length == 0)||(preorder == null || inorder == null)){
            return null;
        }

        int root_value = preorder[0];
        TreeNode root_node = new TreeNode(root_value);
        int position = findIndex(inorder, root_value);
		
        // Get new preorder-list
        int[] preorder_left = Arrays.copyOfRange(preorder, 1, 1+position);
        int[] preorder_right = Arrays.copyOfRange(preorder, 1+position, preorder.length);
		// Get new inorder-list
        int[] inorder_left = Arrays.copyOfRange(inorder, 0, position);
        int[] inorder_right = Arrays.copyOfRange(inorder, position+1, inorder.length);
		
        // Recurrsion starts
        TreeNode node_left = buildTree(preorder_left, inorder_left);
        TreeNode node_right = buildTree(preorder_right, inorder_right);

        root_node.left = node_left;
        root_node.right = node_right;

        return root_node;
    }
}

Method2 Solution With Hashmap

// This method can only be used in the construction of binary tree without duplicate nodes
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 标记中序遍历
    HashMap<Integer, Integer> map = new HashMap<>();
    // 保留先序遍历
    int[] preorder;
    
    // 将索引结果对应填入哈希表map中，方便后续查找
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0;i<preorder.length;i++){
            map.put(inorder[i], i);
        }
        return recurrsion(0, 0, inorder.length-1);
    }
    
    public TreeNode recurrsion(int root_index, int left_bound, int right_bound){
        if(left_bound > right_bound) return null;
        TreeNode root = new TreeNode(preorder[root_index]);
        int target_index_in_inorder = map.get(preorder[root_index]);
        root.left = recurrsion(root_index+1, left_bound, target_index_in_inorder-1);
        root.right = recurrsion(root_index+1+(target_index_in_inorder-left_bound), target_index_in_inorder+1, right_bound);
        return root;
    }
}

复杂度分析

两种方法的时间复杂度与空间复杂度均为$O(N)$。

参考链接

重建二叉树精选题解

重建二叉树官方题解

0x06 用两个栈实现队列

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对appendTail，deleteHead进行 10000 次调用

算法详解

题目主要考察栈和队列这两种存储结构的功能区别。栈具有LIFO的特点，即入栈与出栈都是对栈顶位置的元素进行操作。而队列可以理解为普通数组，可同时实现头部与尾部两向的操作。

结合以上特性，我们采用下面的思路解决问题：

• 使用栈结构存储队列数据，此时栈底元素对应队首元素，其无法直接删除，需要将上方所有元素出栈；
• 使用双栈可以实现列表倒序。假设非空栈A与空栈B，只需要将栈A弹出的元素依次压入栈B即可实现A列表倒序；
• 倒序后B执行出栈操作即相当于删除了A的栈底元素，即对应的队首元素。

本题中要求实现构造函数CQueue()，加入队尾函数appendTail()与删除队首函数deleteHead()。

• CQueue()：初始化两链表结构，分别代表栈A、B，用来实现加入队尾操作与元素倒序；
• appendTail()：将新元素加入栈A即可；
• deleteHead()：删除过程中存在以下三种情况：
  • 当栈B不为空，此时B中仍存在已完成倒序的元素，直接返回B的栈顶元素即可；
  • 当栈A、B均为空，无元素，返回-1；
  • 当栈A不为空，栈B为空，代表未进行倒序操作，此时需要将A中元素全部转移至B中，实现元素倒序并返回栈B栈顶元素即可。

解题代码

class CQueue {
    LinkedList <Integer> A, B;
    public CQueue() {
        // Stack A is used to store the elements by the order of pushment;
        // Stack B is used for reversing stack A.
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        A.addLast(value);
    }
    
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}

复杂度分析

• 时间复杂度：appendTail()函数为$O(1)$；deleteHead()函数在N次队首元素删除操作中共需完成N个元素的倒序；
• 空间复杂度$O(N)$：最差情况下，栈A和B共保存N个元素。

0x07 斐波那契数列

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

算法详解

题目给出斐波那契数列的递推公式，说明其具有递推关系，选择f(n+1) = f(n) + f(n-1)为转移方程，采用动态规划完成问题求解：

• 状态定义：设dp为一维数组，其中dp[i]的值代表斐波那契数列第i个数字；
• 转移方程：dp[i+1] = dp[i] + dp[i-1]；
• 初始状态：dp[0] = 0, dp[1] = 1；
• 返回值：dp[n]，即返回斐波那契数列的第n个数字。

这里采用循环求余法简化运算过程。随着n的增大，f(n)会超过Int32甚至Int64的取值范围，从而导致结果溢出，故需要采用求余运算，规则如下：

设正整数x，y，p，求余符号为mod，则有(x+y) mod p = (x mod p + y mod p) mod p，从而f(n) mod p = [f(n-1) mod p + f(n-2) mod p] mod p。故只需在循环中每次计算sum = (a+b) mod 1000000007即可。

解题代码

class Solution {
    public int fib(int n) {
        int a = 0, b = 1;
        for(int i = 0;i < n;i++){
            int sum = (a+b) % 1000000007;
            b = a;
            a = sum;
        }
        return a;
    }
}

复杂度分析

• 时间复杂度$O(N)$：计算f(n)需要循环n次，每轮循环内计算操作使用$O(1)$;
• 空间复杂度$O(1)$：几个标志变量使用常数大小的额外空间。

0x08 青蛙跳台阶问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

0 <= n <= 100

算法详解

本题目与斐波那契数列解题方法类似，只不过初始参数不同，可以通过普通动态规划和简化版动态规划解决问题，后者占用更少的空间资源。

解题代码

Method1 General DP

class Solution {
    public int numWays(int n) {
        if(n<=1) return 1;
        int dp[] = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i<n+1;i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return dp[n];
    }
}

Method2 Simple Version

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1;
        for(int i = 1;i < n;i++){
            int sum = (a+b) % 1000000007;
            b = a;
            a = sum;
        }
        return a;
    }
}

复杂度分析

• Method1

  时间与空间复杂度均为$O(N)$。

• Method2

  时间复杂度为$O(N)$，空间复杂度为$O(1)$。

0x09 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

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

示例 2：

输入：[2,2,2,0,1]
输出：0

算法详解

本题显然需要使用二分法，目标元素为旋转点元素，一般情况下满足以下条件：该元素值小于右侧元素，大于左侧元素。算法设计过程中需要考虑以下两个特殊情况：

• 输入数组部分元素相同；
• 输入数组旋转后的结果与初始结果相同，均为全升序序列。

二分法本身分以下三种情况讨论：

• nums[mid] > nums[right]
• nums[mid] < nums[right]
• nums[mid] == nums[right]

具体题解参考如下链接：

旋转数组的最小数字（二分法，清晰图解）

需要注意的是，二分法过程中经常使用mid = left + (left-right) / 2来防止溢出。

解题代码

class Solution {
    public int minArray(int[] numbers) {
        if (numbers.length == 0) return -1;
        if(numbers.length == 1) return numbers[0];
        int left = 0;
        int right = numbers.length-1;
        while(left < right){
            int mid = left + (right-left) / 2;
            if(numbers[mid] > numbers[right]){
                left = mid+1;
            }
            else if(numbers[mid] < numbers[right]){
                right = mid;
            }
            else{
                right -= 1;
            }
        }
        return numbers[left];
    }
}

复杂度分析

• 时间复杂度$O(log_{2}N)$：特例情况下会退化到$ O(N) $。
• 空间复杂度$O(1)$：i，j等变量使用常数大小的额外空间。

0x0a 矩阵中的路径

题目描述

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

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

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

示例1：

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

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200

算法详解

题目为典型的矩阵搜索问题，可使用深度优先搜索+剪枝来解决。首先介绍下这两个概念：

• 深度优先搜索（DFS）：该算法通过递归，先朝一个方向搜索至底部，再回溯到上个节点，沿另一个方向搜索，以此类推；
• 剪枝：在搜索过程中，遇到此路无法和目标字符串匹配成功的情况（例如，此矩阵元素和目标字符不同，此元素已被访问等），则应立即返回，此种方法成为可行性剪枝。

DFS过程如下：

• 递归参数：当前元素在矩阵board中的行列索引i和j，当前目标字符在字符串word中的索引k。
• 终止条件：
  • 返回false：1）行或列索引出现越界或(2）当前矩阵元素与目标字符不同或(3）当前矩阵元素已被访问；
  • 返回true：k=len(word)-1，代表字符串word已全部完成匹配。
• 递推工作
  • 标记当前矩阵元素：将board[i][j]修改为 空字符'\0' ，代表此元素已访问过，防止之后搜索时重复访问。
  • 搜索下一单元格：朝当前元素的 上、下、左、右 四个方向开启下层递归，使用或连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至res 。
  • 还原当前矩阵元素： 将board[i][j]元素还原至初始值，即word[k]。
• 返回值： 返回布尔量res，代表是否搜索到目标字符串。

解题代码

class Solution {
    // key parameters: i represents row index, j represents column index, and k represents wordlist index.
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] words, int i, int j, int k){
        if((i < 0 || i >= board.length) || (j < 0 || j >= board[0].length) || board[i][j] != words[k]) return false;
        if(k == words.length-1) return true;
        board[i][j] = '\0';
        boolean result = dfs(board, words, i, j+1, k+1) || dfs(board, words, i, j-1, k+1) || dfs(board, words, i+1, j, k+1)|| dfs(board, words, i-1, j, k+1);
        board[i][j] = words[k];
        return result;
    }
}

复杂度分析

假设M，N分别为矩阵的行列大小，K为字符串word的长度。

• 时间复杂度$O(3^{K}MN)$：设字符串长度为K，搜索中每个字符有上、下、左、右四个方向可供选择，舍弃回头的方向，剩下三种选择，因此方案数的复杂度为$O(3^{K})$。矩阵共有MN个 起点，时间复杂度为$O(MN)$，故最差情况为二者乘积。
• 空间复杂度$O(K)$：搜索过程中递归深度不超过K，因此系统因函数调用累计使用的栈空间占用$O(K)$。

0x0b 机器人的运动范围

题目描述

地上有一个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。请问该机器人能够到达多少个格子？

示例 1：

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

示例 2：

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

提示：

1 <= n,m <= 100
0 <= k <= 20

算法详解

本题与上题类似，均为典型的搜索&回溯问题。与上题不同的是，本题目的起点为(0,0)而非任意点，同时每次机器人运动方向只有向右和向下两个方向。可以采用广度优先搜索与深度优先搜索两种方法解题。可参考题解如下：机器人的运动范围（回溯算法，DFS/BFS）

解题代码

Method1 DFS

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean visited_position[][] = new boolean[m][n];
        return dfs(visited_position, m, n, 0, 0, k);
    }

    public int dfs(boolean[][] visited_position, int m, int n, int i, int j, int k){
        if((i >= m) || (j >= n) || visited_position[i][j] || (sumCount(i) + sumCount(j) > k))return 0;
        visited_position[i][j] = true;
        return 1 + dfs(visited_position, m, n, i+1, j, k) + dfs(visited_position, m, n, i, j+1, k);
    }

    public int sumCount(int index){
        int sum = 0;
        while(index != 0){
            sum += index % 10;
            index /= 10;
        }
        return sum;
    }
}

Method2 BFS

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int result = 0;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[] {0, 0, 0, 0});
        while(queue.size() > 0){
            int[] tmp_list = queue.poll();
            int i = tmp_list[0], j = tmp_list[1], s_i = tmp_list[2], s_j = tmp_list[3];
            if((i >= m) || (j >= n) || visited[i][j] || (s_i + s_j > k)) continue;
            visited[i][j] = true;
            result += 1;
            queue.add(new int[] {i, j+1, s_i, sumCount(j+1)});
            queue.add(new int[] {i+1, j, sumCount(i+1), s_j});
        }
        return result;
    }
    public int sumCount(int index){
        int sum_result = 0;
        while(index != 0){
            sum_result += index % 10;
            index /= 10;
        }
        return sum_result;
    }
}

复杂度分析

• 时间复杂度$O(MN)$：最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为$O(MN)$；
• 空间复杂度$O(MN)$：最差情况下，布尔数组visited内存储矩阵所有单元格的索引，使用$O(MN)$的额外空间。

0x0c 剪绳子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。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

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

提示：

2 <= n <= 58

算法详解

数学推导

设将长度为n的绳子切为a段，满足：$n = n_{1} + n_{2} +… + n_{a}$，则本题等价于求解$max(n_{1}*n_{2}*…*n_{a})$。提出两个假设：1）当所有绳段长度相等时，乘积最大；2）最优的绳段长度为3。进行推导如下：

根据算术几何均值不等式：

$$\frac{(n_{1}+n_{2}+...+n_{a})}{a} \ge \sqrt[a]{n_{1}*n_{2}*...*n_{a}}$$

当且仅当$n_{1} = n_{2} = … = n_{a}$时成立。故将绳子以相等的长度等分为多段，得到的乘积最大。

设将绳子按照x长度等分为a段，即n=a*x，则乘积为$x^{a}$。由于n为常数，满足$x^{a} = x^{\frac{n}{x}} = (x^{\frac{1}{x}})^{n}$。

构造函数$y = x^{\frac{1}{x}}$，对x求导得：

$$y' = \frac{1-lnx}{x^{2}}*x^{\frac{1}{x}}$$

令y’=0，则1-lnx=0，得驻点$x_{0} = 2.7$且该点为极大值点。由于切分长度x必须为整数，分别带入最接近e的整数2或3，比较可知x=3时乘积达到最大。故尽可能将绳子以长度3等分为多段时，乘积最大。

结合以上分析，本算法流程如下：

• 当n <= 3时，按照数学推导不应切分，但由于题目要求必须剪成两段及以上，故此时返回n-1；
• 当n > 3时，n可表示为n = 3*a + b，分别求出整数部分a和余数部分b。
  • 当b == 0时，返回pow(3, a)；
  • 当b == 1时，需将一个3+1转换成2+2，因此返回pow(3, a-1)*4；
  • 当b === 2时，返回pow(3, a)*2。

动态规划

• 状态定义：dp[i]表示长度为i的绳子剪短后的最大乘积；
• 初始状态：dp[0]=1，dp[1]=1；
• 状态转移方程：dp[i] = Math.max(dp[i], Math.max(j*dp[i-j], j*(i-j)))。对于循环到的长度i，假设将其剪成两段，一段长度为j，另一段为i-j。此时需要比较j*(i-j)与j*(dp[i-j])的大小，根据比较结果决定是否继续剪下去：若j*(i-j) > j*(dp[i-j])，说明将长度为i的绳子剪成两段得到最大结果；否则说明需要继续分段，此时将切割长度从i转化为i-j。
• 返回值：dp[n]。

解题代码

Method1 Mathematical Solution

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

Method2 DP

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1;j < i;j++){
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

复杂度分析

• Method1
  • 时间复杂度$O(1)$：方法一仅包含求整、求余和次方运算。
  • 空间复杂度$O(1)$：变量均使用常数大小的额外空间。
• Method2
  • 时间复杂度$O(N^{2})$：该方法需要进行两层嵌套循环，故时间复杂度为平方级别。
  • 空间复杂度$O(N)$：开辟长度为n的数组。

0x0d 剪绳子II

题目描述

本题目与剪绳子I的操作过程完全相同，唯一不同的是n的范围扩展至2 <= n <= 1000。结合上题分析可知，最终乘积呈现指数式增长，故考虑部分编程语言中int32甚至int64类型数据出现溢出的情况，要求最终结果需要进行模1e9+7的处理。

算法详解

本题目与上题基本思路相同，唯一区别为需要进行模运算。故引入快速幂乘法实现该运算。然而，由于模运算的存在无法进行动态规划，于是采用贪心算法解题。

解题代码

Method1 Mathematical Solution

class Solution {
    public int cuttingRope(int n) {
        int modular = (int)1e9+7;
        if(n <= 3) return n-1;
        int a = n / 3;
        int b = n % 3;
        if(b == 0) return (int)fast_power(3, a);
        else if(b == 1) return (int)(fast_power(3, a-1)*4 % modular);
        else return (int)(fast_power(3, a)*2 % modular);
    }

    // This function is used to calculate pow(x, a)
    public long fast_power(long x, int a){
        long result = 1;
        while(a > 0){
            if(a%2 != 0){
                result = (result * x) % 1000000007;
            }
            x *= x;
            x %= 1000000007;
            a /= 2;
        }
        return result;
    }
}

Method2 Greedy Algorithm

class Solution {
    public int cuttingRope(int n) {
        if(n < 4) return n-1;
        if(n == 4) return 4;
        long final_result = 1;
        int mod_number = (int)1e9+7;
        while(n > 4){
            final_result *= 3;
            final_result %= mod_number;
            n -= 3;
        }
        return (int)(final_result*n % mod_number);
    }
}

复杂度分析

• Method1
  • 时间复杂度$O(log_{2}N)$：使用快速幂算法降低时间复杂度。
  • 空间复杂度$O(1)$：变量使用常数大小的空间。
• Method2
  • 时间复杂度$O(N)$；
  • 空间复杂度$O(1)$。

0x0e 二进制中1的个数

题目描述

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

示例：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

提示：

输入必须是长度为 32 的 二进制串 。

算法详解

结合题目需求，可以采用逐位判断与n&(n-1)两种方法。

逐位判断

根据与运算定义，二进制数字n存在以下性质：

• 若n&1 == 0，则n最右一位为0；
• 若n&1 == 1，则n最右一位为1。

根据以上特点，考虑以下循环算法：

• 若n最右一位是否为1，若为1则count_result自加1，否则continue；
• 本题要求把数字n看作无符号数，使用无符号右移一位（Java中为>>>）。

运用n&(n-1)

(n-1)运算：二进制数字n最右边的1变成0，随后此1右边的0都变成1;

n&(n-1)运算：二进制数字n最右边的1变成0，其余不变。

根据以上特点，考虑循环算法：

• 循环消去最右边的1，当n == 0时跳出循环；
• 循环内部持续增加count_result，同时采用n&(n-1)持续消去数字n最右边的1。

解题代码

Method1 Rotation Count

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count_result = 0;
        while(n != 0){
            if((n&1)==1) count_result += 1;
            n >>>= 1;
        }
        return count_result;
    }
}

Method2 ‘1’ Elimination

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count_result = 0;
        while(n != 0){
            count_result += 1;
            n &= (n-1);
        }
        return count_result;
    }
}

复杂度分析

• Method1
  • 时间复杂度$O(log_{2}N)$：此算法循环内部仅有移位、与、加等基本运算，占用$O(1)$；逐位判断需循环$log_{2}n$次，其中$log_{2}n$代表数字n最高位1所在的位数。
  • 空间复杂度$O(1)$。
• Method2
  • 时间复杂度$O(M)$：n&(n-1)操作仅有减法和与运算，占用$O(1)$；设M为二进制数字n中1的个数，则需要循环M次，每轮消去一个1。
  • 空间复杂度$O(1)$。

0x0f 数值的整数次方

题目描述

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

算法详解

针对幂运算问题都可以通过快速幂算法提高运算效率。快速幂实际上是二分思想的一种应用，现推导如下：

$x^{n} = x^{n/2}*x^{n/2}=(x^{2})^{n/2}$，令n/2为整数，则分奇偶两种情况讨论，设向下取整符号为//：

• 当n为偶数时，$x^{n} = (x^{2})^{n//2}$；
• 当n为奇数时，$x^{n} = (x^{2})^{n//2}*x$。

结合以上推导，通过下述方法获取幂结果：

• 通过循环$x = x^{2}$操作，每次把幂从n降至n//2，直至将幂降为0；
• 设count=1，则初始状态为$x^{n} = x^{n}*count$。循环二分过程中，每当n为奇数，将多出的一项x乘入count，最终可化至$x^{n} = x^{0}*count = count$，返回count即可。

为加快运算速率，将不同运算转化为位运算：

• 向下整除n//2等价于有符号数右移一位n>>1；
• 取余数n%2等价于判断二进制最后一位数值n&1。

解题代码

class Solution {
    public double myPow(double x, int n) {
        long b = n;
        double final_result = 1.0000;
        if(x == 0) return 0;
        if(n == 0) return 1;
        if(n > 0){
            final_result = fast_power(x, b);
        }
        if(n < 0){
            final_result = 1.00000/fast_power(x, -b);
        }
        return final_result;
    }

    public double fast_power(double x, long n){
        double result = 1.00000;
        while(n > 0){
            if((n&1) == 1){
                result *= x;
            }
            x *= x;
            n >>= 1;
        }
        return result;
    }
}

复杂度分析

• 时间复杂度$O(log_{2}N)$：二分法的时间复杂度为对数级别；
• 空间复杂度$O(1)$：结果变量及临时变量等占用常数大小的额外空间。