一、整数反转
难度：中等
题目传送门：整数反转
题目
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围[−2^31, 2^31− 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示：
- -2^31 <= x <= 2^31 - 1
思路
通过取模获得最后一位，通过除法截取前面的数据。 需要特别主要的是处理数据的溢出。
代码
func reverse(x int) int {
intMax := 1<<31 - 1
intMin := -1 << 31
if x > intMax || x < intMin || x == 0 {
return 0
}
result := 0
for x != 0 {
// 第一位就后置了
result = result*10 + x%10
x = x / 10
if result > intMax || result < intMin {
return 0
}
}
if result > intMax || result < intMin {
return 0
}
return result
}
性能
来自Leetcode, 0表示小于1个单位。
- 执行用时: 0ms
- 内存消耗: 2 MB
二、杨辉三角
难度：简单
题目传送门：杨辉三角
题目
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例2:
输入: numRows = 1
输出: [[1]]
提示：
- 1 <= numRows <= 30
思路
重点是只需要计算对称的左半边即可。
代码
func generate(numRows int) [][]int {
if numRows == 0 {
return nil
}
result := make([][]int, numRows)
for i := 0; i < numRows; i++ {
raw := make([]int, i+1)
for j := 0; j < (i+2)/2; j++ {
if j == 0 {
raw[j] = 1
raw[i-j] = 1
continue
}
raw[j] = result[i-1][j-1] + result[i-1][j]
raw[i-j] = raw[j]
}
result[i] = raw
}
return result
}
性能
来自Leetcode, 0表示小于1个单位。
- 执行用时: 0ms
- 内存消耗: 1.9 MB
三、幂运算
难度：中等
题目传送门：Pow
题目
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
提示：
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31-1
- -10^4 <= xn <= 10^4
思路
浮点运算在Go的实现有存在一个重要的问题：精度。所以不能简单的进行运算，本题保留8位精度。
简单方法，直接调用内置math函数库。
重复造轮子方法：按照快速降幂的思路，将n折半，计算因子扩大为2次幂。n折半后是奇数，则需要单独✖️计算因子。
代码
保留8位精度，是一个共用方法。
func roundFloat(r float64) float64 {
return float64(int(r*10000000)) / 10 / 1000000
}
简单方法实现：
func myPow2(x float64, n int) float64 {
return roundFloat(math.Pow(x, float64(n)))
}
重复造轮子：
func myPow3(x float64, n int) float64 {
switch {
case n == 0 || x == 1:
return 1
case x == 0:
return 0
}
if n < 0 {
n = -n
x = 1 / x
}
result := 1.0
for i := n; i > 0; i = i / 2 {
if i%2 != 0 {
result *= x
}
x *= x
}
return roundFloat(result)
}
性能
来自Leetcode, 0表示小于1个单位。
两种方法均得到以下数据：
- 执行用时: 0ms
- 内存消耗: 1.9 MB