[C++] [Java] Clean Code


  • 8
             0
         0       1
      0   1     2   3
    0 1  2 3   4 5  6 7
    

    Regardless whether these nodes exist:

    the position of left child is always parent_pos * 2;
    the position of right child is alwaysparent_pos * 2 + 1;
    the position of parent is always child_pos / 2;

    Solution C++ Array

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            int m[5][8] = {};
            for (int n : nums) {
                int i = n / 100; // i is 1 based index;
                int j = (n % 100) / 10 - 1; // j used 0 based index;
                int v = n % 10;
                m[i][j] = m[i - 1][j / 2] + v;
            }
    
            int sum = 0;
            for (int i = 1; i < 5; i++) {
                for (int j = 0; j < 8; j++) {
                    if (i == 4 || m[i][j] && !m[i + 1][j * 2] && !m[i + 1][j * 2 + 1]){
                        sum += m[i][j];
                    }
                }
            }
            return sum;
        }
    };
    

    Solution C++ map
    If we use map, we don't need to do the boundary check at little extra cost of memory.

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            map<int, map<int, int>> m;
            for (int n : nums) {
                int i = n / 100 - 1; // i is 0 based index;
                int j = (n % 100) / 10 - 1; // j used 0 based index;
                int v = n % 10;
                m[i][j] = m[i - 1][j / 2] + v;
            }
    
            int sum = 0;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 8; j++) {
                    sum += m[i][j] && !m[i + 1][j * 2] && !m[i + 1][j * 2 + 1] ? m[i][j] : 0;
                }
            }
            return sum;
        }
    };
    

    Solution C++ - queue

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            if (nums.empty()) return 0;
            int sum = 0;
            queue<info> q;
            info dummy(0);
            info* p = &dummy; // parent start with dummy info, root have no real parent;
            for (int n : nums) {
                info c(n); // child;
                while (!p->isparent(c) && !q.empty()) {
                    sum += p->leaf ? p->v : 0;
                    p = &q.front();
                    q.pop();
                }
                p->leaf = false;
                c.v += p->v;
                q.push(c);
            }
            while (!q.empty()) {
                sum += q.front().v;
                q.pop();
            }
            return sum;
        }
    private:
        struct info {
            int i, j, v;
            bool leaf;
            info(int n) : i(n / 100 - 1), j((n % 100) / 10 - 1), v(n % 10), leaf(true) {};
            bool isparent(info other) { return i == other.i - 1 && j == other.j / 2;};
        };
    };
    

    Solution Java

    class Solution {
        public int pathSum(int[] nums) {
            int[][] m = new int[5][8];
            for (int n : nums) {
                int i = n / 100; // i is 1 based index;
                int j = (n % 100) / 10 - 1; // j used 0 based index;
                int v = n % 10;
                m[i][j] = m[i - 1][j / 2] + v;
            }
    
            int sum = 0;
            for (int i = 1; i < 5; i++) {
                for (int j = 0; j < 8; j++) {
                    if (i == 4 || m[i][j] != 0 && m[i + 1][j * 2] == 0 && m[i + 1][j * 2 + 1] == 0){
                        sum += m[i][j];
                    }
                }
            }
            return sum;        
        }
    }
    

  • 0

    The implementation of using an array is very impressive!


  • 0
    G

    awesome solution :)


  • 2

    C++ different approach !

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            int n = nums.size();
            vector<int> temp(16, -1); //As the max depth of tree is 5 the total nodes will be 2^(depth)-1;
            
            for (int i=0;i<n;i++){
                string arr = to_string(nums[i]);
                int depth = arr[0]-'0';
                int level = arr[1]-'0';
                int value = arr[2]-'0';
                int idx = (1<<(depth-1)) + level - 1; //calculate the index of the node in temp array
                temp[idx] = value;
            }
            
            int res=0;
            for (int i=temp.size()-1;i>0;i--){
                //If the node is a leaf i.e. (i>7 || temp[2*i]==-1 && temp[2*i+1]==-1) then sum the path from leaf till the root
                if (temp[i] != -1 && (i>7 || (temp[2*i]==-1 && temp[2*i+1]==-1))){
                    int j=i;
                    while (j>0){
                        res += temp[j];
                        j = j/2;
                    }   
                }
            }
            return res;
        }
    };
    

  • 0

    Nice solution. I tried to do it using BFS at first but ended up resorting to DFS.


  • 0
    F

    Smart !!!!!!!!


Log in to reply
 

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