Skip to content

Commit 0881edf

Browse files
halfrosthalfrost
committed
Add solution 0119、1439
1 parent 048c42d commit 0881edf

32 files changed

+887
-241
lines changed

‎README.md

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

‎leetcode/0119.Pascals-Triangle-II/119. Pascal's Triangle II.go

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package leetcode
2+
3+
func getRow(rowIndex int) []int {
4+
row := make([]int, rowIndex+1)
5+
row[0] = 1
6+
for i := 1; i <= rowIndex; i++ {
7+
row[i] = row[i-1] * (rowIndex - i + 1) / i
8+
}
9+
return row
10+
}

‎leetcode/0119.Pascals-Triangle-II/119. Pascal's Triangle II_test.go

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question119 struct {
9+
para119
10+
ans119
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para119 struct {
16+
rowIndex int
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans119 struct {
22+
one []int
23+
}
24+
25+
func Test_Problem119(t *testing.T) {
26+
27+
qs := []question119{
28+
29+
{
30+
para119{3},
31+
ans119{[]int{1, 3, 3, 1}},
32+
},
33+
34+
{
35+
para119{0},
36+
ans119{[]int{1}},
37+
},
38+
}
39+
40+
fmt.Printf("------------------------Leetcode Problem 119------------------------\n")
41+
42+
for _, q := range qs {
43+
_, p := q.ans119, q.para119
44+
fmt.Printf("【input】:%v 【output】:%v\n", p, getRow(p.rowIndex))
45+
}
46+
fmt.Printf("\n\n\n")
47+
}

‎leetcode/0119.Pascals-Triangle-II/README.md

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# [119. Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)
2+
3+
4+
## 题目
5+
6+
Given an integer `rowIndex`, return the `rowIndexth` row of the Pascal's triangle.
7+
8+
Notice that the row index starts from **0**.
9+
10+
![https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
11+
12+
In Pascal's triangle, each number is the sum of the two numbers directly above it.
13+
14+
**Follow up:**
15+
16+
Could you optimize your algorithm to use only *O*(*k*) extra space?
17+
18+
**Example 1:**
19+
20+
```
21+
Input: rowIndex = 3
22+
Output: [1,3,3,1]
23+
```
24+
25+
**Example 2:**
26+
27+
```
28+
Input: rowIndex = 0
29+
Output: [1]
30+
```
31+
32+
**Example 3:**
33+
34+
```
35+
Input: rowIndex = 1
36+
Output: [1,1]
37+
```
38+
39+
**Constraints:**
40+
41+
- `0 <= rowIndex <= 33`
42+
43+
## 题目大意
44+
45+
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
46+
47+
## 解题思路
48+
49+
- 题目中的三角是杨辉三角，每个数字是 `(a+b)^n` 二项式展开的系数。题目要求我们只能使用 O(k) 的空间。那么需要找到两两项直接的递推关系。由组合知识得知：
50+
51+
$$\begin{aligned}C_{n}^{m} &= \frac{n!}{m!(n-m)!} \\C_{n}^{m-1} &= \frac{n!}{(m-1)!(n-m+1)!}\end{aligned}$$
52+
53+
于是得到递推公式：
54+
55+
$$C_{n}^{m} = C_{n}^{m-1} \times \frac{n-m+1}{m}$$
56+
57+
利用这个递推公式即可以把空间复杂度优化到 O(k)
58+
59+
## 代码
60+
61+
```go
62+
package leetcode
63+
64+
func getRow(rowIndex int) []int {
65+
row := make([]int, rowIndex+1)
66+
row[0] = 1
67+
for i := 1; i <= rowIndex; i++ {
68+
row[i] = row[i-1] * (rowIndex - i + 1) / i
69+
}
70+
return row
71+
}
72+
```

‎leetcode/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows/1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows.go

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package leetcode
2+
3+
import "container/heap"
4+
5+
func kthSmallest(mat [][]int, k int) int {
6+
if len(mat) == 0 || len(mat[0]) == 0 || k == 0 {
7+
return 0
8+
}
9+
prev := mat[0]
10+
for i := 1; i < len(mat); i++ {
11+
prev = kSmallestPairs(prev, mat[i], k)
12+
}
13+
if k < len(prev) {
14+
return -1
15+
}
16+
return prev[k-1]
17+
}
18+
19+
func kSmallestPairs(nums1 []int, nums2 []int, k int) []int {
20+
res := []int{}
21+
if len(nums2) == 0 {
22+
return res
23+
}
24+
pq := newPriorityQueue()
25+
for i := 0; i < len(nums1) && i < k; i++ {
26+
heap.Push(pq, &pddata{
27+
n1: nums1[i],
28+
n2: nums2[0],
29+
n2Idx: 0,
30+
})
31+
}
32+
for pq.Len() > 0 {
33+
i := heap.Pop(pq)
34+
data := i.(*pddata)
35+
res = append(res, data.n1+data.n2)
36+
k--
37+
if k <= 0 {
38+
break
39+
}
40+
idx := data.n2Idx
41+
idx++
42+
if idx >= len(nums2) {
43+
continue
44+
}
45+
heap.Push(pq, &pddata{
46+
n1: data.n1,
47+
n2: nums2[idx],
48+
n2Idx: idx,
49+
})
50+
}
51+
return res
52+
}
53+
54+
type pddata struct {
55+
n1 int
56+
n2 int
57+
n2Idx int
58+
}
59+
60+
type priorityQueue []*pddata
61+
62+
func newPriorityQueue() *priorityQueue {
63+
pq := priorityQueue([]*pddata{})
64+
heap.Init(&pq)
65+
return &pq
66+
}
67+
68+
func (pq priorityQueue) Len() int { return len(pq) }
69+
func (pq priorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
70+
func (pq priorityQueue) Less(i, j int) bool { return pq[i].n1+pq[i].n2 < pq[j].n1+pq[j].n2 }
71+
func (pq *priorityQueue) Pop() interface{} {
72+
old := *pq
73+
val := old[len(old)-1]
74+
old[len(old)-1] = nil
75+
*pq = old[0 : len(old)-1]
76+
return val
77+
}
78+
79+
func (pq *priorityQueue) Push(i interface{}) {
80+
val := i.(*pddata)
81+
*pq = append(*pq, val)
82+
}

‎leetcode/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows/1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows_test.go

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1439 struct {
9+
para1439
10+
ans1439
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1439 struct {
16+
mat [][]int
17+
k int
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1439 struct {
23+
one int
24+
}
25+
26+
func Test_Problem1439(t *testing.T) {
27+
28+
qs := []question1439{
29+
30+
{
31+
para1439{[][]int{{1, 3, 11}, {2, 4, 6}}, 5},
32+
ans1439{7},
33+
},
34+
35+
{
36+
para1439{[][]int{{1, 3, 11}, {2, 4, 6}}, 9},
37+
ans1439{17},
38+
},
39+
{
40+
para1439{[][]int{{1, 10, 10}, {1, 4, 5}, {2, 3, 6}}, 7},
41+
ans1439{9},
42+
},
43+
{
44+
para1439{[][]int{{1, 1, 10}, {2, 2, 9}}, 7},
45+
ans1439{12},
46+
},
47+
}
48+
49+
fmt.Printf("------------------------Leetcode Problem 1439------------------------\n")
50+
51+
for _, q := range qs {
52+
_, p := q.ans1439, q.para1439
53+
fmt.Printf("【input】:%v 【output】:%v\n", p, kthSmallest(p.mat, p.k))
54+
}
55+
fmt.Printf("\n\n\n")
56+
}

0 commit comments

Comments
 (0)