剑指 Offer 44. 数字序列中某一位的数字

解题思路

第一步：确定n所在的数字位数，记为digit；

第二步：确定n所在的数字，记为num；

第三步：确定n是num中的哪一位。

1. 确定所求数位的所在数字的位数

image-20220303130712123

1
2
3
4
5
6
7
start, digit, count :=1,1,9
for count < n {
    n -= count
    start *= 10
    digit ++
    count = start * digit * 9
}
2. 确定所求数位所在的数字
1
num := start + (n-1)/ digit // start就是第一位，所以要减去1
3. 确定所求数位在 num 的哪一数位
1
2
index := (n-1)%digit
numStr := strconv.Itoa(num)

复杂度分析：

  • 时间复杂度 ： 所求数位 n对应数字 num 的位数 digit最大为 ；第一步最多循环次；第三步中将 num 转化为字符串使用时间；因此总体为O(logn) 。
  • 空间复杂度O(logn) ： 将数字 num转化为字符串占用的额外空间。

258. 各位相加

某数xyzk,可以分解为得到$num = A + B$

A部分必然可以被9整除，对于B来说，他就和num有着一样的特性，即

1
B%9==num%9

所以

1
2
3
func addDigits(num int) int {
    return (num-1)%9 + 1
}

剑指 Offer 14- II. 剪绳子 II

运用数学的求导求最大值

  1. 将绳子n切为a段即$n=ax$，乘积为：$x^a$

n为常数，即当$x^{1/x}$取得最大值，乘积最大，即：

易得驻点$x_0=e$故我们切绳子的时候3为最优的长度

1
2
3
4
5
6
7
8
9
10
11
12
func cuttingRope(n int) int {
    if n <=3 {
        return n-1
    }
    res := 1
    for n>4 {
        res *= 3
        n -= 3
        res%=(1e9+7)
    }
    return res*n%(1e9+7)
}