案例
回文数（简）
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
var isPalindrome = function(x) {
return x.toString().split('').reverse().join('') == x
};
var isPalindrome = function (x) {
x = x.toString()
if (x < 0) return false
let i = 0;
let j = x.length - 1;
while (i < x.length / 2) {
if (x[i++] !== x[j--]) return false;
}
return true
};
加一(简)
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
var plusOne = function (digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] !== 9) {
digits[i]++;
return digits
} else {
digits[i] = 0;
}
}
digits.unshift(1);
return digits;
};
阶乘后的零(中)
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 104
**进阶：**你可以设计并实现对数时间复杂度的算法来解决此问题吗？
解题思路
首先肯定不能依赖于把阶乘算出来再去判断有多少个零了，因为递归的方式会导致非常大的数字计算非常慢，并且可能会导致堆栈溢出错误，特别是对于较大的n值。
其次，计算阶乘末尾0的数量并不需要实际计算出阶乘的值。末尾0的数量实际上是由阶乘中因子5的数量决定的，因为每个10都是由2和5相乘得来的，而在阶乘中2的数量通常比5多，所以我们只需要计算5的数量。
通过不断除以5并累加结果来计算阶乘中5的因子的数量，从而得到末尾0的数量。这是因为每隔5个数就有一个5的倍数，每隔25个数就有一个额外的5（因为25有两个5的因子），以此类推。这个算法的时间复杂度是O(log n)，比直接计算阶乘要高效得多。
var trailingZeroes = function (n) {
let count = 0;
while (n > 0) {
n = Math.floor(n / 5);
count += n;
}
return count;
};
x 的平方根 （简）
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
解题思路
- 初始化变量：
l（左边界）初始化为 0。r（右边界）初始化为x。ans（答案）初始化为 -1，用于存储找到的平方根的整数部分。
- 二分查找循环：
- 当
l小于等于r时，执行循环。 - 计算中点
mid，这是l和r之间的中间值，用Math.floor(l + (r - l) / 2)计算。
- 当
- 检查中点：
- 如果
mid * mid小于等于x，说明mid可能是x的平方根的整数部分。- 更新
ans为mid。 - 将左边界
l更新为mid + 1，继续在更大的数中查找。
- 更新
- 如果
mid * mid大于x，说明mid太大了。- 将右边界
r更新为mid - 1，继续在更小的数中查找。
- 将右边界
- 如果
- 返回结果：
- 当循环结束后，返回
ans，即x的平方根的整数部分。
- 当循环结束后，返回
这个算法的时间复杂度是 O(logx)，因为它是通过不断地将搜索范围减半来找到答案的。这是一种非常高效的计算平方根整数部分的方法。
var mySqrt = function (x) {
let i = 0;
while (i * i < x) {
if ((i + 1) * (i + 1) <= x) {
i++;
} else {
return i
}
}
return i
};
var mySqrt = function (x) {
let l = 0, r = x, ans = -1;
while (l <= r) {
const mid = Math.floor(l + (r - l) / 2);
if (mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
};
Pow(x, n)（中）
实现 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
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一个整数- 要么
x不为零，要么n > 0。 -104 <= xn <= 104
解题思路
当然可以！这段代码定义了一个名为 myPow 的函数，用于计算 x 的 n 次幂。这个函数使用了一种称为“快速幂”的算法，这是一种高效计算幂的方法。下面我会逐行解释这个函数的工作原理：
- 函数定义：
var myPow = function (x, n)定义了一个名为myPow的函数，它接受两个参数：x和n。x是基数，n是指数。 - 基本情况：
if (n == 0 || n == 1)检查指数n是否为 0 或 1。如果是，根据幂的基本规则，任何数的 0 次幂都是 1，任何数的 1 次幂都是它本身。因此，如果n是 0，返回 1；如果n是 1，返回x。 - 负指数情况：
else if (n < 0)处理指数为负数的情况。在这种情况下，函数通过递归调用自身，将基数变为1 / x（即 x 的倒数），并将指数变为绝对值，从而计算 x 的负 n 次幂。 - 正指数情况：
else部分处理指数为正数的情况。这里使用了快速幂算法的核心思想。首先，通过n % 2 == 0检查指数n是否为偶数。如果是偶数，函数递归地计算x * x的n / 2次幂。如果n是奇数，函数递归地计算x * x的Math.floor(n / 2)次幂，并乘以基数x。
通过这种方式，每次递归都将问题规模减半，大大减少了所需的乘法次数，从而提高了计算效率。
var myPow = function (x, n) {
if (n == 0 || n == 1) {
return n == 0 ? 1 : x
} else if (n < 0) {
return myPow(1 / x, Math.abs(n))
} else {
return n % 2 == 0 ? myPow(x * x, n / 2) : myPow(x * x, Math.floor(n / 2)) * x
}
};
直线上最多的点数(难)
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
提示：
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104points中的所有点 互不相同
解题思路
- 最大公约数函数
gcd：- 这个函数用于计算两个数
a和b的最大公约数。 - 它通过递归的方式实现：如果
b为 0，则a就是最大公约数；否则，递归调用gcd函数，将b和a除以b的余数作为参数。
- 这个函数用于计算两个数
- 主函数
maxPoints：n存储点的数量，ans初始化为 1，因为至少可以通过一个点。- 外层循环遍历数组中的每个点
points[i]。 - 对于每个
points[i]，内层循环遍历其余的点points[j]（j > i），以计算通过这两点的直线能穿过的最多点数。 - 对于每对点
(points[i], points[j])，计算它们之间的斜率a/b，并使用gcd函数化简为最简形式。 - 这个最简斜率被用作
mapping对象的键，该对象的值是具有相同斜率的所有点的计数。 maxv用于跟踪通过当前点points[i]的直线能穿过的最多点数。- 最后，
ans更新为所有点中的最大点数。
- 返回值：
- 函数返回
ans，即通过任意两点形成的直线能穿过的最多点的数量。
- 函数返回
这个函数的关键在于它如何处理斜率。通过计算两点间的斜率并化简，它能够正确地识别出在同一直线上的点。这样，即使点的坐标不是整数，或者两点间距离很远，只要它们在同一直线上，就能被正确计数。
function maxPoints(points: number[][]): number {
// 辅助函数，用于计算两个数的最大公约数
function gcd(a: number, b: number): number {
// 如果b为0，则a是最大公约数
return b === 0 ? a : gcd(b, a % b);
}
// n存储点的数量，ans初始化为1，因为至少可以通过一个点
let n = points.length, ans = 1;
for (let i = 0; i < n; i++) {
// mapping用于存储具有相同斜率的点的计数
let mapping = new Map(), maxv = 0;
for (let j = i + 1; j < n; j++) {
// 获取两点坐标
let x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
// 计算两点间的纵坐标和横坐标的变化量
let a = x1 - x2, b = y1 - y2;
// 计算并化简斜率
let k = gcd(a, b);
let key = `${a / k}_${b / k}`;
// 获取当前斜率的计数，如果不存在则默认为0
let count = mapping.get(key) || 0;
// 更新斜率的计数
mapping.set(key, count + 1);
// 更新通过当前点points[i]的直线能穿过的最多点数
maxv = Math.max(maxv, count + 1);
}
// 更新所有点中的最大点数
ans = Math.max(ans, maxv + 1);
}
// 返回通过任意两点形成的直线能穿过的最多点的数量
return ans;
}