← Static tasks

631. Design Excel Sum Formula

leetcode hard

#array#csharp#design#hard#hash-table#leetcode#matrix#string#tree

Task

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input

["Excel", "set", "sum", "set", "get"]

[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]

Output

[null, null, 4, null, 6]

C# solution

matched/original
using System;
using System.Collections.Generic;
public class Excel {
    private int[,] mat;
    private Dictionary<string, List<string>> formulas;
    public Excel(int height, char width) {
        mat = new int[height, width - 'A' + 1];
        formulas = new Dictionary<string, List<string>>();
    }
    public void Set(int row, char column, int val) {
        mat[row - 1, column - 'A'] = val;
        formulas.Remove(row + "," + column);
    }
    public int Get(int row, char column) {
        string key = row + "," + column;
        if (formulas.ContainsKey(key)) {
            return EvaluateFormula(key);
        }
        return mat[row - 1, column - 'A'];
    }
    public int Sum(int row, char column, IList<string> numbers) {
        string key = row + "," + column;
        formulas[key] = new List<string>(numbers);
        return EvaluateFormula(key);
    }
    private int EvaluateFormula(string key) {
        List<string> numbers = formulas[key];
        int total = 0;
        foreach (string number in numbers) {
            if (number.Contains(":")) {
                string[] parts = number.Split(new char[] { ':' });
                int startRow = int.Parse(parts[0].Substring(1));
                char startCol = parts[0][0];
                int endRow = int.Parse(parts[1].Substring(1));
                char endCol = parts[1][0];
                for (int r = startRow; r <= endRow; r++) {
                    for (char c = startCol; c <= endCol; c++) {
                        total += Get(r, c);
                    }
                }
            } else {
                int r = int.Parse(number.Substring(1));
                char c = number[0];
                total += Get(r, c);
            }
        }
        return total;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class Excel {
    private int[,] mat;
    private unordered_map<string, List<string>> formulas;
    public Excel(int height, char width) {
        mat = new int[height, width - 'A' + 1];
        formulas = new unordered_map<string, List<string>>();
    }
    public void Set(int row, char column, int val) {
        mat[row - 1, column - 'A'] = val;
        formulas.Remove(row + "," + column);
    }
    public int Get(int row, char column) {
        string key = row + "," + column;
        if (formulas.count(key)) {
            return EvaluateFormula(key);
        }
        return mat[row - 1, column - 'A'];
    }
    public int Sum(int row, char column, vector<string> numbers) {
        string key = row + "," + column;
        formulas[key] = new List<string>(numbers);
        return EvaluateFormula(key);
    }
    private int EvaluateFormula(string key) {
        List<string> numbers = formulas[key];
        int total = 0;
        foreach (string number in numbers) {
            if (number.Contains(":")) {
                vector<string> parts = number.Split(new char[] { ':' });
                int startRow = int.Parse(parts[0].Substring(1));
                char startCol = parts[0][0];
                int endRow = int.Parse(parts[1].Substring(1));
                char endCol = parts[1][0];
                for (int r = startRow; r <= endRow; r++) {
                    for (char c = startCol; c <= endCol; c++) {
                        total += Get(r, c);
                    }
                }
            } else {
                int r = int.Parse(number.Substring(1));
                char c = number[0];
                total += Get(r, c);
            }
        }
        return total;
    }
}

Java solution

matched/original
import java.util.*;

public class Excel {
    private int[][] mat;
    private Map<String, List<String>> formulas;

    public Excel(int height, char width) {
        mat = new int[height][width - 'A' + 1];
        formulas = new HashMap<>();
    }

    public void set(int row, char column, int val) {
        mat[row - 1][column - 'A'] = val;
        formulas.remove(row + "," + column);
    }

    public int get(int row, char column) {
        String key = row + "," + column;
        if (formulas.containsKey(key)) {
            return evaluateFormula(key);
        }
        return mat[row - 1][column - 'A'];
    }

    public int sum(int row, char column, List<String> numbers) {
        String key = row + "," + column;
        formulas.put(key, numbers);
        return evaluateFormula(key);
    }

    private int evaluateFormula(String key) {
        List<String> numbers = formulas.get(key);
        int total = 0;
        for (String number : numbers) {
            if (number.contains(":")) {
                String[] parts = number.split(":");
                int startRow = Integer.parseInt(parts[0].substring(1));
                char startCol = parts[0].charAt(0);
                int endRow = Integer.parseInt(parts[1].substring(1));
                char endCol = parts[1].charAt(0);
                for (int r = startRow; r <= endRow; r++) {
                    for (char c = startCol; c <= endCol; c++) {
                        total += get(r, c);
                    }
                }
            } else {
                int r = Integer.parseInt(number.substring(1));
                char c = number.charAt(0);
                total += get(r, c);
            }
        }
        return total;
    }
}

JavaScript solution

matched/original
class Excel {
    constructor(height, width) {
        this.mat = Array.from({ length: height }, () => Array(width.charCodeAt(0) - 'A'.charCodeAt(0) + 1).fill(0));
        this.formulas = new Map();
    }

    set(row, column, val) {
        this.mat[row - 1][column.charCodeAt(0) - 'A'.charCodeAt(0)] = val;
        this.formulas.delete(`${row},${column}`);
    }

    get(row, column) {
        const key = `${row},${column}`;
        if (this.formulas.has(key)) {
            return this._evaluateFormula(key);
        }
        return this.mat[row - 1][column.charCodeAt(0) - 'A'.charCodeAt(0)];
    }

    sum(row, column, numbers) {
        const key = `${row},${column}`;
        this.formulas.set(key, numbers);
        return this._evaluateFormula(key);
    }

    _evaluateFormula(key) {
        const numbers = this.formulas.get(key);
        let total = 0;
        for (const number of numbers) {
            if (number.includes(":")) {
                const [start, end] = number.split(":");
                const startRow = parseInt(start.slice(1));
                const startCol = start.charCodeAt(0);
                const endRow = parseInt(end.slice(1));
                const endCol = end.charCodeAt(0);
                for (let r = startRow; r <= endRow; r++) {
                    for (let c = startCol; c <= endCol; c++) {
                        total += this.get(r, String.fromCharCode(c));
                    }
                }
            } else {
                const r = parseInt(number.slice(1));
                const c = number.charAt(0);
                total += this.get(r, c);
            }
        }
        return total;
    }
}

Python solution

matched/original
class Excel:

    def __init__(self, height: int, width: str):
        self.mat = [[0] * (ord(width) - ord('A') + 1) for _ in range(height)]
        self.formulas = {}

    def set(self, row: int, column: str, val: int) -> None:
        self.mat[row - 1][ord(column) - ord('A')] = val
        self.formulas.pop((row, column), None)

    def get(self, row: int, column: str) -> int:
        if (row, column) in self.formulas:
            return self._evaluate_formula(row, column)
        return self.mat[row - 1][ord(column) - ord('A')]

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        self.formulas[(row, column)] = numbers
        return self._evaluate_formula(row, column)

    def _evaluate_formula(self, row: int, column: str) -> int:
        total = 0
        for number in self.formulas[(row, column)]:
            if ':' in number:
                start, end = number.split(':')
                start_row, start_col = int(start[1:]), start[0]
                end_row, end_col = int(end[1:]), end[0]
                for r in range(start_row, end_row + 1):
                    for c in range(ord(start_col), ord(end_col) + 1):
                        total += self.get(r, chr(c))
            else:
                r, c = int(number[1:]), number[0]
                total += self.get(r, c)
        return total

Go solution

matched/original
package main

import (
    "fmt"
    "strconv"
)

type Excel struct {
    mat      [][]int
    formulas map[string][]string
}

func Constructor(height int, width byte) Excel {
    mat := make([][]int, height)
    for i := range mat {
        mat[i] = make([]int, width-'A'+1)
    }
    return Excel{mat: mat, formulas: make(map[string][]string)}
}

func (this *Excel) Set(row int, column byte, val int) {
    this.mat[row-1][column-'A'] = val
    key := strconv.Itoa(row) + string(column)
    delete(this.formulas, key)
}

func (this *Excel) Get(row int, column byte) int {
    key := strconv.Itoa(row) + string(column)
    if numbers, exists := this.formulas[key]; exists {
        return this.evaluateFormula(numbers)
    }
    return this.mat[row-1][column-'A']
}

func (this *Excel) Sum(row int, column byte, numbers []string) int {
    key := strconv.Itoa(row) + string(column)
    this.formulas[key] = numbers
    return this.evaluateFormula(numbers)
}

func (this *Excel) evaluateFormula(numbers []string) int {
    total := 0
    for _, number := range numbers {
        if idx := strings.Index(number, ":"); idx != -1 {
            start, end := number[:idx], number[idx+1:]
            startRow, _ := strconv.Atoi(start[1:])
            startCol := start[0]
            endRow, _ := strconv.Atoi(end[1:])
            endCol := end[0]
            for r := startRow; r <= endRow; r++ {
                for c := startCol; c <= endCol; c++ {
                    total += this.Get(r, c)
                }
            }
        } else {
            r, _ := strconv.Atoi(number[1:])
            c := number[0]
            total += this.Get(r, c)
        }
    }
    return total
}

func main() {
    obj := Constructor(3, 'C')
    obj.Set(1, 'A', 5)
    fmt.Println(obj.Get(1, 'A')) // 5
    fmt.Println(obj.Sum(1, 'B', []string{"A1", "A1"})) // 10
    obj.Set(1, 'A', 10)
    fmt.Println(obj.Get(1, 'B')) // 10
}

Explanation

Algorithm

Инициализация

Создайте класс Excel, который будет инициализировать матрицу нужного размера и хранить текущие значения ячеек. Реализуйте методы для установки значений, получения значений и вычисления суммы.

Метод установки значений

Реализуйте метод set, который будет изменять значение ячейки в матрице.

Метод вычисления суммы

Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎