Skip to content

Latest commit

 

History

History
214 lines (159 loc) · 7.08 KB

README.md

File metadata and controls

214 lines (159 loc) · 7.08 KB
Raw
comments difficulty edit_url tags
true
中等
设计
数组
哈希表
字符串

2408. 设计 SQL 🔒

English Version

题目描述

给定 n 个表，用两个数组 names 和 columns 表示，其中 names[i] 是第 i 个表的名称，columns[i] 是第 i 个表的列数。

您能够执行以下 操作:

  • 在特定的表中 插入 一行。插入的每一行都有一个 id。id 是使用自动递增方法分配的，其中第一个插入行的 id 为 1，插入到同一个表中的其他行的 id 为最后一个插入行的id (即使它已被删除) 加1。
  • 从指定表中 删除 一行。注意，删除一行不会影响下一个插入行的 id。
  • 从任何表中 查询 一个特定的单元格并返回其值。

实现 SQL 类:

  • SQL(String[] names, int[] columns) 创造 n 个表。
  • void insertRow(String name, String[] row) 向表 name 中添加一行。保证 表存在，并且数组 row 的大小等于表中的列数。
  • void deleteRow(String name, int rowId) 从表 name 中移除行 rowId 。保证 表和行都 存在。
  • String selectCell(String name, int rowId, int columnId) 返回表 name 中 rowId 行和 columnId 列中的单元格值。

 

示例 1:

输入
["SQL", "insertRow", "selectCell", "insertRow", "deleteRow", "selectCell"]
[[["one", "two", "three"], [2, 3, 1]], ["two", ["first", "second", "third"]], ["two", 1, 3], ["two", ["fourth", "fifth", "sixth"]], ["two", 1], ["two", 2, 2]]
输出
[null, null, "third", null, null, "fifth"]

解释
SQL sql = new SQL(["one", "two", "three"], [2, 3, 1]); // 创建三个表。
sql.insertRow("two", ["first", "second", "third"]); // 向表 "2" 添加一行。id 是 1。
sql.selectCell("two", 1, 3); // 返回 "third"，查找表 "two" 中 id 为 1 的行中第三列的值。
sql.insertRow("two", ["fourth", "fifth", "sixth"]); // 将另一行添加到表 "2" 中。它的 id 是 2。
sql.deleteRow("two", 1); // 删除表 "two" 的第一行。注意，第二行仍然有 id 2。
sql.selectCell("two", 2, 2); // 返回 "fifth"，查找表 "two" 中 id 为 2 的行中第二列的值。

 

提示:

  • n == names.length == columns.length
  • 1 <= n <= 104
  • 1 <= names[i].length, row[i].length, name.length <= 20
  • names[i], row[i], name 由小写英文字母组成。
  • 1 <= columns[i] <= 100
  • 所有的 names 字符串都是 不同 的。
  • name 存在于 names.
  • row.length 等于所选表中的列数。
  • rowId 和 columnId 是有效的值。
  • 最多 250 次调用 insertRow 和 deleteRow 。
  • 最多 104 次调用 selectCell。

解法

方法一：哈希表

创建哈希表 tables 用于存储表名和表数据行的映射。直接模拟题目中的操作即可。

每个操作的时间复杂度均为 $O(1)$，空间复杂度 $O(n)$。

Python3

class SQL:
    def __init__(self, names: List[str], columns: List[int]):
        self.tables = defaultdict(list)

    def insertRow(self, name: str, row: List[str]) -> None:
        self.tables[name].append(row)

    def deleteRow(self, name: str, rowId: int) -> None:
        pass

    def selectCell(self, name: str, rowId: int, columnId: int) -> str:
        return self.tables[name][rowId - 1][columnId - 1]


# Your SQL object will be instantiated and called as such:
# obj = SQL(names, columns)
# obj.insertRow(name,row)
# obj.deleteRow(name,rowId)
# param_3 = obj.selectCell(name,rowId,columnId)

Java

class SQL {
    private Map<String, List<List<String>>> tables;

    public SQL(List<String> names, List<Integer> columns) {
        tables = new HashMap<>(names.size());
    }

    public void insertRow(String name, List<String> row) {
        tables.computeIfAbsent(name, k -> new ArrayList<>()).add(row);
    }

    public void deleteRow(String name, int rowId) {
    }

    public String selectCell(String name, int rowId, int columnId) {
        return tables.get(name).get(rowId - 1).get(columnId - 1);
    }
}

/**
 * Your SQL object will be instantiated and called as such:
 * SQL obj = new SQL(names, columns);
 * obj.insertRow(name,row);
 * obj.deleteRow(name,rowId);
 * String param_3 = obj.selectCell(name,rowId,columnId);
 */

C++

class SQL {
public:
    unordered_map<string, vector<vector<string>>> tables;
    SQL(vector<string>& names, vector<int>& columns) {
    }

    void insertRow(string name, vector<string> row) {
        tables[name].push_back(row);
    }

    void deleteRow(string name, int rowId) {
    }

    string selectCell(string name, int rowId, int columnId) {
        return tables[name][rowId - 1][columnId - 1];
    }
};

/**
 * Your SQL object will be instantiated and called as such:
 * SQL* obj = new SQL(names, columns);
 * obj->insertRow(name,row);
 * obj->deleteRow(name,rowId);
 * string param_3 = obj->selectCell(name,rowId,columnId);
 */

Go

type SQL struct {
	tables map[string][][]string
}

func Constructor(names []string, columns []int) SQL {
	return SQL{map[string][][]string{}}
}

func (this *SQL) InsertRow(name string, row []string) {
	this.tables[name] = append(this.tables[name], row)
}

func (this *SQL) DeleteRow(name string, rowId int) {

}

func (this *SQL) SelectCell(name string, rowId int, columnId int) string {
	return this.tables[name][rowId-1][columnId-1]
}

/**
 * Your SQL object will be instantiated and called as such:
 * obj := Constructor(names, columns);
 * obj.InsertRow(name,row);
 * obj.DeleteRow(name,rowId);
 * param_3 := obj.SelectCell(name,rowId,columnId);
 */