刷题笔记（第九天）

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===targetreturn 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;
};