My C++ Non-recursive and No DP Solution


  • 0
    G
    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            int res = 0;
            map<int, unordered_set<int>> m;
            unordered_map<int, int> node;
            for (int num : nums) {
                int D = num / 100, P = num % 100 / 10, V = num % 10;
                node[num / 10] = V;
                m[D].insert(P);
            }
            for (auto a : m) {
                for (int p : a.second) {
                    int cur = a.first * 10 + p;
                    int left = (a.first + 1) * 10 + p * 2;
                    int right = (a.first + 1) * 10 + p * 2 - 1;
                    if (node.count(left)) node[left] += node[cur];
                    if (node.count(right)) node[right] += node[cur];
                    if (node.count(left) || node.count(right)) {
                        node.erase(cur);
                    }
                }
            }
            for (auto a : node) {
                res += a.second;
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.