做网站公司费用,婚恋网站策划,安卓开发简单网站开发代码下载,凡科网免费建站步骤及视频文章目录1. 题目2. 解题2.1 回溯1. 题目
给你一个长度为 n 的整数数组 nums #xff0c;这个数组中至多有 50 个不同的值。 同时你有 m 个顾客的订单 quantity #xff0c;其中#xff0c;整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给…
文章目录1. 题目2. 解题2.1 回溯1. 题目
给你一个长度为 n 的整数数组 nums 这个数组中至多有 50 个不同的值。 同时你有 m 个顾客的订单 quantity 其中整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客且满足
第 i 位顾客 恰好 有 quantity[i] 个整数。第 i 位顾客拿到的整数都是 相同的 。每位顾客都满足上述两个要求。
如果你可以分配 nums 中的整数满足上面的要求那么请返回 true 否则返回 false 。
示例 1
输入nums [1,2,3,4], quantity [2]
输出false
解释第 0 位顾客没办法得到两个相同的整数。示例 2
输入nums [1,2,3,3], quantity [2]
输出true
解释第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。示例 3
输入nums [1,1,2,2], quantity [2,2]
输出true
解释第 0 位顾客得到 [1,1] 第 1 位顾客得到 [2,2] 。示例 4
输入nums [1,1,2,3], quantity [2,2]
输出false
解释尽管第 0 位顾客可以得到 [1,1] 第 1 位顾客没法得到 2 个一样的整数。示例 5
输入nums [1,1,1,1,1], quantity [2,3]
输出true
解释第 0 位顾客得到 [1,1] 第 1 位顾客得到 [1,1,1] 。提示
n nums.length
1 n 10^5
1 nums[i] 1000
m quantity.length
1 m 10
1 quantity[i] 10^5
nums 中至多有 50 个不同的数字。来源力扣LeetCode 链接https://leetcode-cn.com/problems/distribute-repeating-integers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 回溯
class Solution {bool ans false;
public:bool canDistribute(vectorint nums, vectorint quantity) {unordered_mapint,int m;for(auto n : nums)m[n];vectorint val(m.size(), 0);int i 0;for(auto it m.begin(); it ! m.end(); it)val[i] it-second;sort(val.rbegin(), val.rend());sort(quantity.rbegin(), quantity.rend());dfs(val, quantity, 0);return ans;}void dfs(vectorint val, vectorint quantity, int i){if(ans)return;if(i quantity.size()){ans true;return;}for(int j 0; j val.size(); j){if(val[j]-quantity[i] 0){val[j] - quantity[i];dfs(val, quantity, i1);val[j] quantity[i];}}}
};820 ms 73.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
