java 126ms solution


  • 1
    T
    public class Excel {
        private HashMap depends = new HashMap();
        
        private int[][] board = null;
        private int H = 0;
        private int W = 0;
    
        public Excel(int H, char W) {
            board = new int[H][W];
            this.H = H;
            this.W = W;
        }
        
        public void set(int r, char c, int v) {
            board[r-1][c-'A'] = v;
            if(depends.get((r-1)*W+(c-'A')) != null)
                depends.remove((r-1)*W+(c-'A'));
        }
        
        public int get(int r, char c) {
            return get(r,c,new HashMap());
            
        }
        
        private int get(int r,char c, HashMap mapping){
            if(mapping.get(r+""+c) == null){
                int key = (r-1)*W+(c-'A');
                if(depends.get(key) == null){
                    mapping.put(r+""+c,board[r-1][c-'A']);
                }else{
                    int result = 0;
                    
                     Iterator<Integer> it = ((ArrayList<Integer>)depends.get(key)).iterator();
                     while(it.hasNext()){
                         int item = (int)it.next();
                        result+=get(item/W+1,(char)('A'+item%W),mapping);
                     }
                    mapping.put(r+""+c,result);
                }
            }
            return (int)(mapping.get(r+""+c));
        }
        
        public int sum(int r, char c, String[] strs) {
            int key = (r-1)*W+(c-'A');
            
                depends.put(key,new ArrayList<Integer>());
            int result = 0;
            HashMap mapping = new HashMap();
            for(String s : strs){
                String[] arr = s.split(":");
                
                if(arr.length == 2){
                    //System.out.println(arr[0]+","+arr[1]);
                    int min = Integer.parseInt(arr[0].substring(1));
                    int max = Integer.parseInt(arr[1].substring(1));
                    //System.out.println(min+","+max);
                    for(int i = min;i<=max;i++){
                        for(char j = arr[0].charAt(0);j<=arr[1].charAt(0);j++){
                            ((ArrayList<Integer>)depends.get(key)).add((i-1)*W+(j-'A'));
                            result+=get(i,j,mapping);
                        }
                    }
                }else{
                    ((ArrayList<Integer>)depends.get(key)).add((s.charAt(1)-'1')*W+(s.charAt(0)-'A'));
                    result+=get(s.charAt(1)-'0',s.charAt(0));
                }
            }
            return result;
        }
    }
    
    /**
     * Your Excel object will be instantiated and called as such:
     * Excel obj = new Excel(H, W);
     * obj.set(r,c,v);
     * int param_2 = obj.get(r,c);
     * int param_3 = obj.sum(r,c,strs);
     */
    

  • 0
    M

    @tangalai
    Thanks for sharing.
    But could you please explain your approach, e.g. the key-value for your map.
    I think the key is how to avoid redundant range-sum calculations, and some update issues.


  • 1
    T

    @mycoy int the mapping, key will be the index of cell (i*cols+j) , value will be a hashset, include all it's depends,

    for example, if A1 = A2+A3,
    A1 = 0;
    A2 = 26;
    A3 = 52;
    the mapping will be {0: [26,52]}


  • 0
    M

    @tangalai
    Thanks.
    Then, what about the get() method, its recursive logic and the HashMap parameter (key, value)?


  • 0
    T

    @mycoy yes, you are right.


  • 0
    M

    @tangalai
    well..., I mean, could you please explain the get(), the recursive logic, and the usage of the Map parameter (what's the map's key, value)


  • 0
    T

    @mycoy OK, the hashmap object in get method is using for remember,

    here is an example

    A1 = A3 + A2
    A9 = A1 + A6;
    A5 = A1 + A8;
    B1 = A9 + A5;

    if I want to get ('B' , 1);

    hashmap is using for save the value already been calculate, such as A1.

    if(mapping.get("A1") == null){
    cal.......
    mapping.put("A1",.......);
    }else{
    return mapping.get("A1")
    }


  • 0
    L
    This post is deleted!

  • 0
    L

    @lugesot said in java 126ms solution:

    Could we consider the 2 senarios below?

    1 Sum(1, "A", ["A1","B1"]);
    2 Sum(1, "A", ["B1","C1"]);
    Sum(1, "B", ["A1"]);
    I think this shoud be illegal and need to defend it.


Log in to reply
 

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