郑州pc网站建设,深圳定制展会,微信公众号运营推广方案,郑州建设劳务管理中心网站挑战100天 AI In LeetCode Day03#xff08;热题面试经典150题#xff09; 一、LeetCode介绍二、LeetCode 热题 HOT 100-52.1 题目2.2 题解 三、面试经典 150 题-53.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站#xff0c;提供各种算法和数据结构的题目热题面试经典150题 一、LeetCode介绍二、LeetCode 热题 HOT 100-52.1 题目2.2 题解 三、面试经典 150 题-53.1 题目3.2 题解 一、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 仅由数字和英文字母组成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;
}三、面试经典 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] 1093.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;
}至此挑战100天 AI In LeetCode Day03热题面试经典150题完成后续会持续调整查阅过程中若遇到问题欢迎留言或私信交流。
