golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-10-22 08:56:37

func pathSum(nums []int) int {
    grid := make([][]int8, 4)
    for i := 0; i < 4; i++ {
        grid[i] = make([]int8, 8)
        for j := 0; j < 8; j++ {
            grid[i][j] = -1
        }
    }
    for _, num := range nums {
        grid[num / 100-1][num % 100 / 10 -1] = int8(num% 10)
    }
    var ans int8
    var dfs func(idx int, level int, sum int8) 
    dfs = func(idx int, level int, sum int8) {
        if level >= 4 || idx > 8 || grid[level][idx] == -1 {
            return
        }
        sum += grid[level][idx]
        left := idx * 2 
        right := idx * 2 + 1
        if level == 3 || grid[level+1][left] == -1 && grid[level+1][right] == -1 {
            ans += sum
            return
        }
        dfs(left, level+1, sum)
        dfs(right, level+1, sum) 
    }
    dfs(0, 0, 0)
    return int(ans)
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-22 08:56:11

func pathSum(nums []int) int {
    tree := make([]int, 16)
    for i := range tree {
        tree[i] = -1
    }
    for i := range nums {
        pos, dep := nums[i]/10%10-1, nums[i]/100%10-1
        tree[1<<dep-1+pos] = nums[i] % 10 // 2^2 是异或……
    }
    return helper(tree, 0, 0)
}

func helper(tree []int, root, sum int) int {
    if tree[root] == -1 {
        return 0
    }
    if root >= 7 || tree[2*root+1] == -1 && tree[2*root+2] == -1 {  // 最后一层或者叶节点直接返回
        return tree[root] + sum
    }
    return helper(tree, 2*root+1, sum+tree[root]) + helper(tree, 2*root+2, sum+tree[root])
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 10.2 MB, 提交时间: 2023-10-22 08:55:50

class Solution {
public:
    pair<int, int> helper(vector<int>& nodes, int ind) {
        if (nodes[ind] == -1) return {0, 0};
        auto left = helper(nodes, 2 * ind + 1);
        auto right = helper(nodes, 2 * ind + 2);
        int count = max(left.second + right.second, 1); // root值被使用几次
        int value = left.first + right.first + nodes[ind] * count; // root及其子树所有可能的路径加和
        return {value, count};
    }
    int pathSum(vector<int>& nums) {
        vector<int> nodes(64, -1); // 能容下6层数组，防止下标溢出
        for (auto x : nums) {
            int val = x % 10;
            int pos = (x / 10) % 10;
            int dep = x / 100;
            int ind = (1 << (dep - 1)) - 1 + pos - 1;
            nodes[ind] = val;
        }
        return helper(nodes, 0).first;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 39 MB, 提交时间: 2023-10-22 08:55:24

class Solution {
    int ans = 0;
    public int pathSum(int[] nums) {
        Node root = new Node(nums[0] % 10);
        for (int num: nums) {
            if (num == nums[0]) continue;
            int depth = num / 100, pos = num / 10 % 10, val = num % 10;
            pos--;
            Node cur = root;
            for (int d = depth - 2; d >= 0; --d) {
                if (pos < 1<<d) {
                    if (cur.left == null) cur.left = new Node(val);
                    cur = cur.left;
                } else {
                    if (cur.right == null) cur.right = new Node(val);
                    cur = cur.right;
                }
                pos %= 1<<d;
            }
        }

        dfs(root, 0);
        return ans;
    }

    public void dfs(Node node, int sum) {
        if (node == null) return;
        sum += node.val;
        if (node.left == null && node.right == null) {
            ans += sum;
        } else {
            dfs(node.left, sum);
            dfs(node.right, sum);
        }
    }
}

class Node {
    Node left, right;
    int val;
    Node(int v) {val = v;}
}

java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-22 08:55:14

class Solution {
    int ans = 0;
    Map<Integer, Integer> values;
    public int pathSum(int[] nums) {
        values = new HashMap();
        for (int num: nums)
            values.put(num / 10, num % 10);

        dfs(nums[0] / 10, 0);
        return ans;
    }

    public void dfs(int node, int sum) {
        if (!values.containsKey(node)) return;
        sum += values.get(node);

        int depth = node / 10, pos = node % 10;
        int left = (depth + 1) * 10 + 2 * pos - 1;
        int right = left + 1;

        if (!values.containsKey(left) && !values.containsKey(right)) {
            ans += sum;
        } else {
            dfs(left, sum);
            dfs(right, sum);
        }
    }
}

python3 解法, 执行用时: 36 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-22 08:54:56

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        self.ans = 0
        values = {x // 10: x % 10 for x in nums}
        def dfs(node, running_sum = 0):
            if node not in values: return
            running_sum += values[node]
            depth, pos = divmod(node, 10)
            left = (depth + 1) * 10 + 2 * pos - 1
            right = left + 1

            if left not in values and right not in values:
                self.ans += running_sum
            else:
                dfs(left, running_sum)
                dfs(right, running_sum)

        dfs(nums[0] // 10)
        return self.ans

python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 08:54:21

class Node:
    def __init__(self, val: int):
        self.val = val
        self.left = self.right = None

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        self.ans = 0
        root = Node(nums[0] % 10)

        for x in nums[1:]:
            depth, pos, val = x//100, x//10 % 10, x % 10
            pos -= 1
            cur = root
            for d in range(depth - 2, -1, -1):
                if pos < 2**d:
                    cur.left = cur = cur.left or Node(val)
                else:
                    cur.right = cur = cur.right or Node(val)

                pos %= 2**d

        def dfs(node, running_sum = 0):
            if not node: return
            running_sum += node.val
            if not node.left and not node.right:
                self.ans += running_sum
            else:
                dfs(node.left, running_sum)
                dfs(node.right, running_sum)

        dfs(root)
        return self.ans