精选力扣300+题目之数组

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解如果可以的话求个B站三连，感谢！

3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！此外，每周都会进行精华总结和分享！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载。

# 1049. 最后一块石头的重量 II 好题，真的好题

力扣原题链接（点我直达） (opens new window)

有一堆石头，每块石头的重量都是正整数。

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

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

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

示例：

输入：[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]，这就是最优值。

1
2
3
4
5
6
7

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

# 第一版，完全看的思路问题

执行用时 :4 ms, 在所有 cpp 提交中击败了89.93%的用户

内存消耗 :8.6 MB, 在所有 cpp 提交中击败了100.00%的用户

    int lastStoneWeightII(vector<int>& stones) {
    
    int sum = accumulate(stones.begin(), stones.end(), 0);
	int target = sum / 2;
	vector<int> dp = vector<int>(target + 1, 0);
	long size = stones.size();
	for (int i = 0; i < size; i++) {
		int s = stones[i];
		for (int j = target; j >= s; j--) {
			dp[j] = max(dp[j], dp[j - s] + s);
		}
	}
	return sum - 2 * dp.back();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

等价于最大化半个背包的重量

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int S = sum / 2;
        int N = stones.size();
        vector<vector<int> > dp(S + 1, vector<int>(N + 1, 0));
        for (int i = 1; i <= S; ++i) {
            for (int j = 1; j <= N; ++j) {
                dp[i][j] = max(dp[i][j - 1],
                    (i >= stones[j - 1]) ? dp[i - stones[j - 1]][j - 1] + stones[j - 1] : 0); 
            }
        }
        return sum - 2 * dp[S][N];
    }
};

// 也可以使用状态压缩后的dp
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int S = sum / 2;
        int N = stones.size();
        vector<int> dp(S + 1, 0);
        for (int i = 0; i < N; ++i) {
            int w = stones[i];
            for (int j = S; j >= w; --j) {
                dp[j] = max(dp[j], dp[j - w] + w);
            }
        }
        return sum - 2 * dp[S];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

← 1046. 最后一块石头的重量 1217. 玩筹码 →