leetcode:15 三数之和(不在话下):
/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function (nums) { nums.sort((a, b) => a - b) // 排序 let res = [] for (let i = 0, len = nums.length; i < len; i++) { if (nums[i] > 0) break // 排除不可能情况 if (i>0 && nums[i] === nums[i - 1]) continue // 去重 let L = i + 1, R = len -1; while (L <R) { let sum = nums[i] + nums[L] + nums[R] if (sum === 0) { res.push([nums[i], nums[L], nums[R]]) while (nums[L] === nums[++L]) continue // 及时去重 }else if (sum > 0) { R--; }else if (sum < 0) { L++; } } } return res };
题目: 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目解析数组中的某三个数之和必须等于0.,结果可以是多样,不过要保证的是结果中某三个数不能和另外的结果中的某三个数全部重复,位置不同,值相同也不行。(两个三个元素的数组) 思路:先排序好,然后找好一个([0])固定的点,然后左[1]右[length-1]指针遍历就行了。
步骤: 先排序:问题:为什么是nums.sort((a, b) => a - b)这样。而不是nums.sort(a, b)? 因为nums.sort(a, b)这样。默认情况下sort方法是按ascii字母顺序排序的,而非我们认为是按数字大小排序 为什么这种行? 因为这种nums.sort((a, b) => a - b)如果a-b大于0就排序,(因为这是从小到大排序的啊),第一个比第二个大啊,所以。。 如果小于0,就代表第一个比第二个小,因为这种是从小到大排序的哈。 然后是,为什么要排序? 因为排序后才能双指针啊,不然乱乱的,怎么搞?
if (nums[i] > 0) break// 排除不可能情况??? 因为如果第一个大于0,那玩什么啊,全都是大于0的数字怎么等于0啊,兄弟。 if (i>0 && nums[i] === nums[i - 1]) continue// 去重 意思是;如果第二个与第一个相等的话,在i是第二个下标(nums[1])或者以上(nums[自增加1])的情况下,就continue执行for,i=2;。。。 如果还是2与i=1相等,就continue,确保没有重复的值。 执行这句话代表开头的固定的nums[0]与下一个nums[1]不会重复了. 然后是看看双指针里面的重复怎么去掉哈。
let L = i + 1, R = len - 1;
意思是;因为i等于固定的值,i+1代表做左指针,len-1代表右指针。
while (L < R) { let sum = nums[i] + nums[L] + nums[R]
什么意思? 当L小于R时,为什么时<为什么不是<=呢? 因为等于的话,就错了,为什么,因为给你的数组里面只有一个2,而<=的话,是[-4,2,2]是两个2了。 问题?为什么测试用例里面的-1可以两个啊,因为给的数组里面有两个-1啊。 注意一下:给的数组里面的元素在一个组合;里面只能出现一次。而-1有两个,证明在一个组合里面有两个-1也可以。但是因为2在给的数组里面只有一个,所以一个数组里面只能有一个2,两个2的话,就错了哈。 然后是 `let sum = nums[i] + nums[L] + nums[R]`看看双指针的与固定值的结果能不能为0.
if (sum === 0) { res.push([nums[i], nums[L], nums[R]]) while (nums[L] === nums[++L]) continue // 及时去重 }
意思是;等等于0时,就代表可以,push进输出的数组里面,然后看看这个可以与其他的可以为0的L与下一个L++是不是重复的, 如果是证明有重复的,就先装进数组里面在跳过下一个,问题?为什么一定要跳过? 因为不跳过的话,有重复,有重复会错,因为题目要求的是不能重复的:(官方要求)注意:答案中不可以包含重复的三元组。(官方要求)。 注意下这里:也能重复,不过要求的是给的数组里面的,如果给的数组里面有两个-1,因为每一个-1在一个组合里面只能出现一次,两个2,可以出现两次了啊,就这种情况。 除了这种,其他的都错。 问题?为什么使用continue跳过,因为如果break的话,就全部完了啊。(跳过for)。
else if (sum > 0) { R--; }
为什么R–因为sum大于0了啊,而右指针是最大的,所以右指针得–啦
else if (sum < 0) { L++; }
为什么这里L++因为sum小于0了啊,而左指针是最小的,所以左指针得++啦
leetcode:557 反转字符串中的单词|||(不在话下)
/** * @param {string} s * @return {string} */ var reverseWords = function(s) { return s.split(" ").map(str=>str.split("").reverse().join("")).join(" "); };
题目就不用我讲解了把,垃圾题目。 思路:字符串先分割为什么分割? 因为后面要使用的函数都是数组的函数所以要。。。。。, 为什么使用的都是数组的函数? 因为字符串中没有办法可以反转的哈。 经过split过程了后的就是字符串的数组了(注意全部才是字符串数组,单独一个元素还是字符串哈),以空格为分割线,每一个都是字符串。 然后是map,为什么使用map? 兄弟们,这是用es6写的,当然用map了呀。 也可以使用foreach遍历哦. 然后是使用split函数为什么? 因为这是字符串啊,数组才有方法反转的。 然后是反转,然后是转换成字符串,为什么一定要转换成字符串? 因为s本来就是字符串的呀,难道要给数组给他吗?是吧,兄弟们。 注意一下这里:为什么不直接在map里面直接最后join(" ");呢? 因为里面反转的都是一个一个单词,不是直接反转整个字符串数组啊啊A1
str.split("").reverse().join("")).join(" ")
因为给一个单词反转有什么用? 要给就给一个全部的s单词join(" ");字符串加空格才行嘛是吧。兄弟们。 返回。 完成。
leetcode:141 环形链表(不在话下):
看下面的图在脑子里想一想.
题目解析:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { let p1=head; let p2=head; while(p1&&p2&&p2.next) { p1=p1.next; p2=p2.next.next; if(p1==p2) { return true; } } return false; };
思路;一快一慢两个指针在同一起点,快的走两步,慢的一步。 直到快的快慢的一圈正好形成一个圆圈就是环形链表了.
let p1=head; let p2=head;
问题; 为什么都是head,因为在起点啊,还没有到达一公里呢。 为什么一个next,一个两个next呢? 因为一快一慢啊.
p1=p1.next; p2=p2.next.next; 为什么if(p1==p2) { return true;
}呢? 因为已经形成一个圈了,已经快的快慢的一圈了. 为什么while(p1&&p2&&p2.next)? p1&&p2代表p1与p2是不是都有值并且下面哪一个 p2.next代表从主要是判断有没有第一个节点的啊,是不是null。 条件是三个。 第一:必须p1与p2都有值,为什么,因为不这样不能相遇。 第二:p2.next必须有值,为什么,因为他如果没值,就代表不是环形链表了啊. 如果它有值,循环里面的p2.next.next;null没值,没关系啦,条件哪里的p2如果是null的话,也跳出循环啊. 完成.
leetcode:1 两数之和(不在话下)
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for(let i=0;i<nums.length;i++) { for(let j=i+1;j<nums.length;j++) { if(nums[i]+nums[j]==target) { return [i,j]; } } } };
思路:第一个for的每一次依次遍历第二个for的全部次数. 然后输出下标即可.
leetcode:242 有效的字母异位词(不在话下)
/** * @param {string} s * @param {string} t * @return {boolean} */ var isAnagram = function(s, t) { if(s.length!=t.length) { return false } var sSort=s.split('').sort(); var tSort=t.split('').sort(); return sSort.join('')==tSort.join(''); };
题目解析:什么是异或词? 它是需要两个字符串进行对比的哈。 比如s=“anagram”, t=“nagaram” 这就属于异位词,长度一样,包含的字母都一样,每个字符出现的频率也一样,只是顺序不同而已 s=“rat”,t=“car” 这种就不属于异位词,因为s中的’r’在t中没有。 知道了把。
思路;先看看长度相不相同,先前的条件。 然后是看看一不一样,怎么做? 排序把,然后转换成字符串,看看==一样不一样把。
leetcode:83 删除排序链表中的重复元素(不在话下)
电脑网络不行啊。。。。 题目这么垃圾就不用解释了把。 因为有序,所以相邻.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { let p=head; while(p&&p.next) { if(p.val===p.next.val) { p.next=p.next.next; } else{ p=p.next; } } return head; };
开始遍历链表的开始。
let p=head;
当前节点的值等于下一个的值就删除下一个节点的元素.
if(p.val===p.next.val) { p.next=p.next.next; }
问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.next;没有值为什么不会报错?因为他不是比较。比较必须是值与值比较的啊。 所以
while(p&&p.next)
然后让p遍历下去。 问题? 如果有三个值都相同怎么办? 在循环一次,然后是p再跟p.next的元素对比,比较。。为什么还是p.next; 因为他被p.next.next;覆盖了呀。所以p.next是原本的第三个元素了啊. 最后是: 遍历完后就返回链表的头部了呀,代表结束了啊.
leetcode:206 反转链表:(不在话下)
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let p1=head; let p2=null; while(p1) { const tmp=p1.next; p1.next=p2; p2=p1; p1=tmp; } return p2; };
怎么做? 先定义两个变量,为双向指针。一个指向null,一个head,为什么不是一个为1,一个为2。 因为如果这样输出的怎么有null呢,所以一个为null,那为什么head呢? 因为链表是从头开始找起的啊。 使用什么方法做? 核心在于:单向链表只能有一个head,赋值也不行,赋值会指向head的next的值。 尾插头? 顾名思义是:箭头是反过来的,也就是左箭头,正常是右箭头的指向,当然左箭头的指向反过来就是逆序了哈。也就是结果了哈。 1->2->null 中间是怎么做的?尾插头。 null<-1<-2 下面是箭头反过来的哈。 2->1->null 代码:
while(p1) { const tmp=p1.next; p1.next=p2; p2=p1; p1=tmp; }
第一次循环: p1.next=p2;//1指向了null; 然后是p1与p2进一位是p1=1;p2=1; 问题? 为什么p2等于1不等于head,因为大哥这是单向的啊,只有一个链表所以是只有一个head,所以p2为1. null<-1 第二次循环: p1.next=p2;//2指向了1。 null<-1<-2 然后是p1与p2进一位是p1=null;p2=2;因为p1为null所以结束了呀。 为什么p1没有值了就跳出呢? 因为前面的没有值了就代表到头了呀。 系统会自动转换成右箭头的哈。 问题? 为什么const tmp=p1.next;? 因为p1.next=p2;代表原来的值不见了,不见了怎么反转啊.
leetcode:2 两数相加(不在话下)
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { const q=new ListNode(0); let p1=l1; let p2=l2; let p3=q; let carry=0; while(p1||p2) { const v1=p1?p1.val:0; const v2=p2?p2.val:0; const val=v1+v2+carry; carry=Math.floor(val/10); p3.next=new ListNode(val%10); if(p1) { p1=p1.next; } if(p2) { p2=p2.next; } p3=p3.next; } if(carry) { p3.next=new ListNode(carry); } return q.next; };
难以理解的点: 它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 意思:每一个数字在链表中是逆序的方式存储的,并且每一个节点只能存储一位数字。 然后是一个数字的链表(加上+)一个数字的链表:是逆序存储的哦。 解题步骤: 像做小学题一样,个十百每一位都跟相同的每一位想加。 注意点:如果"某一位"超过了十就进一,"某一位"就留下(进一的个位的数字),留到下一位在进行+1。 因为js中没有链表的操作,所以通过Object来做。 作用是存储想加后的链表哈。
const q=new ListNode(0);
问题? 0是什么意思? 没有什么意思?在相加操作上没有价值把。 如何遍历两个链表? 两个指针。
let p1=l1; let p2=l2; let p3=q;
第三个指针是新建的链表,相同的位想加后是要存储的。
while(p1||p2)
如果两个中任何一个还有值就继续遍历,为什么? 因为还没完呢啊。。。。 还有一个问题就是一长一短怎么办?p1与p2都有可能哦。
const v1=p1?p1.val:0; const v2=p2?p2.val:0;
然后是什么? 想加啊。
const val=v1+v2;
问题? 如果大于9了怎么办? 个位留下,十位进一下一轮在想加吧。 新建一个carry=0; 然后是获取和的十位上的数字了呀。
carry=Math.floor(val/10);
放到相加的操作上.
const val=v1+v2+carry;
然后是把个位上的数加到新链表上。
p3.next=new ListNode(val%10);
完成了。 难点: 记住哈,兄弟们。
carry=Math.floor(val/10); p3.next=new ListNode(val%10);
这两句第一个是截图十位,等到下一次循环在下位相加所以不管它了。第二句是截图个位的,因为十位已经有人管了,所以管个位就行了,兄弟们。 问题? 第一次的呢?
const val=v1+v2+carry;
加0吗? 没错的兄弟们,因为开始没有进1的啊。
if(p1) { p1=p1.next; } if(p2) { p2=p2.next; }
然后是如果p1或者p2如果有值的话,就继续next,如果某一个没值就不next了。。 p3=p3.next; 然后新建的相加后的指针也进1. 然后是问题: 最后时候的链表如果超过9怎么办? 进1啊。
if(carry) { p3.next=new ListNode(carry); }
好了完成.