刷题笔记（第九天）
1. 求最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
- 示例 1：
- 输入：strs = [“flower”,“flow”,“flight”]
- 输出：“fl”
- 示例 2：
- 输入：strs = [“dog”,“racecar”,“car”]
- 输出：“”
- 解释：输入不存在公共前缀。
解题思路：先将字符数组调用sort()进行排序，然后比较数组第一个元素以及最后一个元素，找到数组第一个元素和最后一个元素的最长公共前缀即可。当数组长度为0，返回""；当数组长度为1，返回数组第一个元素。
var longestCommonPrefix = function (strs) {
if (strs.length === 0) {
return '';
}
if (strs.length === 1) {
return strs[0];
}
strs.sort();
// console.log(strs);
let first = strs[0], last = strs[strs.length - 1];
let len = Math.min(first.length, last.length);
// console.log(first, last, len);
let str = '';
for (let i = 0; i < len; i++) {
console.log(first[i], last[i]);
if (first[i] === last[i]) {
str += first[i] + '';
// console.log(str);
} else {
break;
}
}
return str.length > 0 ? str : "";
};
2. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
解题思路：
- 第一步: 给数组排序（由小到大）
- 第二步: 从前往后遍历数组—— i为第一个值下标; left为i后一位下标; right为数组最后一位下标，然后三个下标所对应的值相加得
sum分3种情况：- 如果和为0; 就把3个下标所对应的值放入答案数组; 同时left往后移动一位; 如果移动后的下标所对应的值与前一位一样那么left继续往后移直到不一样(防止取到相同的答案);
- 如果和大于0; right往左移动一位
- 如果和小于0; left往右移动一位
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
let length = nums.length;
let res = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < length; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let left = i + 1;
let right = length - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
res.push([nums[i], nums[left], nums[right]]);
left++;
while (nums[left] === nums[left - 1]) {
left++;
}
} else if (sum > 0) {
right--;
} else { // sum < 0 的情况
left++;
}
}
}
return res;
};
3. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在恰好一个解。
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
解题思路：
- 给数组排序（由小到大）
- 定义一个变量
res存储最终要返回的值，即最接近target的数 - 从前往后遍历数组—— i为第一个值下标; left为i后一位下标; right为数组最后一位下标，三个下标所对应的值相加得到
sum，判断当前res存储的值和sum哪个更接近target并将该值赋值给res - 三个下标所对应的值相加得
sum与target的关系分3种情况：sum>target：right--sum<target：left++sum==target：直接返回sum，此时sum最接近目标值target，相差0
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
let res=Infinity;
nums.sort((a,b)=>a-b);
for(let i=0;i<nums.length;i++){
let left=i+1;
let right=nums.length-1;
while(left<right){
let sum=nums[i]+nums[left]+nums[right];
if(Math.abs(sum-target)<Math.abs(res-target)) {
res=sum;
}
if(sum>target) {
right--;
} else if(sum<target){
left++;
} else {
// sum===target
return sum;
}
}
}
return res;
};
4. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
输入：s = “()”
输出：true
解题思路：
这道题利用栈来做，当遇到左括号，便入栈，遇到右括号，便将当前栈顶元素与字符比较，判断是出栈还是直接返回。其中有以下几种情况字符串无效：
- 字符串遍历完了，但是栈不为空（说明有左括号没有相应的右括号匹配）
- 栈已经为空，字符串未遍历完（说明有右括号没有相应的左括号匹配）
- 遍历字符串匹配的过程中，当前字符为右括号 且该字符与栈顶字符不匹配
var isValid=function(s){
let stack=[];
let map={
"(": ")",
"{": "}",
"[": "]",
};
for(let x of s){
if(x in map){ // { [ ( ，判断如果是左括号，则入栈
stack.push(x);
continue;
}
if(x!==map[stack.pop()]){
// 右括号，如果与当前栈顶不匹配，则返回false 否则当前栈顶出栈
return false;
}
}
return stack.length===0;
}
5. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
**解题思路：**同时循环两个链表并比较当前结点存储的值，选择较小的添加在新的链表，直到两条链表都循环完毕。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
// 升序
let res=new ListNode(); // 新链表的首结点
let head = res; // 存储新链表的首结点
while(list1 && list2) {
if (list1.val < list2.val) {
let q = new ListNode(list1.val);
res.next=q;
list1=list1.next;
} else {
let q = new ListNode(list2.val);
res.next=q;
list2=list2.next;
}
res=res.next;
}
if(list1){
res.next=list1;
}
if(list2){
res.next=list2;
}
return head.next;
};