剑指Offer(03)数组中重复的数字
今天是小呆刷题的第 18 天，今天的题目是：剑指 Offer 的第 3 题，数组中重复的数字
题目要求
找出数组中重复的数字。
在一个长度为n的数组nums里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
123输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
提示：
2 <= n <= 100000
解题思路这道题的常规解法，就是利用哈希表，遍历数组，判断哈希表中是否包含当前值，如果包含，当前项就是重复项。这种在数组中查找重复的数字的题型，基本都可以用哈希表去解决，它的时间复杂度为O(n)，空间复杂度为O(n)。
哈希表1234567891011/** * @param {number[]} nums * @return {number} */var findRepeatNumber = function (nums) { let hasMap = new Set() for (let ...
LeetCode(118)杨辉三角
今天是小呆刷题的第 17 天，今天的题目是：力扣（LeetCode)的第 118 题，杨辉三角
题目要求
给定一个非负整数*numRows，生成「杨辉三角」的前numRows*行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例：
12345输入: numRows = 5输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]输入: numRows = 1输出: [[1]]
提示：
1 <= numRows <= 30
解题思路这道题其实官方已经给了非常容易理解的规律和图示：每个数是它左上方和右上方的数的和。
我们可以用一个二维数组来描述示例 1 的数据：
1let list = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
根据上面给出的规律能够得出, 首尾的数字一定是 1, 其次从第三行开始，除去首尾，其他的数字都是它左上方和右上方的数的和，所以我们可以做出以下公式：（用i表示行，用j表示列）
list[i][0] = 1 每行的第一个数字是 ...
LeetCode(169)多数元素
今天是小呆刷题的第 16 天，今天的题目是：力扣（LeetCode)的第 169 题，多数元素
题目要求
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例：
12345输入：nums = [3,2,3]输出：3输入：nums = [2,2,1,1,1,2,2]输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
解题思路这道题小呆的第一思路就是用哈希表来解决，因为跟返回数组中出现次数最多的题的思路是一样的，只不过这道题是返回次数大于n/2的那个元素。
12345678910111213141516171819/** * @param {number[]} nums * @return {number} */var majorityElement = function (nums) { let has ...
LeetCode(141)环形链表
今天是小呆刷题的第 15 天，今天的题目是：力扣（LeetCode)的第 141 题，环形链表
题目要求
给你一个链表的头节点head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回true。 否则，返回false。
示例：
123输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。
提示：
链表中节点的数目范围是[0, 10^4]
-10^5 <= Node.val <= 10^5
pos为-1 或者链表中的一个有效索引。
解题思路遇到数组，链表类的题目，首先考虑的就是双指针算法。在这道题中，由于存在一个环，实际上在遍历的时候，如果进入环中，就会无限循环。那其实只要两个指针的步频不一样，就会相交。上图辅助理解：
123456789101112131 ...
LeetCode(121)买卖股票的最佳时机
今天是小呆刷题的第 14 天，今天的题目是：力扣（LeetCode)的第 121 题，买卖股票的最佳时机
题目要求
给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
示例：
12345678输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
解题思路这道题首先我们要明确一个股票买卖的规则就是：当天 ...
LeetCode(136)只出现一次的数字
今天是小呆刷题的第 13 天，今天的题目是：力扣（LeetCode)的第 136 题，只出现一次的数字
题目要求
给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例：
12345输入：nums = [2,2,1]输出：1输入：nums = [4,1,2,1,2]输出：4
提示：
1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外，其余每个元素均出现两次。
解题思路这道题小呆首先想到的是哈希集合，因为题目中讲到：除了某个元素只出现一次以外，其余每个元素均出现两次。所以我们不能直接数组去重，但是我们可以利用Set集合存储的值唯一这个特性，去遍历数组，如果遍历过程中哈希集合中存储过当前项，那说明当前元素不唯一，直接删掉。循环结束后，就得出了那个不唯一的元素。
123456789101112131415/** * @ ...
LeetCode(485)最大连续1的个数
今天是小呆刷题的第12天，今天的题目是：力扣（LeetCode)的第485题，最大连续1的个数
题目要求
给定一个二进制数组nums， 计算其中最大连续1的个数。
示例：
123输入：nums = [1,1,0,1,1,1]输出：3解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
提示：
1 <= nums.length <= 10^5
nums[i]不是0就是1.
解题思路这道题还是比较简单的，题目要求计算最大连续的1的个数，那我们每遇到1个1，就计数一次，如果遇到0，说明中断了，就重新计数，最后返回计数的值就可以了。由于重新计数会覆盖之前的计数，所以还需要额外的一个变量来储存返回值。老规矩，哪怕再简单的题，一图胜千言。
12345678910111213141516/** * @param {number[]} nums * @return {number} */var findMaxConsecutiveOnes = function(nums) { let count = 0 ...
LeetCode(70)爬楼梯
今天是小呆刷题的第11天，今天的题目是：力扣（LeetCode)的第70题，爬楼梯
题目要求
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例：
12345输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶
提示：
0 <= n <= 45
解题思路第一眼看上去，这道题小呆并没有看出什么名堂，所以我们根据示例，写一下输入和输出，看看能否找出规律：
n = 1输出1，有1种方法：1
n = 2输出2，有2种方法：1 + 1, 2
n = 3输出3，有3种方法: 1 + 1 + 1, 1 + 2, 2 + 1
n = 4输出5，有5种方法：1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1， 2 + 2
观察输出，嘿，这不是跟昨天做的斐波那契数一样嘛。那就当做个复习吧~ 先写递归：
12345678/** * @param {number} n * @return {number} ...
LeetCode(509)斐波那契数
今天是小呆刷题的第10天，今天的题目是：力扣（LeetCode)的第509题，斐波那契数
题目要求
斐波那契数（通常用F(n)表示）形成的序列称为斐波那契数列。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定n，请计算F(n)。
示例：
123输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1
提示：
0 <= n <= 30
解题思路大名鼎鼎的斐波那契数，也是面试中经常会考的一道算法题。这道题的解法有很多种，最简单的就是使用递归。毕竟怎么写题目要求都已经给出来了，所以很快就能写出来一个解法：
n < 2，返回n
F(n) = F(n - 1) + F(n - 2)
12345678/** * @param {number} n * @return {number} */var fib = functio ...
LeetCode(20)有效的括号
今天是小呆刷题的第9天，今天的题目是：力扣（LeetCode)的第20题，有效的括号
题目描述
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例：
12345输入：s = "()"输出：true输入：s = "(]"输出：false
提示：
1 <= s.length <= 10^4
s仅由括号'()[]{}'组成
解题思路小呆做这道题的时候，5分钟内没解出来，果断看评论区和题解。这道题的主流思路是用栈来解决，由于括号都是成对出现的，所以我们可以让左侧的括号入栈，当遇到右侧的括号时，出栈匹配，能匹配到，就接着循环，直到所有括号都匹配完或者出现不匹配为止。在JavaScript中我们很容易用数组 ...
