万表网手表官网_苏州新区做网站_广州seo优化效果_关键词排名靠前

更新时间：2025-04-12

算法题解目录汇总：算法刷题记录——题解目录汇总
技术博客总目录：计算机技术系列博客——目录页

171. Excel 表列序号

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1:

输入: columnTitle = "A"
输出: 1

示例 2:

输入: columnTitle = "AB"
输出: 28

示例 3:

输入: columnTitle = "ZY"
输出: 701

提示：

1 <= columnTitle.length <= 7
columnTitle 仅由大写英文组成
columnTitle 在范围 ["A", "FXSHRXW"] 内

方法一：迭代法（逐位累加）

将每个字符视为一个26进制的数位，但由于Excel的列号从1开始（A=1），我们需要将字符转换为对应的数值后进行计算。从字符串的左到右遍历每个字符，每次将当前结果乘以26并加上当前字符的数值。

代码实现(Java)：

public int titleToNumber(String columnTitle) {int sum = 0;for (int i = 0; i < columnTitle.length(); i++) {char c = columnTitle.charAt(i);sum = sum * 26 + (c - 'A' + 1);}return sum;
}

复杂度分析：

时间复杂度：O(n)，其中n为字符串长度。每个字符遍历一次。
空间复杂度：O(1)。

方法二：递归法（从右到左处理）

递归地处理字符串的最后一个字符，每次将剩余部分的结果乘以26，然后加上当前字符的数值。递归的终止条件是字符串为空时返回0。

代码实现(Java)：

public int titleToNumber(String columnTitle) {if (columnTitle.isEmpty()) return 0;String sub = columnTitle.substring(0, columnTitle.length() - 1);char lastChar = columnTitle.charAt(columnTitle.length() - 1);return titleToNumber(sub) * 26 + (lastChar - 'A' + 1);
}

复杂度分析：

时间复杂度：O(n)，递归深度为n，每次递归处理一个字符。
空间复杂度：O(n)，递归调用栈的空间。

方法三：Java 8流处理

使用Java 8的流（Stream）来处理字符，通过reduce操作累加每个字符的数值，逻辑与迭代法一致但更简洁。

代码实现(Java)：

public int titleToNumber(String columnTitle) {return columnTitle.chars().reduce(0, (sum, c) -> sum * 26 + (c - 'A' + 1));
}

复杂度分析：

时间复杂度：O(n)，每个字符处理一次。
空间复杂度：O(1)。

172. 阶乘后的零

给定一个整数 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 <= 10^4

进阶：
你可以设计并实现对数时间复杂度的算法来解决此问题吗？

方法一：计算因子5的个数

阶乘末尾的零由因子10的数量决定，而10由2和5相乘得到。由于2的数量远多于5的数量，因此问题转化为计算n!中因子5的个数。具体方法是通过不断除以5的幂次（5, 25, 125等），累加结果得到总的5的因子数量。

代码实现(Java)：

public int trailingZeroes(int n) {int count = 0;for (int i = 5; i <= n; i *= 5) {count += n / i;}return count;
}

复杂度分析：

时间复杂度：O(log₅n)，每次循环 i 乘以5，直到超过 n。
空间复杂度：O(1)，仅使用常数空间。

方法二：递归计算

递归地将 n 除以 5 并累加，直到 n 小于 5 为止。每次递归处理当前层的 5 的因子数。

代码实现(Java)：

public int trailingZeroes(int n) {if (n < 5) {return 0;}return n / 5 + trailingZeroes(n / 5);
}

复杂度分析：

时间复杂度：O(log₅n)，递归次数为log₅n。
空间复杂度：O(log₅n)，递归调用栈的深度。

方法三：迭代优化（减少循环次数）

与方法一类似，但显式地逐步处理5的各次幂，避免潜在的整数溢出问题。例如，当处理大数时，逐步计算5、25、125等的贡献。

代码实现(Java)：

public int trailingZeroes(int n) {int count = 0;int powerOf5 = 5;while (powerOf5 <= n) {count += n / powerOf5;powerOf5 *= 5;}return count;
}

复杂度分析：

时间复杂度：O(log₅n)，与方法一相同。
空间复杂度：O(1)，使用常数空间。

173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历**二叉搜索树（BST）**的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释：

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 10^5] 内
0 <= Node.val <= 10^6
最多调用 10^5 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

方法一：使用栈模拟中序遍历

利用栈来模拟中序遍历的过程。初始化时将根节点的所有左子节点依次压入栈，每次调用 next() 时弹出栈顶元素，并将该元素的右子树的所有左子节点压入栈中，确保栈顶始终是下一个要访问的节点。

节点定义(Java)：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

代码实现(Java)：

class BSTIterator {private Deque<TreeNode> stack;public BSTIterator(TreeNode root) {stack = new LinkedList<>();pushAllLeft(root);}private void pushAllLeft(TreeNode node) {while (node != null) {stack.push(node);node = node.left;}}public int next() {TreeNode curr = stack.pop();pushAllLeft(curr.right);return curr.val;}public boolean hasNext() {return !stack.isEmpty();}
}

复杂度分析：

时间复杂度：
- 构造函数：O(h)，其中 h 是树的高度，最坏情况下需要遍历到最左叶子节点。
- next()：均摊时间复杂度 O(1)，每个节点被压入和弹出栈各一次，总操作次数为 O(n)。
- hasNext()：O(1)，直接判断栈是否为空。
空间复杂度：O(h)，栈的最大深度等于树的高度，最坏情况下（树退化为链表）为 O(n)。

方法二：预先展开中序遍历序列

提前通过中序遍历将整个树的节点值存入列表，然后通过索引依次访问。这种方法牺牲空间换时间，适合多次调用 next() 和 hasNext() 的场景。

代码实现(Java)：

class BSTIterator {private List<Integer> inorderNodes;private int index;public BSTIterator(TreeNode root) {inorderNodes = new ArrayList<>();index = 0;inorderTraversal(root);}private void inorderTraversal(TreeNode root) {if (root == null) return;inorderTraversal(root.left);inorderNodes.add(root.val);inorderTraversal(root.right);}public int next() {return inorderNodes.get(index++);}public boolean hasNext() {return index < inorderNodes.size();}
}

复杂度分析：

时间复杂度：
- 构造函数：O(n)，需要遍历所有节点。
- next() 和 hasNext()：O(1)。
空间复杂度：O(n)，存储所有节点的值。

174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的右下角。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只向右或向下移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7

解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7 。

示例 2：

输入：dungeon = [[0]]
输出：1

提示：

m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

方法：动态规划

状态定义：dp[i][j] 表示从位置 (i, j) 到终点所需的最小初始血量。
边界条件：终点位置的初始血量取决于其数值，确保进入该位置后血量至少为1。
状态转移：从右下角开始逆推，每个位置的最小初始血量由右边和下边的最小值决定，并考虑当前房间的数值影响。

代码实现(Java)：

class Solution {public int calculateMinimumHP(int[][] dungeon) {int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m][n];// 初始化右下角dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);// 填充最后一行for (int j = n-2; j >= 0; j--) {dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);}// 填充最后一列for (int i = m-2; i >= 0; i--) {dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);}// 填充其他位置for (int i = m-2; i >= 0; i--) {for (int j = n-2; j >= 0; j--) {int minNext = Math.min(dp[i+1][j], dp[i][j+1]);dp[i][j] = Math.max(1, minNext - dungeon[i][j]);}}return dp[0][0];}
}

复杂度分析：

时间复杂度：O(mn)，
空间复杂度：O(mn)。

175. 组合两个表

表: Person

+-------------+---------+
| 列名         | 类型     |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+

personId 是该表的主键（具有唯一值的列）。
该表包含一些人的 ID 和他们的姓和名的信息。

表: Address

+-------------+---------+
| 列名         | 类型    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+

addressId 是该表的主键（具有唯一值的列）。
该表的每一行都包含一个 ID = PersonId 的人的城市和州的信息。

编写解决方案，报告 Person 表中每个人的姓、名、城市和州。如果 personId 的地址不在 Address 表中，则报告为 null 。

以 任意顺序 返回结果表。

结果格式如下所示。

示例 1:

输入:

Person表:

+----------+----------+-----------+
| personId | lastName | firstName |
+----------+----------+-----------+
| 1        | Wang     | Allen     |
| 2        | Alice    | Bob       |
+----------+----------+-----------+

Address表:

+-----------+----------+---------------+------------+
| addressId | personId | city          | state      |
+-----------+----------+---------------+------------+
| 1         | 2        | New York City | New York   |
| 2         | 3        | Leetcode      | California |
+-----------+----------+---------------+------------+

输出:

+-----------+----------+---------------+----------+
| firstName | lastName | city          | state    |
+-----------+----------+---------------+----------+
| Allen     | Wang     | Null          | Null     |
| Bob       | Alice    | New York City | New York |
+-----------+----------+---------------+----------+

解释:
地址表中没有 personId = 1 的地址，所以它们的城市和州返回 null。
addressId = 1 包含了 personId = 2 的地址信息。

方法思路

SELECT：指定需要输出的字段，包括 Person 表的 firstName 和 lastName，以及 Address 表的 city 和 state。
FROM：以 Person 表为主表，使用别名 p 简化引用。
LEFT JOIN：将 Person 表与 Address 表通过 personId 进行左连接，确保所有人员信息都被保留。Address 表使用别名 a。
连接条件：p.personId = a.personId 确保正确匹配两个表中的记录。

代码实现(SQL)：

SELECT p.firstName,p.lastName,a.city,a.state
FROM Person p
LEFT JOIN Address a ON p.personId = a.personId;

176. 第二高的薪水

Employee 表：

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+

id 是这个表的主键。
表的每一行包含员工的工资信息。

查询并返回 Employee 表中第二高的不同薪水。如果不存在第二高的薪水，查询应该返回 null(Pandas 则返回 None) 。

查询结果如下例所示。

示例 1：

输入：

Employee 表：

+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

输出：

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

示例 2：

输入：

Employee 表：

+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+

输出：

+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

方法思路

要查询 Employee 表中第二高的不同薪水，可以按照以下步骤实现：

去重与排序：使用 DISTINCT 关键字获取所有不同的薪水，并按降序排列。
取第二高值：通过 LIMIT 1 OFFSET 1 跳过第一个（最高）值，取第二个值。
处理空值：当没有第二高的薪水时，子查询返回 NULL，确保最终结果正确。

代码实现(SQL)：

SELECT (SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1) 
AS SecondHighestSalary;

177. 第N高的薪水

表: Employee

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+

在 SQL 中，id 是该表的主键。
该表的每一行都包含有关员工工资的信息。

查询 Employee 表中第 n 高的工资。如果没有第 n 个最高工资，查询结果应该为 null 。

查询结果格式如下所示。

示例 1:

输入:

Employee表:

+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

n = 2

输出:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

示例 2:

输入:
Employee 表:

+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+

n = 2

输出:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| null                   |
+------------------------+

方法思路

去重与排序：使用 DISTINCT 关键字获取所有不同的薪水，并按降序排列。
动态偏移量：通过 LIMIT 1 OFFSET (N-1) 跳过前 N-1 个记录，取第 N 高的薪水。
核心查询：
- DISTINCT salary：去重处理重复的薪水值。
- ORDER BY salary DESC：按薪水降序排列。
- LIMIT 1 OFFSET M：跳过 M 条记录后取 1 条，即第 N 高的薪水。
处理空值：当没有足够的记录时，子查询返回空值，外层函数自动返回 NULL。

代码实现(SQL)：

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGINDECLARE M INT;SET M = N - 1;  -- 计算偏移量，OFFSET 从 0 开始RETURN (SELECT DISTINCT salaryFROM EmployeeORDER BY salary DESCLIMIT 1 OFFSET M  -- 跳过 M 条记录后取 1 条);
END;

178. 分数排名

表: Scores

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| score       | decimal |
+-------------+---------+

id 是该表的主键（有不同值的列）。
该表的每一行都包含了一场比赛的分数。Score 是一个有两位小数点的浮点值。

编写一个解决方案来查询分数的排名。排名按以下规则计算:

分数应按从高到低排列。
如果两个分数相等，那么两个分数的排名应该相同。
在排名相同的分数后，排名数应该是下一个连续的整数。换句话说，排名之间不应该有空缺的数字。
按 score 降序返回结果表。

查询结果格式如下所示。

示例 1:

输入:

Scores 表:

+----+-------+
| id | score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

输出:

+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

方法思路

排序分数：按 score 降序排列所有记录。
计算连续排名：使用 DENSE_RANK() 窗口函数为每个分数生成连续且无间隔的排名。
结果排序：最终结果按 score 降序排列。

代码实现(SQL)：

SELECT score,DENSE_RANK() OVER (ORDER BY score DESC) AS 'rank'
FROM Scores
ORDER BY score DESC;

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：
输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 10^9

方法：字符串比较器

转换为字符串数组：将输入的整数数组转换为字符串数组，以便进行拼接比较。
自定义排序规则：比较两个字符串的不同拼接顺序（a+b 和 b+a），选择更大的顺序进行排列。
处理全零情况：若排序后的结果以零开头，说明所有元素都是零，直接返回 “0”。
拼接字符串：将排序后的字符串数组拼接成最终结果。

代码实现(Java)：

class Solution {public String largestNumber(int[] nums) {// 将整数数组转换为字符串数组String[] strs = new String[nums.length];for (int i = 0; i < nums.length; i++) {strs[i] = String.valueOf(nums[i]);}// 自定义比较器，比较拼接后的字符串大小Arrays.sort(strs, new Comparator<String>() {@Overridepublic int compare(String a, String b) {return (b + a).compareTo(a + b);}});// 处理全零的情况if (strs[0].equals("0")) {return "0";}// 拼接所有字符串StringBuilder sb = new StringBuilder();for (String s : strs) {sb.append(s);}return sb.toString();}
}

复杂度分析：

时间复杂度：O(n log n)，其中 n 是数组长度。
空间复杂度：O(n)。

180. 连续出现的数字

表：Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+

在 SQL 中，id 是该表的主键。
id 是一个自增列。

找出所有至少连续出现三次的数字。
返回的结果表中的数据可以按 任意顺序 排列。

结果格式如下面的例子所示：

示例 1:

输入：

Logs 表：

+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+

输出：

Result 表：

+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

解释：1 是唯一连续出现至少三次的数字。

方法思路

相邻行比较：利用 LAG 和 LEAD 窗口函数获取当前行的前一个和后一个 num 值。
筛选条件：当前行的 num 同时等于前一个和后一个的 num，即连续三次相同。
去重处理：使用 DISTINCT 确保结果唯一。

代码实现(SQL)：

SELECT DISTINCTnum AS ConsecutiveNums
FROM (SELECT num,LAG(num, 1) OVER (ORDER BY id) AS prev_num,LEAD(num, 1) OVER (ORDER BY id) AS next_numFROM Logs
) AS temp
WHERE num = prev_num AND num = next_num;

声明

本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。