郑州58同城,网站做竞价对优化有好处吗,wordpress 刀具企业,全球搜官网题目
文件组合 待传输文件被切分成多个部分#xff0c;按照原排列顺序#xff0c;每部分文件编号均为一个 正整数#xff08;至少含有两个文件#xff09;。传输要求为#xff1a;连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组…题目
文件组合 待传输文件被切分成多个部分按照原排列顺序每部分文件编号均为一个 正整数至少含有两个文件。传输要求为连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。 注意返回时需遵循以下规则 每种组合按照文件编号 升序 排列 不同组合按照第一个文件编号 升序 排列。 示例 1 输入target 12 输出[[3, 4, 5]] 解释在上述示例中存在一个连续正整数序列的和为 12为 [3, 4, 5]。 示例 2 输入target 18 输出[[3,4,5,6],[5,6,7]] 解释在上述示例中存在两个连续正整数序列的和分别为18分别为 [3, 4, 5, 6] 和 [5, 6, 7]。 提示 1 target 10^5 解法1分类
这种做法是笔者最朴素的想法如果遍历小于 target 的每一个数逐个相加尝试该数是否能组成一个符合条件的文件序列那时间复杂度太高了其实这种就是滑动窗口的思想复杂度只有O(N)。于是我想能否在遍历到这个数的同时直接根据这个数与 target 之间的某种关系判断其能否形成合适的序列于是在观察到文件序列其实是等差数列后我决定依据等差数列的特点对其进行分类使用 i 进行遍历。文件序列如果有奇数个元素则可以找到等差中项target 能整除 i 且 n target / i 必须为奇数文件序列如果有偶数个元素则target 能整除 i i1 且 n 和 target 的奇偶必须相同!((ntarget)%2)因为n 表示有n对i i1而i i1必为奇数所以当n为偶数的时候n对i i1的和为偶数n为奇数的时候n对i i1的和为奇数。所以 n 和 target 的奇偶必须相同由于题目要求不同组合按照第一个文件编号 升序 排列而当我遍历 i 时无法确定由 i 作为靠中间的元素的这个序列的头部是多少所以我使用了 map 存储利用了 map 会自动排序 key 的特点结构map第一个文件编号文件编号序列的 vector
class Solution {
public:vectorvectorint fileCombination(int target) {vectorvectorint all;mapint, vectorint forOrder;for(int i1; i(target1)/2; i){if(!(target%i)){//target 能整除 i则可能的组合有奇数个元素int n target / i;if(n%2 in/2){//n 为组合中元素的个数必须为奇数vectorint group;for(int ji-n/2; jin/2; j){group.push_back(j);}forOrder[i-n/2] group;}}if(!(target%(i i1))){//target 能整除 i i1可能的组合必为偶数个元素int n target/(i i1);if(!((ntarget)%2) i-(n-1)0){//n 和 target 的奇偶必须相同vectorint group;for(int ji-(n-1); j(i1)(n-1); j){group.push_back(j);}forOrder[i-(n-1)] group;}}}// 将 forOrder 中的元素按顺序存入 all 中for (const auto pair : forOrder) {all.push_back(pair.second);}return all;}
};解法2滑动窗口双指针
这种想法也很简单从 i1 开始计算其后连续的序列的和如果和小于 target那么就在和的基础上往后再加一个数字如果和大于 target 了则表明此时的 i 作为开始元素找不到合适的序列此时 i 往后移动并记得让和减去上一个 i这种想法虽然是遍历求和并比较和与目标值但是时间复杂度并不高这是因为每次遍历和的计算都是在上一轮和的计算结果上进行的由于是从 i1 开始遍历逐渐求和比较故不存在有的序列会遍历不到的问题
//滑动窗口vectorvectorint fileCombination(int target) {vectorvectorint all;int i1, j2, sumij;while(ij){if(sum target){vectorint group;for(int ki; kj; k){group.push_back(k);}all.push_back(group);}if(sum target){j;sum j;// coutj:jsumsumendl;} else{sum - i;i;}}return all;}解法3等比数列求和公式求解
知道序列和 target知道首项 i那么可以利用等差数列求和公式 二次方程求根公式求出末项 j遍历 i 找到所有符合的末项 j 即可。由于是使用公式计算时间复杂度并不高当 j 为整数时符合条件此处的判断方法为if(j (int)j)c 中有int i当 ii 结果超过int时需要写成(long)ii表达式 ii 的结果会首先根据表达式中操作数的类型来决定。如果 i 是整型int那么表达式 ii 也会被视为整型运算。
//等差求和公式做法vectorvectorint fileCombination(int target) {vectorvectorint all;for(int i1; i(target1)/2; i){double j (-1sqrt(14*(2*target(long)i*i-i)))/2.0;if(j (int)j){vectorint group;for(int ki; k(int)j; k){group.push_back(k);}all.push_back(group);}}return all;}
