argcxiang's blog

题目描述给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1： 12345678输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 =...

题目描述给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1 具体见题目详解。 算法思路对于这种问题，我最开始想的是贪心，因为你想让金币数量尽可能的少，还需要凑齐数额，就需要用尽可能大的金币面值。但这很显然进入了一个误区：全局最优并不代表局部最优。举个例子，对于 amount = 19, coins = [1, 6,...

题目描述二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。 示例 1： 123输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 具体见题目详解。 算法思路这是刷HOT100以来貌似碰到的第一个“困难”题目，不过所幸最后还是做出来了，我的思路很简单，首先肯定能想到这是个动态规划，但为什么是深搜呢？可以看我下面的分析。 计自身节点值为selfval，左儿子节点路径值为leftval，右儿子节点路径值为rightval，则有： 对于一个节点，如果最终的路径中，其作为父节点，那么很明显，最大值必然在{selfval、selfval+leftval、selfval+rightval、selfval+leftval+rightval}中间产出。 如果其不是父节点，那么其只能贡献selfval,...

题目描述给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 示例 1： 123输入：s = "abc"输出：3解释：三个回文子串: "a", "b", "c" 具体见题目详解。 算法思路很明显的读到题目就能想到动态规划，因为传统暴力：对于每个子串组合，分别判断其是否回文，时间复杂度最少是 $O(n^3)$，百分之百过不了测试，因为其做了很多重复工作，比如s[i~j]如果已经知道是否是回文之后，对于s[i-1,...

题目描述给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例 1： 123输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。 具体见题目详解。 算法思路这道题目我直接用dfs写的，结果超时了，因为我是正向dfs搜索的，如果遇到字符串 s = "aaa...aaaaa"，worddict={a, aa, aaa,...

题目描述给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 具体见题目详解。 算法思路最近很久没做题了，因为才开学老是摆烂……这道题目我想的很简单，就是遍历链表，同时存储节点，如果当前节点已经存在于“记录”中，那么这个节点就是入口，因此代码如下： 1234567891011121314151617181920class Solution {public: ListNode *detectCycle(ListNode *head) { ...

题目描述给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 示例 1: 123输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 具体见题目详解。 算法思路emmm这道题目我看得出来是一道dp的题目，但是我最后没做出来，看了官方题解跟大神题解后真感觉算法也是等级森严…… 思路借鉴方法1-动态规划先看一下官方题解，主要使用的思路就是动态规划，但是跟以往我做的动态规划不同的就是：虽然这个题目求的是最大乘积子数组，但是我们还需要维护一个最小乘积子数组，为什么呢？因为数组中存在负数，如果当前位置为正数，我们肯定希望他的前一部分越大越好，这样才能得到更大的乘积；但是如果当前位置是一个负数，那么我们需要他的前一部分乘积越小越好，这样才能负负得正。结合动态规划的思想，代码如下： 1234567891011121314class Solution {public: int...

题目描述设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。 示例 1: 12345678910111213141516输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStack minStack = new...

题目描述给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。 示例 1: 12输入: nums = [1,2,3,4]输出: [24,12,8,6] 具体可见题目详解。 算法思路这个题目我在备考蓝桥杯时也做过，我记得当时真的很难想出来怎么用O(n)的时间复杂度做，最终好像是看题解才做出来，但是这次做的时候却感觉很简单（可能是还有印象？）大体思路如下： 分别开辟两个数组记录前缀积和后缀积，所谓前缀积pre[n]就是指对于一个数组nums，nums[0]~nums[n]的乘积。和前缀和比较相像。 除去元素nums[i]自身，那么整个数组的乘积肯定是$nums[0] \times nums[1] \times … \times nums[i-1] \times nums[i + 1] \times … \times...

题目描述给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1： 12输入：nums = [3,2,3]输出：3 具体见题目详解。 算法思路这个题目最麻烦的是题目要求：时间复杂度是O(n)，空间复杂度是O(1)，抛开这个不说，最容易想到的肯定是打hash表，统计每个数字出现的次数，当某个数字出现的次数大于n/2时(n为数组长度)，则表示找到了这个元素。在做这个题目之前一直在思考是使用map还是vector，因为map容易建立映射，不会受到nums[i]的影响，但是访问速率比较慢，通常是O(logn)；vector访问速度快，是O(1)，但是需要对负数特殊处理，通常是取nums[i] - min_num。但是实际测试下来vector会memory out，所以只能使用map，最好是unordered_map。代码可以看官方题解的，代码如下： 123456789101112131415class Solution {public: ...