Какая польза от создания копии ввода при рекурсивном вызове?
Это код для генерации всех подстрок заданного вектора.
class Solution {
public:
void sub(vector<int> &ip, vector<int> &op, vector<vector<int>> &ans) {
if (ip.size() == 0) {
ans.push_back(op);
return;
}
// Create a copy of ip to avoid modifying the original vector
vector<int> ip_copy(ip);
vector<int> op_one = op;
vector<int> op_two = op;
op_two.push_back(ip_copy[0]);
ip_copy.erase(ip_copy.begin());
sub(ip_copy, op_one, ans);
sub(ip_copy, op_two, ans);
return;
}
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> ans;
vector<int> op;
sub(nums, op, ans);
return ans;
}
};
мой вопрос: почему я должен создавать копию IP? Когда копия передается следующему рекурсивному вызову, почему я не могу использовать только исходный ввод? (кроме, конечно, сохранения информации)
Этот код ниже не дает подстроку, содержащую более одного целого числа.
class Solution {
public:
void sub(vector<int> &ip, vector<int> &op, vector<vector<int>> &ans) {
if (ip.size() == 0) {
ans.push_back(op);
return;
}
vector<int> op_one = op;
vector<int> op_two = op;
op_two.push_back(ip[0]);
ip.erase(ip.begin());
sub(ip, op_one, ans);
sub(ip, op_two, ans);
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> op;
sub(nums, op, ans);
return ans;
}
};
Когда я добавляю ту же копию в рекурсивную функцию после ее изменения, почему бы не использовать тот же вектор, когда сохранение информации не является приоритетом
Вы дважды помещаете одну и ту же копию в ссылочный параметр. Без копии каждый из этих вызовов изменяет ip. Гораздо проще было бы взять ip (и op) по значению.
когда сохранение информации не является приоритетом Не так ли? Вы сами сказали, что если вы измените исходный вектор вместо копии, ваш код не будет работать так, как вы ожидаете. Звучит как веская причина уделить приоритетное внимание сохранению информации.
Ответы 1
Когда копия передается следующему рекурсивному вызову, почему я не могу использовать только исходный ввод?
Потому что оригинал ip — это отсылка. Если вы не скопируете его, первый рекурсивный вызов изменит его перед вторым вызовом.
Если вы скопируете его, каждый одноуровневый вызов будет иметь одинаковое состояние.
Однако я считаю очень подозрительным иметь функцию, которая принимает по ссылке и копирует в тело. Гораздо проще просто взять по значению.
class Solution {
public:
vector<vector<int>> subsets(vector<int> ip, vector<int> op = {}) {
if (ip.size() == 0) {
return { op };
}
int value = ip[0];
ip.erase(ip.begin());
vector<vector<int>> ans_one = sub(ip, op);
op.push_back(value);
vector<vector<int>> ans_two = sub(ip, op);
ans_one.insert(ans_one.end(), ans_two.begin(), ans_two.end());
return ans_one;
}
Вы изменяете вектор, очевидно, что изменение копии отличается от изменения ссылки. Может быть, вам стоит пройти шаг за шагом с обеими версиями вашей функции и записать все значения всех переменных, чтобы понять, что происходит в каждом случае?