当前位置:网站首页>leetcode:1755. 最接近目标值的子序列和
leetcode:1755. 最接近目标值的子序列和
2022-07-05 20:43:00 【OceanStar的学习笔记】
题目来源
题目描述
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
}
};
题目解析
分析数据量
在看题之前,我们先看下给出的数据量: 1 < = n u m s . l e n g t h < = 40 1 <= nums.length <= 40 1<=nums.length<=40,这意味着:
- 一方面,它几乎不太可能具有 O ( N 2 ) 、 O ( N 2 l o g N ) 、 O ( N 3 ) O(N^2)、O(N^2 logN)、O(N^3) O(N2)、O(N2logN)、O(N3),这样的时间复杂度,因为[1,40]的数据范围显得太小了
- 另一方面,它也不可能具有 O ( 2 N ) 、 O ( N ∗ 2 N ) 、 O ( 3 N ) O(2^N)、O(N * 2^N)、O(3^N) O(2N)、O(N∗2N)、O(3N)这样的时间复杂度,因为[1,40]的数据范围又太大了
一般来讲,数据量 n < = 20 n <= 20 n<=20,这暗示着我们应该用一个指数级别的算法来解决,比如分治、回溯、dfs等,像哪些动态规划之类的通通pass。那么对于 n < = 40 n <= 40 n<=40,唯一的可能性就是将40拆分成两个20,然后两边分别运行一个指数复杂度的解法
然后看下数据范围,好像有点大呀,动态规划pass
分析题意
然后再来看题。题目要求我们从数组中选出一些子集,经sum(子集) 最近接goal。
因为要求最接近,所以我们是肯定需要看尽所有的子集的。
枚举所有的子集可以用回溯的方法。
但是因为数据量 n < = 40 n <= 40 n<=40,如果枚举全部子集那么复杂度为 2 4 0 2^40 240,肯定会超时,所以需要做一定的处理
补充
ps:关于“最接近目标值的子序列和”这一类问题:
- 如果数组长度特别大,但是值小,我们可以使用背包问题的方式来解决
- 但是如果数组长度不大,但是数值特别大的话,使用DFS。
dfs
class Solution {
int point = 0; // 数组数据组合的指针(表示数组的下标)
/** * @param nums 题目给出的数组 * @param start 数组的开始位置 * @param end 数组的结束位置 * @param sum 保存左侧组合的和(sum) * @param arr 保存数组组合的和 */
void dfs(vector<int>& nums, int goal, int start, int sum, vector<int>& arr){
arr[point++] = sum;
for (int i = start; i < nums.size(); ++i) {
dfs(nums, goal, i + 1, sum + nums[i], arr);
}
}
public:
int minAbsDifference(vector<int>& nums, int goal) {
int N = nums.size();
int mid = N >> 1;
point = 0;
// 数据{ 5, -7, 3, 5 }==>左侧[5,-7] 右侧[5,-2]
// 保存所有左侧数据的组合==>[0, -7, 5, -2] 左侧数据为(5,-7)
std::vector<int> l(1 << 20);
// 保存右侧所有数据的组合==>[0, 5, 3, 8] 右侧数据为(5,-2)
std::vector<int> r(1 << 20);
dfs(nums, 0, mid - 1, 0, l); // 枚举左侧所有组合
point = 0;// 指针归0
dfs(nums, mid, N - 1, 0, r);// 枚举右侧所有组合
int ans = INT32_MAX;
std::sort(l.begin(), l.end());
std::sort(r.begin(), r.end());
//组合左侧数据与右侧数据
int left = 0, right = N - 1;
for(int x : l){
ans = std::min(ans, std::abs(goal - x));
}
for(int x : r){
ans = std::min(ans, std::abs(goal - x));
}
while (left < N && right >= 0){
int t = l[left] + r[right]; //临时保存左侧数据与右侧数据的组合
ans = std::min(ans, std::abs(t - goal));
if(t > goal){
right--;
}else{
left++;
}
}
return ans;
}
};
暴力(超时)
枚举所有子序列
class Solution {
int ans = INT32_MAX;
void dfs(vector<int>& nums, int goal, int start, int sum){
ans = std::min(ans, std::abs(sum - goal));
for (int i = start; i < nums.size(); ++i) {
dfs(nums, goal, i + 1, sum + nums[i]); //注意这里是i+1......易错点
}
}
public:
int minAbsDifference(vector<int>& nums, int goal) {
if(nums.empty()){
return goal;
}
dfs(nums, goal, 0, 0);
return ans;
}
};
小结:数据范围 n :
- n <= 20, 可以暴力,2^20
- n <= 40, 不能直接暴力,但是可以对半来,20 * 2^20
边栏推荐
- Mongodb/ document operation
- phpstudy小皮的mysql点击启动后迅速闪退,已解决
- Interpreting the daily application functions of cooperative robots
- Make Jar, Not War
- Introduction to dead letter queue (two consumers, one producer)
- Duchefa丨MS培养基含维生素说明书
- Wanglaoji pharmaceutical's public welfare activity of "caring for the most lovely people under the scorching sun" was launched in Nanjing
- Duchefa丨P1001植物琼脂中英文说明书
- Abbkine BCA法 蛋白质定量试剂盒说明书
- Abnova CD81 monoclonal antibody related parameters and Applications
猜你喜欢
Return to blowing marshland -- travel notes of zhailidong, founder of duanzhitang
MySQL fully parses json/ arrays
Pytorch 1.12 was released, officially supporting Apple M1 chip GPU acceleration and repairing many bugs
Duchefa丨S0188盐酸大观霉素五水合物中英文说明书
小程序全局配置
Rainbow 5.7.1 supports docking with multiple public clouds and clusters for abnormal alarms
Applet page navigation
Abnova maxpab mouse derived polyclonal antibody solution
MySQL InnoDB架构原理
ProSci LAG3抗体的化学性质和应用说明
随机推荐
Relationship between mongodb documents
Abnova total RNA Purification Kit for cultured cells Chinese and English instructions
欢迎来战,赢取丰厚奖金:Code Golf 代码高尔夫挑战赛正式启动
Material Design组件 - 使用BottomSheet展现扩展内容(二)
mysql全面解析json/数组
Simple understanding of interpolation search
Abnova maxpab mouse derived polyclonal antibody solution
Abnova DNA marker high quality control test program
Abnova 环孢素A单克隆抗体,及其研究工具
教你自己训练的pytorch模型转caffe(一)
Applet global configuration
Mathematical analysis_ Notes_ Chapter 9: curve integral and surface integral
CCPC 2021 Weihai - G. shinyruo and KFC (combination number, tips)
Where is a good stock account? Is online account manager safe to open an account
教你自己训练的pytorch模型转caffe(二)
Codeforces Round #804 (Div. 2) - A, B, C
How to make ERP inventory accounts of chemical enterprises more accurate
研学旅游实践教育的开展助力文旅产业发展
Abnova丨CRISPR SpCas9 多克隆抗体方案
Introduction to dead letter queue (two consumers, one producer)