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

一、LeetCode介绍

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

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

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

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

二、LeetCode 热题 HOT 100-5

2.1 题目

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 题解

时间复杂度为 O(n^2)，其中 n 为字符串的长度，需要遍历字符串并对每个字符进行中心扩散；空间复杂度为 O(1)，只需要常数级别的额外空间。

解题思路：

这个问题可以使用中心扩散法来解决。

具体而言，我们可以遍历字符串 s，以每个字符为中心，向两边扩散，找到以当前字符为中心的最长回文子串。需要注意的是，回文子串的中心可能是一个字符，也可能是两个相邻的字符，因此需要分别考虑这两种情况。

另外，需要考虑奇数长度和偶数长度的回文子串。对于奇数长度，中心只有一个字符；对于偶数长度，中心是两个相邻的字符。

在遍历过程中，记录下目前找到的最长回文子串的起始位置和长度，最终得到的就是整个字符串的最长回文子串。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    
    int start = 0, end = 0;
    
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i); // 以当前字符为中心的奇数长度回文子串
        int len2 = expandAroundCenter(s, i, i + 1); // 以当前字符和下一个字符为中心的偶数长度回文子串
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 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

三、面试经典 150 题-5

数组 / 字符串

3.1 题目

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
 

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 题解

时间复杂度为 O(n)，其中 n 为数组的长度，只需要遍历一次数组即可找到多数元素；空间复杂度为 O(1)，只需要常数级别的额外空间。

解题思路：

这个问题可以使用摩尔投票算法来解决。摩尔投票算法的核心思想是一一对消。

假设数组中的第一个元素为候选多数元素，遍历数组时，如果下一个元素与当前候选元素相同，则增加计数；如果不同，则减少计数。

当计数变为0时，重新选择下一个元素作为候选多数元素。

由于题目保证了一定存在多数元素，最终的候选多数元素就是所求的多数元素。

public int majorityElement(int[] nums) {
    int count = 0;
    int candidate = 0;
    
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    
    return candidate;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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