Skip to content

Commit cfaac27

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problems
* No.1424.Diagonal Traverse II * No.1426.Counting Elements * No.1427.Perform String Shifts
1 parent 7a0f951 commit cfaac27

File tree

19 files changed

+650
-68
lines changed

19 files changed

+650
-68
lines changed

‎solution/1400-1499/1424.Diagonal Traverse II/README.md

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,22 +53,103 @@
5353

5454
<!-- 这里可写通用的实现逻辑 -->
5555

56+
**方法一：排序**
57+
58+
我们观察到：
59+
60+
- 每一条对角线上的 $i + j$ 的值都是相同的；
61+
- 下一条对角线的 $i + j$ 的值比前一条对角线的大；
62+
- 在同一条对角线中的 $i + j$ 是相同的，而 $j$ 值是从小到大递增。
63+
64+
因此，我们将所有数字以 $(i + j, j, nums[i][j])$ 的形式存进 $arr$，然后按照前两项排序。最后返回 $arr$ 所有元素第二项组成的数组即可。
65+
66+
时间复杂度 $O(n\log n)$，其中 $n$ 是 $nums$ 数组元素的个数。
67+
68+
5669
<!-- tabs:start -->
5770

5871
### **Python3**
5972

6073
<!-- 这里可写当前语言的特殊实现逻辑 -->
6174

6275
```python
63-
76+
class Solution:
77+
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
78+
arr = []
79+
for i, row in enumerate(nums):
80+
for j, v in enumerate(row):
81+
arr.append((i + j, j, v))
82+
arr.sort()
83+
return [v[2] for v in arr]
6484
```
6585

6686
### **Java**
6787

6888
<!-- 这里可写当前语言的特殊实现逻辑 -->
6989

7090
```java
91+
class Solution {
92+
public int[] findDiagonalOrder(List<List<Integer>> nums) {
93+
List<int[]> arr = new ArrayList<>();
94+
for (int i = 0; i < nums.size(); ++i) {
95+
for (int j = 0; j < nums.get(i).size(); ++j) {
96+
arr.add(new int[]{i + j, j, nums.get(i).get(j)});
97+
}
98+
}
99+
arr.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
100+
int[] ans = new int[arr.size()];
101+
for (int i = 0; i < arr.size(); ++i) {
102+
ans[i] = arr.get(i)[2];
103+
}
104+
return ans;
105+
}
106+
}
107+
```
108+
109+
### **C++**
110+
111+
```cpp
112+
class Solution {
113+
public:
114+
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
115+
vector<tuple<int, int, int>> arr;
116+
for (int i = 0; i < nums.size(); ++i) {
117+
for (int j = 0; j < nums[i].size(); ++j) {
118+
arr.push_back({i + j, j, nums[i][j]});
119+
}
120+
}
121+
sort(arr.begin(), arr.end());
122+
vector<int> ans;
123+
for (auto& e: arr) {
124+
ans.push_back(get<2>(e));
125+
}
126+
return ans;
127+
}
128+
};
129+
```
71130
131+
### **Go**
132+
133+
```go
134+
func findDiagonalOrder(nums [][]int) []int {
135+
arr := [][]int{}
136+
for i, row := range nums {
137+
for j, v := range row {
138+
arr = append(arr, []int{i + j, j, v})
139+
}
140+
}
141+
sort.Slice(arr, func(i, j int) bool {
142+
if arr[i][0] == arr[j][0] {
143+
return arr[i][1] < arr[j][1]
144+
}
145+
return arr[i][0] < arr[j][0]
146+
})
147+
ans := []int{}
148+
for _, v := range arr {
149+
ans = append(ans, v[2])
150+
}
151+
return ans
152+
}
72153
```
73154

74155
### **...**

‎solution/1400-1499/1424.Diagonal Traverse II/README_EN.md

Lines changed: 69 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,13 +38,81 @@
3838
### **Python3**
3939

4040
```python
41-
41+
class Solution:
42+
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
43+
arr = []
44+
for i, row in enumerate(nums):
45+
for j, v in enumerate(row):
46+
arr.append((i + j, j, v))
47+
arr.sort()
48+
return [v[2] for v in arr]
4249
```
4350

4451
### **Java**
4552

4653
```java
54+
class Solution {
55+
public int[] findDiagonalOrder(List<List<Integer>> nums) {
56+
List<int[]> arr = new ArrayList<>();
57+
for (int i = 0; i < nums.size(); ++i) {
58+
for (int j = 0; j < nums.get(i).size(); ++j) {
59+
arr.add(new int[]{i + j, j, nums.get(i).get(j)});
60+
}
61+
}
62+
arr.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
63+
int[] ans = new int[arr.size()];
64+
for (int i = 0; i < arr.size(); ++i) {
65+
ans[i] = arr.get(i)[2];
66+
}
67+
return ans;
68+
}
69+
}
70+
```
71+
72+
### **C++**
73+
74+
```cpp
75+
class Solution {
76+
public:
77+
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
78+
vector<tuple<int, int, int>> arr;
79+
for (int i = 0; i < nums.size(); ++i) {
80+
for (int j = 0; j < nums[i].size(); ++j) {
81+
arr.push_back({i + j, j, nums[i][j]});
82+
}
83+
}
84+
sort(arr.begin(), arr.end());
85+
vector<int> ans;
86+
for (auto& e: arr) {
87+
ans.push_back(get<2>(e));
88+
}
89+
return ans;
90+
}
91+
};
92+
```
4793
94+
### **Go**
95+
96+
```go
97+
func findDiagonalOrder(nums [][]int) []int {
98+
arr := [][]int{}
99+
for i, row := range nums {
100+
for j, v := range row {
101+
arr = append(arr, []int{i + j, j, v})
102+
}
103+
}
104+
sort.Slice(arr, func(i, j int) bool {
105+
if arr[i][0] == arr[j][0] {
106+
return arr[i][1] < arr[j][1]
107+
}
108+
return arr[i][0] < arr[j][0]
109+
})
110+
ans := []int{}
111+
for _, v := range arr {
112+
ans = append(ans, v[2])
113+
}
114+
return ans
115+
}
48116
```
49117

50118
### **...**

‎solution/1400-1499/1424.Diagonal Traverse II/Solution.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution {
2+
public:
3+
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
4+
vector<tuple<int, int, int>> arr;
5+
for (int i = 0; i < nums.size(); ++i) {
6+
for (int j = 0; j < nums[i].size(); ++j) {
7+
arr.push_back({i + j, j, nums[i][j]});
8+
}
9+
}
10+
sort(arr.begin(), arr.end());
11+
vector<int> ans;
12+
for (auto& e: arr) {
13+
ans.push_back(get<2>(e));
14+
}
15+
return ans;
16+
}
17+
};

‎solution/1400-1499/1424.Diagonal Traverse II/Solution.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
func findDiagonalOrder(nums [][]int) []int {
2+
arr := [][]int{}
3+
for i, row := range nums {
4+
for j, v := range row {
5+
arr = append(arr, []int{i + j, j, v})
6+
}
7+
}
8+
sort.Slice(arr, func(i, j int) bool {
9+
if arr[i][0] == arr[j][0] {
10+
return arr[i][1] < arr[j][1]
11+
}
12+
return arr[i][0] < arr[j][0]
13+
})
14+
ans := []int{}
15+
for _, v := range arr {
16+
ans = append(ans, v[2])
17+
}
18+
return ans
19+
}

‎solution/1400-1499/1424.Diagonal Traverse II/Solution.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution {
2+
public int[] findDiagonalOrder(List<List<Integer>> nums) {
3+
List<int[]> arr = new ArrayList<>();
4+
for (int i = 0; i < nums.size(); ++i) {
5+
for (int j = 0; j < nums.get(i).size(); ++j) {
6+
arr.add(new int[]{i + j, j, nums.get(i).get(j)});
7+
}
8+
}
9+
arr.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
10+
int[] ans = new int[arr.size()];
11+
for (int i = 0; i < arr.size(); ++i) {
12+
ans[i] = arr.get(i)[2];
13+
}
14+
return ans;
15+
}
16+
}

‎solution/1400-1499/1424.Diagonal Traverse II/Solution.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
class Solution:
2+
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
3+
arr = []
4+
for i, row in enumerate(nums):
5+
for j, v in enumerate(row):
6+
arr.append((i + j, j, v))
7+
arr.sort()
8+
return [v[2] for v in arr]

0 commit comments

Comments
 (0)