LeetCode(344)反转字符串
今天是小呆刷题的第8天,今天的题目是:力扣(LeetCode)的第344题,反转字符串
题目要求
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。
示例:
12输入:s = ["h","e","l","l","o"]输出:["o","l","l","e","h"]
提示:
1 <= s.length <= 10^5
s[i]都是ASCII码表中的可打印字符
解题思路这道题,由于题目要求原地修改数组,小呆首先想到了前几天一直在用的双指针算法。具体思路如下:
设置left,right两个指针,一个指向数组头部,一个指向数组尾部
循环条件是left <= right
设置一个temp变量,用于left和right交换时的中转站
交换left ...
LeetCode(21)合并两个有序链表
今天是小呆刷题的第7天,今天的题目是:力扣(LeetCode)的第21题,合并两个有序链表
题目要求
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
12输入:l1 = [1,2,4], l2 = [1,3,4]输出:[1,1,2,3,4,4]
提示:
两个链表的节点数目范围是[0, 50]
-100 <= Node.val <= 100
l1和l2均按非递减顺序排列
解题思路这道题,5分钟内我没写出来。思路其实是有的,就是比较两个链表的头节点,把小的拿出来放前面,然后去比对剩下的两个链表,依次类推,但是问题是,思路有,但不知道该怎么写,这其实也是我刷题过程中最难受的。看了题解,用递归比较好实现。
比较两个链表节点的val值,将值较小的节点往前排
用值较小的节点的next节点,与另一个链表的节点比较,依次类比
两个链表的任意一方到达尾部,直接返回另一方即可
具体过程用gif图辅助理解一下:
1234567891011121314151617181920212223/** * Definition fo ...
LeetCode(206)反转链表
今天是小呆刷题的第6天,今天的题目是:力扣(LeetCode)的第206题,反转链表
题目要求
给你单链表的头节点head ,请你反转链表,并返回反转后的链表。
示例:
12输入:head = [1,2,3,4,5]输出:[5,4,3,2,1]
提示:
链表中节点的数目范围是[0, 5000]
-5000 <= Node.val <= 5000
解题思路关于链表和数组的题目,小呆还是优先考虑是否可以用双指针算法解决,毕竟最近刷的几道题都与双指针有关。由于链表之间是由next相连,所以反转链表其实就是把next的指向反转。那如何将next指向反转的呢?一共有3步:
链表的尾部节点的next一定指向null,所以我们初始化两个指针prev,curr,让其一个指向null,一个指向链表头head
进入循环,终止条件为curr !== null表示链表已经循环完毕
由于反转next会断掉当前链表,所以创建一个临时变量next,指向curr.next,防止反转next找不到路
将curr.next指向prev,然后将prev指向curr,最后将curr指向next
最 ...
JavaScript 关于闭包的理解
对于前端的同学来说,闭包这个词一定在无数的面试过程中被问到过,小呆也不例外。早些年有些公司甚至会把理解闭包当成区分初级、中级甚至高级前端工程师的一个方式。在被问到什么是闭包的时候,有些同学会回答:“闭包就是函数内部嵌套并返回一个函数”,果真如此吗?一起来复习一下闭包的知识吧。
知识点
理解闭包
闭包的应用
理解闭包闭包的定义关于对闭包的定义,一千个读者有一千个哈姆雷特,MDN Doc文档、《你不知道的JavaScript》、《JavaScript高级程序设计第3版》各自的定义都大不相同:
闭包是一个函数以及其捆绑的周边环境状态(lexical environment, 词法环境)的引用的组合。换而言之,闭包让开发者可以从内部函数访问外部函数的作用域。在JavaScript中,闭包会随着函数的创建而被同时创建。—— MDN Doc文档
当函数可以记住并访问所在的词法作用域时,就产生了闭包,即使函数是在当前词法作用域之外执行。 —— 《你不知道的JavaScript》
闭包是指有权访问另一个函数作用域中的变量的函数。—— 《JavaScript高级程序设计第3版》
初看这 ...
LeetCode(1)两数之和
今天是小呆刷题的第5天,今天的题目是:力扣(LeetCode)的第1题,两数之和
题目要求
给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例:
123输入:nums = [2,7,11,15], target = 9输出:[0,1]解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
提示:
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
解题思路大名鼎鼎的LeetCode第一题,通过率只有52.9%,小呆第一次做这道题也没做出来。思路其实蛮简单的,维护一个HasMap,一般情况下我们存储数据都是index -> value,因为这道题要求返回下标,所以这个HasMap维护的是value ...
JavaScript 关于作用域的理解
如果你对作用域、作用域链、词法作用域等概念还傻傻分不清楚,那就看看这篇文章吧。了解作用域相关知识,也有助于理解闭包、执行上下文等JS核心知识。跟随小呆的视角,一起来复习一下吧。
知识点
理解JavaScript的执行过程
理解什么是作用域 & 作用域链
理解什么是词法作用域
理解JavaScript的执行过程在说作用域之前,我们要知道JavaScript的执行过程是分为两个阶段的:代码的编译阶段和代码的执行阶段。编译阶段由编译器完成,将代码翻译成可执行代码,这个阶段作用域规则会确定。执行阶段由引擎完成,主要任务是执行可执行代码,执行上下文在这个阶段创建。
作用域和执行上下文是完全不同的两个概念。一个在代码的编译阶段发生,一个在代码的执行阶段发生。
编译阶段词法分析编译器首先会将由字符组成的字符串分解成有意义的代码块,这些代码块被称为词法单元(token)。
1var a = 2;
以上面的代码为例,通常会被分解成词法单元:如 var, a, =, 2, ;,这些词法单元组成了一个词法单元流数组。
12345678910111213141516171819202122[ ...
LeetCode(283)移动零
今天是小呆刷题的第4天,今天的题目是:力扣(LeetCode)的第283题,移动零
题目要求
给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。
请注意,必须在不复制数组的情况下原地对数组进行操作。
示例:
12输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]
提示:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
解题思路刷题的第4天,遇到这种原地操作数组的题,看起来要求跟第27题移除元素很相似,唯一的区别是把数组里所有的0移到末尾。小呆首先的思路是考虑用双指针算法,所以第一步是先将非0的元素移到前面。以示例代码为例:
1234567891011121314151617/** * @param {number[0, 1, 0, 3, 12]} nums * @return {void} Do not return anything, modify nums in-place inst ...
LeetCode(27)移除元素
今天是小呆刷题的第3天,今天的题目是:力扣(LeetCode)的第27题,移除元素
题目要求
给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用O(1)额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例:
123输入:nums = [0,1,2,2,3,0,4,2], val = 2输出:5, nums = [0,1,4,0,3]解释:函数应该返回新的长度5, 并且nums中的前五个元素均为0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为5 ,而 nums = [0,1,3,0,4,2,2,2] 或 nums = [0,1,3,0,4,0,0,0],也会被视作正确答案。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
解题思路因为需要原地修改数组,并且无需考虑元素的 ...
LeetCode(83)删除排序链表中的重复元素
今天是小呆刷题的第2天,今天的题目是:力扣(LeetCode)的第83题,删除排序链表中的重复元素
题目要求
给定一个已排序的链表的头head,删除所有重复的元素,使每个元素只出现一次。返回已排序的链表。
示例:
12输入:head = [1,1,2,3,3]输出:[1,2,3]
提示:
链表中节点数目在范围[0, 300]内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
解题思路由于链表已经按升序排列,所以值相同的两个节点肯定相连。这道题的本质其实与昨天的题一样,只不过数据结构由数组变成了链表。我们依然可以使用双指针算法来解决。
依旧用一张git图来帮助理解代码在循环过程中,及最后的slow.next = null的作用。
123456789101112131415161718192021222324/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ...
LeetCode(26)删除有序数组中的重复项
如果说面试中小呆最怕什么,那一定是算法。在以往的业务开发中,遇到需要算法的地方屈指可数。加上大学期间并没有系统的学过数据结构与算法,导致算法成为了小呆的一个非常明显的短板。曾经有一段时间突击过数据结构与算法的学习,遗憾的是并没有坚持下来。从今天开始,重新开启每日一题,旨在弥补短板,成为更好的自己。
今天是小呆刷题的第1天,今天的题目是:力扣(LeetCode)的第26题,删除有序数组中的重复项
题目要求
给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有k个元素,那么nums的前k个元素应该保存最终结果。
将最终结果插入nums的前k个位置后返回k。
不要使用额外的空间,你必须在 原地修改输入数组并在使用O(1)额外空间的条件下完成。
示例:
123输入:nums = [1,1,2]输出:2, nums = [1,2,_]解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个 ...