0x00 前言
寒假赋闲在家,搞科研的同时希望提升一下自己的代码水平,于是回到阔别已久的LeetCode平台开始刷题。这次选择了剑指offer系列题目,编程语言采用Java。话不多说,直接开刷。
0x01 数组中重复的数字
题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
1 | 输入: |
限制:
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表示元素与索引一一对应。
解题代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(N)$。
- 空间复杂度$O(1)$:该算法提供原地置换,无需开辟新的存储空间。
0x02 二维数组中的查找
题目描述
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
1 | [ |
给定 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
,找到目标。
该算法选择从右上角开始遍历,需要注意下标范围及二维数组空判断问题。
解题代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(M+N)$:其中N和M分别代表矩阵的行数和列数,算法最多循环N+M次;
- 空间复杂度$O(1)$:i,j指针使用常数大小的额外空间。
0x03 替换空格
题目描述
请实现一个函数,把字符串 s 中的每个空格替换成”%20”。
示例 1:
1 | 输入:s = "We are happy." |
限制:
0 <= s 的长度 <= 10000
算法详解
根据题目要求,最简单的方法是采用String类自带的替换函数replaceAll()
,当然面试官肯定不会允许。于是就需要自己研究替换函数。注意到Java中String类型使用final关键词修饰,即String对象是不可修改的,从而考虑两种方法:
- 方法一:引入可修改的数据类型StringBuilder,最后使用
toString()
函数转换成String类型输出即可。 - 方法二:引入静态数组
char[]
,首先确定数组的长度为原始字符串的三倍(假设原始字符串全部由空格组成),随后采用双指针法循环遍历原始字符串和新的字符串,完成比较与添加字符的操作。
解题代码
Method 1
1 | class Solution { |
Method 2
1 | class Solution { |
复杂度分析
Method1
- 时间复杂度$O(N)$。
- 空间复杂度$O(N)$:Java新建StringBuilder使用了线性大小的额外空间。
Method2
- 时间复杂度$O(N)$。
- 空间复杂度$O(1)$:由于是原地扩展字符串s的长度,因此使用$O(1)$的额外空间。
0x04 从尾到头打印链表
题目描述
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
1 | 输入:head = [1,3,2] |
限制:
0 <= 链表长度 <= 10000
算法详解
本题目为最基础的链表逆序问题,可采用两种不同的数据结构辅助完成:
- 方法一:不引入栈而仅使用定长数组。由于Java中数组具有长度固定的特点,故首先需要遍历链表以获得结果数组的长度。建立对应长度数组后,采用从后向前逐位填充的方法完成逆序输出。
- 方法二:引入栈这一数据结构。由于栈具有LIFO的特点,只需通过进出操作就能实现链表逆序输出,将输出结果按序存入结果数组即可。
解题代码
Method 1
1 | /** |
Method 2
1 | /** |
复杂度分析
两种方法的时间复杂度与空间复杂度均为$O(N)$。
0x05 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
1 | 前序遍历 preorder = [3,9,20,15,7] |
返回如下的二叉树:
1 | 3 |
限制:
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
1 | /** |
Method2 Solution With Hashmap
1 | // This method can only be used in the construction of binary tree without duplicate nodes |
复杂度分析
两种方法的时间复杂度与空间复杂度均为$O(N)$。
参考链接
0x06 用两个栈实现队列
题目描述
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail
和deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead
操作返回 -1 )
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
提示:
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栈顶元素即可。
解题代码
1 | class CQueue { |
复杂度分析
- 时间复杂度:
appendTail()
函数为$O(1)$;deleteHead()
函数在N次队首元素删除操作中共需完成N个元素的倒序; - 空间复杂度$O(N)$:最差情况下,栈A和B共保存N个元素。
0x07 斐波那契数列
题目描述
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
1 | F(0) = 0, F(1) = 1 |
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
1 | 输入:n = 2 |
示例 2:
1 | 输入:n = 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即可。
解题代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(N)$:计算f(n)需要循环n次,每轮循环内计算操作使用$O(1)$;
- 空间复杂度$O(1)$:几个标志变量使用常数大小的额外空间。
0x08 青蛙跳台阶问题
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
1 | 输入:n = 2 |
示例 2:
1 | 输入:n = 7 |
示例 3:
1 | 输入:n = 0 |
提示:
0 <= n <= 100
算法详解
本题目与斐波那契数列解题方法类似,只不过初始参数不同,可以通过普通动态规划和简化版动态规划解决问题,后者占用更少的空间资源。
解题代码
Method1 General DP
1 | class Solution { |
Method2 Simple Version
1 | class Solution { |
复杂度分析
Method1
时间与空间复杂度均为$O(N)$。
Method2
时间复杂度为$O(N)$,空间复杂度为$O(1)$。
0x09 旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例 1:
1 | 输入:[3,4,5,1,2] |
示例 2:
1 | 输入:[2,2,2,0,1] |
算法详解
本题显然需要使用二分法,目标元素为旋转点元素,一般情况下满足以下条件:该元素值小于右侧元素,大于左侧元素。算法设计过程中需要考虑以下两个特殊情况:
- 输入数组部分元素相同;
- 输入数组旋转后的结果与初始结果相同,均为全升序序列。
二分法本身分以下三种情况讨论:
nums[mid] > nums[right]
nums[mid] < nums[right]
nums[mid] == nums[right]
具体题解参考如下链接:
需要注意的是,二分法过程中经常使用mid = left + (left-right) / 2
来防止溢出。
解题代码
1 | class Solution { |
复杂度分析
- 时间复杂度$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:
1 | 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" |
示例 2:
1 | 输入:board = [["a","b"],["c","d"]], word = "abcd" |
提示:
1 | 1 <= board.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
,代表是否搜索到目标字符串。
解题代码
1 | class Solution { |
复杂度分析
假设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:
1 | 输入:m = 2, n = 3, k = 1 |
示例 2:
1 | 输入:m = 3, n = 1, k = 0 |
提示:
1 | 1 <= n,m <= 100 |
算法详解
本题与上题类似,均为典型的搜索&回溯问题。与上题不同的是,本题目的起点为(0,0)
而非任意点,同时每次机器人运动方向只有向右和向下两个方向。可以采用广度优先搜索与深度优先搜索两种方法解题。可参考题解如下:机器人的运动范围(回溯算法,DFS/BFS)
解题代码
Method1 DFS
1 | class Solution { |
Method2 BFS
1 | class Solution { |
复杂度分析
- 时间复杂度$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:
1 | 输入: 2 |
示例 2:
1 | 输入: 10 |
提示:
1 | 2 <= n <= 58 |
算法详解
数学推导
设将长度为n的绳子切为a段,满足:$n = n_{1} + n_{2} +… + n_{a}$,则本题等价于求解$max(n_{1}*n_{2}*…*n_{a})$。提出两个假设:1)当所有绳段长度相等时,乘积最大;2)最优的绳段长度为3。进行推导如下:
根据算术几何均值不等式:
当且仅当$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’=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
1 | class Solution { |
Method2 DP
1 | class Solution { |
复杂度分析
- 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
1 | class Solution { |
Method2 Greedy Algorithm
1 | class Solution { |
复杂度分析
- Method1
- 时间复杂度$O(log_{2}N)$:使用快速幂算法降低时间复杂度。
- 空间复杂度$O(1)$:变量使用常数大小的空间。
- Method2
- 时间复杂度$O(N)$;
- 空间复杂度$O(1)$。
0x0e 二进制中1的个数
题目描述
请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。
示例:
1 | 输入:00000000000000000000000000001011 |
提示:
输入必须是长度为 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
1 | public class Solution { |
Method2 ‘1’ Elimination
1 | public class Solution { |
复杂度分析
- 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)$。
- 时间复杂度$O(M)$:
0x0f 数值的整数次方
题目描述
实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。
示例 1:
1 | 输入: 2.00000, 10 |
示例 2:
1 | 输入: 2.00000, -2 |
说明:
- -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
。
解题代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(log_{2}N)$:二分法的时间复杂度为对数级别;
- 空间复杂度$O(1)$:结果变量及临时变量等占用常数大小的额外空间。