argcxiang's blog

题目描述整数数组 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 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 12输入：nums = [4,5,6,7,0,1,2], target =...

题目描述给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 12输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4] 算法思路同样，题目的难点主要是在于他的时间复杂度要求，只能是$O(logn)$，这意味着你不能去遍历这个数组，不然时间复杂度最低也是$O(n)$，但是都提示到这里了，也很难不想到二分查找，毕竟你必须得对$log$这个符号敏感！ 这里我的方法比较蠢，我主要的思路是这样的： 记答案为1, 2 假如nums[mid] > target，那么1，2出现在[left, mid] 假如nums[mid] < target，那么1，2出现在[mid, right] 假如nums[mid] ==...

题目描述给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 示例 1： 12输入：nums = [1,3,4,2,2]输出：2 算法思路这个题目如果不要求不能修改数组并且不额外使用空间，那么这道题解法太多了，排序或者哈希表都能解决。这个题目去年我做过，但是已经忘了，只记得是二分查找，于是就看了官方题解。总结一下，大概思路是这样的： 如果一个数字重复了，我们假设它是target，我们记cnt[i]为小于等于i的数字的数量，那么对于： 1~target-1，每个数字不重复，cnt[i] <= i >=target，至少重复一个target，cnt[i] > i 则我们需要找到这个target，即刚好满足i < target,cnt[i]<=i; i >= target, cnt[i] >...

题目描述有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。 求所能获得硬币的最大数量。 示例 1： 12345输入：nums = [3,1,5,8]输出：167解释：nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 =...

题目描述给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 12输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2] 具体见题目详解。 算法思路这道题很容易想到的是先使用hash_map存储每个元素的出现频次，但是接下来怎么处理就比较麻烦，因为题目要求时间复杂度不高于 $O(N \times LogN)$ ，如果用了传统的排序，那么最低就需要$NLogN$的复杂度。因此需要考虑别的方法，比如桶排序和堆排序，这里我没有采用堆排序一是因为其复杂度其实是$O(N \times LogN)$，其二是因为自己不太会堆排序hhh，桶排序就比较简单了，我们先通过hash表存储每个元素的出现频次，再将key和map倒过来，何谓倒过来？可以这么理解，我们之前的数据结构hash_map[num] =...

题目描述给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例 1： 12输入：s = "3[a]2[bc]"输出："aaabcbc" 具体见题目详解。 算法思路又是摆烂了很久才写出一道题哈！真的是懒得动了……这个题目其实在大一程设课后习题上就见过，当时也是讲栈这一章节，所以我很快就想起来怎么做的，只不过编码确实花了不少时间，很容易发现，我们需要做的就是遍历字符串，根据数字、字母、[、]分别作出不同的决策即可，决策的目的在于将数字（也可以说是系数）和后面括号里的符号串匹配，难点在于括号嵌套括号，比如...

题目描述假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。 示例 1： 12345678910输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]解释：编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1...

题目描述给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1： 123输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。 具体见题目详解。 算法思路这个题目确实有点气煞我也，因为就在不久前，我做了一道很类似的题目，当时觉得自己弄懂了……结果到头来还是在深搜+剪枝，最后时间复杂度过不去，最开始的一版代码很简单： 123456789101112131415161718192021222324class Solution { void dfs(vector<int> &nums, int target, int now, int index) { if (now == target) { ans = 1; } if (index >= nums.size() || now > target || ans)...

题目描述给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 1： 123输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出：3解释：和等于 8 的路径有 3 条，如图所示。 具体见题目描述。 算法思路打眼一看其实这题真的唬人，因为本来树上搜索就比较麻烦，现在还不知道从哪个节点能找到这么一条路径，给人的第一念头就是想暴力，但是那肯定不会过的。但是仔细观察后就不难想到前缀和。大致这么个思路：我们记前缀和为presum，那么如上图那棵树而言，如果我们进行深搜，很容易发现第一次到达底部时,presum中的值为[10, 15, 18, 21]，那我们需要做什么呢？只需要找到presum[i], presum[j]使其满足presum[j] - presum[i] =...

题目描述给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。 示例 1： 12输入：nums = [4,3,2,7,8,2,3,1]输出：[5,6] 算法思路这道题目主要难点在于要求：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。 如果可以利用额外空间，那么这个题目很简单，只需要先创建一个集合，将1~n所有数字加进去，再遍历nums，把所有存在的数字剔除掉就可以，然后返回集合的数组形式。 但是要求不能用额外空间我就没办法做了，只能看官方题解，题解思路比较奇怪，其使用了原地哈希表，也就是把nums本身当作哈希表进行操作，大体上是这样： 遍历nums[i]，由题意由$1 <=...