php教育视频网站开发,成都seo外包,网站建设朋友圈怎么写,深圳教育 网站建设文章目录1. 题目2. 解题2.1 DFS2.2 状态压缩DP265 / 3871#xff0c; 前6.85%
前3题题解#xff1a;
LeetCode 5649. 解码异或后的数组#xff08;位运算#xff09;LeetCode 5652. 交换链表中的节点#xff08;快慢指针#xff09;LeetCode 5650. 执行交换操作后的最小…
文章目录1. 题目2. 解题2.1 DFS2.2 状态压缩DP265 / 3871 前6.85%
前3题题解
LeetCode 5649. 解码异或后的数组位运算LeetCode 5652. 交换链表中的节点快慢指针LeetCode 5650. 执行交换操作后的最小汉明距离并查集
1. 题目
给你一个整数数组 jobs 其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。 所有工作都应该分配给工人且每项工作只能分配给一位工人。 工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。 请你设计一套最佳的工作分配方案使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1
输入jobs [3,2,3], k 3
输出3
解释给每位工人分配一项工作最大工作时间是 3 。示例 2
输入jobs [1,2,4,7,8], k 2
输出11
解释按下述方式分配工作
1 号工人1、2、8工作时间 1 2 8 11
2 号工人4、7工作时间 4 7 11
最大工作时间是 11 。提示
1 k jobs.length 12
1 jobs[i] 10^7https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/
2. 解题
2.1 DFS
先排序也可以不排序使用 DFS 暴力搜索过程中进行剪枝
class Solution {int ans INT_MAX;
public:int minimumTimeRequired(vectorint jobs, int k) {int n jobs.size();// 不排序 88mssort(jobs.begin(), jobs.end()); // 40ms// sort(jobs.rbegin(), jobs.rend()); // 680msvectorint time(k, 0);dfs(jobs, time, k, 0);return ans;}void dfs(vectorint jobs, vectorint time, int k, int idx){if(idx jobs.size()){int t *max_element(time.begin(), time.end());if(t ans)// 最大的时间总和 更小ans t;return;}for(int i 0; i k; i){if(time[i]jobs[idx] ans)//如果某人的时间超过答案不可能是更优答案剪枝continue;time[i] jobs[idx];dfs(jobs, time, k, idx1);time[i] - jobs[idx];if(time[i] 0)break;//搜完了不加会超时}}
};40 ms 7.6 MB C
2.2 状态压缩DP
参考大佬题解
类似题目LeetCode 1178. 猜字谜状态压缩枚举二进制子集哈希
class Solution {
public:int minimumTimeRequired(vectorint jobs, int k) {int n jobs.size();// 使用 12 位二进制数的 0,1 表示某个工作分配了没vectorint time(1n, 0);for(int i 1; i (1n); i){for(int j 0; j n; j){if((i (1j)) 0)continue;int left i - (1j);//除去 j 工作外的工作time[i] time[left]jobs[j];}}vectorvectorint dp(k, vectorint(1n, INT_MAX));// dp[k][sub] 表示 前 k 个人处理 sub 任务子集 的最优分配时间for(int i 0; i (1n); i)dp[0][i] time[i];for(int ki 1; ki k; ki){for(int i 0; i (1n); i){for(int s i; s; s i(s-1))//枚举 i 的全部子集{int left i - s;int t max(dp[ki-1][left], time[s]);dp[ki][i] min(dp[ki][i], t);}}}return dp[k-1][(1n)-1];}
};1352 ms 11.2 MB C
附枚举子集 for(int s i; s; s (s-1) i)
#includebits/stdc.h
using namespace std;
int main()
{char buf[50];for(int i 6; i 8; i){cout i endl;for(int s i; s; s (s-1)i){itoa(s, buf, 2);printf(buf);printf(\n);}cout -------- endl;}return 0;
}6
110
100
10
--------
7
111
110
101
100
11
10
1
--------
8
1000
--------
请按任意键继续. . .我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
