Skip to content

Commit 2189396

Browse files
halfrosthalfrost
committed
Add solution 0677
1 parent 4268f58 commit 2189396

25 files changed

+791
-539
lines changed

‎README.md

Lines changed: 333 additions & 333 deletions
Large diffs are not rendered by default.

‎leetcode/0677.Map-Sum-Pairs/677. Map Sum Pairs.go

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package leetcode
2+
3+
type MapSum struct {
4+
keys map[string]int
5+
}
6+
7+
/** Initialize your data structure here. */
8+
func Constructor() MapSum {
9+
return MapSum{make(map[string]int)}
10+
}
11+
12+
func (this *MapSum) Insert(key string, val int) {
13+
this.keys[key] = val
14+
}
15+
16+
func (this *MapSum) Sum(prefix string) int {
17+
prefixAsRunes, res := []rune(prefix), 0
18+
for key, val := range this.keys {
19+
if len(key) >= len(prefix) {
20+
shouldSum := true
21+
for i, char := range key {
22+
if i >= len(prefixAsRunes) {
23+
break
24+
}
25+
if prefixAsRunes[i] != char {
26+
shouldSum = false
27+
break
28+
}
29+
}
30+
if shouldSum {
31+
res += val
32+
}
33+
}
34+
}
35+
return res
36+
}
37+
38+
/**
39+
* Your MapSum object will be instantiated and called as such:
40+
* obj := Constructor();
41+
* obj.Insert(key,val);
42+
* param_2 := obj.Sum(prefix);
43+
*/

‎leetcode/0677.Map-Sum-Pairs/677. Map Sum Pairs_test.go

Whitespace-only changes.

‎leetcode/0677.Map-Sum-Pairs/README.md

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
# [677. Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/)
2+
3+
4+
## 题目
5+
6+
Design a map that allows you to do the following:
7+
8+
- Maps a string key to a given value.
9+
- Returns the sum of the values that have a key with a prefix equal to a given string.
10+
11+
Implement the `MapSum` class:
12+
13+
- `MapSum()` Initializes the `MapSum` object.
14+
- `void insert(String key, int val)` Inserts the `key-val` pair into the map. If the `key` already existed, the original `key-value` pair will be overridden to the new one.
15+
- `int sum(string prefix)` Returns the sum of all the pairs' value whose `key` starts with the `prefix`.
16+
17+
**Example 1:**
18+
19+
```
20+
Input
21+
["MapSum", "insert", "sum", "insert", "sum"]
22+
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
23+
Output
24+
[null, null, 3, null, 5]
25+
26+
Explanation
27+
MapSum mapSum = new MapSum();
28+
mapSum.insert("apple", 3);
29+
mapSum.sum("ap"); // return 3 (apple = 3)
30+
mapSum.insert("app", 2);
31+
mapSum.sum("ap"); // return 5 (apple +app = 3 + 2 = 5)
32+
33+
```
34+
35+
**Constraints:**
36+
37+
- `1 <= key.length, prefix.length <= 50`
38+
- `key` and `prefix` consist of only lowercase English letters.
39+
- `1 <= val <= 1000`
40+
- At most `50` calls will be made to `insert` and `sum`.
41+
42+
## 题目大意
43+
44+
实现一个 MapSum 类，支持两个方法，insert 和 sum：
45+
46+
- MapSum() 初始化 MapSum 对象
47+
- void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
48+
- int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
49+
50+
## 解题思路
51+
52+
- 简单题。用一个 map 存储数据，Insert() 方法即存储 key-value。Sum() 方法即累加满足条件前缀对应的 value。判断是否满足条件，先根据前缀长度来判断，只有长度大于等于 prefix 长度才可能满足要求。如果 key 是具有 prefix 前缀的，那么累加上这个值。最后输出总和即可。
53+
54+
## 代码
55+
56+
```go
57+
package leetcode
58+
59+
type MapSum struct {
60+
keys map[string]int
61+
}
62+
63+
/** Initialize your data structure here. */
64+
func Constructor() MapSum {
65+
return MapSum{make(map[string]int)}
66+
}
67+
68+
func (this *MapSum) Insert(key string, val int) {
69+
this.keys[key] = val
70+
}
71+
72+
func (this *MapSum) Sum(prefix string) int {
73+
prefixAsRunes, res := []rune(prefix), 0
74+
for key, val := range this.keys {
75+
if len(key) >= len(prefix) {
76+
shouldSum := true
77+
for i, char := range key {
78+
if i >= len(prefixAsRunes) {
79+
break
80+
}
81+
if prefixAsRunes[i] != char {
82+
shouldSum = false
83+
break
84+
}
85+
}
86+
if shouldSum {
87+
res += val
88+
}
89+
}
90+
}
91+
return res
92+
}
93+
94+
/**
95+
* Your MapSum object will be instantiated and called as such:
96+
* obj := Constructor();
97+
* obj.Insert(key,val);
98+
* param_2 := obj.Sum(prefix);
99+
*/
100+
```

‎website/content/ChapterFour/0600~0699/0676.Implement-Magic-Dictionary.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -90,5 +90,5 @@ func (this *MagicDictionary) Search(word string) bool {
9090
----------------------------------------------
9191
<div style="display: flex;justify-content: space-between;align-items: center;">
9292
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0674.Longest-Continuous-Increasing-Subsequence/">⬅️上一页</a></p>
93-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0682.Baseball-Game/">下一页➡️</a></p>
93+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0677.Map-Sum-Pairs/">下一页➡️</a></p>
9494
</div>

‎website/content/ChapterFour/0600~0699/0677.Map-Sum-Pairs.md

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
# [677. Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/)
2+
3+
4+
## 题目
5+
6+
Design a map that allows you to do the following:
7+
8+
- Maps a string key to a given value.
9+
- Returns the sum of the values that have a key with a prefix equal to a given string.
10+
11+
Implement the `MapSum` class:
12+
13+
- `MapSum()` Initializes the `MapSum` object.
14+
- `void insert(String key, int val)` Inserts the `key-val` pair into the map. If the `key` already existed, the original `key-value` pair will be overridden to the new one.
15+
- `int sum(string prefix)` Returns the sum of all the pairs' value whose `key` starts with the `prefix`.
16+
17+
**Example 1:**
18+
19+
```
20+
Input
21+
["MapSum", "insert", "sum", "insert", "sum"]
22+
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
23+
Output
24+
[null, null, 3, null, 5]
25+
26+
Explanation
27+
MapSum mapSum = new MapSum();
28+
mapSum.insert("apple", 3);
29+
mapSum.sum("ap"); // return 3 (apple = 3)
30+
mapSum.insert("app", 2);
31+
mapSum.sum("ap"); // return 5 (apple +app = 3 + 2 = 5)
32+
33+
```
34+
35+
**Constraints:**
36+
37+
- `1 <= key.length, prefix.length <= 50`
38+
- `key` and `prefix` consist of only lowercase English letters.
39+
- `1 <= val <= 1000`
40+
- At most `50` calls will be made to `insert` and `sum`.
41+
42+
## 题目大意
43+
44+
实现一个 MapSum 类，支持两个方法，insert 和 sum：
45+
46+
- MapSum() 初始化 MapSum 对象
47+
- void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
48+
- int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
49+
50+
## 解题思路
51+
52+
- 简单题。用一个 map 存储数据，Insert() 方法即存储 key-value。Sum() 方法即累加满足条件前缀对应的 value。判断是否满足条件，先根据前缀长度来判断，只有长度大于等于 prefix 长度才可能满足要求。如果 key 是具有 prefix 前缀的，那么累加上这个值。最后输出总和即可。
53+
54+
## 代码
55+
56+
```go
57+
package leetcode
58+
59+
type MapSum struct {
60+
keys map[string]int
61+
}
62+
63+
/** Initialize your data structure here. */
64+
func Constructor() MapSum {
65+
return MapSum{make(map[string]int)}
66+
}
67+
68+
func (this *MapSum) Insert(key string, val int) {
69+
this.keys[key] = val
70+
}
71+
72+
func (this *MapSum) Sum(prefix string) int {
73+
prefixAsRunes, res := []rune(prefix), 0
74+
for key, val := range this.keys {
75+
if len(key) >= len(prefix) {
76+
shouldSum := true
77+
for i, char := range key {
78+
if i >= len(prefixAsRunes) {
79+
break
80+
}
81+
if prefixAsRunes[i] != char {
82+
shouldSum = false
83+
break
84+
}
85+
}
86+
if shouldSum {
87+
res += val
88+
}
89+
}
90+
}
91+
return res
92+
}
93+
94+
/**
95+
* Your MapSum object will be instantiated and called as such:
96+
* obj := Constructor();
97+
* obj.Insert(key,val);
98+
* param_2 := obj.Sum(prefix);
99+
*/
100+
```
101+
102+
103+
----------------------------------------------
104+
<div style="display: flex;justify-content: space-between;align-items: center;">
105+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0676.Implement-Magic-Dictionary/">⬅️上一页</a></p>
106+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0682.Baseball-Game/">下一页➡️</a></p>
107+
</div>

‎website/content/ChapterFour/0600~0699/0682.Baseball-Game.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -108,6 +108,6 @@ func calPoints(ops []string) int {
108108

109109
----------------------------------------------
110110
<div style="display: flex;justify-content: space-between;align-items: center;">
111-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0676.Implement-Magic-Dictionary/">⬅️上一页</a></p>
111+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0677.Map-Sum-Pairs/">⬅️上一页</a></p>
112112
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0600~0699/0684.Redundant-Connection/">下一页➡️</a></p>
113113
</div>

0 commit comments

Comments
 (0)