Java, implement the logic in Cell class, easy to understand


  • 6

    O(1) set() operation, only do the traverse in get()/sum() operation, 103ms.
    Good for set() heavy system.

    public class Excel {
        Cell[][] table;
    
        public Excel(int H, char W) {
            table = new Cell[H+1][W-'A'+1];
        }
        
        public void set(int r, char c, int v) {
            if(table[r][c-'A'] == null) table[r][c-'A'] = new Cell (v); 
            else table[r][c-'A'].setValue(v); 
        }
        
        public int get(int r, char c) {
            if( table[r][c-'A'] == null) return 0;
            else return table[r][c-'A'].getValue();  
        }
        
        public int sum(int r, char c, String[] strs) {
            if (table[r][c-'A'] == null) {
                table[r][c-'A'] = new Cell(strs);
            } else {
                table[r][c-'A'].setFormula(strs);
            }
            
            return table[r][c-'A'].getValue();
        }
        
        
        private class Cell{
            int val=0;
            HashMap<Cell, Integer> formula=new HashMap<>();//one cell might appear multiple times
            
            public Cell(int val){
                setValue(val); 
            }
            public Cell(String[] formulaStr){
                setFormula(formulaStr);
            }
            
            public void setValue(int val) {           
                formula.clear(); //will not be treated as a formula cell anymore        
                this.val = val;
            }
            
            public void setFormula(String[] formulaStr){
                formula.clear();            
                for(String str : formulaStr){
                    if (str.indexOf(":")<0){
                        int[] pos = getPos(str);
                        addFormulaCell(pos[0], pos[1]);
                    } else {
                        String[] pos = str.split(":");
                        int[] startPos = getPos(pos[0]);
                        int[] endPos = getPos(pos[1]);
                        for(int r = startPos[0]; r<=endPos[0]; r++){
                            for(int c = startPos[1]; c<=endPos[1]; c++){
                                addFormulaCell(r, c);
                            }
                        }
                    }
                }
            }
            
            private int[] getPos(String str){
                int[] pos = new int[2];
                pos[1]=str.charAt(0)-'A';
                pos[0]=Integer.parseInt(str.substring(1));
                return pos;
            }
            
            private void addFormulaCell(int r, int c){
                if(table[r][c] == null) table[r][c] = new Cell(0);
                Cell rangeCell = table[r][c];                            
                formula.put(rangeCell, (formula.containsKey(rangeCell)? formula.get(rangeCell) : 0)+1);
            }
            
            //recursive method
            private int getValue(){
                if(this.formula.isEmpty()) return this.val;
                int sum = 0;
                for(Cell cell : formula.keySet()){
                    sum+=cell.getValue()*formula.get(cell);
                }
                return sum;
            }
        }
    }
    

  • 2

    All cells' values are always up to date after each operation, O(1) get() operation, 110ms.

    Good for get()/sum() heavy system:

    public class Excel {
        Cell[][] table;
    
        public Excel(int H, char W) {
            table = new Cell[H+1][W-'A'+1];
        }
        
        public void set(int r, char c, int v) {
            if(table[r][c-'A'] == null) table[r][c-'A'] = new Cell (v); 
            else table[r][c-'A'].setValue(v); 
        }
        
        public int get(int r, char c) {
            if( table[r][c-'A'] == null) return 0;
            else return table[r][c-'A'].val;       
        }
        
        public int sum(int r, char c, String[] strs) {
            if (table[r][c-'A'] == null) table[r][c-'A'] = new Cell(strs);
            else {
                table[r][c-'A'].setFormula(strs);
            }
            return table[r][c-'A'].val;
        }
        
        
        private class Cell{
            int val=0;
            HashMap<Cell, Integer> formula=new HashMap<>();
            HashSet<Cell> dependentCells=new HashSet<>();
            
            public Cell(int val){
                setValue(val); 
            }
            public Cell(String[] formulaStr){
                setFormula(formulaStr);
            }
            
            public void setValue(int val) {           
                removeFormulaCells();
                formula.clear();
                updateDependentCells(val);            
                this.val = val;
            }
            
            public void setFormula(String[] formulaStr){
                removeFormulaCells();
                formula.clear();            
                int newVal = 0;
                for(String str : formulaStr){
                    if (str.indexOf(":")<0){
                        int[] pos = getPos(str);
                        newVal += addFormulaCell(pos[0], pos[1]);  
                    } else {
                        String[] pos = str.split(":");
                        int[] startPos = getPos(pos[0]);
                        int[] endPos = getPos(pos[1]);
                        for(int r = startPos[0]; r<=endPos[0]; r++){
                            for(int c = startPos[1]; c<=endPos[1]; c++){
                                newVal += addFormulaCell(r, c);
                            }
                        }
                    }
                }
                updateDependentCells(newVal);
                this.val=newVal;
            }
            
            private int[] getPos(String str){
                int[] pos = new int[2];
                pos[1]=str.charAt(0)-'A';
                pos[0]=Integer.parseInt(str.substring(1));
                return pos;
            }
            
            private int addFormulaCell(int r, int c){
                if(table[r][c] == null) table[r][c] = new Cell(0);
                Cell rangeCell = table[r][c];                            
                formula.put(rangeCell, (formula.containsKey(rangeCell)? formula.get(rangeCell) : 0)+1);
                rangeCell.dependentCells.add(this);
                return rangeCell.val;
            }
            
            private void removeFormulaCells(){
                if (!this.formula.isEmpty()) {
                    for(Cell rangeCell : this.formula.keySet()){
                        rangeCell.dependentCells.remove(this);
                    }
                }    
            }
            //recursive method
            private void updateDependentCells(int newVal){
                int delta = newVal-this.val;
                for(Cell cell : dependentCells){
                    int cellNewVal =  cell.val + delta*cell.formula.get(this);
                    cell.updateDependentCells(cellNewVal);
                }
                this.val = newVal;
            }
        }
    }
    

  • 1
    M

    So clean and easy to understand. Also very object-oriented. Amazing part is to give 2 different solutions on different situations. I strongly recommend everyone read this thread.


  • 0
    A

    Great solution. I was about to post mine and found that this one closely resembles my solution.


Log in to reply
 

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