回文数
做题过程
不会，只能面向结果。
算法概述
原题
本题要求为如题所示。
- 时间复杂度为O(logn)：log类型的时间复杂度是自动忽略底数的，这是因为底数相当于常数
- 空间复杂度为O(1)：优化的核心
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
}
|
总结
这道题的核心不在于推导出某个能用的公式来解决这个问题，而是通过数学计算（常数空间处理）避免额外的复杂度，核心在于优化复杂度，而非解决问题。
阶乘后的零🟨
做题过程
不会，超时了。
算法概述
原题
本题要求为计算给定数阶乘结构的尾部零的个数。就是说把阶乘看成很多因数的乘积，然后想象一下做因式分解把所有因数分为质数，那么只有2*5能变成10，但是2肯定比5多，所以看5的个数就行了。
- 时间复杂度为O(logn)
- 空间复杂度为O(1)
JAVA
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int trailingZeroes(int n) {
int ans=0;
while(n!=0){
n/=5;
ans+=n;
}
return ans;
}
}
|
总结
像这个解法计算5的个数，是通过计算有多少个5的倍数来计算的，众所周知，只有5的倍数能提供5的质因数，而上述代码就是通过不断计算5的倍数、25的倍数、125的倍数，等等，来计算有多少个5的，当然，是25的倍数肯定也是5的倍数，但25的倍数能多提供一个5，所以要多计算一次，以此类推。
x的平方根🟩
做题过程
不会。
算法概述
原题
本题要求为算出给定参数的算术平方根取整。
- 时间复杂度为O(logn)
- 空间复杂度为O(1)
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}
}
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int left = 0, right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
long midSquared = (long) mid * mid;
if (midSquared == x) {
return mid;
} else if (midSquared < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (Math.abs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return (int) x0;
}
}
|
总结
牛顿迭代法的更新规则源于泰勒级数和切线法，以下四个式子：
f(x)=x2−C
xn+1=xn−f′(xn)f(xn)
xn+1=xn−2xnxn2−C
xn+1=21(xn+xnC)
Pow(x, n)🟨
做题过程
快速幂，但是不记得了。
算法概述
原题
本题要求为计算幂。使用 快速幂+迭代 算法实现。
- 时间复杂度为O(logn)：快速幂是这样的
- 空间复杂度为O(1)
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
long power = n;
if (power < 0) {
x = 1 / x;
power = -power;
}
double result = 1.0;
while (power > 0) {
if (power % 2 == 1) {
result *= x;
}
x *= x;
power /= 2;
}
return result;
}
}
|
总结
其实就是二分迭代通过 使底数以平方上升 减少幂运算的次数。
x→x2→x4→x9→x19→x38→x77
像上述例子中，就是不断使底数变为自己的平方，基本就是这个思路，其实很简单。
直线上最多的点数🟥
做题过程
不会。
算法概述
原题
本题要求为给出多个数组表示点坐标，判断最多有多少个点在同一直线上。还是使用哈希表记录，但是在处理精度上要深入利用基本类型的位来表示信息，避免装不下。
- 时间复杂度为O(n2×logm)：最坏情况下就是每个点都要遍历，且需要计算最大公约数
- 空间复杂度为O(n)
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) {
return n;
}
int ret = 0;
for (int i = 0; i < n; i++) {
if (ret >= n - i || ret > n / 2) {
break;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int j = i + 1; j < n; j++) {
int x = points[i][0] - points[j][0];
int y = points[i][1] - points[j][1];
if (x == 0) {
y = 1;
} else if (y == 0) {
x = 1;
} else {
if (y < 0) {
x = -x;
y = -y;
}
int gcdXY = gcd(Math.abs(x), Math.abs(y));
x /= gcdXY;
y /= gcdXY;
}
int key = y + x * 20001;
map.put(key, map.getOrDefault(key, 0) + 1);
}
int maxn = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
int num = entry.getValue();
maxn = Math.max(maxn, num + 1);
}
ret = Math.max(ret, maxn);
}
return ret;
}
public int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
}
|
总结
在处理数据上还是暴力，主要是存储数据到哈希表上的预处理，用到了 通过分子分母同除以最大公约数获得唯一最简分数 以及 扩大数据范围确保一组数据对应结果唯一 等，其实用到的技巧和第430场周赛里的第三题一样。
