海安县城乡建设局网站,成都网站建设名录,长沙创求网络科技有限公司,做盗版频网站【LeetCode】挑战100天 Day12#xff08;热题面试经典150题#xff09; 一、LeetCode介绍二、LeetCode 热题 HOT 100-142.1 题目2.2 题解 三、面试经典 150 题-143.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站#xff0c;提供各种算法和数据结构的题目热题面试经典150题 一、LeetCode介绍二、LeetCode 热题 HOT 100-142.1 题目2.2 题解 三、面试经典 150 题-143.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站提供各种算法和数据结构的题目面向程序员、计算机科学专业学生和技术爱好者等人群旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目因此它也是程序员面试准备的重要资源之一。
LeetCode上的问题涵盖了各种难度级别从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案LeetCode能够对结果进行评估并返回测试结果。
除了题目外LeetCode还提供了讨论区、排行榜等社区功能用户可以在这里交流学习心得、解决疑难问题并与其他用户比较自己的做题成绩。
挑战100天 AI In LeetCode是基于LeetCode题库借助AI的能力进行解题、并学习其解题过程。
二、LeetCode 热题 HOT 100-14
2.1 题目
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串 。示例 1输入strs [flower,flow,flight]
输出fl
示例 2输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。提示1 strs.length 200
0 strs[i].length 200
strs[i] 仅由小写英文字母组成2.2 题解
解题思路
我们可以将字符串数组中的第一个字符串作为基准字符串然后逐个比较每个字符串的前缀是否与基准字符串相同如果不同则缩短基准字符串的长度一直到找到公共前缀为止。
具体实现步骤如下
判断输入的字符串数组是否为空或长度是否为0若是则返回空字符串。将字符串数组中的第一个字符串赋值给一个变量 prefix。遍历字符串数组中的每个字符串比较该字符串与 prefix 的公共前缀如果不匹配则将 prefix 的长度缩短继续比较直到找到公共前缀或 prefix 变为空字符串。返回 prefix。
public class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}String prefix strs[0];for (int i 1; i strs.length; i) {while (strs[i].indexOf(prefix) ! 0) {prefix prefix.substring(0, prefix.length() - 1);if (prefix.isEmpty()) {return ;}}}return prefix;}
}三、面试经典 150 题-14 数组 / 字符串 3.1 题目
加油站
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。示例 1:输入: gas [1,2,3,4,5], cost [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油
开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油
开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油
开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油
开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油
开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。
因此3 可为起始索引。
示例 2:输入: gas [2,3,4], cost [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油
开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油
开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油
你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。
因此无论怎样你都不可能绕环路行驶一周。提示:gas.length n
cost.length n
1 n 105
0 gas[i], cost[i] 1043.2 题解
解题思路
可以使用一个变量来跟踪当前剩余的油量以及另一个变量来跟踪从起始加油站到当前加油站的总油量差值。具体步骤如下
初始化两个变量start 表示起始加油站的索引total 表示累计的油量与消耗量之差。初始化 currGas 和 totalGas 为 0。遍历加油站数组 gas 和消耗数组 cost对于每个加油站 i 将 currGas 加上 gas[i] - cost[i]表示到达该加油站后剩余的油量与消耗量之差。将 totalGas 加上 gas[i] - cost[i]表示从起始加油站到当前加油站的总油量差值。如果 currGas 小于 0则将 start 设为下一个加油站的索引并将 currGas 清零。 遍历结束后判断 totalGas 的值是否小于 0如果是则返回 -1否则返回 start。
public class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int start 0; // 起始加油站的索引int currGas 0; // 当前剩余的油量int totalGas 0; // 从起始加油站到当前加油站的总油量差值for (int i 0; i gas.length; i) {currGas gas[i] - cost[i];totalGas gas[i] - cost[i];if (currGas 0) {start i 1;currGas 0;}}// 判断是否可以绕环路行驶一周if (totalGas 0) {return -1;} else {return start;}}
}至此挑战100天 AI In LeetCode Day12热题面试经典150题完成后续会持续调整查阅过程中若遇到问题欢迎留言或私信交流。
