挑战100天 AI In LeetCode Day06（热题+面试经典150题）

一、LeetCode介绍

LeetCode是一个在线编程网站，提供各种算法和数据结构的题目，面向程序员、计算机科学专业学生和技术爱好者等人群，旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目，因此它也是程序员面试准备的重要资源之一。

LeetCode上的问题涵盖了各种难度级别，从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案，LeetCode能够对结果进行评估并返回测试结果。

除了题目外，LeetCode还提供了讨论区、排行榜等社区功能，用户可以在这里交流学习心得、解决疑难问题，并与其他用户比较自己的做题成绩。

挑战100天 AI In LeetCode是基于LeetCode题库，借助AI的能力进行解题、并学习其解题过程。

二、LeetCode 热题 HOT 100-8

2.1 题目

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。
 

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0
 

提示：

-231 <= x <= 231 - 1
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

2.2 题解

题目要求我们反转一个给定的 32 位有符号整数，并且在反转后的整数超过 32 位有符号整数的范围时，返回 0。我们可以使用取余和除法来操作这个题目。

解题思路：

1. 首先，我们使用整除操作 x / 10 来移除 x 的最后一位数字。我们需要在 x 不会是 0 的情况下进行这个操作，否则会造成除以 0 的错误。
2. 然后，我们将 x 除以 10 的结果存储在临时变量中，并将其模 10 的结果加到反转后的结果中。
3. 最后，我们将临时变量赋值给 x，然后重复上述步骤，直到 x 为 0。

在 Java 中，我们可以使用循环和除法操作来实现这个算法。需要注意的是，我们需要使用 long 类型来存储中间结果，以避免超出 int 类型的范围。

在这个解法中，我们使用了一个 while 循环来重复执行操作，直到 x 等于 0。在每次循环中，我们将 result 乘以 10，然后加上 x 取模 10 的结果。然后，我们将 x 除以 10，以便下一次循环。在每次循环结束时，我们检查 result 是否超出了 int 类型的范围。如果是，则返回 0。否则，我们将 result 赋值给 result，并继续循环。当 x 为 0 时，我们退出循环并返回 result 的整数值。

public class Solution {  
    public int reverse(int x) {  
        long result = 0;  
        while (x != 0) {  
            long temp = result * 10 + x % 10;  
            x /= 10;  
            if (temp > Integer.MAX_VALUE || temp < Integer.MIN_VALUE) {  
                return 0;  
            }  
            result = temp;  
        }  
        return (int) result;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、面试经典 150 题-8

数组 / 字符串

3.1 题目

买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
 

提示：

1 <= prices.length <= 3 * 10 4
0 <= prices[i] <= 10 4
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

3.2 题解

时间复杂度是 O(n)，其中 n 是 prices 数组的长度。因为我们只需要遍历一次 prices 数组即可得到最大利润。

空间复杂度是 O(1)，因为我们只使用了一个额外的变量 max_profit 来存储最大利润，而不需要额外的数据结构来存储中间结果。

解题思路：

1. 初始化一个变量 max_profit 为 0，用于存储最大利润。
2. 遍历 prices 数组，对于每个元素 prices[i]： a. 如果 i == 0，说明还没有进行过交易，所以跳过当前循环。 b. 否则，计算当前价格与前一天价格的差值 diff = prices[i] - prices[i-1]。 c. 如果 diff > 0，说明今天的价格高于昨天的价格，可以进行卖出操作，更新 max_profit = max(max_profit, diff)。
3. 返回 max_profit。

public int maxProfit(int[] prices) {
    int max_profit = 0;
    for (int i = 1; i < prices.length; i++) {
        int diff = prices[i] - prices[i - 1];
        if (diff > 0) {
            max_profit += diff;
        }
    }
    return max_profit;
}
1
2
3
4
5
6
7
8
9
10

至此，挑战100天 AI In LeetCode Day06（热题+面试经典150题）完成，后续会持续调整；查阅过程中若遇到问题欢迎留言或私信交流。