Skip to content

Commit 35c3917

Browse files
halfrosthalfrost
committed
Add solution 1656、1657
1 parent 91e1a92 commit 35c3917

10 files changed

Lines changed: 542 additions & 162 deletions

leetcode/5601/5601. Design an Ordered Stream.go renamed to leetcode/1656.Design-an-Ordered-Stream/1656. Design an Ordered Stream.go

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,5 @@
11
package leetcode
22

3-
import (
4-
"fmt"
5-
)
6-
73
type OrderedStream struct {
84
ptr int
95
stream []string
@@ -17,7 +13,6 @@ func Constructor(n int) OrderedStream {
1713
func (this *OrderedStream) Insert(id int, value string) []string {
1814
this.stream[id] = value
1915
res := []string{}
20-
fmt.Printf("%v %v %v\n", this.ptr, id, value)
2116
if this.ptr == id || this.stream[this.ptr] != "" {
2217
res = append(res, this.stream[this.ptr])
2318
for i := id + 1; i < len(this.stream); i++ {

leetcode/5601/5601. Design an Ordered Stream_test.go renamed to leetcode/1656.Design-an-Ordered-Stream/1656. Design an Ordered Stream_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ import (
55
"testing"
66
)
77

8-
func Test_Problem707(t *testing.T) {
8+
func Test_Problem1656(t *testing.T) {
99
obj := Constructor(5)
1010
fmt.Printf("obj = %v\n", obj)
1111
param1 := obj.Insert(3, "ccccc")

‎leetcode/1656.Design-an-Ordered-Stream/README.md‎

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
# [1656. Design an Ordered Stream](https://leetcode.com/problems/design-an-ordered-stream/)
2+
3+
## 题目
4+
5+
There is a stream of `n` `(id, value)` pairs arriving in an **arbitrary** order, where `id` is an integer between `1` and `n` and `value` is a string. No two pairs have the same `id`.
6+
7+
Design a stream that returns the values in **increasing order of their IDs** by returning a **chunk** (list) of values after each insertion. The concatenation of all the **chunks** should result in a list of the sorted values.
8+
9+
Implement the `OrderedStream` class:
10+
11+
- `OrderedStream(int n)` Constructs the stream to take `n` values.
12+
- `String[] insert(int id, String value)` Inserts the pair `(id, value)` into the stream, then returns the **largest possible chunk** of currently inserted values that appear next in the order.
13+
14+
**Example:**
15+
16+
![https://assets.leetcode.com/uploads/2020/11/10/q1.gif](https://assets.leetcode.com/uploads/2020/11/10/q1.gif)
17+
18+
```
19+
Input
20+
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
21+
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
22+
Output
23+
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
24+
25+
Explanation
26+
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
27+
OrderedStream os = new OrderedStream(5);
28+
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
29+
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
30+
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
31+
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
32+
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
33+
// Concatentating all the chunks returned:
34+
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
35+
// The resulting order is the same as the order above.
36+
37+
```
38+
39+
**Constraints:**
40+
41+
- `1 <= n <= 1000`
42+
- `1 <= id <= n`
43+
- `value.length == 5`
44+
- `value` consists only of lowercase letters.
45+
- Each call to `insert` will have a unique `id.`
46+
- Exactly `n` calls will be made to `insert`.
47+
48+
## 题目大意
49+
50+
有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
51+
52+
设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。
53+
54+
实现 OrderedStream 类：
55+
56+
- OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
57+
- String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
58+
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
59+
否则，返回一个空列表。
60+
61+
## 解题思路
62+
63+
- 设计一个具有插入操作的 Ordered Stream。insert 操作先在指定位置插入 value，然后返回当前指针 ptr 到最近一个空位置的最长连续递增字符串。如果字符串不为空，ptr 移动到非空 value 的后一个下标位置处。
64+
- 简单题。按照题目描述模拟即可。注意控制好 ptr 的位置。
65+
66+
## 代码
67+
68+
```go
69+
package leetcode
70+
71+
type OrderedStream struct {
72+
ptr int
73+
stream []string
74+
}
75+
76+
func Constructor(n int) OrderedStream {
77+
ptr, stream := 1, make([]string, n+1)
78+
return OrderedStream{ptr: ptr, stream: stream}
79+
}
80+
81+
func (this *OrderedStream) Insert(id int, value string) []string {
82+
this.stream[id] = value
83+
res := []string{}
84+
if this.ptr == id || this.stream[this.ptr] != "" {
85+
res = append(res, this.stream[this.ptr])
86+
for i := id + 1; i < len(this.stream); i++ {
87+
if this.stream[i] != "" {
88+
res = append(res, this.stream[i])
89+
} else {
90+
this.ptr = i
91+
return res
92+
}
93+
}
94+
}
95+
if len(res) > 0 {
96+
return res
97+
}
98+
return []string{}
99+
}
100+
101+
/**
102+
* Your OrderedStream object will be instantiated and called as such:
103+
* obj := Constructor(n);
104+
* param_1 := obj.Insert(id,value);
105+
*/
106+
```

‎leetcode/1657.Determine-if-Two-Strings-Are-Close/1657. Determine if Two Strings Are Close.go‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package leetcode
2+
3+
import (
4+
"sort"
5+
)
6+
7+
func closeStrings(word1 string, word2 string) bool {
8+
if len(word1) != len(word2) {
9+
return false
10+
}
11+
freqCount1, freqCount2 := make([]int, 26), make([]int, 26)
12+
for _, c := range word1 {
13+
freqCount1[c-97]++
14+
}
15+
for _, c := range word2 {
16+
freqCount2[c-97]++
17+
}
18+
for i := 0; i < 26; i++ {
19+
if (freqCount1[i] == freqCount2[i]) ||
20+
(freqCount1[i] > 0 && freqCount2[i] > 0) {
21+
continue
22+
}
23+
return false
24+
}
25+
sort.Ints(freqCount1)
26+
sort.Ints(freqCount2)
27+
for i := 0; i < 26; i++ {
28+
if freqCount1[i] != freqCount2[i] {
29+
return false
30+
}
31+
}
32+
return true
33+
}

‎leetcode/1657.Determine-if-Two-Strings-Are-Close/1657. Determine if Two Strings Are Close_test.go‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1657 struct {
9+
para1657
10+
ans1657
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1657 struct {
16+
word1 string
17+
word2 string
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1657 struct {
23+
one bool
24+
}
25+
26+
func Test_Problem1657(t *testing.T) {
27+
28+
qs := []question1657{
29+
30+
{
31+
para1657{"abc", "bca"},
32+
ans1657{true},
33+
},
34+
35+
{
36+
para1657{"a", "aa"},
37+
ans1657{false},
38+
},
39+
40+
{
41+
para1657{"cabbba", "abbccc"},
42+
ans1657{true},
43+
},
44+
45+
{
46+
para1657{"cabbba", "aabbss"},
47+
ans1657{false},
48+
},
49+
50+
{
51+
para1657{"uau", "ssx"},
52+
ans1657{false},
53+
},
54+
55+
{
56+
para1657{"uuukuuuukkuusuususuuuukuskuusuuusuusuuuuuuk", "kssskkskkskssskksskskksssssksskksskskksksuu"},
57+
ans1657{false},
58+
},
59+
}
60+
61+
fmt.Printf("------------------------Leetcode Problem 1657------------------------\n")
62+
63+
for _, q := range qs {
64+
_, p := q.ans1657, q.para1657
65+
fmt.Printf("【input】:%v 【output】:%v \n", p, closeStrings(p.word1, p.word2))
66+
}
67+
fmt.Printf("\n\n\n")
68+
}

‎leetcode/1657.Determine-if-Two-Strings-Are-Close/README.md‎

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
# [1657. Determine if Two Strings Are Close](https://leetcode.com/problems/determine-if-two-strings-are-close/)
2+
3+
4+
## 题目
5+
6+
Two strings are considered **close** if you can attain one from the other using the following operations:
7+
8+
- Operation 1: Swap any two **existing** characters.
9+
- For example, `abcde -> aecdb`
10+
- Operation 2: Transform **every** occurrence of one **existing** character into another **existing** character, and do the same with the other character.
11+
- For example, `aacabb -> bbcbaa` (all `a`'s turn into `b`'s, and all `b`'s turn into `a`'s)
12+
13+
You can use the operations on either string as many times as necessary.
14+
15+
Given two strings, `word1` and `word2`, return `true` *if* `word1` *and* `word2` *are **close**, and* `false` *otherwise.*
16+
17+
**Example 1:**
18+
19+
```
20+
Input: word1 = "abc", word2 = "bca"
21+
Output: true
22+
Explanation: You can attain word2 from word1 in 2 operations.
23+
Apply Operation 1: "abc" -> "acb"
24+
Apply Operation 1: "acb" -> "bca"
25+
26+
```
27+
28+
**Example 2:**
29+
30+
```
31+
Input: word1 = "a", word2 = "aa"
32+
Output: false
33+
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.
34+
35+
```
36+
37+
**Example 3:**
38+
39+
```
40+
Input: word1 = "cabbba", word2 = "abbccc"
41+
Output: true
42+
Explanation: You can attain word2 from word1 in 3 operations.
43+
Apply Operation 1: "cabbba" -> "caabbb"
44+
Apply Operation 2: "caabbb" -> "baaccc"
45+
Apply Operation 2: "baaccc" -> "abbccc"
46+
47+
```
48+
49+
**Example 4:**
50+
51+
```
52+
Input: word1 = "cabbba", word2 = "aabbss"
53+
Output: false
54+
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.
55+
56+
```
57+
58+
**Constraints:**
59+
60+
- `1 <= word1.length, word2.length <= 105`
61+
- `word1` and `word2` contain only lowercase English letters.
62+
63+
## 题目大意
64+
65+
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
66+
67+
- 操作 1：交换任意两个 现有 字符。例如，abcde -> aecdb
68+
- 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
69+
70+
你可以根据需要对任意一个字符串多次使用这两种操作。给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
71+
72+
## 解题思路
73+
74+
- 判断 2 个字符串是否“接近”。“接近”的定义是能否通过交换 2 个字符或者 2 个字母互换，从一个字符串变换成另外一个字符串，如果存在这样的变换，即是“接近”。
75+
- 先统计 2 个字符串的 26 个字母的频次，如果频次有不相同的，直接返回 false。在频次相同的情况下，再从小到大排序，再次扫描判断频次是否相同。
76+
- 注意几种特殊情况：频次相同，再判断字母交换是否合法存在，如果字母不存在，输出 false。例如测试文件中的 case 5 。出现频次个数相同，但是频次不同。例如测试文件中的 case 6 。
77+
78+
## 代码
79+
80+
```go
81+
package leetcode
82+
83+
import (
84+
"sort"
85+
)
86+
87+
func closeStrings(word1 string, word2 string) bool {
88+
if len(word1) != len(word2) {
89+
return false
90+
}
91+
freqCount1, freqCount2 := make([]int, 26), make([]int, 26)
92+
for _, c := range word1 {
93+
freqCount1[c-97]++
94+
}
95+
for _, c := range word2 {
96+
freqCount2[c-97]++
97+
}
98+
for i := 0; i < 26; i++ {
99+
if (freqCount1[i] == freqCount2[i]) ||
100+
(freqCount1[i] > 0 && freqCount2[i] > 0) {
101+
continue
102+
}
103+
return false
104+
}
105+
sort.Ints(freqCount1)
106+
sort.Ints(freqCount2)
107+
for i := 0; i < 26; i++ {
108+
if freqCount1[i] != freqCount2[i] {
109+
return false
110+
}
111+
}
112+
return true
113+
}
114+
```

0 commit comments

Comments
 (0)