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

Love The Way You Lie 2024-02-19 10:28 74阅读 0赞

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

*  一、LeetCode介绍
 *  二、LeetCode 热题 HOT 100-8
 *   *  2.1 题目
     *  2.2 题解
 *  三、面试经典 150 题-8
 *   *  3.1 题目
     *  3.2 题解

## 一、LeetCode介绍 ##

![在这里插入图片描述][3e8d6d563f984f299bbec4d81dea17d2.png]

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

### 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;  
        }  
    }

![在这里插入图片描述][c611425ffaba41afab90961279aa0ff0.png]

## 三、面试经典 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

### 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;
    }

![在这里插入图片描述][471ae2a3d43b4b1791419bb523673248.png]

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

[3e8d6d563f984f299bbec4d81dea17d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/5333ccf7167f4172a466064a5e981ed6.png
[c611425ffaba41afab90961279aa0ff0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/43735e936a1e4a129d216de1d2cd7412.png
[471ae2a3d43b4b1791419bb523673248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/8947961f295a4ef98c819c733da49412.png