题目描述：

LeetCode 631. Design Excel Sum Formula

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:

Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from 'A'.

void Set(int row, char column, int val): Change the value at C(row, column) to be val.

int Get(int row, char column): Return the value at C(row, column).

int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.

numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, "F7" represents the cell at (7, F).

If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Example 1:

Excel(3,"C"); 
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0

Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0

Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4. 
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4

Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:

1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

题目大意：

设计Excel，支持下列操作：

Excel(int H, char W): 初始化一个H行，W列的表格

void Set(int row, char column, int val): 将row行column列的单元格值设置为val

int Get(int row, char column): 获取row行column列的单元格值

int Sum(int row, char column, List of Strings : numbers): 将row行column列单元格设置为numbers的和，并返回和的值

解题思路：

观察者模式（Observer Pattern）

为单元格cell注册观察者列表target（关心cell变化的单元格），被观察者列表source（变化会影响到cell的单元格）

利用字典values存储每个单元格的值

单元格之间的观察者关系为图结构，当某一单元格发生变化时，其所有观察者节点均会依次发生变化

对于某单元格触发的观察者单元格更新操作，可以利用BFS实现

当执行set操作时，清除单元格的被观察者列表，然后更新其观察者列表的值

当执行sum操作时，清除单元格的被观察者列表，然后重新注册其被观察者，并更新其被观察者的观察关系，最后更新其观察者列表的值

Python代码：

class Excel(object):

    def __init__(self, H, W):
        """
        :type H: int
        :type W: str
        """
        self.col = lambda c: ord(c) - ord('A')
        self.H, self.W = H, self.col(W) + 1
        self.values = collections.defaultdict(int)
        self.target = collections.defaultdict(lambda : collections.defaultdict(int))
        self.source = collections.defaultdict(lambda : collections.defaultdict(int))
        self.getIdx = lambda r, c: (r - 1) * self.W + self.col(c)

    def updateTgt(self, idx, delta):
        queue = [idx]
        while queue:
            first = queue.pop(0)
            for tgt in self.target[first]:
                self.values[tgt] += self.target[first][tgt] * delta
                queue.append(tgt)

    def removeSrc(self, idx):
        for src in self.source[idx]:
            del self.target[src][idx]
        del self.source[idx]

    def set(self, r, c, v):
        """
        :type r: int
        :type c: str
        :type v: int
        :rtype: void
        """
        idx = self.getIdx(r, c)
        delta = v - self.values[idx]
        self.values[idx] = v
        self.removeSrc(idx)
        self.updateTgt(idx, delta)

    def get(self, r, c):
        """
        :type r: int
        :type c: str
        :rtype: int
        """
        return self.values[self.getIdx(r, c)]

    def sum(self, r, c, strs):
        """
        :type r: int
        :type c: str
        :type strs: List[str]
        :rtype: int
        """
        idx = self.getIdx(r, c)
        self.removeSrc(idx)
        cval = self.values[idx]
        self.values[idx] = 0
        for src in strs:
            if ':' not in src:
                sc, sr = src[0], int(src[1:])
                sidx = self.getIdx(sr, sc)
                self.target[sidx][idx] += 1
                self.source[idx][sidx] += 1
                self.values[idx] += self.values[sidx]
            else:
                st, ed = src.split(':')
                for r in range(int(st[1:]), int(ed[1:]) + 1):
                    for c in range(self.col(st[0]), self.col(ed[0]) + 1):
                        sidx = (r - 1) * self.W + c
                        self.target[sidx][idx] += 1
                        self.source[idx][sidx] += 1
                        self.values[idx] += self.values[sidx]
        self.updateTgt(idx, self.values[idx] - cval)
        return self.values[idx]

# Your Excel object will be instantiated and called as such:
# obj = Excel(H, W)
# obj.set(r,c,v)
# param_2 = obj.get(r,c)
# param_3 = obj.sum(r,c,strs) 

 

本文链接：http://bookshadow.com/weblog/2017/06/25/leetcode-design-excel-sum-formula/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码