二进制的叮当喵

Leetcode42. 接雨水 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 12输入：height = [4,2,0,3,2,5]输出：9 提示： n == height.length 0 <= n <= 3 * 104 0 <= height[i] <= 105 解题思路 我们可以一列一列地观察规律，发现每一列能够承接的雨水为**这一列左边的最大值和右边的最大值的最小值减去当前列的高度得到的值。**如何求解每一列能都承接的雨水，我们可以有不同的解法。 方法一：动态规划法 这里的动态规划的思想主要体现在求解每一列左侧和右侧的最大值上。 我们用一个leftMaxleftMaxleftMax数组来保存到第iii列为止它左侧的最大值，那么它 ...

Leetcode41. 缺失的第一个正数 题目描述 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 **进阶：**你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？ 示例 1： 12输入：nums = [1,2,0]输出：3 示例 2： 12输入：nums = [3,4,-1,1]输出：2 示例 3： 12输入：nums = [7,8,9,11,12]输出：1 提示： 0≤nums.length≤3000 \leq nums.length \leq 3000≤nums.length≤300 −231≤nums[i]≤231−1-2^{31} \leq nums[i] \leq 2^{31} - 1−231≤nums[i]≤231−1 解题思路 这道题如果不规定时间复杂度和空间复杂度的话就是简单题。 方法一：哈希表法 如果抛开时间复杂度和空间复杂度的限制，我们自然想到可以用哈希表来记录数组中出现的元素，然后从1开始遍历[1,len]之间的正整数，如果哪一个没有被记录，那就是第一个缺失的元素。如果遍历结束都没返回，说明前len个整数都 ...

Leetcode39. 组合总和 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1： 123456输入：candidates = [2,3,6,7], target = 7,所求解集为：[ [7], [2,2,3]] 示例 2： 1234567输入：candidates = [2,3,5], target = 8,所求解集为：[ [2,2,2,2], [2,3,3], [3,5]] 提示： 1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500 解题思路 这道题也是用DFS+回溯的方式暴力求解。难点在于如何重复选取元素。 暴力解法的写法有两种不 ...

Leetcode34.在排序数组中查找元素的第一个和最后一个位置 题目描述 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 进阶： 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1： 12输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4] 示例 2： 12输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1] 示例 3： 12输入：nums = [], target = 0输出：[-1,-1] 提示： 0≤nums.length≤1050 \leq nums.length \leq 10^50≤nums.length≤105 −109≤nums[i]≤109-10^9 \leq nums[i] \leq 10^9−109≤nums[i]≤109 nums是一个非递减数组nums \quad 是一个非递减数组nums是一个非递减数组 −109≤ta ...

Leetcode 33. 搜索旋转排序数组 题目描述 整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 示例 1： 12输入：nums = [4,5,6,7,0,1,2], target = 0输出：4 示例 2： 12输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1 示例 3： 12输入：nums = [1], target = 0输出：-1 提示： 1 <= nums.length ...

Leetcode32. 最长有效括号 题目描述 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 示例 1： 123输入：s = "(()"输出：2解释：最长有效括号子串是 "()" 示例 2： 123输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()" 示例 3： 12输入：s = ""输出：0 提示： 0≤s.length≤3×1040 \leq s.length \leq 3 \times 10^40≤s.length≤3×104​ s[i] 为 '(' 或 ')' 解题思路 方法一：动态规划 算法描述 这道题有”最长“两个字，而且又是字符串，首先考虑一下能不能用动态规划来求解。 定义dp[i]表示以下标i处字符为结尾的最长有效括号的长度。那么我们很容易知道，以(结尾的字串的对应dp数组的值为0，我们只需要求解以)结尾的字串对应的dp数组的值。为了方便，我们可以初始化dp数组为0。 以)结尾的子串有以下情况： ...

Leetcode31. 下一个排列 题目描述 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须** 原地 **修改，只允许使用额外常数空间。 示例 1： 12输入：nums = [1,2,3]输出：[1,3,2] 示例 2： 12输入：nums = [3,2,1]输出：[1,2,3] 示例 3： 12输入：nums = [1,1,5]输出：[1,5,1] 示例 4： 12输入：nums = [1]输出：[1] 提示： 1 <= nums.length <= 100 0 <= nums[i] <= 100 解题思路 这道题的题目有亿点难懂！！！ 先看看啥叫下一个排列。以数字序列[1,2,3][1,2,3][1,2,3]为例，其排列按照字典序以此为： [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1][1,2,3] \\\\ [1,3,2] \\\\ [2,1,3] \\\\ [2,3,1] \\\\ [3,1 ...

Leetcode24. 两两交换链表中的节点 题目描述 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1： 12输入：head = [1,2,3,4]输出：[2,1,4,3] 示例 2： 12输入：head = []输出：[] 示例 3： 12输入：head = [1]输出：[1] 提示： 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100 解题思路 这道题是关于链表操作的题。思路上比较简单，注意边界条件就好。 具体的方法如下： 如上图所示，需要翻转的两个节点为curNode和curNode->next。为了翻转后的节点的链接，还需要标记之前的节点preNode和之后的节点nextNode。需要做的翻转操作为： 123preNode->next = curNode->next;curNode->next->next = curNode;curNode->next = nextNode; 为了方便统一操作，不对头节 ...

Leetcode22. 括号生成 题目描述 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1： 12输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2： 12输入：n = 1输出：["()"] 提示： 1 <= n <= 8 解题思路 算法描述 这道题考虑用暴力的方法，那么就是考虑DFS或者BFS两种方式。一般由于DFS的编码比较简单而选择DFS的方法。同时，在暴力的同时尽可能考虑剪枝。 首先一种最简单的暴力的方法就是将所有可能的括号序列列出来，然后写一个函数去判断这个序列是不是合理的。这种方法思路很简单，但是递归的时候有很多无用的路径，所以可以通过剪枝的方法优化一下，保证在加入(或者)后序列仍然有效的条件下才进行递归。 那么关键就在于如何保证加入括号后序列仍然保持有效。通过观察归纳，我们可以得出以下两个加入括号的条件： ...

Leetcode19. 删除链表的倒数第 N 个结点 题目描述 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 **进阶：**你能尝试使用一趟扫描实现吗？ 示例 1： 12输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5] 示例 2： 12输入：head = [1], n = 1输出：[] 示例 3： 12输入：head = [1,2], n = 1输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 解题思路 这道题的思路比较简单。运用快慢两个指针，快指针先走n步，然后慢指针和快指针同步走，当快指针走到结尾的时候，慢指针指向的位置就是要删除的结点。 这个题有两个问题： 要删除当前结点，那么就需要记录当前结点的上一个结点； 如果要删除的结点是头结点，那么就需要特判。 但是这两个问题我们可以通过设置虚拟头结点virtualHead来解决，让virtualHead的next指针指向头结点。这样就会统一删除操 ...