Как сохранить значение при использовании рекурсии - PullRequest
Новая
       5

Как сохранить значение при использовании рекурсии

1 голос
/ 20 июня 2019

Я недавно решаю проблему кода leetcode: https://leetcode.com/problems/employee-importance/

Я также прилагаю вопрос ниже:

Вам предоставляется структура данных о сотруднике, которая включает уникальный идентификатор сотрудника, значение его важности и идентификатор его непосредственного подчиненного.

Например, сотрудник 1 является лидером сотрудника 2, а сотрудник 2 - лидером сотрудника 3. Они имеют значение важности 15, 10 и 5 соответственно.,Тогда сотрудник 1 имеет структуру данных, подобную [1, 15, [2]], а сотрудник 2 имеет [2, 10, [3]], а сотрудник 3 имеет [3, 5, []].Обратите внимание, что хотя сотрудник 3 также является подчиненным сотрудника 1, отношения не являются прямыми.

Теперь, учитывая информацию о сотруднике компании и идентификатор сотрудника, необходимо вернуть значение общей важности этого сотрудника.и все его подчиненные.

Пример 1:

Ввод: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 Вывод: 11 Объяснение: Сотрудник 1 имеет значение важности 5, и у него есть два прямых подчиненных: сотрудник 2 и сотрудник 3. Они оба имеют значение важности 3. Таким образом, общее значение важности сотрудника 1 равно 5 + 3 +3 = 11.

Я использовал этот тестовый пример: Ввод: [[1,5, [2,3]], [2,3, [4,5]], [3,4, []], [4,6, []], [5,1, []]], 1

Ниже мой код: 

/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {

        int subImportance(vector<Employee*> employees, vector<int> &_subordinates, int _i, int _count)
    {


            for(int _subid : _subordinates)
            {
                for(int i = 0; i < employees.size(); i++)
                {
                    if(employees[i] ->id == _subid)
                    {
                        _count = _count + employees[i] -> importance;

                        cout<<i<<" "<<_count<<" "<<_subid<<endl;

                       if(employees[i] -> subordinates.size() == 0)
                           break;
                        else
        subImportance(employees, employees[i] -> subordinates, i , _count);
                        }
                }
            }
            cout<<"mark"<<endl;
           return _count;  

    }
public:

    int getImportance(vector<Employee*> employees, int id) {


        int found;
        for(int i = 0; i < employees.size(); i++)
        {
            if(employees[i] -> id == id)
            {
               found = i;
            }
        }

        int count = employees[found] -> importance;

        if((employees[found] -> subordinates).size() == 0 )

            return count;
        else
        {

            return subImportance(employees,  employees[found] ->subordinates, found, count);
        }
    }
};

_count накапливается с сотрудниками [я] -> значение правильно, когда оно проходит через ветвь 1-> 2-> 4-> 5, затем достигает конца цикла родительского узла 2 и переходит к узлу 3, но накопленное значение не сохраняется (важностьID 1 + 2+ 4 + 5), вместо этогоLy сохраняет (1 + 2), затем добавляет значение 3 и возвращает значение (я распечатал значения).Я полагаю, что это потому, что функция достигает конца цикла родительского 2 (2-> 4-> 5) и "return _cout" и когда она возвращается к узлу 3, чтобы завершить цикл, она как-то не сохраняет значение врекурсии.

Как мне обновить мой код, чтобы сохранить рассчитанные значения?

Заранее спасибо.

...