无      2021-06-12

题目

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数:

  • 给当前结果添加一个数位(i + 1)的成本为 cost[i] (cost 数组下标从 0 开始)。
  • 总成本必须恰好等于 target 。
  • 添加的数位中没有数字 0 。

由于答案可能会很大,请你以字符串形式返回。

如果按照上述要求无法得到任何整数,请你返回 "0" 。

 

示例 1:

输入:cost = [4,3,2,5,6,7,2,5,5], target = 9
输出:"7772"
解释:添加数位 '7' 的成本为 2 ,添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字,但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2:

输入:cost = [7,6,5,5,5,6,8,7,8], target = 12
输出:"85"
解释:添加数位 '8' 的成本是 7 ,添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3:

输入:cost = [2,4,6,2,4,6,4,4,4], target = 5
输出:"0"
解释:总成本是 target 的条件下,无法生成任何整数。

示例 4:

输入:cost = [6,10,15,40,40,40,40,40,40], target = 47
输出:"32211"

 

提示:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

思路分析

本题仍是一个常规dp,虽然是困难题,只要我们分析到位,

无      2021-06-11

题目

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

 

示例 1:

  1. 输入:n = 12
  2. 输出:3
  3. 解释:12 = 4 + 4 + 4

示例 2:

  1. 输入:n = 13
  2. 输出:2
  3. 解释:13 = 4 + 9

 

提示:

  • 1 <= n <= 104

思路分析

本道题如果从dp的角度来看,是一个非常常规的背包问题,唯一要注意的点就是每一个完全平方数都可以无限次使用,所以是一个完全背包问题。

递推公式 dp[i] = min(dp[i], dp[i - 完全平方数] + 1)
边界条件 dp[0] = 1,其余等于正无穷
dp[i]的意义 i最少可以由dp[i]个完全平方数组成

这样一列就非常简单了。

当然本题还有一个数学做法。用通俗的说法来说就是,每个自然数都已经被证明了可以由至多四个完全平方数相加得到,而且还是有特解的。具体的证明可以看四平方和定理 百度百科
然后用O(1)的时间特判一下n是不是完全平方数,如果不是,那么只有2和3两种答案了。如果是,答案就是1。

因为由三个完全平方数的和不好获得,所以继续判断是不是两个平方数的和,仅使用O(n)就可获得是不是2,所以整体的复杂度就是O(n)级别的。

当然,这道题主要还是考验大家dp的算法。

C++代码

  1. class Solution {
  2. public:
  3. int numSquares(int n) {
  4. ve
无      2021-06-10

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

 

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

 

注意:

你可以假设:

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数

思路分析

这个题非常简单,我们直接用dp的思想去思考即可。
状态量只有一个,就是金额,也就是说,我们对总金额amount进行dp即可。
dp[i]自然表示的就是总金额为i元时的方案数。
递推公式也很好出,dp[i] += dp[i - coins[t]]

这里有没有发现一个问题,递推式其实跟题目中的某一句话没有关系,”每一种面额的硬币有无数个“,不管硬币的数量有多少,或者是只有一个,我们的递推公式都没有任何变化。

那么如果有之前做过这两类题目的同学,应该就能知道区别了,每一种有无限个,我们从前向后遍历dp数组,每种只有一个的时候,我们从后向前遍历dp数组。

虽然递推式都是dp[i] += dp[i - coins[t]]不变的。

这一点非常关键。

C++代码

  1. ```
  2. # Rust代码
  3. ```rust
  4. impl Solution {
  5. pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
  6. let amount = amount as usize;
  7. let mut v = vec
无      2021-06-09
原贴地址:[http://blog.leanote.com/post/dawnmagnet/lc879](http://blog.leanote.com/post/dawnmagnet/lc879)
# 题目

集团里有 n 名员工,他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作,就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n

有多少种计划可以选择?因为答案很大,所以 返回结果模 10^9 + 7 的值

 

示例 1:

输入:n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出:2
解释:至少产生 3 的利润,该集团可以完成工作 0 和工作 1 ,或仅完成工作 1 。
总的来说,有两种计划。

示例 2:

输入:n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出:7
解释:至少产生 5 的利润,只要完成其中一种工作就行,所以该集团可以完成任何工作。
有 7 种可能的计划:(0),(1),(2),(0,1),(0,2),(1,2),以及 (0,1,2) 。

 

提示:

  • 1 <= n <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

思路分析

我们一开始就拿动态规划的思想去套,其实还是比较好套的
因为我们最终要求的是方案数,那么dp[][]一定是一个状态下的方案数。接下来就需要找到方案数的递推关系。
因为有两个变量,收益和人数,很轻松的就可以套进去。
那么dp[it][jt]的含义就代表在使用it名员工,收益为jt的情况下所有的方案数。

无      2021-06-08

题目

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

  • 如果 x == y,那么两块石头都会被完全粉碎;
  • 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x

最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0

 

示例 1:

输入:stones = [2,7,4,1,8,1]
输出:1
解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

示例 2:

输入:stones = [31,26,33,21,40]
输出:5

示例 3:

输入:stones = [1,2]
输出:1

 

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

思路分析

这个题一开始我还不太会。
一开始想到的是dfs,也就是模拟题目中所说的场景,但复杂度过高,基本上达到了O(3030),非常地不现实。

然后我就开始想dp,怎么dp感觉都不行。如果我们是二维dp,我们又怎么表示两块石头相减之后的那一小块呢?没法表示,也就没法dp

思路一时间陷入了瓶颈。

我又仔细地读了一遍题目。发现我们做的是这么一个事情。我们将石头看成棍子,假设有两根棍子一根长x,一根长y,我们同时拿一个东西去砍,如果两根长度相同,那么砍完就什么都不剩了,如果一根长一根短,剩的就是长的那根减去短的那根剩下来

无      2021-06-07

题目

给你一个整数数组 nums 和一个整数 target

向数组中的每个整数前添加 '+''-' ,然后串联起所有整数,可以构造一个 表达式

  • 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

 

示例 1:

输入: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 = 3

示例 2:

输入:nums = [1], target = 1
输出:1

 

提示:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 100

思路分析

一开始我有一个想法,就是使用HashSet来存储。
每一次读取到一个num,就将所有HashSet中的数字拿出来,加减num之后存到另一个HashSet中。
做是做出来了,题目也通过了。

  1. class Solution {
  2. public:
  3. int findTargetSumWays(vector<int>& nums, int target) {
  4. unordered_map<int, int> m;
  5. m[0] = 1;
  6. for (auto & num : nums) {
  7. unordered_map<int, int> mx;
  8. for (auto & p
无      2021-06-05

题目

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

 

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

 

提示:

  • 列表中的节点在范围 [0, 104]
  • 1 <= Node.val <= 50
  • 0 <= k <= 50

思路分析

本题的难点就在于对链表的操作,如果这个链表是一个形式如示例3的链表,删除完之后可能会连原先的head节点都会被删除,但是如果我们捏着head不放,根本就没法删head,怎么办呢。

这里就会说到一个常用的做链表题的手段了,就是添加watch节点。
原来是7->7->7->7->null
添加了watch之后 变成了watch->7->7->7->7->null

这样操作以后,我们就不用担心对之前的head节点做什么操作了,因为head已经变成了一个普通的节点,无需顾虑。操作完之后,我们不返回之前的head,因为head可能已经不知道去哪儿了。所以我们返回watch->next即可,不管这个链表处理完是什么样,watch都不会对链表的操作产生影响,这也是为什么它叫watch,因为它只是起一个辅助作用。

C++代码

  1. class Solution {
  2. public:
  3. ListNode* removeElements(ListNode* head, int val) {
  4. ListNode * watch = new ListNode(0);
  5. watch->next = head;
  6. ListNode* cur = watch;
  7. while (cur->next) {
无      2021-06-04

题目

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

图示两个链表在节点 c1 开始相交

title

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构

 

示例 1:

title

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

title

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

title

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

 

提示:

  • listA 中节点数目为 m
  • listB 中节点数目为 n
无      2021-06-03

题目

给定一个二进制数组 nums , 找到含有相同数量的 01 的最长连续子数组,并返回该子数组的长度。

 

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

 

提示:

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1

思路分析

这道题画张图大家就明白了

0
1
0
1
1
1
0
0
0比1多的数量
0
1
-1
-2

每一条线上的任意两点之间,都是一个含有相同数量0和1的连续子数组。
想找到最长的子数组,就是找到每条线最右边的点到最左边的点的最大差值
所以我们就用哈希表来存最左边的点。

C++代码

  1. class Solution {
  2. public:
  3. int findMaxLength(vector<int>& nums) {
  4. unordered_map<int, int> m;
  5. int res = 0;
  6. m[0] = 0;
  7. vector<int> prefix(nums.size() + 1);
  8. for (int i = 0; i < nums.size(); ++i) {
  9. prefix[i + 1] = (prefix[i] + nums[i] * 2 - 1);
  10. if (m.find(prefix[i + 1]) != m.end()) {
  11. res = max(res, i + 1 - m[prefix[i + 1]]);
  12. } else {
  13. m[prefix[i + 1]] = i + 1;
  14. }
  15. }
无      2021-06-02

题目

给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

  • 子数组大小 至少为 2 ,且
  • 子数组元素总和为 k 的倍数。

如果存在,返回 true ;否则返回 false

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 xk 的一个倍数。

 

示例 1:

输入:nums = [23,2,4,6,7], k = 6
输出:true
解释:[2,4] 是一个大小为 2 的子数组,并且和为 6 。

示例 2:

输入:nums = [23,2,6,4,7], k = 6
输出:true
解释:[23, 2, 6, 4, 7] 是大小为 5 的子数组,并且和为 42 。 
42 是 6 的倍数,因为 42 = 7 * 6 且 7 是一个整数。

示例 3:

输入:nums = [23,2,6,4,7], k = 13
输出:false

 

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= sum(nums[i]) <= 231 - 1
  • 1 <= k <= 231 - 1

思路分析

这道题是一个道子数组的题目。
子数组通常会有一个暴力解法。复杂度是O(n2),且通常都会超时
一般来说都需要我们优化成O(nlgn)或者O(n)的复杂度。

在这道题中,子数组最关键的性质是可以被k整除。
如果无从下手,可以从暴力的思路里找找线索。
我们可以枚举左边界也可以枚举右边界,对于每一次枚举右边界来说,我们都需要让左边界在0至右边界的范围内移动,获得该区间的值。之前我们说过,快速获取一段区间内的和这种问题