Mind palace

some thoughts

0%

666. Path Sum IV

Posted on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

dfs O(32) time O(16) space
generic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int pathSum(vector<int>& nums) {
        unordered_map<int, int> t;
        for (int x : nums) {
            t[x / 10] = x % 10; // 利用现有父子关系
        }
        dfs(t, 11, 0);
        return res;
    }

    void dfs(unordered_map<int, int> &t, int i, int s) {
        if (!t.count(i)) return;
        s += t[i];
        int r = i + 10 + i % 10, l = r - 1; // 33->45和46即33->43然后43+3得到46再-1得到45
        if (!t.count(l) && !t.count(r)) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int pathSum(vector<int>& nums) {
        unordered_map<int, int> t;
        for (int x : nums) {
            t[(1 << (x / 100 - 1)) + x % 100 / 10 - 1] = x % 10; // 转成tree-like array
        }
        dfs(t, 1, 0);
        return res;
    }

    void dfs(unordered_map<int, int> &t, int i, int s) {
        if (!t.count(i)) return;
        s += t[i];
        int l = i << 1, r = l + 1;
        if (!t.count(l) && !t.count(r)) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};

dfs O(32) time O(32) space
array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int pathSum(vector<int>& nums) {
        vector<int> t(32, -1);
        for (int x : nums) {
            t[(1 << (x / 100 - 1)) + x % 100 / 10 - 1] = x % 10;
        }
        dfs(t, 1, 0);
        return res;
    }

    void dfs(const vector<int> &t, int i, int s) {
        if (t[i] == -1) return;
        s += t[i];
        int l = i << 1, r = l + 1;
        if (t[l] == -1 && t[r] == -1) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int pathSum(vector<int>& nums) {
        array<int, 32> t;
        t.fill(-1);
        for (int x : nums) {
            t[(1 << (x / 100 - 1)) + x % 100 / 10 - 1] = x % 10;
        }
        dfs(t, 1, 0);
        return res;
    }

    void dfs(const array<int, 32> &t, int i, int s) {
        if (t[i] == -1) return;
        s += t[i];
        int l = i << 1, r = l + 1;
        if (t[l] == -1 && t[r] == -1) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int pathSum(vector<int>& nums) {
        int t[32] = {0};
        for (int x : nums) {
            t[(1 << (x / 100 - 1)) + x % 100 / 10 - 1] = x;
        }
        dfs(t, 1, 0);
        return res;
    }

    void dfs(int t[], int i, int s) {
        if (t[i] == 0) return;
        s += t[i] % 10;
        int l = i << 1, r = l + 1;
        if (t[l] == -1 && t[r] == -1) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};