mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-08 10:24:58 +08:00
Compare commits
1 Commits
dependabot
...
1.6.6
Author | SHA1 | Date | |
---|---|---|---|
8796fe779f |
13
.github/FUNDING.yml
vendored
13
.github/FUNDING.yml
vendored
@ -1,13 +0,0 @@
|
||||
# These are supported funding model platforms
|
||||
|
||||
github: [halfrost]
|
||||
patreon: # Replace with a single Patreon username
|
||||
open_collective: # Replace with a single Open Collective username
|
||||
ko_fi: # Replace with a single Ko-fi username
|
||||
tidelift: # Replace with a single Tidelift platform-name/package-name e.g., npm/babel
|
||||
community_bridge: # Replace with a single Community Bridge project-name e.g., cloud-foundry
|
||||
liberapay: # Replace with a single Liberapay username
|
||||
issuehunt: # Replace with a single IssueHunt username
|
||||
otechie: # Replace with a single Otechie username
|
||||
lfx_crowdfunding: # Replace with a single LFX Crowdfunding project-name e.g., cloud-foundry
|
||||
custom: # Replace with up to 4 custom sponsorship URLs e.g., ['link1', 'link2']
|
1
.gitignore
vendored
1
.gitignore
vendored
@ -1,2 +1 @@
|
||||
*.toml
|
||||
.idea
|
||||
|
21
ctl/label.go
21
ctl/label.go
@ -4,21 +4,20 @@ import (
|
||||
"bufio"
|
||||
"errors"
|
||||
"fmt"
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"github.com/spf13/cobra"
|
||||
"io"
|
||||
"io/ioutil"
|
||||
"os"
|
||||
"regexp"
|
||||
"strings"
|
||||
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"github.com/spf13/cobra"
|
||||
)
|
||||
|
||||
var (
|
||||
chapterOneFileOrder = []string{"_index", "Data_Structure", "Algorithm", "Time_Complexity"}
|
||||
chapterOneMenuOrder = []string{"_index", "#关于作者", "Data_Structure", "Algorithm", "Time_Complexity"}
|
||||
chapterOneFileOrder = []string{"_index", "Data_Structure", "Algorithm"}
|
||||
chapterOneMenuOrder = []string{"_index", "#关于作者", "Data_Structure", "Algorithm"}
|
||||
chapterTwoFileOrder = []string{"_index", "Array", "String", "Two_Pointers", "Linked_List", "Stack", "Tree", "Dynamic_Programming", "Backtracking", "Depth_First_Search", "Breadth_First_Search",
|
||||
"Binary_Search", "Math", "Hash_Table", "Sorting", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
|
||||
"Binary_Search", "Math", "Hash_Table", "Sort", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
|
||||
chapterThreeFileOrder = []string{"_index", "Segment_Tree", "UnionFind", "LRUCache", "LFUCache"}
|
||||
preNextHeader = "----------------------------------------------\n<div style=\"display: flex;justify-content: space-between;align-items: center;\">\n"
|
||||
preNextFotter = "</div>"
|
||||
@ -35,10 +34,10 @@ var (
|
||||
|
||||
chapterMap = map[string]map[string]string{
|
||||
"ChapterOne": {
|
||||
"_index": "第一章 序章",
|
||||
"Data_Structure": "1.1 数据结构知识",
|
||||
"Algorithm": "1.2 算法知识",
|
||||
"Time_Complexity": "1.3 时间复杂度",
|
||||
"_index": "第一章 序章",
|
||||
"#关于作者": "1.1 关于作者",
|
||||
"Data_Structure": "1.2 数据结构知识",
|
||||
"Algorithm": "1.3 算法知识",
|
||||
},
|
||||
"ChapterTwo": {
|
||||
"_index": "第二章 算法专题",
|
||||
@ -55,7 +54,7 @@ var (
|
||||
"Binary_Search": "2.11 Binary Search",
|
||||
"Math": "2.12 Math",
|
||||
"Hash_Table": "2.13 Hash Table",
|
||||
"Sorting": "2.14 ✅ Sorting",
|
||||
"Sort": "2.14 ✅ Sort",
|
||||
"Bit_Manipulation": "2.15 ✅ Bit Manipulation",
|
||||
"Union_Find": "2.16 ✅ Union Find",
|
||||
"Sliding_Window": "2.17 ✅ Sliding Window",
|
||||
|
@ -3,7 +3,7 @@
|
||||
|
||||
# 说明
|
||||
|
||||
此版本是 https://books.halfrost.com/leetcode 网页的离线版,由于网页版实时会更新,所以此 PDF 版难免会有一些排版或者错别字。如果读者遇到了,可以到网页版相应页面,点击页面 edit 按钮,提交 pr 进行更改。此 PDF 版本号是 V1.5.20。PDF 永久更新地址是 https://github.com/halfrost/leetcode-go/releases/,以版本号区分不同版本。笔者还是强烈推荐看在线版,有任何错误都会立即更新。如果觉得此书对刷题有一点点帮助,可以给此书点一个 star,鼓励一下笔者早点更新更多题解。
|
||||
此版本是 https://books.halfrost.com/leetcode 网页的离线版,由于网页版实时会更新,所以此 PDF 版难免会有一些排版或者错别字。如果读者遇到了,可以到网页版相应页面,点击页面 edit 按钮,提交 pr 进行更改。此 PDF 版本号是 V1.5.20。PDF 永久更新地址是 https://github.com/halfrost/LeetCode-Go/releases/,以版本号区分不同版本。笔者还是强烈推荐看在线版,有任何错误都会立即更新。如果觉得此书对刷题有一点点帮助,可以给此书点一个 star,鼓励一下笔者早点更新更多题解。
|
||||
|
||||
> 版本号说明,V1.5.20,1 是大版本号,5 代表当前题解中有几百题,目前是 520 题,所以第二个版本号是 5,20 代表当前题解中有几十题,目前是 520 题,所以第三个版本号是 20 。
|
||||
|
||||
|
@ -1,7 +1,7 @@
|
||||
|56. Merge Intervals | [Go]({{< relref "/ChapterFour/0056.Merge-Intervals.md" >}})| Medium | O(n log n)| O(log n)||
|
||||
|57. Insert Interval | [Go]({{< relref "/ChapterFour/0057.Insert-Interval.md" >}})| Hard | O(n)| O(1)||
|
||||
|75. Sort Colors | [Go]({{< relref "/ChapterFour/0075.Sort-Colors.md" >}})| Medium| O(n)| O(1)|❤️|
|
||||
|147. Insertion Sort List | [Go]({{< relref "/ChapterFour/0147.Insertion-Sort-List.md" >}})| Medium | O(n^2)| O(1) |❤️|
|
||||
|147. Insertion Sort List | [Go]({{< relref "/ChapterFour/0147.Insertion-Sort-List.md" >}})| Medium | O(n)| O(1) |❤️|
|
||||
|148. Sort List | [Go]({{< relref "/ChapterFour/0148.Sort-List.md" >}})| Medium |O(n log n)| O(log n)|❤️|
|
||||
|164. Maximum Gap | [Go]({{< relref "/ChapterFour/0164.Maximum-Gap.md" >}})| Hard | O(n log n)| O(log n) |❤️|
|
||||
|179. Largest Number | [Go]({{< relref "/ChapterFour/0179.Largest-Number.md" >}})| Medium | O(n log n)| O(log n) |❤️|
|
@ -1,7 +0,0 @@
|
||||
module github.com/halfrost/LeetCode-Go/ctl/models
|
||||
|
||||
go 1.19
|
||||
|
||||
replace github.com/halfrost/LeetCode-Go/ctl/models => ../util
|
||||
|
||||
require github.com/halfrost/LeetCode-Go/ctl/util v0.0.0-20220910225043-e3bb5aff34d0
|
@ -1,2 +0,0 @@
|
||||
github.com/halfrost/LeetCode-Go/ctl/util v0.0.0-20220910225043-e3bb5aff34d0 h1:WAOAj59szR52uAnEQljAt7ucpbGGOsy0xgR/NeP4Xbc=
|
||||
github.com/halfrost/LeetCode-Go/ctl/util v0.0.0-20220910225043-e3bb5aff34d0/go.mod h1:+cA8KYcbGxP2Itd3NG+QJVGL/MEZISKlei0tvgDeEag=
|
@ -14,8 +14,8 @@ type LeetCodeProblemAll struct {
|
||||
AcMedium int32 `json:"ac_medium"`
|
||||
AcHard int32 `json:"ac_hard"`
|
||||
StatStatusPairs []StatStatusPairs `json:"stat_status_pairs"`
|
||||
FrequencyHigh float64 `json:"frequency_high"`
|
||||
FrequencyMid float64 `json:"frequency_mid"`
|
||||
FrequencyHigh int32 `json:"frequency_high"`
|
||||
FrequencyMid int32 `json:"frequency_mid"`
|
||||
CategorySlug string `json:"category_slug"`
|
||||
AcEasyTotal int32
|
||||
AcMediumTotal int32
|
||||
|
@ -18,41 +18,18 @@ type Mdrow struct {
|
||||
|
||||
// GenerateMdRows define
|
||||
func GenerateMdRows(solutionIds []int, mdrows []Mdrow) {
|
||||
mdMap := map[int]Mdrow{}
|
||||
for _, row := range mdrows {
|
||||
mdMap[int(row.FrontendQuestionID)] = row
|
||||
}
|
||||
for i := 0; i < len(solutionIds); i++ {
|
||||
if row, ok := mdMap[solutionIds[i]]; ok {
|
||||
s7 := standardizedTitle(row.QuestionTitle, row.FrontendQuestionID)
|
||||
mdMap[solutionIds[i]] = Mdrow{
|
||||
FrontendQuestionID: row.FrontendQuestionID,
|
||||
QuestionTitle: strings.TrimSpace(row.QuestionTitle),
|
||||
QuestionTitleSlug: row.QuestionTitleSlug,
|
||||
SolutionPath: fmt.Sprintf("[Go](https://github.com/halfrost/leetcode-go/tree/master/leetcode/%v)", fmt.Sprintf("%04d.%v", solutionIds[i], s7)),
|
||||
Acceptance: row.Acceptance,
|
||||
Difficulty: row.Difficulty,
|
||||
Frequency: row.Frequency,
|
||||
}
|
||||
id := mdrows[solutionIds[i]-1].FrontendQuestionID
|
||||
if solutionIds[i] == int(id) {
|
||||
//fmt.Printf("id = %v i = %v solutionIds = %v\n", id, i, solutionIds[i])
|
||||
mdrows[id-1].SolutionPath = fmt.Sprintf("[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/%v)", fmt.Sprintf("%04d.%v", id, strings.Replace(strings.TrimSpace(mdrows[id-1].QuestionTitle), " ", "-", -1)))
|
||||
} else {
|
||||
fmt.Printf("序号不存在 len(solutionIds) = %v len(mdrows) = %v len(solutionIds) = %v solutionIds[i] = %v QuestionTitle = %v\n", len(solutionIds), len(mdrows), len(solutionIds), solutionIds[i], mdrows[solutionIds[i]-1].QuestionTitle)
|
||||
fmt.Printf("序号出错了 solutionIds = %v id = %v\n", solutionIds[i], id)
|
||||
}
|
||||
}
|
||||
for i := range mdrows {
|
||||
mdrows[i] = Mdrow{
|
||||
FrontendQuestionID: mdrows[i].FrontendQuestionID,
|
||||
QuestionTitle: strings.TrimSpace(mdrows[i].QuestionTitle),
|
||||
QuestionTitleSlug: mdrows[i].QuestionTitleSlug,
|
||||
SolutionPath: mdMap[int(mdrows[i].FrontendQuestionID)].SolutionPath,
|
||||
Acceptance: mdrows[i].Acceptance,
|
||||
Difficulty: mdrows[i].Difficulty,
|
||||
Frequency: mdrows[i].Frequency,
|
||||
}
|
||||
}
|
||||
// fmt.Printf("mdrows = %v\n\n", mdrows)
|
||||
}
|
||||
|
||||
// | 0001 | Two Sum | [Go](https://github.com/halfrost/leetcode-go/tree/master/leetcode/0001.Two-Sum)| 45.6% | Easy | |
|
||||
// | 0001 | Two Sum | [Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0001.Two-Sum)| 45.6% | Easy | |
|
||||
func (m Mdrow) tableLine() string {
|
||||
return fmt.Sprintf("|%04d|%v|%v|%v|%v||\n", m.FrontendQuestionID, m.QuestionTitle, m.SolutionPath, m.Acceptance, m.Difficulty)
|
||||
}
|
||||
|
@ -32,7 +32,7 @@ type TopicTag struct {
|
||||
TranslatedName string `json:"translatedName"`
|
||||
Slug string `json:"slug"`
|
||||
Questions []Question `json:"questions"`
|
||||
Frequencies string `json:"frequencies"`
|
||||
Frequencies float64 `json:"frequencies"`
|
||||
Typename string `json:"__typename"`
|
||||
}
|
||||
|
||||
@ -115,41 +115,6 @@ func (t TagList) tableLine() string {
|
||||
return fmt.Sprintf("|%04d|%v|%v|%v|%v|%v|%v|%v|\n", t.FrontendQuestionID, t.QuestionTitle, t.SolutionPath, t.Difficulty, t.TimeComplexity, t.SpaceComplexity, t.Favorite, t.Acceptance)
|
||||
}
|
||||
|
||||
func standardizedTitle(orig string, frontendQuestionID int32) string {
|
||||
s0 := strings.TrimSpace(orig)
|
||||
s1 := strings.Replace(s0, " ", "-", -1)
|
||||
s2 := strings.Replace(s1, "'", "", -1)
|
||||
s3 := strings.Replace(s2, "%", "", -1)
|
||||
s4 := strings.Replace(s3, "(", "", -1)
|
||||
s5 := strings.Replace(s4, ")", "", -1)
|
||||
s6 := strings.Replace(s5, ",", "", -1)
|
||||
s7 := strings.Replace(s6, "?", "", -1)
|
||||
count := 0
|
||||
// 去掉 --- 这种情况,这种情况是由于题目标题中包含 - ,左右有空格,左右一填充,造成了 ---,3 个 -
|
||||
for i := 0; i < len(s7)-2; i++ {
|
||||
if s7[i] == '-' && s7[i+1] == '-' && s7[i+2] == '-' {
|
||||
fmt.Printf("【需要修正 --- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(frontendQuestionID), s7))
|
||||
s7 = s7[:i+1] + s7[i+3:]
|
||||
count++
|
||||
}
|
||||
}
|
||||
if count > 0 {
|
||||
fmt.Printf("总共修正了 %v 个标题\n", count)
|
||||
}
|
||||
// 去掉 -- 这种情况,这种情况是由于题目标题中包含负号 -
|
||||
for i := 0; i < len(s7)-2; i++ {
|
||||
if s7[i] == '-' && s7[i+1] == '-' {
|
||||
fmt.Printf("【需要修正 -- 的标题是 %v】\n", fmt.Sprintf("%04d.%v", int(frontendQuestionID), s7))
|
||||
s7 = s7[:i+1] + s7[i+2:]
|
||||
count++
|
||||
}
|
||||
}
|
||||
if count > 0 {
|
||||
fmt.Printf("总共修正了 %v 个标题\n", count)
|
||||
}
|
||||
return s7
|
||||
}
|
||||
|
||||
// GenerateTagMdRows define
|
||||
func GenerateTagMdRows(solutionIds []int, metaMap map[int]TagList, mdrows []Mdrow, internal bool) []TagList {
|
||||
tl := []TagList{}
|
||||
@ -158,7 +123,13 @@ func GenerateTagMdRows(solutionIds []int, metaMap map[int]TagList, mdrows []Mdro
|
||||
tmp := TagList{}
|
||||
tmp.FrontendQuestionID = row.FrontendQuestionID
|
||||
tmp.QuestionTitle = strings.TrimSpace(row.QuestionTitle)
|
||||
s7 := standardizedTitle(row.QuestionTitle, row.FrontendQuestionID)
|
||||
s1 := strings.Replace(tmp.QuestionTitle, " ", "-", -1)
|
||||
s2 := strings.Replace(s1, "'", "", -1)
|
||||
s3 := strings.Replace(s2, "%", "", -1)
|
||||
s4 := strings.Replace(s3, "(", "", -1)
|
||||
s5 := strings.Replace(s4, ")", "", -1)
|
||||
s6 := strings.Replace(s5, ",", "", -1)
|
||||
s7 := strings.Replace(s6, "?", "", -1)
|
||||
if internal {
|
||||
tmp.SolutionPath = fmt.Sprintf("[Go]({{< relref \"/ChapterFour/%v/%v.md\" >}})", util.GetChpaterFourFileNum(int(row.FrontendQuestionID)), fmt.Sprintf("%04d.%v", int(row.FrontendQuestionID), s7))
|
||||
} else {
|
||||
@ -180,8 +151,8 @@ type TagLists struct {
|
||||
TagLists []TagList
|
||||
}
|
||||
|
||||
// | No. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |Favorite| Acceptance |
|
||||
// |:--------:|:------- | :--------: | :----------: | :----: | :-----: | :-----: |:-----: |
|
||||
//| No. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |Favorite| Acceptance |
|
||||
//|:--------:|:------- | :--------: | :----------: | :----: | :-----: | :-----: |:-----: |
|
||||
func (tls TagLists) table() string {
|
||||
res := "| No. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity |Favorite| Acceptance |\n"
|
||||
res += "|:--------:|:------- | :--------: | :----------: | :----: | :-----: | :-----: |:-----: |\n"
|
||||
|
@ -18,9 +18,9 @@ type UserInfo struct {
|
||||
OptimizingEasy int32
|
||||
OptimizingMedium int32
|
||||
OptimizingHard int32
|
||||
FrequencyHigh float64 `json:"frequency_high"`
|
||||
FrequencyMid float64 `json:"frequency_mid"`
|
||||
CategorySlug string `json:"category_slug"`
|
||||
FrequencyHigh int32 `json:"frequency_high"`
|
||||
FrequencyMid int32 `json:"frequency_mid"`
|
||||
CategorySlug string `json:"category_slug"`
|
||||
}
|
||||
|
||||
// | | Easy | Medium | Hard | Total | optimizing |
|
||||
|
@ -3,15 +3,14 @@ package main
|
||||
import (
|
||||
"bufio"
|
||||
"fmt"
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"github.com/spf13/cobra"
|
||||
"io"
|
||||
"io/ioutil"
|
||||
"os"
|
||||
"regexp"
|
||||
"strconv"
|
||||
"strings"
|
||||
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"github.com/spf13/cobra"
|
||||
)
|
||||
|
||||
var (
|
||||
@ -24,7 +23,7 @@ var (
|
||||
|
||||
# 说明
|
||||
|
||||
此版本是 https://books.halfrost.com/leetcode 网页的离线版,由于网页版实时会更新,所以此 PDF 版难免会有一些排版或者错别字。如果读者遇到了,可以到网页版相应页面,点击页面 edit 按钮,提交 pr 进行更改。此 PDF 版本号是 V%v.%v.%v。PDF 永久更新地址是 https://github.com/halfrost/leetcode-go/releases/,以版本号区分不同版本。笔者还是强烈推荐看在线版,有任何错误都会立即更新。如果觉得此书对刷题有一点点帮助,可以给此书点一个 star,鼓励一下笔者早点更新更多题解。
|
||||
此版本是 https://books.halfrost.com/leetcode 网页的离线版,由于网页版实时会更新,所以此 PDF 版难免会有一些排版或者错别字。如果读者遇到了,可以到网页版相应页面,点击页面 edit 按钮,提交 pr 进行更改。此 PDF 版本号是 V%v.%v.%v。PDF 永久更新地址是 https://github.com/halfrost/LeetCode-Go/releases/,以版本号区分不同版本。笔者还是强烈推荐看在线版,有任何错误都会立即更新。如果觉得此书对刷题有一点点帮助,可以给此书点一个 star,鼓励一下笔者早点更新更多题解。
|
||||
|
||||
> 版本号说明,V%v.%v.%v,%v 是大版本号,%v 代表当前题解中有几百题,目前是 %v 题,所以第二个版本号是 %v,%v 代表当前题解中有几十题,目前是 %v 题,所以第三个版本号是 %v 。
|
||||
|
||||
|
@ -18,11 +18,11 @@ import (
|
||||
|
||||
var (
|
||||
chapterTwoList = []string{"Array", "String", "Two Pointers", "Linked List", "Stack", "Tree", "Dynamic Programming", "Backtracking", "Depth First Search", "Breadth First Search",
|
||||
"Binary Search", "Math", "Hash Table", "Sorting", "Bit Manipulation", "Union Find", "Sliding Window", "Segment Tree", "Binary Indexed Tree"}
|
||||
"Binary Search", "Math", "Hash Table", "Sort", "Bit Manipulation", "Union Find", "Sliding Window", "Segment Tree", "Binary Indexed Tree"}
|
||||
chapterTwoFileName = []string{"Array", "String", "Two_Pointers", "Linked_List", "Stack", "Tree", "Dynamic_Programming", "Backtracking", "Depth_First_Search", "Breadth_First_Search",
|
||||
"Binary_Search", "Math", "Hash_Table", "Sorting", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
|
||||
"Binary_Search", "Math", "Hash_Table", "Sort", "Bit_Manipulation", "Union_Find", "Sliding_Window", "Segment_Tree", "Binary_Indexed_Tree"}
|
||||
chapterTwoSlug = []string{"array", "string", "two-pointers", "linked-list", "stack", "tree", "dynamic-programming", "backtracking", "depth-first-search", "breadth-first-search",
|
||||
"binary-search", "math", "hash-table", "sorting", "bit-manipulation", "union-find", "sliding-window", "segment-tree", "binary-indexed-tree"}
|
||||
"binary-search", "math", "hash-table", "sort", "bit-manipulation", "union-find", "sliding-window", "segment-tree", "binary-indexed-tree"}
|
||||
)
|
||||
|
||||
func newBuildCommand() *cobra.Command {
|
||||
@ -163,8 +163,7 @@ func renderReadme(filePath string, total, try int, mdrows, omdrows m.Mdrows, use
|
||||
}
|
||||
|
||||
// internal: true 渲染的链接都是 hugo 内部链接,用户生成 hugo web
|
||||
//
|
||||
// false 渲染的链接是外部 HTTPS 链接,用于生成 PDF
|
||||
// false 渲染的链接是外部 HTTPS 链接,用于生成 PDF
|
||||
func buildChapterTwo(internal bool) {
|
||||
var (
|
||||
gr m.GraphQLResp
|
||||
|
@ -3,10 +3,9 @@ package main
|
||||
import (
|
||||
"bytes"
|
||||
"fmt"
|
||||
"github.com/mozillazg/request"
|
||||
"io/ioutil"
|
||||
"net/http"
|
||||
|
||||
"github.com/mozillazg/request"
|
||||
)
|
||||
|
||||
const (
|
||||
|
@ -1,10 +1,9 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"sort"
|
||||
|
||||
m "github.com/halfrost/LeetCode-Go/ctl/models"
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"sort"
|
||||
)
|
||||
|
||||
func statisticalData(problemsMap map[int]m.StatStatusPairs, solutionIds []int) (easyTotal, mediumTotal, hardTotal, optimizingEasy, optimizingMedium, optimizingHard int32, optimizingIds []int) {
|
||||
|
@ -1,10 +1,10 @@
|
||||
---
|
||||
title: 2.14 ✅ Sorting
|
||||
title: 2.14 ✅ Sort
|
||||
type: docs
|
||||
weight: 14
|
||||
---
|
||||
|
||||
# Sorting
|
||||
# Sort
|
||||
|
||||

|
||||
|
@ -10,20 +10,19 @@
|
||||

|
||||
|
||||
<p align='center'>
|
||||
<a href="https://github.com/halfrost/leetcode-go/releases/" rel="nofollow"><img alt="GitHub All Releases" src="https://img.shields.io/github/downloads/halfrost/LeetCode-Go/total?label=PDF%20downloads"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/releases/" rel="nofollow"><img alt="GitHub All Releases" src="https://img.shields.io/github/downloads/halfrost/LeetCode-Go/total?label=PDF%20downloads"></a>
|
||||
<img src="https://img.shields.io/badge/Total%20Word%20Count-738884-success">
|
||||
<a href="https://github.com/halfrost/leetcode-go/actions" rel="nofollow"><img src="https://github.com/halfrost/leetcode-go/workflows/Deploy%20leetcode-cookbook/badge.svg?branch=master"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/actions" rel="nofollow"><img src="https://github.com/halfrost/LeetCode-Go/workflows/Deploy%20leetcode-cookbook/badge.svg?branch=master"></a>
|
||||
<a href="https://travis-ci.org/github/halfrost/LeetCode-Go" rel="nofollow"><img src="https://travis-ci.org/halfrost/LeetCode-Go.svg?branch=master"></a>
|
||||
<a href="https://goreportcard.com/report/github.com/halfrost/LeetCode-Go" rel="nofollow"><img src="https://goreportcard.com/badge/github.com/halfrost/LeetCode-Go"></a>
|
||||
<img src="https://img.shields.io/badge/runtime%20beats-100%25-success">
|
||||
<a href="https://codecov.io/gh/halfrost/LeetCode-Go"><img src="https://codecov.io/gh/halfrost/LeetCode-Go/branch/master/graph/badge.svg" /></a>
|
||||
<!--<img alt="GitHub go.mod Go version" src="https://img.shields.io/github/go-mod/go-version/halfrost/LeetCode-Go?color=26C2F0">-->
|
||||
<img alt="Support Go version" src="https://img.shields.io/badge/Go-v1.15-26C2F0">
|
||||
<img src="https://visitor-badge.laobi.icu/badge?page_id=halfrost.LeetCode-Go">
|
||||
</p>
|
||||
|
||||
<p align='center'>
|
||||
<a href="https://github.com/halfrost/leetcode-go/blob/master/LICENSE"><img alt="GitHub" src="https://img.shields.io/github/license/halfrost/LeetCode-Go?label=License"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/blob/master/LICENSE"><img alt="GitHub" src="https://img.shields.io/github/license/halfrost/LeetCode-Go?label=License"></a>
|
||||
<img src="https://img.shields.io/badge/License-CC-000000.svg">
|
||||
<a href="https://leetcode.com/halfrost/"><img src="https://img.shields.io/badge/@halfrost-8751-yellow.svg">
|
||||
<img src="https://img.shields.io/badge/language-Golang-26C2F0.svg">
|
||||
@ -32,7 +31,7 @@
|
||||
<a href="https://twitter.com/halffrost"><img src="https://img.shields.io/badge/twitter-@halffrost-F8E81C.svg?style=flat&colorA=009df2"></a>
|
||||
<a href="https://www.zhihu.com/people/halfrost/activities"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@halfrost-fd6f32.svg?style=flat&colorA=0083ea"></a>
|
||||
<img src="https://img.shields.io/badge/made%20with-=1-blue.svg">
|
||||
<a href="https://github.com/halfrost/leetcode-go/pulls"><img src="https://img.shields.io/badge/PR-Welcome-brightgreen.svg"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/pulls"><img src="https://img.shields.io/badge/PR-Welcome-brightgreen.svg"></a>
|
||||
</p>
|
||||
|
||||
支持 Progressive Web Apps 和 Dark Mode 的题解电子书《LeetCode Cookbook》 <a href="https://books.halfrost.com/leetcode/" rel="nofollow">Online Reading</a>
|
||||
@ -42,10 +41,10 @@
|
||||
<a href="https://books.halfrost.com/leetcode/"><img src="https://img.halfrost.com/Leetcode/Cookbook_Chrome_PWA.png"></a>
|
||||
</p>
|
||||
|
||||
离线版本的电子书《LeetCode Cookbook》PDF <a href="https://github.com/halfrost/leetcode-go/releases/" rel="nofollow">Download here</a>
|
||||
离线版本的电子书《LeetCode Cookbook》PDF <a href="https://github.com/halfrost/LeetCode-Go/releases/" rel="nofollow">Download here</a>
|
||||
|
||||
<p align='center'>
|
||||
<a href="https://github.com/halfrost/leetcode-go/releases/"><img src="https://img.halfrost.com/Leetcode/Cookbook.png"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/releases/"><img src="https://img.halfrost.com/Leetcode/Cookbook.png"></a>
|
||||
</p>
|
||||
|
||||
通过 iOS / Android 浏览器安装 PWA 版《LeetCode Cookbook》至设备桌面随时学习
|
||||
@ -550,7 +549,7 @@ Problems List in [there](https://books.halfrost.com/leetcode/ChapterTwo/Bit_Mani
|
||||
|
||||

|
||||
|
||||
- 灵活使用并查集的思想,熟练掌握并查集的[模板](https://github.com/halfrost/leetcode-go/blob/master/template/UnionFind.go),模板中有两种并查集的实现方式,一种是路径压缩 + 秩优化的版本,另外一种是计算每个集合中元素的个数 + 最大集合元素个数的版本,这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有:第 128 题,第 130 题,第 547 题,第 684 题,第 721 题,第 765 题,第 778 题,第 839 题,第 924 题,第 928 题,第 947 题,第 952 题,第 959 题,第 990 题。能使用第二类并查集模板的题目有:第 803 题,第 952 题。第 803 题秩优化和统计集合个数这些地方会卡时间,如果不优化,会 TLE。
|
||||
- 灵活使用并查集的思想,熟练掌握并查集的[模板](https://github.com/halfrost/LeetCode-Go/blob/master/template/UnionFind.go),模板中有两种并查集的实现方式,一种是路径压缩 + 秩优化的版本,另外一种是计算每个集合中元素的个数 + 最大集合元素个数的版本,这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有:第 128 题,第 130 题,第 547 题,第 684 题,第 721 题,第 765 题,第 778 题,第 839 题,第 924 题,第 928 题,第 947 题,第 952 题,第 959 题,第 990 题。能使用第二类并查集模板的题目有:第 803 题,第 952 题。第 803 题秩优化和统计集合个数这些地方会卡时间,如果不优化,会 TLE。
|
||||
- 并查集是一种思想,有些题需要灵活使用这种思想,而不是死套模板,如第 399 题,这一题是 stringUnionFind,利用并查集思想实现的。这里每个节点是基于字符串和 map 的,而不是单纯的用 int 节点编号实现的。
|
||||
- 有些题死套模板反而做不出来,比如第 685 题,这一题不能路径压缩和秩优化,因为题目中涉及到有向图,需要知道节点的前驱节点,如果路径压缩了,这一题就没法做了。这一题不需要路径压缩和秩优化。
|
||||
- 灵活的抽象题目给的信息,将给定的信息合理的编号,使用并查集解题,并用 map 降低时间复杂度,如第 721 题,第 959 题。
|
||||
@ -630,10 +629,10 @@ Problems List in [there](https://books.halfrost.com/leetcode/ChapterTwo/Binary_I
|
||||
----------------------------------------------------------------------------------------
|
||||
|
||||
<p align='center'>
|
||||
<a href="https://github.com/halfrost/leetcode-go/releases/tag/Special"><img src="https://img.halfrost.com/Leetcode/ACM-ICPC_Algorithm_Template.png"></a>
|
||||
<a href="https://github.com/halfrost/LeetCode-Go/releases/tag/Special"><img src="https://img.halfrost.com/Leetcode/ACM-ICPC_Algorithm_Template.png"></a>
|
||||
</p>
|
||||
|
||||
Thank you for reading here. This is bonus. You can download my [《ACM-ICPC Algorithm Template》](https://github.com/halfrost/leetcode-go/releases/tag/Special/)
|
||||
Thank you for reading here. This is bonus. You can download my [《ACM-ICPC Algorithm Template》](https://github.com/halfrost/LeetCode-Go/releases/tag/Special/)
|
||||
|
||||
|
||||
|
||||
|
@ -3,12 +3,11 @@ package main
|
||||
import (
|
||||
"bytes"
|
||||
"fmt"
|
||||
m "github.com/halfrost/LeetCode-Go/ctl/models"
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
"html/template"
|
||||
"io/ioutil"
|
||||
"os"
|
||||
|
||||
m "github.com/halfrost/LeetCode-Go/ctl/models"
|
||||
"github.com/halfrost/LeetCode-Go/ctl/util"
|
||||
)
|
||||
|
||||
func makeReadmeFile(mdrows m.Mdrows) {
|
||||
|
@ -1,3 +0,0 @@
|
||||
module github.com/halfrost/LeetCode-Go/ctl/util
|
||||
|
||||
go 1.19
|
29
go.mod
29
go.mod
@ -1,30 +1,13 @@
|
||||
module github.com/halfrost/LeetCode-Go
|
||||
|
||||
go 1.19
|
||||
|
||||
replace github.com/halfrost/LeetCode-Go/structures => ./structures
|
||||
|
||||
replace github.com/halfrost/LeetCode-Go/template => ./template
|
||||
|
||||
replace github.com/halfrost/LeetCode-Go/ctl/util => ./ctl/util
|
||||
|
||||
replace github.com/halfrost/LeetCode-Go/ctl/models => ./ctl/models
|
||||
|
||||
require (
|
||||
github.com/BurntSushi/toml v1.2.0
|
||||
github.com/halfrost/LeetCode-Go/ctl/models v0.0.0-20220910225043-e3bb5aff34d0
|
||||
github.com/halfrost/LeetCode-Go/ctl/util v0.0.0-20220910225043-e3bb5aff34d0
|
||||
github.com/halfrost/LeetCode-Go/structures v0.0.0-20220910233101-aa0e2c897b18
|
||||
github.com/halfrost/LeetCode-Go/template v0.0.0-20220910233504-e2a72e6212ce
|
||||
github.com/mozillazg/request v0.8.0
|
||||
github.com/spf13/cobra v1.5.0
|
||||
)
|
||||
go 1.15
|
||||
|
||||
require (
|
||||
github.com/BurntSushi/toml v0.3.1
|
||||
github.com/bitly/go-simplejson v0.5.0 // indirect
|
||||
github.com/bmizerany/assert v0.0.0-20160611221934-b7ed37b82869 // indirect
|
||||
github.com/inconshreveable/mousetrap v1.0.0 // indirect
|
||||
github.com/kr/pretty v0.3.0 // indirect
|
||||
github.com/spf13/pflag v1.0.5 // indirect
|
||||
golang.org/x/net v0.17.0 // indirect
|
||||
github.com/mozillazg/request v0.8.0
|
||||
github.com/spf13/cobra v1.1.1
|
||||
github.com/stretchr/testify v1.3.0
|
||||
golang.org/x/net v0.0.0-20201021035429-f5854403a974 // indirect
|
||||
)
|
||||
|
303
go.sum
303
go.sum
@ -1,36 +1,303 @@
|
||||
github.com/BurntSushi/toml v1.2.0 h1:Rt8g24XnyGTyglgET/PRUNlrUeu9F5L+7FilkXfZgs0=
|
||||
github.com/BurntSushi/toml v1.2.0/go.mod h1:CxXYINrC8qIiEnFrOxCa7Jy5BFHlXnUU2pbicEuybxQ=
|
||||
cloud.google.com/go v0.26.0/go.mod h1:aQUYkXzVsufM+DwF1aE+0xfcU+56JwCaLick0ClmMTw=
|
||||
cloud.google.com/go v0.34.0/go.mod h1:aQUYkXzVsufM+DwF1aE+0xfcU+56JwCaLick0ClmMTw=
|
||||
cloud.google.com/go v0.38.0/go.mod h1:990N+gfupTy94rShfmMCWGDn0LpTmnzTp2qbd1dvSRU=
|
||||
cloud.google.com/go v0.44.1/go.mod h1:iSa0KzasP4Uvy3f1mN/7PiObzGgflwredwwASm/v6AU=
|
||||
cloud.google.com/go v0.44.2/go.mod h1:60680Gw3Yr4ikxnPRS/oxxkBccT6SA1yMk63TGekxKY=
|
||||
cloud.google.com/go v0.45.1/go.mod h1:RpBamKRgapWJb87xiFSdk4g1CME7QZg3uwTez+TSTjc=
|
||||
cloud.google.com/go v0.46.3/go.mod h1:a6bKKbmY7er1mI7TEI4lsAkts/mkhTSZK8w33B4RAg0=
|
||||
cloud.google.com/go/bigquery v1.0.1/go.mod h1:i/xbL2UlR5RvWAURpBYZTtm/cXjCha9lbfbpx4poX+o=
|
||||
cloud.google.com/go/datastore v1.0.0/go.mod h1:LXYbyblFSglQ5pkeyhO+Qmw7ukd3C+pD7TKLgZqpHYE=
|
||||
cloud.google.com/go/firestore v1.1.0/go.mod h1:ulACoGHTpvq5r8rxGJ4ddJZBZqakUQqClKRT5SZwBmk=
|
||||
cloud.google.com/go/pubsub v1.0.1/go.mod h1:R0Gpsv3s54REJCy4fxDixWD93lHJMoZTyQ2kNxGRt3I=
|
||||
cloud.google.com/go/storage v1.0.0/go.mod h1:IhtSnM/ZTZV8YYJWCY8RULGVqBDmpoyjwiyrjsg+URw=
|
||||
dmitri.shuralyov.com/gpu/mtl v0.0.0-20190408044501-666a987793e9/go.mod h1:H6x//7gZCb22OMCxBHrMx7a5I7Hp++hsVxbQ4BYO7hU=
|
||||
github.com/BurntSushi/toml v0.3.1 h1:WXkYYl6Yr3qBf1K79EBnL4mak0OimBfB0XUf9Vl28OQ=
|
||||
github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
|
||||
github.com/BurntSushi/xgb v0.0.0-20160522181843-27f122750802/go.mod h1:IVnqGOEym/WlBOVXweHU+Q+/VP0lqqI8lqeDx9IjBqo=
|
||||
github.com/OneOfOne/xxhash v1.2.2/go.mod h1:HSdplMjZKSmBqAxg5vPj2TmRDmfkzw+cTzAElWljhcU=
|
||||
github.com/alecthomas/template v0.0.0-20160405071501-a0175ee3bccc/go.mod h1:LOuyumcjzFXgccqObfd/Ljyb9UuFJ6TxHnclSeseNhc=
|
||||
github.com/alecthomas/units v0.0.0-20151022065526-2efee857e7cf/go.mod h1:ybxpYRFXyAe+OPACYpWeL0wqObRcbAqCMya13uyzqw0=
|
||||
github.com/armon/circbuf v0.0.0-20150827004946-bbbad097214e/go.mod h1:3U/XgcO3hCbHZ8TKRvWD2dDTCfh9M9ya+I9JpbB7O8o=
|
||||
github.com/armon/go-metrics v0.0.0-20180917152333-f0300d1749da/go.mod h1:Q73ZrmVTwzkszR9V5SSuryQ31EELlFMUz1kKyl939pY=
|
||||
github.com/armon/go-radix v0.0.0-20180808171621-7fddfc383310/go.mod h1:ufUuZ+zHj4x4TnLV4JWEpy2hxWSpsRywHrMgIH9cCH8=
|
||||
github.com/beorn7/perks v0.0.0-20180321164747-3a771d992973/go.mod h1:Dwedo/Wpr24TaqPxmxbtue+5NUziq4I4S80YR8gNf3Q=
|
||||
github.com/beorn7/perks v1.0.0/go.mod h1:KWe93zE9D1o94FZ5RNwFwVgaQK1VOXiVxmqh+CedLV8=
|
||||
github.com/bgentry/speakeasy v0.1.0/go.mod h1:+zsyZBPWlz7T6j88CTgSN5bM796AkVf0kBD4zp0CCIs=
|
||||
github.com/bitly/go-simplejson v0.5.0 h1:6IH+V8/tVMab511d5bn4M7EwGXZf9Hj6i2xSwkNEM+Y=
|
||||
github.com/bitly/go-simplejson v0.5.0/go.mod h1:cXHtHw4XUPsvGaxgjIAn8PhEWG9NfngEKAMDJEczWVA=
|
||||
github.com/bketelsen/crypt v0.0.3-0.20200106085610-5cbc8cc4026c/go.mod h1:MKsuJmJgSg28kpZDP6UIiPt0e0Oz0kqKNGyRaWEPv84=
|
||||
github.com/bmizerany/assert v0.0.0-20160611221934-b7ed37b82869 h1:DDGfHa7BWjL4YnC6+E63dPcxHo2sUxDIu8g3QgEJdRY=
|
||||
github.com/bmizerany/assert v0.0.0-20160611221934-b7ed37b82869/go.mod h1:Ekp36dRnpXw/yCqJaO+ZrUyxD+3VXMFFr56k5XYrpB4=
|
||||
github.com/cpuguy83/go-md2man/v2 v2.0.2/go.mod h1:tgQtvFlXSQOSOSIRvRPT7W67SCa46tRHOmNcaadrF8o=
|
||||
github.com/creack/pty v1.1.9/go.mod h1:oKZEueFk5CKHvIhNR5MUki03XCEU+Q6VDXinZuGJ33E=
|
||||
github.com/cespare/xxhash v1.1.0/go.mod h1:XrSqR1VqqWfGrhpAt58auRo0WTKS1nRRg3ghfAqPWnc=
|
||||
github.com/client9/misspell v0.3.4/go.mod h1:qj6jICC3Q7zFZvVWo7KLAzC3yx5G7kyvSDkc90ppPyw=
|
||||
github.com/coreos/bbolt v1.3.2/go.mod h1:iRUV2dpdMOn7Bo10OQBFzIJO9kkE559Wcmn+qkEiiKk=
|
||||
github.com/coreos/etcd v3.3.13+incompatible/go.mod h1:uF7uidLiAD3TWHmW31ZFd/JWoc32PjwdhPthX9715RE=
|
||||
github.com/coreos/go-semver v0.3.0/go.mod h1:nnelYz7RCh+5ahJtPPxZlU+153eP4D4r3EedlOD2RNk=
|
||||
github.com/coreos/go-systemd v0.0.0-20190321100706-95778dfbb74e/go.mod h1:F5haX7vjVVG0kc13fIWeqUViNPyEJxv/OmvnBo0Yme4=
|
||||
github.com/coreos/pkg v0.0.0-20180928190104-399ea9e2e55f/go.mod h1:E3G3o1h8I7cfcXa63jLwjI0eiQQMgzzUDFVpN/nH/eA=
|
||||
github.com/cpuguy83/go-md2man/v2 v2.0.0/go.mod h1:maD7wRr/U5Z6m/iR4s+kqSMx2CaBsrgA7czyZG/E6dU=
|
||||
github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
|
||||
github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
|
||||
github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
|
||||
github.com/dgrijalva/jwt-go v3.2.0+incompatible/go.mod h1:E3ru+11k8xSBh+hMPgOLZmtrrCbhqsmaPHjLKYnJCaQ=
|
||||
github.com/dgryski/go-sip13 v0.0.0-20181026042036-e10d5fee7954/go.mod h1:vAd38F8PWV+bWy6jNmig1y/TA+kYO4g3RSRF0IAv0no=
|
||||
github.com/fatih/color v1.7.0/go.mod h1:Zm6kSWBoL9eyXnKyktHP6abPY2pDugNf5KwzbycvMj4=
|
||||
github.com/fsnotify/fsnotify v1.4.7/go.mod h1:jwhsz4b93w/PPRr/qN1Yymfu8t87LnFCMoQvtojpjFo=
|
||||
github.com/ghodss/yaml v1.0.0/go.mod h1:4dBDuWmgqj2HViK6kFavaiC9ZROes6MMH2rRYeMEF04=
|
||||
github.com/go-gl/glfw v0.0.0-20190409004039-e6da0acd62b1/go.mod h1:vR7hzQXu2zJy9AVAgeJqvqgH9Q5CA+iKCZ2gyEVpxRU=
|
||||
github.com/go-kit/kit v0.8.0/go.mod h1:xBxKIO96dXMWWy0MnWVtmwkA9/13aqxPnvrjFYMA2as=
|
||||
github.com/go-logfmt/logfmt v0.3.0/go.mod h1:Qt1PoO58o5twSAckw1HlFXLmHsOX5/0LbT9GBnD5lWE=
|
||||
github.com/go-logfmt/logfmt v0.4.0/go.mod h1:3RMwSq7FuexP4Kalkev3ejPJsZTpXXBr9+V4qmtdjCk=
|
||||
github.com/go-stack/stack v1.8.0/go.mod h1:v0f6uXyyMGvRgIKkXu+yp6POWl0qKG85gN/melR3HDY=
|
||||
github.com/gogo/protobuf v1.1.1/go.mod h1:r8qH/GZQm5c6nD/R0oafs1akxWv10x8SbQlK7atdtwQ=
|
||||
github.com/gogo/protobuf v1.2.1/go.mod h1:hp+jE20tsWTFYpLwKvXlhS1hjn+gTNwPg2I6zVXpSg4=
|
||||
github.com/golang/glog v0.0.0-20160126235308-23def4e6c14b/go.mod h1:SBH7ygxi8pfUlaOkMMuAQtPIUF8ecWP5IEl/CR7VP2Q=
|
||||
github.com/golang/groupcache v0.0.0-20190129154638-5b532d6fd5ef/go.mod h1:cIg4eruTrX1D+g88fzRXU5OdNfaM+9IcxsU14FzY7Hc=
|
||||
github.com/golang/mock v1.1.1/go.mod h1:oTYuIxOrZwtPieC+H1uAHpcLFnEyAGVDL/k47Jfbm0A=
|
||||
github.com/golang/mock v1.2.0/go.mod h1:oTYuIxOrZwtPieC+H1uAHpcLFnEyAGVDL/k47Jfbm0A=
|
||||
github.com/golang/mock v1.3.1/go.mod h1:sBzyDLLjw3U8JLTeZvSv8jJB+tU5PVekmnlKIyFUx0Y=
|
||||
github.com/golang/protobuf v1.2.0/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
|
||||
github.com/golang/protobuf v1.3.1/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
|
||||
github.com/golang/protobuf v1.3.2/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
|
||||
github.com/google/btree v0.0.0-20180813153112-4030bb1f1f0c/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
|
||||
github.com/google/btree v1.0.0/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
|
||||
github.com/google/go-cmp v0.2.0/go.mod h1:oXzfMopK8JAjlY9xF4vHSVASa0yLyX7SntLO5aqRK0M=
|
||||
github.com/google/go-cmp v0.3.0/go.mod h1:8QqcDgzrUqlUb/G2PQTWiueGozuR1884gddMywk6iLU=
|
||||
github.com/google/martian v2.1.0+incompatible/go.mod h1:9I4somxYTbIHy5NJKHRl3wXiIaQGbYVAs8BPL6v8lEs=
|
||||
github.com/google/pprof v0.0.0-20181206194817-3ea8567a2e57/go.mod h1:zfwlbNMJ+OItoe0UupaVj+oy1omPYYDuagoSzA8v9mc=
|
||||
github.com/google/pprof v0.0.0-20190515194954-54271f7e092f/go.mod h1:zfwlbNMJ+OItoe0UupaVj+oy1omPYYDuagoSzA8v9mc=
|
||||
github.com/google/renameio v0.1.0/go.mod h1:KWCgfxg9yswjAJkECMjeO8J8rahYeXnNhOm40UhjYkI=
|
||||
github.com/googleapis/gax-go/v2 v2.0.4/go.mod h1:0Wqv26UfaUD9n4G6kQubkQ+KchISgw+vpHVxEJEs9eg=
|
||||
github.com/googleapis/gax-go/v2 v2.0.5/go.mod h1:DWXyrwAJ9X0FpwwEdw+IPEYBICEFu5mhpdKc/us6bOk=
|
||||
github.com/gopherjs/gopherjs v0.0.0-20181017120253-0766667cb4d1/go.mod h1:wJfORRmW1u3UXTncJ5qlYoELFm8eSnnEO6hX4iZ3EWY=
|
||||
github.com/gorilla/websocket v1.4.2/go.mod h1:YR8l580nyteQvAITg2hZ9XVh4b55+EU/adAjf1fMHhE=
|
||||
github.com/grpc-ecosystem/go-grpc-middleware v1.0.0/go.mod h1:FiyG127CGDf3tlThmgyCl78X/SZQqEOJBCDaAfeWzPs=
|
||||
github.com/grpc-ecosystem/go-grpc-prometheus v1.2.0/go.mod h1:8NvIoxWQoOIhqOTXgfV/d3M/q6VIi02HzZEHgUlZvzk=
|
||||
github.com/grpc-ecosystem/grpc-gateway v1.9.0/go.mod h1:vNeuVxBJEsws4ogUvrchl83t/GYV9WGTSLVdBhOQFDY=
|
||||
github.com/hashicorp/consul/api v1.1.0/go.mod h1:VmuI/Lkw1nC05EYQWNKwWGbkg+FbDBtguAZLlVdkD9Q=
|
||||
github.com/hashicorp/consul/sdk v0.1.1/go.mod h1:VKf9jXwCTEY1QZP2MOLRhb5i/I/ssyNV1vwHyQBF0x8=
|
||||
github.com/hashicorp/errwrap v1.0.0/go.mod h1:YH+1FKiLXxHSkmPseP+kNlulaMuP3n2brvKWEqk/Jc4=
|
||||
github.com/hashicorp/go-cleanhttp v0.5.1/go.mod h1:JpRdi6/HCYpAwUzNwuwqhbovhLtngrth3wmdIIUrZ80=
|
||||
github.com/hashicorp/go-immutable-radix v1.0.0/go.mod h1:0y9vanUI8NX6FsYoO3zeMjhV/C5i9g4Q3DwcSNZ4P60=
|
||||
github.com/hashicorp/go-msgpack v0.5.3/go.mod h1:ahLV/dePpqEmjfWmKiqvPkv/twdG7iPBM1vqhUKIvfM=
|
||||
github.com/hashicorp/go-multierror v1.0.0/go.mod h1:dHtQlpGsu+cZNNAkkCN/P3hoUDHhCYQXV3UM06sGGrk=
|
||||
github.com/hashicorp/go-rootcerts v1.0.0/go.mod h1:K6zTfqpRlCUIjkwsN4Z+hiSfzSTQa6eBIzfwKfwNnHU=
|
||||
github.com/hashicorp/go-sockaddr v1.0.0/go.mod h1:7Xibr9yA9JjQq1JpNB2Vw7kxv8xerXegt+ozgdvDeDU=
|
||||
github.com/hashicorp/go-syslog v1.0.0/go.mod h1:qPfqrKkXGihmCqbJM2mZgkZGvKG1dFdvsLplgctolz4=
|
||||
github.com/hashicorp/go-uuid v1.0.0/go.mod h1:6SBZvOh/SIDV7/2o3Jml5SYk/TvGqwFJ/bN7x4byOro=
|
||||
github.com/hashicorp/go-uuid v1.0.1/go.mod h1:6SBZvOh/SIDV7/2o3Jml5SYk/TvGqwFJ/bN7x4byOro=
|
||||
github.com/hashicorp/go.net v0.0.1/go.mod h1:hjKkEWcCURg++eb33jQU7oqQcI9XDCnUzHA0oac0k90=
|
||||
github.com/hashicorp/golang-lru v0.5.0/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ4Ao+sR/qLZy8=
|
||||
github.com/hashicorp/golang-lru v0.5.1/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ4Ao+sR/qLZy8=
|
||||
github.com/hashicorp/hcl v1.0.0/go.mod h1:E5yfLk+7swimpb2L/Alb/PJmXilQ/rhwaUYs4T20WEQ=
|
||||
github.com/hashicorp/logutils v1.0.0/go.mod h1:QIAnNjmIWmVIIkWDTG1z5v++HQmx9WQRO+LraFDTW64=
|
||||
github.com/hashicorp/mdns v1.0.0/go.mod h1:tL+uN++7HEJ6SQLQ2/p+z2pH24WQKWjBPkE0mNTz8vQ=
|
||||
github.com/hashicorp/memberlist v0.1.3/go.mod h1:ajVTdAv/9Im8oMAAj5G31PhhMCZJV2pPBoIllUwCN7I=
|
||||
github.com/hashicorp/serf v0.8.2/go.mod h1:6hOLApaqBFA1NXqRQAsxw9QxuDEvNxSQRwA/JwenrHc=
|
||||
github.com/inconshreveable/mousetrap v1.0.0 h1:Z8tu5sraLXCXIcARxBp/8cbvlwVa7Z1NHg9XEKhtSvM=
|
||||
github.com/inconshreveable/mousetrap v1.0.0/go.mod h1:PxqpIevigyE2G7u3NXJIT2ANytuPF1OarO4DADm73n8=
|
||||
github.com/jonboulle/clockwork v0.1.0/go.mod h1:Ii8DK3G1RaLaWxj9trq07+26W01tbo22gdxWY5EU2bo=
|
||||
github.com/json-iterator/go v1.1.6/go.mod h1:+SdeFBvtyEkXs7REEP0seUULqWtbJapLOCVDaaPEHmU=
|
||||
github.com/jstemmer/go-junit-report v0.0.0-20190106144839-af01ea7f8024/go.mod h1:6v2b51hI/fHJwM22ozAgKL4VKDeJcHhJFhtBdhmNjmU=
|
||||
github.com/jtolds/gls v4.20.0+incompatible/go.mod h1:QJZ7F/aHp+rZTRtaJ1ow/lLfFfVYBRgL+9YlvaHOwJU=
|
||||
github.com/julienschmidt/httprouter v1.2.0/go.mod h1:SYymIcj16QtmaHHD7aYtjjsJG7VTCxuUUipMqKk8s4w=
|
||||
github.com/kisielk/errcheck v1.1.0/go.mod h1:EZBBE59ingxPouuu3KfxchcWSUPOHkagtvWXihfKN4Q=
|
||||
github.com/kisielk/gotool v1.0.0/go.mod h1:XhKaO+MFFWcvkIS/tQcRk01m1F5IRFswLeQ+oQHNcck=
|
||||
github.com/konsorten/go-windows-terminal-sequences v1.0.1/go.mod h1:T0+1ngSBFLxvqU3pZ+m/2kptfBszLMUkC4ZK/EgS/cQ=
|
||||
github.com/kr/logfmt v0.0.0-20140226030751-b84e30acd515/go.mod h1:+0opPa2QZZtGFBFZlji/RkVcI2GknAs/DXo4wKdlNEc=
|
||||
github.com/kr/pretty v0.1.0 h1:L/CwN0zerZDmRFUapSPitk6f+Q3+0za1rQkzVuMiMFI=
|
||||
github.com/kr/pretty v0.1.0/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
|
||||
github.com/kr/pretty v0.3.0 h1:WgNl7dwNpEZ6jJ9k1snq4pZsg7DOEN8hP9Xw0Tsjwk0=
|
||||
github.com/kr/pretty v0.3.0/go.mod h1:640gp4NfQd8pI5XOwp5fnNeVWj67G7CFk/SaSQn7NBk=
|
||||
github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
|
||||
github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
|
||||
github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
|
||||
github.com/kr/text v0.2.0 h1:5Nx0Ya0ZqY2ygV366QzturHI13Jq95ApcVaJBhpS+AY=
|
||||
github.com/kr/text v0.2.0/go.mod h1:eLer722TekiGuMkidMxC/pM04lWEeraHUUmBw8l2grE=
|
||||
github.com/magiconair/properties v1.8.1/go.mod h1:PppfXfuXeibc/6YijjN8zIbojt8czPbwD3XqdrwzmxQ=
|
||||
github.com/mattn/go-colorable v0.0.9/go.mod h1:9vuHe8Xs5qXnSaW/c/ABM9alt+Vo+STaOChaDxuIBZU=
|
||||
github.com/mattn/go-isatty v0.0.3/go.mod h1:M+lRXTBqGeGNdLjl/ufCoiOlB5xdOkqRJdNxMWT7Zi4=
|
||||
github.com/matttproud/golang_protobuf_extensions v1.0.1/go.mod h1:D8He9yQNgCq6Z5Ld7szi9bcBfOoFv/3dc6xSMkL2PC0=
|
||||
github.com/miekg/dns v1.0.14/go.mod h1:W1PPwlIAgtquWBMBEV9nkV9Cazfe8ScdGz/Lj7v3Nrg=
|
||||
github.com/mitchellh/cli v1.0.0/go.mod h1:hNIlj7HEI86fIcpObd7a0FcrxTWetlwJDGcceTlRvqc=
|
||||
github.com/mitchellh/go-homedir v1.0.0/go.mod h1:SfyaCUpYCn1Vlf4IUYiD9fPX4A5wJrkLzIz1N1q0pr0=
|
||||
github.com/mitchellh/go-homedir v1.1.0/go.mod h1:SfyaCUpYCn1Vlf4IUYiD9fPX4A5wJrkLzIz1N1q0pr0=
|
||||
github.com/mitchellh/go-testing-interface v1.0.0/go.mod h1:kRemZodwjscx+RGhAo8eIhFbs2+BFgRtFPeD/KE+zxI=
|
||||
github.com/mitchellh/gox v0.4.0/go.mod h1:Sd9lOJ0+aimLBi73mGofS1ycjY8lL3uZM3JPS42BGNg=
|
||||
github.com/mitchellh/iochan v1.0.0/go.mod h1:JwYml1nuB7xOzsp52dPpHFffvOCDupsG0QubkSMEySY=
|
||||
github.com/mitchellh/mapstructure v0.0.0-20160808181253-ca63d7c062ee/go.mod h1:FVVH3fgwuzCH5S8UJGiWEs2h04kUh9fWfEaFds41c1Y=
|
||||
github.com/mitchellh/mapstructure v1.1.2/go.mod h1:FVVH3fgwuzCH5S8UJGiWEs2h04kUh9fWfEaFds41c1Y=
|
||||
github.com/modern-go/concurrent v0.0.0-20180306012644-bacd9c7ef1dd/go.mod h1:6dJC0mAP4ikYIbvyc7fijjWJddQyLn8Ig3JB5CqoB9Q=
|
||||
github.com/modern-go/reflect2 v1.0.1/go.mod h1:bx2lNnkwVCuqBIxFjflWJWanXIb3RllmbCylyMrvgv0=
|
||||
github.com/mozillazg/request v0.8.0 h1:TbXeQUdBWr1J1df5Z+lQczDFzX9JD71kTCl7Zu/9rNM=
|
||||
github.com/mozillazg/request v0.8.0/go.mod h1:weoQ/mVFNbWgRBtivCGF1tUT9lwneFesues+CleXMWc=
|
||||
github.com/mwitkow/go-conntrack v0.0.0-20161129095857-cc309e4a2223/go.mod h1:qRWi+5nqEBWmkhHvq77mSJWrCKwh8bxhgT7d/eI7P4U=
|
||||
github.com/oklog/ulid v1.3.1/go.mod h1:CirwcVhetQ6Lv90oh/F+FBtV6XMibvdAFo93nm5qn4U=
|
||||
github.com/pascaldekloe/goe v0.0.0-20180627143212-57f6aae5913c/go.mod h1:lzWF7FIEvWOWxwDKqyGYQf6ZUaNfKdP144TG7ZOy1lc=
|
||||
github.com/pelletier/go-toml v1.2.0/go.mod h1:5z9KED0ma1S8pY6P1sdut58dfprrGBbd/94hg7ilaic=
|
||||
github.com/pkg/errors v0.8.0/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
|
||||
github.com/pkg/errors v0.8.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
|
||||
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
|
||||
github.com/rogpeppe/go-internal v1.6.1 h1:/FiVV8dS/e+YqF2JvO3yXRFbBLTIuSDkuC7aBOAvL+k=
|
||||
github.com/rogpeppe/go-internal v1.6.1/go.mod h1:xXDCJY+GAPziupqXw64V24skbSoqbTEfhy4qGm1nDQc=
|
||||
github.com/russross/blackfriday/v2 v2.1.0/go.mod h1:+Rmxgy9KzJVeS9/2gXHxylqXiyQDYRxCVz55jmeOWTM=
|
||||
github.com/spf13/cobra v1.5.0 h1:X+jTBEBqF0bHN+9cSMgmfuvv2VHJ9ezmFNf9Y/XstYU=
|
||||
github.com/spf13/cobra v1.5.0/go.mod h1:dWXEIy2H428czQCjInthrTRUg7yKbok+2Qi/yBIJoUM=
|
||||
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
|
||||
github.com/posener/complete v1.1.1/go.mod h1:em0nMJCgc9GFtwrmVmEMR/ZL6WyhyjMBndrE9hABlRI=
|
||||
github.com/prometheus/client_golang v0.9.1/go.mod h1:7SWBe2y4D6OKWSNQJUaRYU/AaXPKyh/dDVn+NZz0KFw=
|
||||
github.com/prometheus/client_golang v0.9.3/go.mod h1:/TN21ttK/J9q6uSwhBd54HahCDft0ttaMvbicHlPoso=
|
||||
github.com/prometheus/client_model v0.0.0-20180712105110-5c3871d89910/go.mod h1:MbSGuTsp3dbXC40dX6PRTWyKYBIrTGTE9sqQNg2J8bo=
|
||||
github.com/prometheus/client_model v0.0.0-20190129233127-fd36f4220a90/go.mod h1:xMI15A0UPsDsEKsMN9yxemIoYk6Tm2C1GtYGdfGttqA=
|
||||
github.com/prometheus/common v0.0.0-20181113130724-41aa239b4cce/go.mod h1:daVV7qP5qjZbuso7PdcryaAu0sAZbrN9i7WWcTMWvro=
|
||||
github.com/prometheus/common v0.4.0/go.mod h1:TNfzLD0ON7rHzMJeJkieUDPYmFC7Snx/y86RQel1bk4=
|
||||
github.com/prometheus/procfs v0.0.0-20181005140218-185b4288413d/go.mod h1:c3At6R/oaqEKCNdg8wHV1ftS6bRYblBhIjjI8uT2IGk=
|
||||
github.com/prometheus/procfs v0.0.0-20190507164030-5867b95ac084/go.mod h1:TjEm7ze935MbeOT/UhFTIMYKhuLP4wbCsTZCD3I8kEA=
|
||||
github.com/prometheus/tsdb v0.7.1/go.mod h1:qhTCs0VvXwvX/y3TZrWD7rabWM+ijKTux40TwIPHuXU=
|
||||
github.com/rogpeppe/fastuuid v0.0.0-20150106093220-6724a57986af/go.mod h1:XWv6SoW27p1b0cqNHllgS5HIMJraePCO15w5zCzIWYg=
|
||||
github.com/rogpeppe/go-internal v1.3.0/go.mod h1:M8bDsm7K2OlrFYOpmOWEs/qY81heoFRclV5y23lUDJ4=
|
||||
github.com/russross/blackfriday/v2 v2.0.1/go.mod h1:+Rmxgy9KzJVeS9/2gXHxylqXiyQDYRxCVz55jmeOWTM=
|
||||
github.com/ryanuber/columnize v0.0.0-20160712163229-9b3edd62028f/go.mod h1:sm1tb6uqfes/u+d4ooFouqFdy9/2g9QGwK3SQygK0Ts=
|
||||
github.com/sean-/seed v0.0.0-20170313163322-e2103e2c3529/go.mod h1:DxrIzT+xaE7yg65j358z/aeFdxmN0P9QXhEzd20vsDc=
|
||||
github.com/shurcooL/sanitized_anchor_name v1.0.0/go.mod h1:1NzhyTcUVG4SuEtjjoZeVRXNmyL/1OwPU0+IJeTBvfc=
|
||||
github.com/sirupsen/logrus v1.2.0/go.mod h1:LxeOpSwHxABJmUn/MG1IvRgCAasNZTLOkJPxbbu5VWo=
|
||||
github.com/smartystreets/assertions v0.0.0-20180927180507-b2de0cb4f26d/go.mod h1:OnSkiWE9lh6wB0YB77sQom3nweQdgAjqCqsofrRNTgc=
|
||||
github.com/smartystreets/goconvey v1.6.4/go.mod h1:syvi0/a8iFYH4r/RixwvyeAJjdLS9QV7WQ/tjFTllLA=
|
||||
github.com/soheilhy/cmux v0.1.4/go.mod h1:IM3LyeVVIOuxMH7sFAkER9+bJ4dT7Ms6E4xg4kGIyLM=
|
||||
github.com/spaolacci/murmur3 v0.0.0-20180118202830-f09979ecbc72/go.mod h1:JwIasOWyU6f++ZhiEuf87xNszmSA2myDM2Kzu9HwQUA=
|
||||
github.com/spf13/afero v1.1.2/go.mod h1:j4pytiNVoe2o6bmDsKpLACNPDBIoEAkihy7loJ1B0CQ=
|
||||
github.com/spf13/cast v1.3.0/go.mod h1:Qx5cxh0v+4UWYiBimWS+eyWzqEqokIECu5etghLkUJE=
|
||||
github.com/spf13/cobra v1.1.1 h1:KfztREH0tPxJJ+geloSLaAkaPkr4ki2Er5quFV1TDo4=
|
||||
github.com/spf13/cobra v1.1.1/go.mod h1:WnodtKOvamDL/PwE2M4iKs8aMDBZ5Q5klgD3qfVJQMI=
|
||||
github.com/spf13/jwalterweatherman v1.0.0/go.mod h1:cQK4TGJAtQXfYWX+Ddv3mKDzgVb68N+wFjFa4jdeBTo=
|
||||
github.com/spf13/pflag v1.0.3/go.mod h1:DYY7MBk1bdzusC3SYhjObp+wFpr4gzcvqqNjLnInEg4=
|
||||
github.com/spf13/pflag v1.0.5 h1:iy+VFUOCP1a+8yFto/drg2CJ5u0yRoB7fZw3DKv/JXA=
|
||||
github.com/spf13/pflag v1.0.5/go.mod h1:McXfInJRrz4CZXVZOBLb0bTZqETkiAhM9Iw0y3An2Bg=
|
||||
github.com/stretchr/testify v1.8.0 h1:pSgiaMZlXftHpm5L7V1+rVB+AZJydKsMxsQBIJw4PKk=
|
||||
golang.org/x/net v0.17.0 h1:pVaXccu2ozPjCXewfr1S7xza/zcXTity9cCdXQYSjIM=
|
||||
golang.org/x/net v0.17.0/go.mod h1:NxSsAGuq816PNPmqtQdLE42eU2Fs7NoRIZrHJAlaCOE=
|
||||
github.com/spf13/viper v1.7.0/go.mod h1:8WkrPz2fc9jxqZNCJI/76HCieCp4Q8HaLFoCha5qpdg=
|
||||
github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
|
||||
github.com/stretchr/objx v0.1.1/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
|
||||
github.com/stretchr/testify v1.2.2/go.mod h1:a8OnRcib4nhh0OaRAV+Yts87kKdq0PP7pXfy6kDkUVs=
|
||||
github.com/stretchr/testify v1.3.0 h1:TivCn/peBQ7UY8ooIcPgZFpTNSz0Q2U6UrFlUfqbe0Q=
|
||||
github.com/stretchr/testify v1.3.0/go.mod h1:M5WIy9Dh21IEIfnGCwXGc5bZfKNJtfHm1UVUgZn+9EI=
|
||||
github.com/subosito/gotenv v1.2.0/go.mod h1:N0PQaV/YGNqwC0u51sEeR/aUtSLEXKX9iv69rRypqCw=
|
||||
github.com/tmc/grpc-websocket-proxy v0.0.0-20190109142713-0ad062ec5ee5/go.mod h1:ncp9v5uamzpCO7NfCPTXjqaC+bZgJeR0sMTm6dMHP7U=
|
||||
github.com/xiang90/probing v0.0.0-20190116061207-43a291ad63a2/go.mod h1:UETIi67q53MR2AWcXfiuqkDkRtnGDLqkBTpCHuJHxtU=
|
||||
go.etcd.io/bbolt v1.3.2/go.mod h1:IbVyRI1SCnLcuJnV2u8VeU0CEYM7e686BmAb1XKL+uU=
|
||||
go.opencensus.io v0.21.0/go.mod h1:mSImk1erAIZhrmZN+AvHh14ztQfjbGwt4TtuofqLduU=
|
||||
go.opencensus.io v0.22.0/go.mod h1:+kGneAE2xo2IficOXnaByMWTGM9T73dGwxeWcUqIpI8=
|
||||
go.uber.org/atomic v1.4.0/go.mod h1:gD2HeocX3+yG+ygLZcrzQJaqmWj9AIm7n08wl/qW/PE=
|
||||
go.uber.org/multierr v1.1.0/go.mod h1:wR5kodmAFQ0UK8QlbwjlSNy0Z68gJhDJUG5sjR94q/0=
|
||||
go.uber.org/zap v1.10.0/go.mod h1:vwi/ZaCAaUcBkycHslxD9B2zi4UTXhF60s6SWpuDF0Q=
|
||||
golang.org/x/crypto v0.0.0-20180904163835-0709b304e793/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
|
||||
golang.org/x/crypto v0.0.0-20181029021203-45a5f77698d3/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
|
||||
golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
|
||||
golang.org/x/crypto v0.0.0-20190510104115-cbcb75029529/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
|
||||
golang.org/x/crypto v0.0.0-20190605123033-f99c8df09eb5/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
|
||||
golang.org/x/crypto v0.0.0-20200622213623-75b288015ac9/go.mod h1:LzIPMQfyMNhhGPhUkYOs5KpL4U8rLKemX1yGLhDgUto=
|
||||
golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
|
||||
golang.org/x/exp v0.0.0-20190306152737-a1d7652674e8/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
|
||||
golang.org/x/exp v0.0.0-20190510132918-efd6b22b2522/go.mod h1:ZjyILWgesfNpC6sMxTJOJm9Kp84zZh5NQWvqDGG3Qr8=
|
||||
golang.org/x/exp v0.0.0-20190829153037-c13cbed26979/go.mod h1:86+5VVa7VpoJ4kLfm080zCjGlMRFzhUhsZKEZO7MGek=
|
||||
golang.org/x/exp v0.0.0-20191030013958-a1ab85dbe136/go.mod h1:JXzH8nQsPlswgeRAPE3MuO9GYsAcnJvJ4vnMwN/5qkY=
|
||||
golang.org/x/image v0.0.0-20190227222117-0694c2d4d067/go.mod h1:kZ7UVZpmo3dzQBMxlp+ypCbDeSB+sBbTgSJuh5dn5js=
|
||||
golang.org/x/image v0.0.0-20190802002840-cff245a6509b/go.mod h1:FeLwcggjj3mMvU+oOTbSwawSJRM1uh48EjtB4UJZlP0=
|
||||
golang.org/x/lint v0.0.0-20181026193005-c67002cb31c3/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
|
||||
golang.org/x/lint v0.0.0-20190227174305-5b3e6a55c961/go.mod h1:wehouNa3lNwaWXcvxsM5YxQ5yQlVC4a0KAMCusXpPoU=
|
||||
golang.org/x/lint v0.0.0-20190301231843-5614ed5bae6f/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
|
||||
golang.org/x/lint v0.0.0-20190313153728-d0100b6bd8b3/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
|
||||
golang.org/x/lint v0.0.0-20190409202823-959b441ac422/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
|
||||
golang.org/x/lint v0.0.0-20190909230951-414d861bb4ac/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
|
||||
golang.org/x/lint v0.0.0-20190930215403-16217165b5de/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
|
||||
golang.org/x/mobile v0.0.0-20190312151609-d3739f865fa6/go.mod h1:z+o9i4GpDbdi3rU15maQ/Ox0txvL9dWGYEHz965HBQE=
|
||||
golang.org/x/mobile v0.0.0-20190719004257-d2bd2a29d028/go.mod h1:E/iHnbuqvinMTCcRqshq8CkpyQDoeVncDDYHnLhea+o=
|
||||
golang.org/x/mod v0.0.0-20190513183733-4bf6d317e70e/go.mod h1:mXi4GBBbnImb6dmsKGUJ2LatrhH/nqhxcFungHvyanc=
|
||||
golang.org/x/mod v0.1.0/go.mod h1:0QHyrYULN0/3qlju5TqG8bIK38QM8yzMo5ekMj3DlcY=
|
||||
golang.org/x/net v0.0.0-20180724234803-3673e40ba225/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20180826012351-8a410e7b638d/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20181023162649-9b4f9f5ad519/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20181114220301-adae6a3d119a/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20181201002055-351d144fa1fc/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20181220203305-927f97764cc3/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20190108225652-1e06a53dbb7e/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20190213061140-3a22650c66bd/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
|
||||
golang.org/x/net v0.0.0-20190311183353-d8887717615a/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
|
||||
golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
|
||||
golang.org/x/net v0.0.0-20190501004415-9ce7a6920f09/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
|
||||
golang.org/x/net v0.0.0-20190503192946-f4e77d36d62c/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
|
||||
golang.org/x/net v0.0.0-20190603091049-60506f45cf65/go.mod h1:HSz+uSET+XFnRR8LxR5pz3Of3rY3CfYBVs4xY44aLks=
|
||||
golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
|
||||
golang.org/x/net v0.0.0-20201021035429-f5854403a974 h1:IX6qOQeG5uLjB/hjjwjedwfjND0hgjPMMyO1RoIXQNI=
|
||||
golang.org/x/net v0.0.0-20201021035429-f5854403a974/go.mod h1:sp8m0HH+o8qH0wwXwYZr8TS3Oi6o0r6Gce1SSxlDquU=
|
||||
golang.org/x/oauth2 v0.0.0-20180821212333-d2e6202438be/go.mod h1:N/0e6XlmueqKjAGxoOufVs8QHGRruUQn6yWY3a++T0U=
|
||||
golang.org/x/oauth2 v0.0.0-20190226205417-e64efc72b421/go.mod h1:gOpvHmFTYa4IltrdGE7lF6nIHvwfUNPOp7c8zoXwtLw=
|
||||
golang.org/x/oauth2 v0.0.0-20190604053449-0f29369cfe45/go.mod h1:gOpvHmFTYa4IltrdGE7lF6nIHvwfUNPOp7c8zoXwtLw=
|
||||
golang.org/x/sync v0.0.0-20180314180146-1d60e4601c6f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
|
||||
golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
|
||||
golang.org/x/sync v0.0.0-20181221193216-37e7f081c4d4/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
|
||||
golang.org/x/sync v0.0.0-20190227155943-e225da77a7e6/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
|
||||
golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
|
||||
golang.org/x/sys v0.0.0-20180823144017-11551d06cbcc/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20180830151530-49385e6e1522/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20180905080454-ebe1bf3edb33/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20181026203630-95b1ffbd15a5/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20181107165924-66b7b1311ac8/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20181116152217-5ac8a444bdc5/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
|
||||
golang.org/x/sys v0.0.0-20190312061237-fead79001313/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20190502145724-3ef323f4f1fd/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20190507160741-ecd444e8653b/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20190606165138-5da285871e9c/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20190624142023-c5567b49c5d0/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/sys v0.0.0-20200930185726-fdedc70b468f/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
|
||||
golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
|
||||
golang.org/x/text v0.3.1-0.20180807135948-17ff2d5776d2/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
|
||||
golang.org/x/text v0.3.2/go.mod h1:bEr9sfX3Q8Zfm5fL9x+3itogRgK3+ptLWKqgva+5dAk=
|
||||
golang.org/x/text v0.3.3/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
|
||||
golang.org/x/time v0.0.0-20181108054448-85acf8d2951c/go.mod h1:tRJNPiyCQ0inRvYxbN9jk5I+vvW/OXSQhTDSoE431IQ=
|
||||
golang.org/x/time v0.0.0-20190308202827-9d24e82272b4/go.mod h1:tRJNPiyCQ0inRvYxbN9jk5I+vvW/OXSQhTDSoE431IQ=
|
||||
golang.org/x/tools v0.0.0-20180221164845-07fd8470d635/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
|
||||
golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
|
||||
golang.org/x/tools v0.0.0-20190114222345-bf090417da8b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
|
||||
golang.org/x/tools v0.0.0-20190226205152-f727befe758c/go.mod h1:9Yl7xja0Znq3iFh3HoIrodX9oNMXvdceNzlUR8zjMvY=
|
||||
golang.org/x/tools v0.0.0-20190311212946-11955173bddd/go.mod h1:LCzVGOaR6xXOjkQ3onu1FJEFr0SW1gC7cKk1uF8kGRs=
|
||||
golang.org/x/tools v0.0.0-20190312151545-0bb0c0a6e846/go.mod h1:LCzVGOaR6xXOjkQ3onu1FJEFr0SW1gC7cKk1uF8kGRs=
|
||||
golang.org/x/tools v0.0.0-20190312170243-e65039ee4138/go.mod h1:LCzVGOaR6xXOjkQ3onu1FJEFr0SW1gC7cKk1uF8kGRs=
|
||||
golang.org/x/tools v0.0.0-20190328211700-ab21143f2384/go.mod h1:LCzVGOaR6xXOjkQ3onu1FJEFr0SW1gC7cKk1uF8kGRs=
|
||||
golang.org/x/tools v0.0.0-20190425150028-36563e24a262/go.mod h1:RgjU9mgBXZiqYHBnxXauZ1Gv1EHHAz9KjViQ78xBX0Q=
|
||||
golang.org/x/tools v0.0.0-20190506145303-2d16b83fe98c/go.mod h1:RgjU9mgBXZiqYHBnxXauZ1Gv1EHHAz9KjViQ78xBX0Q=
|
||||
golang.org/x/tools v0.0.0-20190606124116-d0a3d012864b/go.mod h1:/rFqwRUd4F7ZHNgwSSTFct+R/Kf4OFW1sUzUTQQTgfc=
|
||||
golang.org/x/tools v0.0.0-20190621195816-6e04913cbbac/go.mod h1:/rFqwRUd4F7ZHNgwSSTFct+R/Kf4OFW1sUzUTQQTgfc=
|
||||
golang.org/x/tools v0.0.0-20190628153133-6cdbf07be9d0/go.mod h1:/rFqwRUd4F7ZHNgwSSTFct+R/Kf4OFW1sUzUTQQTgfc=
|
||||
golang.org/x/tools v0.0.0-20190816200558-6889da9d5479/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
|
||||
golang.org/x/tools v0.0.0-20190911174233-4f2ddba30aff/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
|
||||
golang.org/x/tools v0.0.0-20191012152004-8de300cfc20a/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
|
||||
golang.org/x/tools v0.0.0-20191112195655-aa38f8e97acc/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
|
||||
golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
|
||||
google.golang.org/api v0.4.0/go.mod h1:8k5glujaEP+g9n7WNsDg8QP6cUVNI86fCNMcbazEtwE=
|
||||
google.golang.org/api v0.7.0/go.mod h1:WtwebWUNSVBH/HAw79HIFXZNqEvBhG+Ra+ax0hx3E3M=
|
||||
google.golang.org/api v0.8.0/go.mod h1:o4eAsZoiT+ibD93RtjEohWalFOjRDx6CVaqeizhEnKg=
|
||||
google.golang.org/api v0.9.0/go.mod h1:o4eAsZoiT+ibD93RtjEohWalFOjRDx6CVaqeizhEnKg=
|
||||
google.golang.org/api v0.13.0/go.mod h1:iLdEw5Ide6rF15KTC1Kkl0iskquN2gFfn9o9XIsbkAI=
|
||||
google.golang.org/appengine v1.1.0/go.mod h1:EbEs0AVv82hx2wNQdGPgUI5lhzA/G0D9YwlJXL52JkM=
|
||||
google.golang.org/appengine v1.4.0/go.mod h1:xpcJRLb0r/rnEns0DIKYYv+WjYCduHsrkT7/EB5XEv4=
|
||||
google.golang.org/appengine v1.5.0/go.mod h1:xpcJRLb0r/rnEns0DIKYYv+WjYCduHsrkT7/EB5XEv4=
|
||||
google.golang.org/appengine v1.6.1/go.mod h1:i06prIuMbXzDqacNJfV5OdTW448YApPu5ww/cMBSeb0=
|
||||
google.golang.org/genproto v0.0.0-20180817151627-c66870c02cf8/go.mod h1:JiN7NxoALGmiZfu7CAH4rXhgtRTLTxftemlI0sWmxmc=
|
||||
google.golang.org/genproto v0.0.0-20190307195333-5fe7a883aa19/go.mod h1:VzzqZJRnGkLBvHegQrXjBqPurQTc5/KpmUdxsrq26oE=
|
||||
google.golang.org/genproto v0.0.0-20190418145605-e7d98fc518a7/go.mod h1:VzzqZJRnGkLBvHegQrXjBqPurQTc5/KpmUdxsrq26oE=
|
||||
google.golang.org/genproto v0.0.0-20190425155659-357c62f0e4bb/go.mod h1:VzzqZJRnGkLBvHegQrXjBqPurQTc5/KpmUdxsrq26oE=
|
||||
google.golang.org/genproto v0.0.0-20190502173448-54afdca5d873/go.mod h1:VzzqZJRnGkLBvHegQrXjBqPurQTc5/KpmUdxsrq26oE=
|
||||
google.golang.org/genproto v0.0.0-20190801165951-fa694d86fc64/go.mod h1:DMBHOl98Agz4BDEuKkezgsaosCRResVns1a3J2ZsMNc=
|
||||
google.golang.org/genproto v0.0.0-20190819201941-24fa4b261c55/go.mod h1:DMBHOl98Agz4BDEuKkezgsaosCRResVns1a3J2ZsMNc=
|
||||
google.golang.org/genproto v0.0.0-20190911173649-1774047e7e51/go.mod h1:IbNlFCBrqXvoKpeg0TB2l7cyZUmoaFKYIwrEpbDKLA8=
|
||||
google.golang.org/genproto v0.0.0-20191108220845-16a3f7862a1a/go.mod h1:n3cpQtvxv34hfy77yVDNjmbRyujviMdxYliBSkLhpCc=
|
||||
google.golang.org/grpc v1.19.0/go.mod h1:mqu4LbDTu4XGKhr4mRzUsmM4RtVoemTSY81AxZiDr8c=
|
||||
google.golang.org/grpc v1.20.1/go.mod h1:10oTOabMzJvdu6/UiuZezV6QK5dSlG84ov/aaiqXj38=
|
||||
google.golang.org/grpc v1.21.1/go.mod h1:oYelfM1adQP15Ek0mdvEgi9Df8B9CZIaU1084ijfRaM=
|
||||
gopkg.in/alecthomas/kingpin.v2 v2.2.6/go.mod h1:FMv+mEhP44yOT+4EoQTLFTRgOQ1FBLkstjWtayDeSgw=
|
||||
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
|
||||
gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
|
||||
gopkg.in/errgo.v2 v2.1.0/go.mod h1:hNsd1EY+bozCKY1Ytp96fpM3vjJbqLJn88ws8XvfDNI=
|
||||
gopkg.in/yaml.v2 v2.4.0/go.mod h1:RDklbk79AGWmwhnvt/jBztapEOGDOx6ZbXqjP6csGnQ=
|
||||
gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
|
||||
gopkg.in/ini.v1 v1.51.0/go.mod h1:pNLf8WUiyNEtQjuu5G5vTm06TEv9tsIgeAvK8hOrP4k=
|
||||
gopkg.in/resty.v1 v1.12.0/go.mod h1:mDo4pnntr5jdWRML875a/NmxYqAlA73dVijT2AXvQQo=
|
||||
gopkg.in/yaml.v2 v2.0.0-20170812160011-eb3733d160e7/go.mod h1:JAlM8MvJe8wmxCU4Bli9HhUf9+ttbYbLASfIpnQbh74=
|
||||
gopkg.in/yaml.v2 v2.2.1/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
|
||||
gopkg.in/yaml.v2 v2.2.4/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
|
||||
gopkg.in/yaml.v2 v2.2.8/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
|
||||
honnef.co/go/tools v0.0.0-20190102054323-c2f93a96b099/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
|
||||
honnef.co/go/tools v0.0.0-20190106161140-3f1c8253044a/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
|
||||
honnef.co/go/tools v0.0.0-20190418001031-e561f6794a2a/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
|
||||
honnef.co/go/tools v0.0.1-2019.2.3/go.mod h1:a3bituU0lyd329TUQxRnasdCoJDkEUEAqEt0JzvZhAg=
|
||||
rsc.io/binaryregexp v0.2.0/go.mod h1:qTv7/COck+e2FymRvadv62gMdZztPaShugOCi3I+8D8=
|
||||
|
@ -8,7 +8,7 @@ func lengthOfLongestSubstring(s string) int {
|
||||
var bitSet [256]bool
|
||||
result, left, right := 0, 0, 0
|
||||
for left < len(s) {
|
||||
// 右侧字符对应的 bitSet 被标记 true,说明此字符在 X 位置重复,需要左侧向前移动,直到将 X 标记为 false
|
||||
// 右侧字符对应的bitSet被标记true,说明此字符在X位置重复,需要左侧向前移动,直到将X标记为false
|
||||
if bitSet[s[right]] {
|
||||
bitSet[s[left]] = false
|
||||
left++
|
||||
@ -27,20 +27,19 @@ func lengthOfLongestSubstring(s string) int {
|
||||
}
|
||||
|
||||
// 解法二 滑动窗口
|
||||
func lengthOfLongestSubstring1(s string) int {
|
||||
func lengthOfLongestSubstring_(s string) int {
|
||||
if len(s) == 0 {
|
||||
return 0
|
||||
}
|
||||
var freq [127]int
|
||||
var freq [256]int
|
||||
result, left, right := 0, 0, -1
|
||||
|
||||
for left < len(s) {
|
||||
if right+1 < len(s) && freq[s[right+1]] == 0 {
|
||||
freq[s[right+1]]++
|
||||
if right+1 < len(s) && freq[s[right+1]-'a'] == 0 {
|
||||
freq[s[right+1]-'a']++
|
||||
right++
|
||||
|
||||
} else {
|
||||
freq[s[left]]--
|
||||
freq[s[left]-'a']--
|
||||
left++
|
||||
}
|
||||
result = max(result, right-left+1)
|
||||
@ -48,21 +47,6 @@ func lengthOfLongestSubstring1(s string) int {
|
||||
return result
|
||||
}
|
||||
|
||||
// 解法三 滑动窗口-哈希桶
|
||||
func lengthOfLongestSubstring2(s string) int {
|
||||
right, left, res := 0, 0, 0
|
||||
indexes := make(map[byte]int, len(s))
|
||||
for left < len(s) {
|
||||
if idx, ok := indexes[s[left]]; ok && idx >= right {
|
||||
right = idx + 1
|
||||
}
|
||||
indexes[s[left]] = left
|
||||
left++
|
||||
res = max(res, left-right)
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
func max(a int, b int) int {
|
||||
if a > b {
|
||||
return a
|
||||
|
@ -51,7 +51,7 @@ func Test_Problem3(t *testing.T) {
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans3, q.para3
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, lengthOfLongestSubstring(p.s))
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, lengthOfLongestSubstring_(p.s))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
||||
|
@ -34,7 +34,7 @@ Explanation: The answer is "wke", with the length of 3.
|
||||
## 题目大意
|
||||
|
||||
|
||||
在一个字符串中寻找没有重复字母的最长子串。
|
||||
在一个字符串重寻找没有重复字母的最长子串。
|
||||
|
||||
## 解题思路
|
||||
|
||||
|
@ -39,7 +39,7 @@ You may assume **nums1** and **nums2** cannot be both empty.
|
||||
|
||||
|
||||
- 给出两个有序数组,要求找出这两个数组合并以后的有序数组中的中位数。要求时间复杂度为 O(log (m+n))。
|
||||
- 这一题最容易想到的办法是把两个数组合并,然后取出中位数。但是合并有序数组的操作是 `O(m+n)` 的,不符合题意。看到题目给的 `log` 的时间复杂度,很容易联想到二分搜索。
|
||||
- 这一题最容易想到的办法是把两个数组合并,然后取出中位数。但是合并有序数组的操作是 `O(max(n,m))` 的,不符合题意。看到题目给的 `log` 的时间复杂度,很容易联想到二分搜索。
|
||||
- 由于要找到最终合并以后数组的中位数,两个数组的总大小也知道,所以中间这个位置也是知道的。只需要二分搜索一个数组中切分的位置,另一个数组中切分的位置也能得到。为了使得时间复杂度最小,所以二分搜索两个数组中长度较小的那个数组。
|
||||
- 关键的问题是如何切分数组 1 和数组 2 。其实就是如何切分数组 1 。先随便二分产生一个 `midA`,切分的线何时算满足了中位数的条件呢?即,线左边的数都小于右边的数,即,`nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA]` 。如果这些条件都不满足,切分线就需要调整。如果 `nums1[midA] < nums2[midB-1]`,说明 `midA` 这条线划分出来左边的数小了,切分线应该右移;如果 `nums1[midA-1] > nums2[midB]`,说明 midA 这条线划分出来左边的数大了,切分线应该左移。经过多次调整以后,切分线总能找到满足条件的解。
|
||||
- 假设现在找到了切分的两条线了,`数组 1` 在切分线两边的下标分别是 `midA - 1` 和 `midA`。`数组 2` 在切分线两边的下标分别是 `midB - 1` 和 `midB`。最终合并成最终数组,如果数组长度是奇数,那么中位数就是 `max(nums1[midA-1], nums2[midB-1])`。如果数组长度是偶数,那么中间位置的两个数依次是:`max(nums1[midA-1], nums2[midB-1])` 和 `min(nums1[midA], nums2[midB])`,那么中位数就是 `(max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2`。图示见下图:
|
||||
|
@ -1,117 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
// 解法一 Manacher's algorithm,时间复杂度 O(n),空间复杂度 O(n)
|
||||
func longestPalindrome(s string) string {
|
||||
if len(s) < 2 {
|
||||
return s
|
||||
}
|
||||
newS := make([]rune, 0)
|
||||
newS = append(newS, '#')
|
||||
for _, c := range s {
|
||||
newS = append(newS, c)
|
||||
newS = append(newS, '#')
|
||||
}
|
||||
// dp[i]: 以预处理字符串下标 i 为中心的回文半径(奇数长度时不包括中心)
|
||||
// maxRight: 通过中心扩散的方式能够扩散的最右边的下标
|
||||
// center: 与 maxRight 对应的中心字符的下标
|
||||
// maxLen: 记录最长回文串的半径
|
||||
// begin: 记录最长回文串在起始串 s 中的起始下标
|
||||
dp, maxRight, center, maxLen, begin := make([]int, len(newS)), 0, 0, 1, 0
|
||||
for i := 0; i < len(newS); i++ {
|
||||
if i < maxRight {
|
||||
// 这一行代码是 Manacher 算法的关键所在
|
||||
dp[i] = min(maxRight-i, dp[2*center-i])
|
||||
}
|
||||
// 中心扩散法更新 dp[i]
|
||||
left, right := i-(1+dp[i]), i+(1+dp[i])
|
||||
for left >= 0 && right < len(newS) && newS[left] == newS[right] {
|
||||
dp[i]++
|
||||
left--
|
||||
right++
|
||||
}
|
||||
// 更新 maxRight,它是遍历过的 i 的 i + dp[i] 的最大者
|
||||
if i+dp[i] > maxRight {
|
||||
maxRight = i + dp[i]
|
||||
center = i
|
||||
}
|
||||
// 记录最长回文子串的长度和相应它在原始字符串中的起点
|
||||
if dp[i] > maxLen {
|
||||
maxLen = dp[i]
|
||||
begin = (i - maxLen) / 2 // 这里要除以 2 因为有我们插入的辅助字符 #
|
||||
}
|
||||
}
|
||||
return s[begin : begin+maxLen]
|
||||
}
|
||||
|
||||
func min(x, y int) int {
|
||||
if x < y {
|
||||
return x
|
||||
}
|
||||
return y
|
||||
}
|
||||
|
||||
// 解法二 滑动窗口,时间复杂度 O(n^2),空间复杂度 O(1)
|
||||
func longestPalindrome1(s string) string {
|
||||
if len(s) == 0 {
|
||||
return ""
|
||||
}
|
||||
left, right, pl, pr := 0, -1, 0, 0
|
||||
for left < len(s) {
|
||||
// 移动到相同字母的最右边(如果有相同字母)
|
||||
for right+1 < len(s) && s[left] == s[right+1] {
|
||||
right++
|
||||
}
|
||||
// 找到回文的边界
|
||||
for left-1 >= 0 && right+1 < len(s) && s[left-1] == s[right+1] {
|
||||
left--
|
||||
right++
|
||||
}
|
||||
if right-left > pr-pl {
|
||||
pl, pr = left, right
|
||||
}
|
||||
// 重置到下一次寻找回文的中心
|
||||
left = (left+right)/2 + 1
|
||||
right = left
|
||||
}
|
||||
return s[pl : pr+1]
|
||||
}
|
||||
|
||||
// 解法三 中心扩散法,时间复杂度 O(n^2),空间复杂度 O(1)
|
||||
func longestPalindrome2(s string) string {
|
||||
res := ""
|
||||
for i := 0; i < len(s); i++ {
|
||||
res = maxPalindrome(s, i, i, res)
|
||||
res = maxPalindrome(s, i, i+1, res)
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
func maxPalindrome(s string, i, j int, res string) string {
|
||||
sub := ""
|
||||
for i >= 0 && j < len(s) && s[i] == s[j] {
|
||||
sub = s[i : j+1]
|
||||
i--
|
||||
j++
|
||||
}
|
||||
if len(res) < len(sub) {
|
||||
return sub
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
// 解法四 DP,时间复杂度 O(n^2),空间复杂度 O(n^2)
|
||||
func longestPalindrome3(s string) string {
|
||||
res, dp := "", make([][]bool, len(s))
|
||||
for i := 0; i < len(s); i++ {
|
||||
dp[i] = make([]bool, len(s))
|
||||
}
|
||||
for i := len(s) - 1; i >= 0; i-- {
|
||||
for j := i; j < len(s); j++ {
|
||||
dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])
|
||||
if dp[i][j] && (res == "" || j-i+1 > len(res)) {
|
||||
res = s[i : j+1]
|
||||
}
|
||||
}
|
||||
}
|
||||
return res
|
||||
}
|
@ -1,67 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question5 struct {
|
||||
para5
|
||||
ans5
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para5 struct {
|
||||
s string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans5 struct {
|
||||
one string
|
||||
}
|
||||
|
||||
func Test_Problem5(t *testing.T) {
|
||||
|
||||
qs := []question5{
|
||||
|
||||
{
|
||||
para5{"babad"},
|
||||
ans5{"bab"},
|
||||
},
|
||||
|
||||
{
|
||||
para5{"cbbd"},
|
||||
ans5{"bb"},
|
||||
},
|
||||
|
||||
{
|
||||
para5{"a"},
|
||||
ans5{"a"},
|
||||
},
|
||||
|
||||
{
|
||||
para5{"ac"},
|
||||
ans5{"a"},
|
||||
},
|
||||
|
||||
{
|
||||
para5{"aa"},
|
||||
ans5{"aa"},
|
||||
},
|
||||
|
||||
{
|
||||
para5{"ajgiljtperkvubjmdsefcylksrxtftqrehoitdgdtttswwttmfuvwgwrruuqmxttzsbmuhgfaoueumvbhajqsaxkkihjwevzzedizmrsmpxqavyryklbotwzngxscvyuqjkkaotitddlhhnutmotupwuwyltebtsdfssbwayuxrbgihmtphshdslktvsjadaykyjivbzhwujcdvzdxxfiixnzrmusqvwujjmxhbqbdpauacnzojnzxxgrkmupadfcsujkcwajsgintahwgbjnvjqubcxajdyyapposrkpqtpqfjcvbhlmwfutgognqxgaukpmdyaxghgoqkqnigcllachmwzrazwhpppmsodvxilrccfqgpkmdqhoorxpyjsrtbeeidsinpeyxxpsjnymxkouskyhenzgieybwkgzrhhrzgkwbyeigznehyksuokxmynjspxxyepnisdieebtrsjypxroohqdmkpgqfccrlixvdosmppphwzarzwmhcallcginqkqoghgxaydmpkuagxqngogtufwmlhbvcjfqptqpkrsoppayydjaxcbuqjvnjbgwhatnigsjawckjuscfdapumkrgxxznjozncauapdbqbhxmjjuwvqsumrznxiifxxdzvdcjuwhzbvijykyadajsvtklsdhshptmhigbrxuyawbssfdstbetlywuwputomtunhhlddtitoakkjquyvcsxgnzwtoblkyryvaqxpmsrmzidezzvewjhikkxasqjahbvmueuoafghumbszttxmquurrwgwvufmttwwstttdgdtioherqtftxrsklycfesdmjbuvkreptjligja"},
|
||||
ans5{"ajgiljtperkvubjmdsefcylksrxtftqrehoitdgdtttswwttmfuvwgwrruuqmxttzsbmuhgfaoueumvbhajqsaxkkihjwevzzedizmrsmpxqavyryklbotwzngxscvyuqjkkaotitddlhhnutmotupwuwyltebtsdfssbwayuxrbgihmtphshdslktvsjadaykyjivbzhwujcdvzdxxfiixnzrmusqvwujjmxhbqbdpauacnzojnzxxgrkmupadfcsujkcwajsgintahwgbjnvjqubcxajdyyapposrkpqtpqfjcvbhlmwfutgognqxgaukpmdyaxghgoqkqnigcllachmwzrazwhpppmsodvxilrccfqgpkmdqhoorxpyjsrtbeeidsinpeyxxpsjnymxkouskyhenzgieybwkgzrhhrzgkwbyeigznehyksuokxmynjspxxyepnisdieebtrsjypxroohqdmkpgqfccrlixvdosmppphwzarzwmhcallcginqkqoghgxaydmpkuagxqngogtufwmlhbvcjfqptqpkrsoppayydjaxcbuqjvnjbgwhatnigsjawckjuscfdapumkrgxxznjozncauapdbqbhxmjjuwvqsumrznxiifxxdzvdcjuwhzbvijykyadajsvtklsdhshptmhigbrxuyawbssfdstbetlywuwputomtunhhlddtitoakkjquyvcsxgnzwtoblkyryvaqxpmsrmzidezzvewjhikkxasqjahbvmueuoafghumbszttxmquurrwgwvufmttwwstttdgdtioherqtftxrsklycfesdmjbuvkreptjligja"},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 5------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans5, q.para5
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, longestPalindrome(p.s))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,186 +0,0 @@
|
||||
# [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given a string `s`, return *the longest palindromic substring* in `s`.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: s = "babad"
|
||||
Output: "bab"
|
||||
Note: "aba" is also a valid answer.
|
||||
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s = "cbbd"
|
||||
Output: "bb"
|
||||
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s = "a"
|
||||
Output: "a"
|
||||
|
||||
```
|
||||
|
||||
**Example 4:**
|
||||
|
||||
```
|
||||
Input: s = "ac"
|
||||
Output: "a"
|
||||
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= s.length <= 1000`
|
||||
- `s` consist of only digits and English letters (lower-case and/or upper-case),
|
||||
|
||||
## 题目大意
|
||||
|
||||
给你一个字符串 `s`,找到 `s` 中最长的回文子串。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 此题非常经典,并且有多种解法。
|
||||
- 解法一,动态规划。定义 `dp[i][j]` 表示从字符串第 `i` 个字符到第 `j` 个字符这一段子串是否是回文串。由回文串的性质可以得知,回文串去掉一头一尾相同的字符以后,剩下的还是回文串。所以状态转移方程是 `dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])`,注意特殊的情况,`j - i == 1` 的时候,即只有 2 个字符的情况,只需要判断这 2 个字符是否相同即可。`j - i == 2` 的时候,即只有 3 个字符的情况,只需要判断除去中心以外对称的 2 个字符是否相等。每次循环动态维护保存最长回文串即可。时间复杂度 O(n^2),空间复杂度 O(n^2)。
|
||||
- 解法二,中心扩散法。动态规划的方法中,我们将任意起始,终止范围内的字符串都判断了一遍。其实没有这个必要,如果不是最长回文串,无需判断并保存结果。所以动态规划的方法在空间复杂度上还有优化空间。判断回文有一个核心问题是找到“轴心”。如果长度是偶数,那么轴心是中心虚拟的,如果长度是奇数,那么轴心正好是正中心的那个字母。中心扩散法的思想是枚举每个轴心的位置。然后做两次假设,假设最长回文串是偶数,那么以虚拟中心往 2 边扩散;假设最长回文串是奇数,那么以正中心的字符往 2 边扩散。扩散的过程就是对称判断两边字符是否相等的过程。这个方法时间复杂度和动态规划是一样的,但是空间复杂度降低了。时间复杂度 O(n^2),空间复杂度 O(1)。
|
||||
- 解法三,滑动窗口。这个写法其实就是中心扩散法变了一个写法。中心扩散是依次枚举每一个轴心。滑动窗口的方法稍微优化了一点,有些轴心两边字符不相等,下次就不会枚举这些不可能形成回文子串的轴心了。不过这点优化并没有优化时间复杂度,时间复杂度 O(n^2),空间复杂度 O(1)。
|
||||
- 解法四,马拉车算法。这个算法是本题的最优解,也是最复杂的解法。时间复杂度 O(n),空间复杂度 O(n)。中心扩散法有 2 处有重复判断,第一处是每次都往两边扩散,不同中心扩散多次,实际上有很多重复判断的字符,能否不重复判断?第二处,中心能否跳跃选择,不是每次都枚举,是否可以利用前一次的信息,跳跃选择下一次的中心?马拉车算法针对重复判断的问题做了优化,增加了一个辅助数组,将时间复杂度从 O(n^2) 优化到了 O(n),空间换了时间,空间复杂度增加到 O(n)。
|
||||
|
||||

|
||||
|
||||
- 首先是预处理,向字符串的头尾以及每两个字符中间添加一个特殊字符 `#`,比如字符串 `aaba` 处理后会变成 `#a#a#b#a#`。那么原先长度为偶数的回文字符串 `aa` 会变成长度为奇数的回文字符串 `#a#a#`,而长度为奇数的回文字符串 `aba` 会变成长度仍然为奇数的回文字符串 `#a#b#a#`,经过预处理以后,都会变成长度为奇数的字符串。**注意这里的特殊字符不需要是没有出现过的字母,也可以使用任何一个字符来作为这个特殊字符。**这是因为,当我们只考虑长度为奇数的回文字符串时,每次我们比较的两个字符奇偶性一定是相同的,所以原来字符串中的字符不会与插入的特殊字符互相比较,不会因此产生问题。**预处理以后,以某个中心扩散的步数和实际字符串长度是相等的。**因为半径里面包含了插入的特殊字符,又由于左右对称的性质,所以扩散半径就等于原来回文子串的长度。
|
||||
|
||||

|
||||
|
||||
- 核心部分是如何通过左边已经扫描过的数据推出右边下一次要扩散的中心。这里定义下一次要扩散的中心下标是 `i`。如果 `i` 比 `maxRight` 要小,只能继续中心扩散。如果 `i` 比 `maxRight` 大,这是又分为 3 种情况。三种情况见上图。将上述 3 种情况总结起来,就是 :`dp[i] = min(maxRight-i, dp[2*center-i])`,其中,`mirror` 相对于 `center` 是和 `i` 中心对称的,所以它的下标可以计算出来是 `2*center-i`。更新完 `dp[i]` 以后,就要进行中心扩散了。中心扩散以后动态维护最长回文串并相应的更新 `center`,`maxRight`,并且记录下原始字符串的起始位置 `begin` 和 `maxLen`。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
// 解法一 Manacher's algorithm,时间复杂度 O(n),空间复杂度 O(n)
|
||||
func longestPalindrome(s string) string {
|
||||
if len(s) < 2 {
|
||||
return s
|
||||
}
|
||||
newS := make([]rune, 0)
|
||||
newS = append(newS, '#')
|
||||
for _, c := range s {
|
||||
newS = append(newS, c)
|
||||
newS = append(newS, '#')
|
||||
}
|
||||
// dp[i]: 以预处理字符串下标 i 为中心的回文半径(奇数长度时不包括中心)
|
||||
// maxRight: 通过中心扩散的方式能够扩散的最右边的下标
|
||||
// center: 与 maxRight 对应的中心字符的下标
|
||||
// maxLen: 记录最长回文串的半径
|
||||
// begin: 记录最长回文串在起始串 s 中的起始下标
|
||||
dp, maxRight, center, maxLen, begin := make([]int, len(newS)), 0, 0, 1, 0
|
||||
for i := 0; i < len(newS); i++ {
|
||||
if i < maxRight {
|
||||
// 这一行代码是 Manacher 算法的关键所在
|
||||
dp[i] = min(maxRight-i, dp[2*center-i])
|
||||
}
|
||||
// 中心扩散法更新 dp[i]
|
||||
left, right := i-(1+dp[i]), i+(1+dp[i])
|
||||
for left >= 0 && right < len(newS) && newS[left] == newS[right] {
|
||||
dp[i]++
|
||||
left--
|
||||
right++
|
||||
}
|
||||
// 更新 maxRight,它是遍历过的 i 的 i + dp[i] 的最大者
|
||||
if i+dp[i] > maxRight {
|
||||
maxRight = i + dp[i]
|
||||
center = i
|
||||
}
|
||||
// 记录最长回文子串的长度和相应它在原始字符串中的起点
|
||||
if dp[i] > maxLen {
|
||||
maxLen = dp[i]
|
||||
begin = (i - maxLen) / 2 // 这里要除以 2 因为有我们插入的辅助字符 #
|
||||
}
|
||||
}
|
||||
return s[begin : begin+maxLen]
|
||||
}
|
||||
|
||||
func min(x, y int) int {
|
||||
if x < y {
|
||||
return x
|
||||
}
|
||||
return y
|
||||
}
|
||||
|
||||
// 解法二 滑动窗口,时间复杂度 O(n^2),空间复杂度 O(1)
|
||||
func longestPalindrome1(s string) string {
|
||||
if len(s) == 0 {
|
||||
return ""
|
||||
}
|
||||
left, right, pl, pr := 0, -1, 0, 0
|
||||
for left < len(s) {
|
||||
// 移动到相同字母的最右边(如果有相同字母)
|
||||
for right+1 < len(s) && s[left] == s[right+1] {
|
||||
right++
|
||||
}
|
||||
// 找到回文的边界
|
||||
for left-1 >= 0 && right+1 < len(s) && s[left-1] == s[right+1] {
|
||||
left--
|
||||
right++
|
||||
}
|
||||
if right-left > pr-pl {
|
||||
pl, pr = left, right
|
||||
}
|
||||
// 重置到下一次寻找回文的中心
|
||||
left = (left+right)/2 + 1
|
||||
right = left
|
||||
}
|
||||
return s[pl : pr+1]
|
||||
}
|
||||
|
||||
// 解法三 中心扩散法,时间复杂度 O(n^2),空间复杂度 O(1)
|
||||
func longestPalindrome2(s string) string {
|
||||
res := ""
|
||||
for i := 0; i < len(s); i++ {
|
||||
res = maxPalindrome(s, i, i, res)
|
||||
res = maxPalindrome(s, i, i+1, res)
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
func maxPalindrome(s string, i, j int, res string) string {
|
||||
sub := ""
|
||||
for i >= 0 && j < len(s) && s[i] == s[j] {
|
||||
sub = s[i : j+1]
|
||||
i--
|
||||
j++
|
||||
}
|
||||
if len(res) < len(sub) {
|
||||
return sub
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
// 解法四 DP,时间复杂度 O(n^2),空间复杂度 O(n^2)
|
||||
func longestPalindrome3(s string) string {
|
||||
res, dp := "", make([][]bool, len(s))
|
||||
for i := 0; i < len(s); i++ {
|
||||
dp[i] = make([]bool, len(s))
|
||||
}
|
||||
for i := len(s) - 1; i >= 0; i-- {
|
||||
for j := i; j < len(s); j++ {
|
||||
dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])
|
||||
if dp[i][j] && (res == "" || j-i+1 > len(res)) {
|
||||
res = s[i : j+1]
|
||||
}
|
||||
}
|
||||
}
|
||||
return res
|
||||
}
|
||||
```
|
@ -1,26 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func convert(s string, numRows int) string {
|
||||
matrix, down, up := make([][]byte, numRows, numRows), 0, numRows-2
|
||||
for i := 0; i != len(s); {
|
||||
if down != numRows {
|
||||
matrix[down] = append(matrix[down], byte(s[i]))
|
||||
down++
|
||||
i++
|
||||
} else if up > 0 {
|
||||
matrix[up] = append(matrix[up], byte(s[i]))
|
||||
up--
|
||||
i++
|
||||
} else {
|
||||
up = numRows - 2
|
||||
down = 0
|
||||
}
|
||||
}
|
||||
solution := make([]byte, 0, len(s))
|
||||
for _, row := range matrix {
|
||||
for _, item := range row {
|
||||
solution = append(solution, item)
|
||||
}
|
||||
}
|
||||
return string(solution)
|
||||
}
|
@ -1,53 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question6 struct {
|
||||
para6
|
||||
ans6
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para6 struct {
|
||||
s string
|
||||
numRows int
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans6 struct {
|
||||
one string
|
||||
}
|
||||
|
||||
func Test_Problem6(t *testing.T) {
|
||||
|
||||
qs := []question6{
|
||||
|
||||
{
|
||||
para6{"PAYPALISHIRING", 3},
|
||||
ans6{"PAHNAPLSIIGYIR"},
|
||||
},
|
||||
|
||||
{
|
||||
para6{"PAYPALISHIRING", 4},
|
||||
ans6{"PINALSIGYAHRPI"},
|
||||
},
|
||||
|
||||
{
|
||||
para6{"A", 1},
|
||||
ans6{"A"},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 6------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans6, q.para6
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, convert(p.s, p.numRows))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,107 +0,0 @@
|
||||
# [6. ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
|
||||
|
||||
```
|
||||
P A H N
|
||||
A P L S I I G
|
||||
Y I R
|
||||
```
|
||||
|
||||
And then read line by line: `"PAHNAPLSIIGYIR"`
|
||||
|
||||
Write the code that will take a string and make this conversion given a number of rows:
|
||||
|
||||
```
|
||||
string convert(string s, int numRows);
|
||||
```
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: s = "PAYPALISHIRING", numRows = 3
|
||||
Output: "PAHNAPLSIIGYIR"
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s = "PAYPALISHIRING", numRows = 4
|
||||
Output: "PINALSIGYAHRPI"
|
||||
Explanation:
|
||||
P I N
|
||||
A L S I G
|
||||
Y A H R
|
||||
P I
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s = "A", numRows = 1
|
||||
Output: "A"
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= s.length <= 1000`
|
||||
- `s` consists of English letters (lower-case and upper-case), `','` and `'.'`.
|
||||
- `1 <= numRows <= 1000`
|
||||
|
||||
## 题目大意
|
||||
|
||||
将一个给定字符串 `s` 根据给定的行数 `numRows` ,以从上往下、从左到右进行 Z 字形排列。
|
||||
|
||||
比如输入字符串为 `"PAYPALISHIRING"` 行数为 3 时,排列如下:
|
||||
|
||||
```go
|
||||
P A H N
|
||||
A P L S I I G
|
||||
Y I R
|
||||
```
|
||||
|
||||
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:`"PAHNAPLSIIGYIR"`。
|
||||
|
||||
请你实现这个将字符串进行指定行数变换的函数:
|
||||
|
||||
```go
|
||||
string convert(string s, int numRows);
|
||||
```
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 这一题没有什么算法思想,考察的是对程序控制的能力。用 2 个变量保存方向,当垂直输出的行数达到了规定的目标行数以后,需要从下往上转折到第一行,循环中控制好方向ji
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func convert(s string, numRows int) string {
|
||||
matrix, down, up := make([][]byte, numRows, numRows), 0, numRows-2
|
||||
for i := 0; i != len(s); {
|
||||
if down != numRows {
|
||||
matrix[down] = append(matrix[down], byte(s[i]))
|
||||
down++
|
||||
i++
|
||||
} else if up > 0 {
|
||||
matrix[up] = append(matrix[up], byte(s[i]))
|
||||
up--
|
||||
i++
|
||||
} else {
|
||||
up = numRows - 2
|
||||
down = 0
|
||||
}
|
||||
}
|
||||
solution := make([]byte, 0, len(s))
|
||||
for _, row := range matrix {
|
||||
for _, item := range row {
|
||||
solution = append(solution, item)
|
||||
}
|
||||
}
|
||||
return string(solution)
|
||||
}
|
||||
```
|
@ -1,56 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func myAtoi(s string) int {
|
||||
maxInt, signAllowed, whitespaceAllowed, sign, digits := int64(2<<30), true, true, 1, []int{}
|
||||
for _, c := range s {
|
||||
if c == ' ' && whitespaceAllowed {
|
||||
continue
|
||||
}
|
||||
if signAllowed {
|
||||
if c == '+' {
|
||||
signAllowed = false
|
||||
whitespaceAllowed = false
|
||||
continue
|
||||
} else if c == '-' {
|
||||
sign = -1
|
||||
signAllowed = false
|
||||
whitespaceAllowed = false
|
||||
continue
|
||||
}
|
||||
}
|
||||
if c < '0' || c > '9' {
|
||||
break
|
||||
}
|
||||
whitespaceAllowed, signAllowed = false, false
|
||||
digits = append(digits, int(c-48))
|
||||
}
|
||||
var num, place int64
|
||||
place, num = 1, 0
|
||||
lastLeading0Index := -1
|
||||
for i, d := range digits {
|
||||
if d == 0 {
|
||||
lastLeading0Index = i
|
||||
} else {
|
||||
break
|
||||
}
|
||||
}
|
||||
if lastLeading0Index > -1 {
|
||||
digits = digits[lastLeading0Index+1:]
|
||||
}
|
||||
var rtnMax int64
|
||||
if sign > 0 {
|
||||
rtnMax = maxInt - 1
|
||||
} else {
|
||||
rtnMax = maxInt
|
||||
}
|
||||
digitsCount := len(digits)
|
||||
for i := digitsCount - 1; i >= 0; i-- {
|
||||
num += int64(digits[i]) * place
|
||||
place *= 10
|
||||
if digitsCount-i > 10 || num > rtnMax {
|
||||
return int(int64(sign) * rtnMax)
|
||||
}
|
||||
}
|
||||
num *= int64(sign)
|
||||
return int(num)
|
||||
}
|
@ -1,62 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question8 struct {
|
||||
para8
|
||||
ans8
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para8 struct {
|
||||
one string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans8 struct {
|
||||
one int
|
||||
}
|
||||
|
||||
func Test_Problem8(t *testing.T) {
|
||||
|
||||
qs := []question8{
|
||||
|
||||
{
|
||||
para8{"42"},
|
||||
ans8{42},
|
||||
},
|
||||
|
||||
{
|
||||
para8{" -42"},
|
||||
ans8{-42},
|
||||
},
|
||||
|
||||
{
|
||||
para8{"4193 with words"},
|
||||
ans8{4193},
|
||||
},
|
||||
|
||||
{
|
||||
para8{"words and 987"},
|
||||
ans8{0},
|
||||
},
|
||||
|
||||
{
|
||||
para8{"-91283472332"},
|
||||
ans8{-2147483648},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 8------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans8, q.para8
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p.one, myAtoi(p.one))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,192 +0,0 @@
|
||||
# [8. String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Implement the `myAtoi(string s)` function, which converts a string to a 32-bit signed integer (similar to C/C++'s `atoi` function).
|
||||
|
||||
The algorithm for `myAtoi(string s)` is as follows:
|
||||
|
||||
1. Read in and ignore any leading whitespace.
|
||||
2. Check if the next character (if not already at the end of the string) is `'-'` or `'+'`. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
|
||||
3. Read in next the characters until the next non-digit charcter or the end of the input is reached. The rest of the string is ignored.
|
||||
4. Convert these digits into an integer (i.e. `"123" -> 123`, `"0032" -> 32`). If no digits were read, then the integer is `0`. Change the sign as necessary (from step 2).
|
||||
5. If the integer is out of the 32-bit signed integer range `[-231, 231 - 1]`, then clamp the integer so that it remains in the range. Specifically, integers less than `231` should be clamped to `231`, and integers greater than `231 - 1` should be clamped to `231 - 1`.
|
||||
6. Return the integer as the final result.
|
||||
|
||||
**Note:**
|
||||
|
||||
- Only the space character `' '` is considered a whitespace character.
|
||||
- **Do not ignore** any characters other than the leading whitespace or the rest of the string after the digits.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: s = "42"
|
||||
Output: 42
|
||||
Explanation: The underlined characters are what is read in, the caret is the current reader position.
|
||||
Step 1: "42" (no characters read because there is no leading whitespace)
|
||||
^
|
||||
Step 2: "42" (no characters read because there is neither a '-' nor '+')
|
||||
^
|
||||
Step 3: "42" ("42" is read in)
|
||||
^
|
||||
The parsed integer is 42.
|
||||
Since 42 is in the range [-231, 231 - 1], the final result is 42.
|
||||
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s = " -42"
|
||||
Output: -42
|
||||
Explanation:
|
||||
Step 1: " -42" (leading whitespace is read and ignored)
|
||||
^
|
||||
Step 2: " -42" ('-' is read, so the result should be negative)
|
||||
^
|
||||
Step 3: " -42" ("42" is read in)
|
||||
^
|
||||
The parsed integer is -42.
|
||||
Since -42 is in the range [-231, 231 - 1], the final result is -42.
|
||||
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s = "4193 with words"
|
||||
Output: 4193
|
||||
Explanation:
|
||||
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
|
||||
^
|
||||
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
|
||||
^
|
||||
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
|
||||
^
|
||||
The parsed integer is 4193.
|
||||
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
|
||||
|
||||
```
|
||||
|
||||
**Example 4:**
|
||||
|
||||
```
|
||||
Input: s = "words and 987"
|
||||
Output: 0
|
||||
Explanation:
|
||||
Step 1: "words and 987" (no characters read because there is no leading whitespace)
|
||||
^
|
||||
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
|
||||
^
|
||||
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
|
||||
^
|
||||
The parsed integer is 0 because no digits were read.
|
||||
Since 0 is in the range [-231, 231 - 1], the final result is 0.
|
||||
|
||||
```
|
||||
|
||||
**Example 5:**
|
||||
|
||||
```
|
||||
Input: s = "-91283472332"
|
||||
Output: -2147483648
|
||||
Explanation:
|
||||
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
|
||||
^
|
||||
Step 2: "-91283472332" ('-' is read, so the result should be negative)
|
||||
^
|
||||
Step 3: "-91283472332" ("91283472332" is read in)
|
||||
^
|
||||
The parsed integer is -91283472332.
|
||||
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `0 <= s.length <= 200`
|
||||
- `s` consists of English letters (lower-case and upper-case), digits (`0-9`), `' '`, `'+'`
|
||||
|
||||
## 题目大意
|
||||
|
||||
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。
|
||||
|
||||
函数 myAtoi(string s) 的算法如下:
|
||||
|
||||
- 读入字符串并丢弃无用的前导空格
|
||||
- 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
|
||||
- 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
|
||||
- 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
|
||||
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
|
||||
- 返回整数作为最终结果。
|
||||
|
||||
注意:
|
||||
|
||||
- 本题中的空白字符只包括空格字符 ' ' 。
|
||||
- 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 这题是简单题。题目要求实现类似 `C++` 中 `atoi` 函数的功能。这个函数功能是将字符串类型的数字转成 `int` 类型数字。先去除字符串中的前导空格,并判断记录数字的符号。数字需要去掉前导 `0` 。最后将数字转换成数字类型,判断是否超过 `int` 类型的上限 `[-2^31, 2^31 - 1]`,如果超过上限,需要输出边界,即 `-2^31`,或者 `2^31 - 1`。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func myAtoi(s string) int {
|
||||
maxInt, signAllowed, whitespaceAllowed, sign, digits := int64(2<<30), true, true, 1, []int{}
|
||||
for _, c := range s {
|
||||
if c == ' ' && whitespaceAllowed {
|
||||
continue
|
||||
}
|
||||
if signAllowed {
|
||||
if c == '+' {
|
||||
signAllowed = false
|
||||
whitespaceAllowed = false
|
||||
continue
|
||||
} else if c == '-' {
|
||||
sign = -1
|
||||
signAllowed = false
|
||||
whitespaceAllowed = false
|
||||
continue
|
||||
}
|
||||
}
|
||||
if c < '0' || c > '9' {
|
||||
break
|
||||
}
|
||||
whitespaceAllowed, signAllowed = false, false
|
||||
digits = append(digits, int(c-48))
|
||||
}
|
||||
var num, place int64
|
||||
place, num = 1, 0
|
||||
lastLeading0Index := -1
|
||||
for i, d := range digits {
|
||||
if d == 0 {
|
||||
lastLeading0Index = i
|
||||
} else {
|
||||
break
|
||||
}
|
||||
}
|
||||
if lastLeading0Index > -1 {
|
||||
digits = digits[lastLeading0Index+1:]
|
||||
}
|
||||
var rtnMax int64
|
||||
if sign > 0 {
|
||||
rtnMax = maxInt - 1
|
||||
} else {
|
||||
rtnMax = maxInt
|
||||
}
|
||||
digitsCount := len(digits)
|
||||
for i := digitsCount - 1; i >= 0; i-- {
|
||||
num += int64(digits[i]) * place
|
||||
place *= 10
|
||||
if digitsCount-i > 10 || num > rtnMax {
|
||||
return int(int64(sign) * rtnMax)
|
||||
}
|
||||
}
|
||||
num *= int64(sign)
|
||||
return int(num)
|
||||
}
|
||||
```
|
@ -2,33 +2,7 @@ package leetcode
|
||||
|
||||
import "strconv"
|
||||
|
||||
// 解法一
|
||||
func isPalindrome(x int) bool {
|
||||
if x < 0 {
|
||||
return false
|
||||
}
|
||||
if x == 0 {
|
||||
return true
|
||||
}
|
||||
if x%10 == 0 {
|
||||
return false
|
||||
}
|
||||
arr := make([]int, 0, 32)
|
||||
for x > 0 {
|
||||
arr = append(arr, x%10)
|
||||
x = x / 10
|
||||
}
|
||||
sz := len(arr)
|
||||
for i, j := 0, sz-1; i <= j; i, j = i+1, j-1 {
|
||||
if arr[i] != arr[j] {
|
||||
return false
|
||||
}
|
||||
}
|
||||
return true
|
||||
}
|
||||
|
||||
// 解法二 数字转字符串
|
||||
func isPalindrome1(x int) bool {
|
||||
if x < 0 {
|
||||
return false
|
||||
}
|
||||
|
@ -49,33 +49,7 @@ package leetcode
|
||||
|
||||
import "strconv"
|
||||
|
||||
// 解法一
|
||||
func isPalindrome(x int) bool {
|
||||
if x < 0 {
|
||||
return false
|
||||
}
|
||||
if x == 0 {
|
||||
return true
|
||||
}
|
||||
if x%10 == 0 {
|
||||
return false
|
||||
}
|
||||
arr := make([]int, 0, 32)
|
||||
for x > 0 {
|
||||
arr = append(arr, x%10)
|
||||
x = x / 10
|
||||
}
|
||||
sz := len(arr)
|
||||
for i, j := 0, sz-1; i <= j; i, j = i+1, j-1 {
|
||||
if arr[i] != arr[j] {
|
||||
return false
|
||||
}
|
||||
}
|
||||
return true
|
||||
}
|
||||
|
||||
// 解法二 数字转字符串
|
||||
func isPalindrome1(x int) bool {
|
||||
if x < 0 {
|
||||
return false
|
||||
}
|
||||
@ -92,5 +66,4 @@ func isPalindrome1(x int) bool {
|
||||
return true
|
||||
}
|
||||
|
||||
|
||||
```
|
@ -1,15 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func intToRoman(num int) string {
|
||||
values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
|
||||
symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
|
||||
res, i := "", 0
|
||||
for num != 0 {
|
||||
for values[i] > num {
|
||||
i++
|
||||
}
|
||||
num -= values[i]
|
||||
res += symbols[i]
|
||||
}
|
||||
return res
|
||||
}
|
@ -1,71 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question12 struct {
|
||||
para12
|
||||
ans12
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para12 struct {
|
||||
one int
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans12 struct {
|
||||
one string
|
||||
}
|
||||
|
||||
func Test_Problem12(t *testing.T) {
|
||||
|
||||
qs := []question12{
|
||||
|
||||
{
|
||||
para12{3},
|
||||
ans12{"III"},
|
||||
},
|
||||
|
||||
{
|
||||
para12{4},
|
||||
ans12{"IV"},
|
||||
},
|
||||
|
||||
{
|
||||
para12{9},
|
||||
ans12{"IX"},
|
||||
},
|
||||
|
||||
{
|
||||
para12{58},
|
||||
ans12{"LVIII"},
|
||||
},
|
||||
|
||||
{
|
||||
para12{1994},
|
||||
ans12{"MCMXCIV"},
|
||||
},
|
||||
{
|
||||
para12{123},
|
||||
ans12{"CXXIII"},
|
||||
},
|
||||
|
||||
{
|
||||
para12{120},
|
||||
ans12{"CXX"},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 12------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans12, q.para12
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p.one, intToRoman(p.one))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,102 +0,0 @@
|
||||
# [12. Integer to Roman](https://leetcode.com/problems/integer-to-roman/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
|
||||
|
||||
```
|
||||
Symbol Value
|
||||
I 1
|
||||
V 5
|
||||
X 10
|
||||
L 50
|
||||
C 100
|
||||
D 500
|
||||
M 1000
|
||||
```
|
||||
|
||||
For example, `2` is written as `II` in Roman numeral, just two one's added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.
|
||||
|
||||
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:
|
||||
|
||||
- `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
|
||||
- `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
|
||||
- `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.
|
||||
|
||||
Given an integer, convert it to a roman numeral.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: num = 3
|
||||
Output: "III"
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: num = 4
|
||||
Output: "IV"
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: num = 9
|
||||
Output: "IX"
|
||||
```
|
||||
|
||||
**Example 4:**
|
||||
|
||||
```
|
||||
Input: num = 58
|
||||
Output: "LVIII"
|
||||
Explanation: L = 50, V = 5, III = 3.
|
||||
```
|
||||
|
||||
**Example 5:**
|
||||
|
||||
```
|
||||
Input: num = 1994
|
||||
Output: "MCMXCIV"
|
||||
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= num <= 3999`
|
||||
|
||||
## 题目大意
|
||||
|
||||
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
|
||||
|
||||
- I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
|
||||
- X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
|
||||
- C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
|
||||
|
||||
给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 依照题意,优先选择大的数字,解题思路采用贪心算法。将 1-3999 范围内的罗马数字从大到小放在数组中,从头选择到尾,即可把整数转成罗马数字。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func intToRoman(num int) string {
|
||||
values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
|
||||
symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
|
||||
res, i := "", 0
|
||||
for num != 0 {
|
||||
for values[i] > num {
|
||||
i++
|
||||
}
|
||||
num -= values[i]
|
||||
res += symbols[i]
|
||||
}
|
||||
return res
|
||||
}
|
||||
```
|
@ -1,16 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func longestCommonPrefix(strs []string) string {
|
||||
prefix := strs[0]
|
||||
|
||||
for i := 1; i < len(strs); i++ {
|
||||
for j := 0; j < len(prefix); j++ {
|
||||
if len(strs[i]) <= j || strs[i][j] != prefix[j] {
|
||||
prefix = prefix[0:j]
|
||||
break
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
return prefix
|
||||
}
|
@ -1,50 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question14 struct {
|
||||
para14
|
||||
ans14
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
type para14 struct {
|
||||
strs []string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
type ans14 struct {
|
||||
ans string
|
||||
}
|
||||
|
||||
func Test_Problem14(t *testing.T) {
|
||||
|
||||
qs := []question14{
|
||||
|
||||
{
|
||||
para14{[]string{"flower", "flow", "flight"}},
|
||||
ans14{"fl"},
|
||||
},
|
||||
|
||||
{
|
||||
para14{[]string{"dog", "racecar", "car"}},
|
||||
ans14{""},
|
||||
},
|
||||
|
||||
{
|
||||
para14{[]string{"ab", "a"}},
|
||||
ans14{"a"},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 14------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans14, q.para14
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p.strs, longestCommonPrefix(p.strs))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,57 +0,0 @@
|
||||
# [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)
|
||||
|
||||
## 题目
|
||||
|
||||
Write a function to find the longest common prefix string amongst an array of strings.
|
||||
|
||||
If there is no common prefix, return an empty string "".
|
||||
|
||||
**Example 1**:
|
||||
|
||||
Input: strs = ["flower","flow","flight"]
|
||||
Output: "fl"
|
||||
|
||||
**Example 2**:
|
||||
|
||||
Input: strs = ["dog","racecar","car"]
|
||||
Output: ""
|
||||
Explanation: There is no common prefix among the input strings.
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- 1 <= strs.length <= 200
|
||||
- 0 <= strs[i].length <= 200
|
||||
- strs[i] consists of only lower-case English letters.
|
||||
|
||||
## 题目大意
|
||||
|
||||
编写一个函数来查找字符串数组中的最长公共前缀。
|
||||
|
||||
如果不存在公共前缀,返回空字符串 ""。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 对 strs 按照字符串长度进行升序排序,求出 strs 中长度最小字符串的长度 minLen
|
||||
- 逐个比较长度最小字符串与其它字符串中的字符,如果不相等就返回 commonPrefix,否则就把该字符加入 commonPrefix
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
|
||||
package leetcode
|
||||
|
||||
func longestCommonPrefix(strs []string) string {
|
||||
prefix := strs[0]
|
||||
|
||||
for i := 1; i < len(strs); i++ {
|
||||
for j := 0; j < len(prefix); j++ {
|
||||
if len(strs[i]) <= j || strs[i][j] != prefix[j] {
|
||||
prefix = prefix[0:j]
|
||||
break
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
return prefix
|
||||
}
|
||||
```
|
@ -11,9 +11,6 @@ func threeSumClosest(nums []int, target int) int {
|
||||
if n > 2 {
|
||||
sort.Ints(nums)
|
||||
for i := 0; i < n-2; i++ {
|
||||
if i > 0 && nums[i] == nums[i-1] {
|
||||
continue
|
||||
}
|
||||
for j, k := i+1, n-1; j < k; {
|
||||
sum := nums[i] + nums[j] + nums[k]
|
||||
if abs(sum-target) < diff {
|
||||
|
@ -2,92 +2,7 @@ package leetcode
|
||||
|
||||
import "sort"
|
||||
|
||||
// 解法一 双指针
|
||||
func fourSum(nums []int, target int) (quadruplets [][]int) {
|
||||
sort.Ints(nums)
|
||||
n := len(nums)
|
||||
for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
|
||||
if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
|
||||
continue
|
||||
}
|
||||
for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
|
||||
if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
|
||||
continue
|
||||
}
|
||||
for left, right := j+1, n-1; left < right; {
|
||||
if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
|
||||
quadruplets = append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
|
||||
for left++; left < right && nums[left] == nums[left-1]; left++ {
|
||||
}
|
||||
for right--; left < right && nums[right] == nums[right+1]; right-- {
|
||||
}
|
||||
} else if sum < target {
|
||||
left++
|
||||
} else {
|
||||
right--
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
return
|
||||
}
|
||||
|
||||
// 解法二 kSum
|
||||
func fourSum1(nums []int, target int) [][]int {
|
||||
res, cur := make([][]int, 0), make([]int, 0)
|
||||
sort.Ints(nums)
|
||||
kSum(nums, 0, len(nums)-1, target, 4, cur, &res)
|
||||
return res
|
||||
}
|
||||
|
||||
func kSum(nums []int, left, right int, target int, k int, cur []int, res *[][]int) {
|
||||
if right-left+1 < k || k < 2 || target < nums[left]*k || target > nums[right]*k {
|
||||
return
|
||||
}
|
||||
if k == 2 {
|
||||
// 2 sum
|
||||
twoSum(nums, left, right, target, cur, res)
|
||||
} else {
|
||||
for i := left; i < len(nums); i++ {
|
||||
if i == left || (i > left && nums[i-1] != nums[i]) {
|
||||
next := make([]int, len(cur))
|
||||
copy(next, cur)
|
||||
next = append(next, nums[i])
|
||||
kSum(nums, i+1, len(nums)-1, target-nums[i], k-1, next, res)
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
}
|
||||
|
||||
func twoSum(nums []int, left, right int, target int, cur []int, res *[][]int) {
|
||||
for left < right {
|
||||
sum := nums[left] + nums[right]
|
||||
if sum == target {
|
||||
cur = append(cur, nums[left], nums[right])
|
||||
temp := make([]int, len(cur))
|
||||
copy(temp, cur)
|
||||
*res = append(*res, temp)
|
||||
// reset cur to previous state
|
||||
cur = cur[:len(cur)-2]
|
||||
left++
|
||||
right--
|
||||
for left < right && nums[left] == nums[left-1] {
|
||||
left++
|
||||
}
|
||||
for left < right && nums[right] == nums[right+1] {
|
||||
right--
|
||||
}
|
||||
} else if sum < target {
|
||||
left++
|
||||
} else {
|
||||
right--
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// 解法三
|
||||
func fourSum2(nums []int, target int) [][]int {
|
||||
func fourSum(nums []int, target int) [][]int {
|
||||
res := [][]int{}
|
||||
counter := map[int]int{}
|
||||
for _, value := range nums {
|
||||
|
@ -17,18 +17,22 @@ type ListNode = structures.ListNode
|
||||
|
||||
// 解法一
|
||||
func removeNthFromEnd(head *ListNode, n int) *ListNode {
|
||||
dummyHead := &ListNode{Next: head}
|
||||
preSlow, slow, fast := dummyHead, head, head
|
||||
for fast != nil {
|
||||
if n <= 0 {
|
||||
preSlow = slow
|
||||
slow = slow.Next
|
||||
}
|
||||
n--
|
||||
var fast, slow *ListNode
|
||||
fast = head
|
||||
slow = head
|
||||
for i := 0; i < n; i++ {
|
||||
fast = fast.Next
|
||||
}
|
||||
preSlow.Next = slow.Next
|
||||
return dummyHead.Next
|
||||
if fast == nil {
|
||||
head = head.Next
|
||||
return head
|
||||
}
|
||||
for fast.Next != nil {
|
||||
fast = fast.Next
|
||||
slow = slow.Next
|
||||
}
|
||||
slow.Next = slow.Next.Next
|
||||
return head
|
||||
}
|
||||
|
||||
// 解法二
|
||||
|
@ -29,26 +29,6 @@ func Test_Problem19(t *testing.T) {
|
||||
|
||||
qs := []question19{
|
||||
|
||||
{
|
||||
para19{[]int{1}, 3},
|
||||
ans19{[]int{1}},
|
||||
},
|
||||
|
||||
{
|
||||
para19{[]int{1, 2}, 2},
|
||||
ans19{[]int{2}},
|
||||
},
|
||||
|
||||
{
|
||||
para19{[]int{1}, 1},
|
||||
ans19{[]int{}},
|
||||
},
|
||||
|
||||
{
|
||||
para19{[]int{1, 2, 3, 4, 5}, 10},
|
||||
ans19{[]int{1, 2, 3, 4, 5}},
|
||||
},
|
||||
|
||||
{
|
||||
para19{[]int{1, 2, 3, 4, 5}, 1},
|
||||
ans19{[]int{1, 2, 3, 4}},
|
||||
|
@ -2,44 +2,16 @@
|
||||
|
||||
## 题目
|
||||
|
||||
Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head.
|
||||
Given a linked list, remove the n-th node from the end of list and return its head.
|
||||
|
||||
**Follow up:** Could you do this in one pass?
|
||||
|
||||
**Example 1:**
|
||||
|
||||

|
||||
Example:
|
||||
|
||||
```
|
||||
Input: head = [1,2,3,4,5], n = 2
|
||||
Output: [1,2,3,5]
|
||||
Given linked list: 1->2->3->4->5, and n = 2.
|
||||
|
||||
After removing the second node from the end, the linked list becomes 1->2->3->5.
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: head = [1], n = 1
|
||||
Output: []
|
||||
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: head = [1,2], n = 1
|
||||
Output: [1]
|
||||
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- The number of nodes in the list is `sz`.
|
||||
- `1 <= sz <= 30`
|
||||
- `0 <= Node.val <= 100`
|
||||
- `1 <= n <= sz`
|
||||
|
||||
|
||||
## 题目大意
|
||||
|
||||
删除链表中倒数第 n 个结点。
|
||||
|
@ -16,9 +16,30 @@ type ListNode = structures.ListNode
|
||||
*/
|
||||
|
||||
func swapPairs(head *ListNode) *ListNode {
|
||||
dummy := &ListNode{Next: head}
|
||||
for pt := dummy; pt != nil && pt.Next != nil && pt.Next.Next != nil; {
|
||||
pt, pt.Next, pt.Next.Next, pt.Next.Next.Next = pt.Next, pt.Next.Next, pt.Next.Next.Next, pt.Next
|
||||
if head == nil || head.Next == nil {
|
||||
return head
|
||||
}
|
||||
return dummy.Next
|
||||
s := head.Next
|
||||
var behind *ListNode
|
||||
for head.Next != nil {
|
||||
headNext := head.Next
|
||||
if behind != nil && behind.Next != nil {
|
||||
behind.Next = headNext
|
||||
}
|
||||
var next *ListNode
|
||||
if head.Next.Next != nil {
|
||||
next = head.Next.Next
|
||||
}
|
||||
if head.Next.Next != nil {
|
||||
head.Next = next
|
||||
} else {
|
||||
head.Next = nil
|
||||
}
|
||||
headNext.Next = head
|
||||
behind = head
|
||||
if head.Next != nil {
|
||||
head = next
|
||||
}
|
||||
}
|
||||
return s
|
||||
}
|
||||
|
@ -1,4 +1,4 @@
|
||||
# [28. Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
|
||||
# [28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)
|
||||
|
||||
## 题目
|
||||
|
@ -1,6 +1,5 @@
|
||||
package leetcode
|
||||
|
||||
// 解法一
|
||||
func nextPermutation(nums []int) {
|
||||
i, j := 0, 0
|
||||
for i = len(nums) - 2; i >= 0; i-- {
|
||||
@ -30,43 +29,3 @@ func reverse(nums *[]int, i, j int) {
|
||||
func swap(nums *[]int, i, j int) {
|
||||
(*nums)[i], (*nums)[j] = (*nums)[j], (*nums)[i]
|
||||
}
|
||||
|
||||
// 解法二
|
||||
// [2,(3),6,5,4,1] -> 2,(4),6,5,(3),1 -> 2,4, 1,3,5,6
|
||||
func nextPermutation1(nums []int) {
|
||||
var n = len(nums)
|
||||
var pIdx = checkPermutationPossibility(nums)
|
||||
if pIdx == -1 {
|
||||
reverse(&nums, 0, n-1)
|
||||
return
|
||||
}
|
||||
|
||||
var rp = len(nums) - 1
|
||||
// start from right most to leftward,find the first number which is larger than PIVOT
|
||||
for rp > 0 {
|
||||
if nums[rp] > nums[pIdx] {
|
||||
swap(&nums, pIdx, rp)
|
||||
break
|
||||
} else {
|
||||
rp--
|
||||
}
|
||||
}
|
||||
// Finally, Reverse all elements which are right from pivot
|
||||
reverse(&nums, pIdx+1, n-1)
|
||||
}
|
||||
|
||||
// checkPermutationPossibility returns 1st occurrence Index where
|
||||
// value is in decreasing order(from right to left)
|
||||
// returns -1 if not found(it's already in its last permutation)
|
||||
func checkPermutationPossibility(nums []int) (idx int) {
|
||||
// search right to left for 1st number(from right) that is not in increasing order
|
||||
var rp = len(nums) - 1
|
||||
for rp > 0 {
|
||||
if nums[rp-1] < nums[rp] {
|
||||
idx = rp - 1
|
||||
return idx
|
||||
}
|
||||
rp--
|
||||
}
|
||||
return -1
|
||||
}
|
||||
|
@ -1,58 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
// 解法一 栈
|
||||
func longestValidParentheses(s string) int {
|
||||
stack, res := []int{}, 0
|
||||
stack = append(stack, -1)
|
||||
for i := 0; i < len(s); i++ {
|
||||
if s[i] == '(' {
|
||||
stack = append(stack, i)
|
||||
} else {
|
||||
stack = stack[:len(stack)-1]
|
||||
if len(stack) == 0 {
|
||||
stack = append(stack, i)
|
||||
} else {
|
||||
res = max(res, i-stack[len(stack)-1])
|
||||
}
|
||||
}
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
func max(a, b int) int {
|
||||
if a > b {
|
||||
return a
|
||||
}
|
||||
return b
|
||||
}
|
||||
|
||||
// 解法二 双指针
|
||||
func longestValidParentheses1(s string) int {
|
||||
left, right, maxLength := 0, 0, 0
|
||||
for i := 0; i < len(s); i++ {
|
||||
if s[i] == '(' {
|
||||
left++
|
||||
} else {
|
||||
right++
|
||||
}
|
||||
if left == right {
|
||||
maxLength = max(maxLength, 2*right)
|
||||
} else if right > left {
|
||||
left, right = 0, 0
|
||||
}
|
||||
}
|
||||
left, right = 0, 0
|
||||
for i := len(s) - 1; i >= 0; i-- {
|
||||
if s[i] == '(' {
|
||||
left++
|
||||
} else {
|
||||
right++
|
||||
}
|
||||
if left == right {
|
||||
maxLength = max(maxLength, 2*left)
|
||||
} else if left > right {
|
||||
left, right = 0, 0
|
||||
}
|
||||
}
|
||||
return maxLength
|
||||
}
|
@ -1,61 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question32 struct {
|
||||
para32
|
||||
ans32
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para32 struct {
|
||||
s string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans32 struct {
|
||||
one int
|
||||
}
|
||||
|
||||
func Test_Problem32(t *testing.T) {
|
||||
|
||||
qs := []question32{
|
||||
|
||||
{
|
||||
para32{"(()"},
|
||||
ans32{2},
|
||||
},
|
||||
|
||||
{
|
||||
para32{")()())"},
|
||||
ans32{4},
|
||||
},
|
||||
|
||||
{
|
||||
para32{"()(())"},
|
||||
ans32{6},
|
||||
},
|
||||
|
||||
{
|
||||
para32{"()(())))"},
|
||||
ans32{6},
|
||||
},
|
||||
|
||||
{
|
||||
para32{"()(()"},
|
||||
ans32{2},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 32------------------------\n")
|
||||
for _, q := range qs {
|
||||
_, p := q.ans32, q.para32
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, longestValidParentheses(p.s))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,108 +0,0 @@
|
||||
# [32. Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: s = "(()"
|
||||
Output: 2
|
||||
Explanation: The longest valid parentheses substring is "()".
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s = ")()())"
|
||||
Output: 4
|
||||
Explanation: The longest valid parentheses substring is "()()".
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s = ""
|
||||
Output: 0
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `0 <= s.length <= 3 * 104`
|
||||
- `s[i]` is `'('`, or `')'`.
|
||||
|
||||
## 题目大意
|
||||
|
||||
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 提到括号匹配,第一时间能让人想到的就是利用栈。这里需要计算嵌套括号的总长度,所以栈里面不能单纯的存左括号,而应该存左括号在原字符串的下标,这样通过下标相减可以获取长度。那么栈如果是非空,栈底永远存的是当前遍历过的字符串中**上一个没有被匹配的右括号的下标**。**上一个没有被匹配的右括号的下标**可以理解为每段括号匹配之间的“隔板”。例如,`())((()))`,第三个右括号,即为左右 2 段正确的括号匹配中间的“隔板”。“隔板”的存在影响计算最长括号长度。如果不存在“隔板”,前后 2 段正确的括号匹配应该“融合”在一起,最长长度为 `2 + 6 = 8`,但是这里存在了“隔板”,所以最长长度仅为 `6`。
|
||||
- 具体算法实现,遇到每个 `'('` ,将它的下标压入栈中。对于遇到的每个 `')'`,先弹出栈顶元素表示匹配了当前右括号。如果栈为空,说明当前的右括号为没有被匹配的右括号,于是将其下标放入栈中来更新**上一个没有被匹配的右括号的下标**。如果栈不为空,当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度。需要注意初始化时,不存在**上一个没有被匹配的右括号的下标**,那么将 `-1` 放入栈中,充当下标为 `0` 的“隔板”。时间复杂度 O(n),空间复杂度 O(n)。
|
||||
- 在栈的方法中,实际用到的元素仅仅是栈底的**上一个没有被匹配的右括号的下标**。那么考虑能否把这个值存在一个变量中,这样可以省去栈 O(n) 的时间复杂度。利用两个计数器 left 和 right 。首先,从左到右遍历字符串,每当遇到 `'('`,增加 left 计数器,每当遇到 `')'` ,增加 right 计数器。每当 left 计数器与 right 计数器相等时,计算当前有效字符串的长度,并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时,说明括号不匹配,于是将 left 和 right 计数器同时变回 0。这样的做法利用了贪心的思想,考虑了以当前字符下标结尾的有效括号长度,每次当右括号数量多于左括号数量的时候之前的字符就扔掉不再考虑,重新从下一个字符开始计算。
|
||||
- 但上面的做法会漏掉一种情况,就是遍历的时候左括号的数量始终大于右括号的数量,即 `(()` ,这种时候最长有效括号是求不出来的。解决办法是反向再计算一遍,如果从右往左计算,`(()` 先计算匹配的括号,最后只剩下 `'('`,这样依旧可以算出最长匹配的括号长度。反过来计算的方法和上述从左往右计算的方法一致:当 left 计数器比 right 计数器大时,将 left 和 right 计数器同时变回 0;当 left 计数器与 right 计数器相等时,计算当前有效字符串的长度,并且记录目前为止找到的最长子字符串。这种方法的时间复杂度是 O(n),空间复杂度 O(1)。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
// 解法一 栈
|
||||
func longestValidParentheses(s string) int {
|
||||
stack, res := []int{}, 0
|
||||
stack = append(stack, -1)
|
||||
for i := 0; i < len(s); i++ {
|
||||
if s[i] == '(' {
|
||||
stack = append(stack, i)
|
||||
} else {
|
||||
stack = stack[:len(stack)-1]
|
||||
if len(stack) == 0 {
|
||||
stack = append(stack, i)
|
||||
} else {
|
||||
res = max(res, i-stack[len(stack)-1])
|
||||
}
|
||||
}
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
func max(a, b int) int {
|
||||
if a > b {
|
||||
return a
|
||||
}
|
||||
return b
|
||||
}
|
||||
|
||||
// 解法二 双指针
|
||||
func longestValidParentheses1(s string) int {
|
||||
left, right, maxLength := 0, 0, 0
|
||||
for i := 0; i < len(s); i++ {
|
||||
if s[i] == '(' {
|
||||
left++
|
||||
} else {
|
||||
right++
|
||||
}
|
||||
if left == right {
|
||||
maxLength = max(maxLength, 2*right)
|
||||
} else if right > left {
|
||||
left, right = 0, 0
|
||||
}
|
||||
}
|
||||
left, right = 0, 0
|
||||
for i := len(s) - 1; i >= 0; i-- {
|
||||
if s[i] == '(' {
|
||||
left++
|
||||
} else {
|
||||
right++
|
||||
}
|
||||
if left == right {
|
||||
maxLength = max(maxLength, 2*left)
|
||||
} else if left > right {
|
||||
left, right = 0, 0
|
||||
}
|
||||
}
|
||||
return maxLength
|
||||
}
|
||||
```
|
@ -45,4 +45,4 @@ candidates 中的每个数字在每个组合中只能使用一次。
|
||||
## 解题思路
|
||||
|
||||
- 题目要求出总和为 sum 的所有组合,组合需要去重。这一题是第 39 题的加强版,第 39 题中元素可以重复利用(重复元素可无限次使用),这一题中元素只能有限次数的利用,因为存在重复元素,并且每个元素只能用一次(重复元素只能使用有限次)
|
||||
- 这一题和第 47 题类似。
|
||||
- 这一题和第 47 题类似,只不过元素可以反复使用。
|
||||
|
@ -1,25 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func multiply(num1 string, num2 string) string {
|
||||
if num1 == "0" || num2 == "0" {
|
||||
return "0"
|
||||
}
|
||||
b1, b2, tmp := []byte(num1), []byte(num2), make([]int, len(num1)+len(num2))
|
||||
for i := 0; i < len(b1); i++ {
|
||||
for j := 0; j < len(b2); j++ {
|
||||
tmp[i+j+1] += int(b1[i]-'0') * int(b2[j]-'0')
|
||||
}
|
||||
}
|
||||
for i := len(tmp) - 1; i > 0; i-- {
|
||||
tmp[i-1] += tmp[i] / 10
|
||||
tmp[i] = tmp[i] % 10
|
||||
}
|
||||
if tmp[0] == 0 {
|
||||
tmp = tmp[1:]
|
||||
}
|
||||
res := make([]byte, len(tmp))
|
||||
for i := 0; i < len(tmp); i++ {
|
||||
res[i] = '0' + byte(tmp[i])
|
||||
}
|
||||
return string(res)
|
||||
}
|
@ -1,48 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question43 struct {
|
||||
para43
|
||||
ans43
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para43 struct {
|
||||
num1 string
|
||||
num2 string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans43 struct {
|
||||
one string
|
||||
}
|
||||
|
||||
func Test_Problem43(t *testing.T) {
|
||||
|
||||
qs := []question43{
|
||||
|
||||
{
|
||||
para43{"2", "3"},
|
||||
ans43{"6"},
|
||||
},
|
||||
|
||||
{
|
||||
para43{"123", "456"},
|
||||
ans43{"56088"},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 43------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans43, q.para43
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, multiply(p.num1, p.num2))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,66 +0,0 @@
|
||||
# [43. Multiply Strings](https://leetcode.com/problems/multiply-strings/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.
|
||||
|
||||
**Note:** You must not use any built-in BigInteger library or convert the inputs to integer directly.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: num1 = "2", num2 = "3"
|
||||
Output: "6"
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: num1 = "123", num2 = "456"
|
||||
Output: "56088"
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= num1.length, num2.length <= 200`
|
||||
- `num1` and `num2` consist of digits only.
|
||||
- Both `num1` and `num2` do not contain any leading zero, except the number `0` itself.
|
||||
|
||||
## 题目大意
|
||||
|
||||
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 用数组模拟乘法。创建一个数组长度为 `len(num1) + len(num2)` 的数组用于存储乘积。对于任意 `0 ≤ i < len(num1)`,`0 ≤ j < len(num2)`,`num1[i] * num2[j]` 的结果位于 `tmp[i+j+1]`,如果 `tmp[i+j+1]≥10`,则将进位部分加到 `tmp[i+j]`。最后,将数组 `tmp` 转成字符串,如果最高位是 0 则舍弃最高位。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func multiply(num1 string, num2 string) string {
|
||||
if num1 == "0" || num2 == "0" {
|
||||
return "0"
|
||||
}
|
||||
b1, b2, tmp := []byte(num1), []byte(num2), make([]int, len(num1)+len(num2))
|
||||
for i := 0; i < len(b1); i++ {
|
||||
for j := 0; j < len(b2); j++ {
|
||||
tmp[i+j+1] += int(b1[i]-'0') * int(b2[j]-'0')
|
||||
}
|
||||
}
|
||||
for i := len(tmp) - 1; i > 0; i-- {
|
||||
tmp[i-1] += tmp[i] / 10
|
||||
tmp[i] = tmp[i] % 10
|
||||
}
|
||||
if tmp[0] == 0 {
|
||||
tmp = tmp[1:]
|
||||
}
|
||||
res := make([]byte, len(tmp))
|
||||
for i := 0; i < len(tmp); i++ {
|
||||
res[i] = '0' + byte(tmp[i])
|
||||
}
|
||||
return string(res)
|
||||
}
|
||||
```
|
@ -1,21 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func jump(nums []int) int {
|
||||
if len(nums) == 1 {
|
||||
return 0
|
||||
}
|
||||
needChoose, canReach, step := 0, 0, 0
|
||||
for i, x := range nums {
|
||||
if i+x > canReach {
|
||||
canReach = i + x
|
||||
if canReach >= len(nums)-1 {
|
||||
return step + 1
|
||||
}
|
||||
}
|
||||
if i == needChoose {
|
||||
needChoose = canReach
|
||||
step++
|
||||
}
|
||||
}
|
||||
return step
|
||||
}
|
@ -1,47 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question45 struct {
|
||||
para45
|
||||
ans45
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para45 struct {
|
||||
nums []int
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans45 struct {
|
||||
one int
|
||||
}
|
||||
|
||||
func Test_Problem45(t *testing.T) {
|
||||
|
||||
qs := []question45{
|
||||
|
||||
{
|
||||
para45{[]int{2, 3, 1, 1, 4}},
|
||||
ans45{2},
|
||||
},
|
||||
|
||||
{
|
||||
para45{[]int{2, 3, 0, 1, 4}},
|
||||
ans45{2},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 45------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans45, q.para45
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, jump(p.nums))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,67 +0,0 @@
|
||||
# [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given an array of non-negative integers `nums`, you are initially positioned at the first index of the array.
|
||||
|
||||
Each element in the array represents your maximum jump length at that position.
|
||||
|
||||
Your goal is to reach the last index in the minimum number of jumps.
|
||||
|
||||
You can assume that you can always reach the last index.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: nums = [2,3,1,1,4]
|
||||
Output: 2
|
||||
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: nums = [2,3,0,1,4]
|
||||
Output: 2
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= nums.length <= 1000`
|
||||
- `0 <= nums[i] <= 10^5`
|
||||
|
||||
## 题目大意
|
||||
|
||||
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 要求找到最少跳跃次数,顺理成章的会想到用贪心算法解题。扫描步数数组,维护当前能够到达最大下标的位置,记为能到达的最远边界,如果扫描过程中到达了最远边界,更新边界并将跳跃次数 + 1。
|
||||
- 扫描数组的时候,其实不需要扫描最后一个元素,因为在跳到最后一个元素之前,能到达的最远边界一定大于等于最后一个元素的位置,不然就跳不到最后一个元素,到达不了终点了;如果遍历到最后一个元素,说明边界正好为最后一个位置,最终跳跃次数直接 + 1 即可,也不需要访问最后一个元素。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func jump(nums []int) int {
|
||||
if len(nums) == 1 {
|
||||
return 0
|
||||
}
|
||||
needChoose, canReach, step := 0, 0, 0
|
||||
for i, x := range nums {
|
||||
if i+x > canReach {
|
||||
canReach = i + x
|
||||
if canReach >= len(nums)-1 {
|
||||
return step + 1
|
||||
}
|
||||
}
|
||||
if i == needChoose {
|
||||
needChoose = canReach
|
||||
step++
|
||||
}
|
||||
}
|
||||
return step
|
||||
}
|
||||
```
|
@ -1,61 +1,26 @@
|
||||
package leetcode
|
||||
|
||||
// 解法一
|
||||
func rotate(matrix [][]int) {
|
||||
length := len(matrix)
|
||||
row := len(matrix)
|
||||
if row <= 0 {
|
||||
return
|
||||
}
|
||||
column := len(matrix[0])
|
||||
// rotate by diagonal 对角线变换
|
||||
for i := 0; i < length; i++ {
|
||||
for j := i + 1; j < length; j++ {
|
||||
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
|
||||
for i := 0; i < row; i++ {
|
||||
for j := i + 1; j < column; j++ {
|
||||
tmp := matrix[i][j]
|
||||
matrix[i][j] = matrix[j][i]
|
||||
matrix[j][i] = tmp
|
||||
}
|
||||
}
|
||||
// rotate by vertical centerline 竖直轴对称翻转
|
||||
for i := 0; i < length; i++ {
|
||||
for j := 0; j < length/2; j++ {
|
||||
matrix[i][j], matrix[i][length-j-1] = matrix[i][length-j-1], matrix[i][j]
|
||||
halfColumn := column / 2
|
||||
for i := 0; i < row; i++ {
|
||||
for j := 0; j < halfColumn; j++ {
|
||||
tmp := matrix[i][j]
|
||||
matrix[i][j] = matrix[i][column-j-1]
|
||||
matrix[i][column-j-1] = tmp
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// 解法二
|
||||
func rotate1(matrix [][]int) {
|
||||
n := len(matrix)
|
||||
if n == 1 {
|
||||
return
|
||||
}
|
||||
/* rotate clock-wise = 1. transpose matrix => 2. reverse(matrix[i])
|
||||
|
||||
1 2 3 4 1 5 9 13 13 9 5 1
|
||||
5 6 7 8 => 2 6 10 14 => 14 10 6 2
|
||||
9 10 11 12 3 7 11 15 15 11 7 3
|
||||
13 14 15 16 4 8 12 16 16 12 8 4
|
||||
|
||||
*/
|
||||
|
||||
for i := 0; i < n; i++ {
|
||||
// transpose, i=rows, j=columns
|
||||
// j = i+1, coz diagonal elements didn't change in a square matrix
|
||||
for j := i + 1; j < n; j++ {
|
||||
swap(matrix, i, j)
|
||||
}
|
||||
// reverse each row of the image
|
||||
matrix[i] = reverse(matrix[i])
|
||||
}
|
||||
}
|
||||
|
||||
// swap changes original slice's i,j position
|
||||
func swap(nums [][]int, i, j int) {
|
||||
nums[i][j], nums[j][i] = nums[j][i], nums[i][j]
|
||||
}
|
||||
|
||||
// reverses a row of image, matrix[i]
|
||||
func reverse(nums []int) []int {
|
||||
var lp, rp = 0, len(nums) - 1
|
||||
|
||||
for lp < rp {
|
||||
nums[lp], nums[rp] = nums[rp], nums[lp]
|
||||
lp++
|
||||
rp--
|
||||
}
|
||||
return nums
|
||||
}
|
||||
|
@ -10,9 +10,8 @@ Rotate the image by 90 degrees (clockwise).
|
||||
|
||||
You have to rotate the image **[in-place](https://en.wikipedia.org/wiki/In-place_algorithm)**, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.
|
||||
|
||||
**Example 1**:
|
||||
**Example 1:**
|
||||
|
||||

|
||||
|
||||
Given input matrix =
|
||||
[
|
||||
@ -29,9 +28,8 @@ You have to rotate the image **[in-place](https://en.wikipedia.org/wiki/In-plac
|
||||
]
|
||||
|
||||
|
||||
**Example 2**:
|
||||
**Example 2:**
|
||||
|
||||

|
||||
|
||||
Given input matrix =
|
||||
[
|
||||
|
@ -47,45 +47,39 @@ func generateBoard(n int, row *[]int) []string {
|
||||
return board
|
||||
}
|
||||
|
||||
// 解法二 二进制操作法 Signed-off-by: Hanlin Shi shihanlin9@gmail.com
|
||||
func solveNQueens2(n int) (res [][]string) {
|
||||
placements := make([]string, n)
|
||||
for i := range placements {
|
||||
buf := make([]byte, n)
|
||||
for j := range placements {
|
||||
if i == j {
|
||||
buf[j] = 'Q'
|
||||
} else {
|
||||
buf[j] = '.'
|
||||
}
|
||||
}
|
||||
placements[i] = string(buf)
|
||||
}
|
||||
var construct func(prev []int)
|
||||
construct = func(prev []int) {
|
||||
if len(prev) == n {
|
||||
plan := make([]string, n)
|
||||
for i := 0; i < n; i++ {
|
||||
plan[i] = placements[prev[i]]
|
||||
}
|
||||
res = append(res, plan)
|
||||
return
|
||||
}
|
||||
occupied := 0
|
||||
for i := range prev {
|
||||
dist := len(prev) - i
|
||||
bit := 1 << prev[i]
|
||||
occupied |= bit | bit<<dist | bit>>dist
|
||||
}
|
||||
prev = append(prev, -1)
|
||||
for i := 0; i < n; i++ {
|
||||
if (occupied>>i)&1 != 0 {
|
||||
continue
|
||||
}
|
||||
prev[len(prev)-1] = i
|
||||
construct(prev)
|
||||
}
|
||||
}
|
||||
construct(make([]int, 0, n))
|
||||
return
|
||||
}
|
||||
// 解法二 二进制操作法
|
||||
// class Solution
|
||||
// {
|
||||
// int n;
|
||||
// string getNq(int p)
|
||||
// {
|
||||
// string s(n, '.');
|
||||
// s[p] = 'Q';
|
||||
// return s;
|
||||
// }
|
||||
// void nQueens(int p, int l, int m, int r, vector<vector<string>> &res)
|
||||
// {
|
||||
// static vector<string> ans;
|
||||
// if (p >= n)
|
||||
// {
|
||||
// res.push_back(ans);
|
||||
// return ;
|
||||
// }
|
||||
// int mask = l | m | r;
|
||||
// for (int i = 0, b = 1; i < n; ++ i, b <<= 1)
|
||||
// if (!(mask & b))
|
||||
// {
|
||||
// ans.push_back(getNq(i));
|
||||
// nQueens(p + 1, (l | b) >> 1, m | b, (r | b) << 1, res);
|
||||
// ans.pop_back();
|
||||
// }
|
||||
// }
|
||||
// public:
|
||||
// vector<vector<string> > solveNQueens(int n)
|
||||
// {
|
||||
// this->n = n;
|
||||
// vector<vector<string>> res;
|
||||
// nQueens(0, 0, 0, 0, res);
|
||||
// return res;
|
||||
// }
|
||||
// };
|
||||
|
@ -40,5 +40,4 @@ Each solution contains a distinct board configuration of the *n*-queens' placem
|
||||
- 利用 col 数组记录列信息,col 有 `n` 列。用 dia1,dia2 记录从左下到右上的对角线,从左上到右下的对角线的信息,dia1 和 dia2 分别都有 `2*n-1` 个。
|
||||
- dia1 对角线的规律是 `i + j 是定值`,例如[0,0],为 0;[1,0]、[0,1] 为 1;[2,0]、[1,1]、[0,2] 为 2;
|
||||
- dia2 对角线的规律是 `i - j 是定值`,例如[0,7],为 -7;[0,6]、[1,7] 为 -6;[0,5]、[1,6]、[2,7] 为 -5;为了使他们从 0 开始,i - j + n - 1 偏移到 0 开始,所以 dia2 的规律是 `i - j + n - 1 为定值`。
|
||||
- 还有一个位运算的方法,每行只能选一个位置放皇后,那么对每行遍历可能放皇后的位置。如何高效判断哪些点不能放皇后呢?这里的做法毕竟巧妙,把所有之前选过的点按照顺序存下来,然后根据之前选的点到当前行的距离,就可以快速判断是不是会有冲突。举个例子: 假如在 4 皇后问题中,如果第一二行已经选择了位置 [1, 3],那么在第三行选择时,首先不能再选 1, 3 列了,而对于第三行, 1 距离长度为2,所以它会影响到 -1, 3 两个列。同理,3 在第二行,距离第三行为 1,所以 3 会影响到列 2, 4。由上面的结果,我们知道 -1, 4 超出边界了不用去管,别的不能选的点是 1, 2, 3,所以第三行就只能选 0。在代码实现中,可以在每次遍历前根据之前选择的情况生成一个 occupied 用来记录当前这一行,已经被选了的和由于之前皇后攻击范围所以不能选的位置,然后只选择合法的位置进入到下一层递归。另外就是预处理了一个皇后放不同位置的字符串,这样这些字符串在返回结果的时候是可以在内存中复用的,省一点内存。
|
||||
|
||||
|
@ -1,16 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func lengthOfLastWord(s string) int {
|
||||
last := len(s) - 1
|
||||
for last >= 0 && s[last] == ' ' {
|
||||
last--
|
||||
}
|
||||
if last < 0 {
|
||||
return 0
|
||||
}
|
||||
first := last
|
||||
for first >= 0 && s[first] != ' ' {
|
||||
first--
|
||||
}
|
||||
return last - first
|
||||
}
|
@ -1,50 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question58 struct {
|
||||
para58
|
||||
ans58
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
type para58 struct {
|
||||
s string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
type ans58 struct {
|
||||
ans int
|
||||
}
|
||||
|
||||
func Test_Problem58(t *testing.T) {
|
||||
|
||||
qs := []question58{
|
||||
|
||||
{
|
||||
para58{"Hello World"},
|
||||
ans58{5},
|
||||
},
|
||||
|
||||
{
|
||||
para58{" fly me to the moon "},
|
||||
ans58{4},
|
||||
},
|
||||
|
||||
{
|
||||
para58{"luffy is still joyboy"},
|
||||
ans58{6},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 58------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans58, q.para58
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, lengthOfLastWord(p.s))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,70 +0,0 @@
|
||||
# [58. Length of Last Word](https://leetcode.com/problems/length-of-last-word/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given a string `s` consisting of some words separated by some number of spaces, return *the length of the **last** word in the string.*
|
||||
|
||||
A **word** is a maximal substring consisting of non-space characters only.
|
||||
|
||||
**Example 1:**
|
||||
|
||||
```
|
||||
Input: s = "Hello World"
|
||||
Output: 5
|
||||
Explanation: The last word is "World" with length 5.
|
||||
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s = " fly me to the moon "
|
||||
Output: 4
|
||||
Explanation: The last word is "moon" with length 4.
|
||||
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s = "luffy is still joyboy"
|
||||
Output: 6
|
||||
Explanation: The last word is "joyboy" with length 6.
|
||||
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `1 <= s.length <= 104`
|
||||
- `s` consists of only English letters and spaces `' '`.
|
||||
- There will be at least one word in `s`.
|
||||
|
||||
## 题目大意
|
||||
|
||||
给你一个字符串 `s`,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。**单词** 是指仅由字母组成、不包含任何空格字符的最大子字符串。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 先从后过滤掉空格找到单词尾部,再从尾部向前遍历,找到单词头部,最后两者相减,即为单词的长度。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func lengthOfLastWord(s string) int {
|
||||
last := len(s) - 1
|
||||
for last >= 0 && s[last] == ' ' {
|
||||
last--
|
||||
}
|
||||
if last < 0 {
|
||||
return 0
|
||||
}
|
||||
first := last
|
||||
for first >= 0 && s[first] != ' ' {
|
||||
first--
|
||||
}
|
||||
return last - first
|
||||
}
|
||||
```
|
@ -5,12 +5,14 @@ func uniquePaths(m int, n int) int {
|
||||
for i := 0; i < n; i++ {
|
||||
dp[i] = make([]int, m)
|
||||
}
|
||||
for i := 0; i < m; i++ {
|
||||
dp[0][i] = 1
|
||||
}
|
||||
for i := 0; i < n; i++ {
|
||||
for j := 0; j < m; j++ {
|
||||
if i == 0 || j == 0 {
|
||||
dp[i][j] = 1
|
||||
continue
|
||||
}
|
||||
dp[i][0] = 1
|
||||
}
|
||||
for i := 1; i < n; i++ {
|
||||
for j := 1; j < m; j++ {
|
||||
dp[i][j] = dp[i-1][j] + dp[i][j-1]
|
||||
}
|
||||
}
|
||||
|
@ -1,22 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func isNumber(s string) bool {
|
||||
numFlag, dotFlag, eFlag := false, false, false
|
||||
for i := 0; i < len(s); i++ {
|
||||
if '0' <= s[i] && s[i] <= '9' {
|
||||
numFlag = true
|
||||
} else if s[i] == '.' && !dotFlag && !eFlag {
|
||||
dotFlag = true
|
||||
} else if (s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag {
|
||||
eFlag = true
|
||||
numFlag = false // reJudge integer after 'e' or 'E'
|
||||
} else if (s[i] == '+' || s[i] == '-') && (i == 0 || s[i-1] == 'e' || s[i-1] == 'E') {
|
||||
continue
|
||||
} else {
|
||||
return false
|
||||
}
|
||||
}
|
||||
// avoid case: s == '.' or 'e/E' or '+/-' and etc...
|
||||
// string s must have num
|
||||
return numFlag
|
||||
}
|
@ -1,41 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
func Test_Problem65(t *testing.T) {
|
||||
|
||||
tcs := []struct {
|
||||
s string
|
||||
ans bool
|
||||
}{
|
||||
|
||||
{
|
||||
"0",
|
||||
true,
|
||||
},
|
||||
|
||||
{
|
||||
"e",
|
||||
false,
|
||||
},
|
||||
|
||||
{
|
||||
".",
|
||||
false,
|
||||
},
|
||||
|
||||
{
|
||||
".1",
|
||||
true,
|
||||
},
|
||||
}
|
||||
fmt.Printf("------------------------Leetcode Problem 65------------------------\n")
|
||||
|
||||
for _, tc := range tcs {
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", tc, isNumber(tc.s))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,78 +0,0 @@
|
||||
# [65. Valid Number](https://leetcode.com/problems/valid-number/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
A **valid number** can be split up into these components (in order):
|
||||
|
||||
1. A **decimal number** or an integer.
|
||||
2. (Optional) An 'e' or 'E', followed by an **integer.**
|
||||
|
||||
A **decimal number** can be split up into these components (in order):
|
||||
|
||||
1. (Optional) A sign character (either '+' or '-').
|
||||
2. One of the following formats:
|
||||
1. One or more digits, followed by a dot '.'.
|
||||
2. One or more digits, followed by a dot '.', followed by one or more digits.
|
||||
3. A dot '.', followed by one or more digits.
|
||||
|
||||
An **integer** can be split up into these components (in order):
|
||||
|
||||
1. (Optional) A sign character (either '+' or '-').
|
||||
2. One or more digits.
|
||||
|
||||
For example, all the following are valid numbers: `["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]`, while the following are not valid numbers: `["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].`
|
||||
|
||||
Given a string s, return true if s is a **valid number.**
|
||||
|
||||
**Example:**
|
||||
|
||||
Input: s = "0"
|
||||
Output: true
|
||||
|
||||
Input: s = "e"
|
||||
Output: false
|
||||
|
||||
## 题目大意
|
||||
|
||||
给定一个字符串S,请根据以上的规则判断该字符串是否是一个有效的数字字符串。
|
||||
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 用三个变量分别标记是否出现过数字、是否出现过'.'和 是否出现过 'e/E'
|
||||
- 从左到右依次遍历字符串中的每一个元素
|
||||
- 如果是数字,则标记数字出现过
|
||||
- 如果是 '.', 则需要 '.'没有出现过,并且 'e/E' 没有出现过,才会进行标记
|
||||
- 如果是 'e/E', 则需要 'e/E'没有出现过,并且前面出现过数字,才会进行标记
|
||||
- 如果是 '+/-', 则需要是第一个字符,或者前一个字符是 'e/E',才会进行标记,并重置数字出现的标识
|
||||
- 最后返回时,需要字符串中至少出现过数字,避免下列case: s == '.' or 'e/E' or '+/e' and etc...
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
|
||||
package leetcode
|
||||
|
||||
func isNumber(s string) bool {
|
||||
numFlag, dotFlag, eFlag := false, false, false
|
||||
for i := 0; i < len(s); i++ {
|
||||
if '0' <= s[i] && s[i] <= '9' {
|
||||
numFlag = true
|
||||
} else if s[i] == '.' && !dotFlag && !eFlag {
|
||||
dotFlag = true
|
||||
} else if (s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag {
|
||||
eFlag = true
|
||||
numFlag = false // reJudge integer after 'e' or 'E'
|
||||
} else if (s[i] == '+' || s[i] == '-') && (i == 0 || s[i-1] == 'e' || s[i-1] == 'E') {
|
||||
continue
|
||||
} else {
|
||||
return false
|
||||
}
|
||||
}
|
||||
// avoid case: s == '.' or 'e/E' or '+/-' and etc...
|
||||
// string s must have num
|
||||
return numFlag
|
||||
}
|
||||
|
||||
```
|
@ -1,17 +1,21 @@
|
||||
package leetcode
|
||||
|
||||
func plusOne(digits []int) []int {
|
||||
for i := len(digits) - 1; i >= 0; i-- {
|
||||
digits[i]++
|
||||
if digits[i] != 10 {
|
||||
// no carry
|
||||
return digits
|
||||
}
|
||||
// carry
|
||||
digits[i] = 0
|
||||
if len(digits) == 0 {
|
||||
return []int{}
|
||||
}
|
||||
carry := 1
|
||||
for i := len(digits) - 1; i >= 0; i-- {
|
||||
if digits[i]+carry > 9 {
|
||||
digits[i] = 0
|
||||
carry = 1
|
||||
} else {
|
||||
digits[i] += carry
|
||||
carry = 0
|
||||
}
|
||||
}
|
||||
if digits[0] == 0 && carry == 1 {
|
||||
digits = append([]int{1}, digits...)
|
||||
}
|
||||
// all carry
|
||||
digits[0] = 1
|
||||
digits = append(digits, 0)
|
||||
return digits
|
||||
}
|
||||
|
@ -1,17 +1,23 @@
|
||||
package leetcode
|
||||
|
||||
// 解法一 二分, 找到最后一个满足 n^2 <= x 的整数n
|
||||
// 解法一 二分
|
||||
func mySqrt(x int) int {
|
||||
l, r := 0, x
|
||||
for l < r {
|
||||
mid := (l + r + 1) / 2
|
||||
if mid*mid > x {
|
||||
r = mid - 1
|
||||
if x == 0 {
|
||||
return 0
|
||||
}
|
||||
left, right, res := 1, x, 0
|
||||
for left <= right {
|
||||
mid := left + ((right - left) >> 1)
|
||||
if mid < x/mid {
|
||||
left = mid + 1
|
||||
res = mid
|
||||
} else if mid == x/mid {
|
||||
return mid
|
||||
} else {
|
||||
l = mid
|
||||
right = mid - 1
|
||||
}
|
||||
}
|
||||
return l
|
||||
return res
|
||||
}
|
||||
|
||||
// 解法二 牛顿迭代法 https://en.wikipedia.org/wiki/Integer_square_root
|
||||
|
@ -1,54 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func setZeroes(matrix [][]int) {
|
||||
if len(matrix) == 0 || len(matrix[0]) == 0 {
|
||||
return
|
||||
}
|
||||
isFirstRowExistZero, isFirstColExistZero := false, false
|
||||
for i := 0; i < len(matrix); i++ {
|
||||
if matrix[i][0] == 0 {
|
||||
isFirstColExistZero = true
|
||||
break
|
||||
}
|
||||
}
|
||||
for j := 0; j < len(matrix[0]); j++ {
|
||||
if matrix[0][j] == 0 {
|
||||
isFirstRowExistZero = true
|
||||
break
|
||||
}
|
||||
}
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
if matrix[i][j] == 0 {
|
||||
matrix[i][0] = 0
|
||||
matrix[0][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
// 处理[1:]行全部置 0
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
if matrix[i][0] == 0 {
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
matrix[i][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
// 处理[1:]列全部置 0
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
if matrix[0][j] == 0 {
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
matrix[i][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
if isFirstRowExistZero {
|
||||
for j := 0; j < len(matrix[0]); j++ {
|
||||
matrix[0][j] = 0
|
||||
}
|
||||
}
|
||||
if isFirstColExistZero {
|
||||
for i := 0; i < len(matrix); i++ {
|
||||
matrix[i][0] = 0
|
||||
}
|
||||
}
|
||||
}
|
@ -1,47 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question73 struct {
|
||||
para73
|
||||
ans73
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para73 struct {
|
||||
matrix [][]int
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans73 struct {
|
||||
}
|
||||
|
||||
func Test_Problem73(t *testing.T) {
|
||||
|
||||
qs := []question73{
|
||||
|
||||
{
|
||||
para73{[][]int{
|
||||
{0, 1, 2, 0},
|
||||
{3, 4, 5, 2},
|
||||
{1, 3, 1, 5},
|
||||
}},
|
||||
ans73{},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 73------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans73, q.para73
|
||||
fmt.Printf("【input】:%v ", p)
|
||||
setZeroes(p.matrix)
|
||||
fmt.Printf("【output】:%v\n", p)
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,104 +0,0 @@
|
||||
# [73. Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given an *`m* x *n*` matrix. If an element is **0**, set its entire row and column to **0**. Do it **[in-place](https://en.wikipedia.org/wiki/In-place_algorithm)**.
|
||||
|
||||
**Follow up:**
|
||||
|
||||
- A straight forward solution using O(*mn*) space is probably a bad idea.
|
||||
- A simple improvement uses O(*m* + *n*) space, but still not the best solution.
|
||||
- Could you devise a constant space solution?
|
||||
|
||||
**Example 1:**
|
||||
|
||||

|
||||
|
||||
```
|
||||
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
|
||||
Output: [[1,0,1],[0,0,0],[1,0,1]]
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||

|
||||
|
||||
```
|
||||
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
|
||||
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `m == matrix.length`
|
||||
- `n == matrix[0].length`
|
||||
- `1 <= m, n <= 200`
|
||||
- `2^31 <= matrix[i][j] <= 2^31 - 1`
|
||||
|
||||
## 题目大意
|
||||
|
||||
给定一个 `m x n` 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 此题考查对程序的控制能力,无算法思想。题目要求采用原地的算法,所有修改即在原二维数组上进行。在二维数组中有 2 个特殊位置,一个是第一行,一个是第一列。它们的特殊性在于,它们之间只要有一个 0,它们都会变为全 0 。先用 2 个变量记录这一行和这一列中是否有 0,防止之后的修改覆盖了这 2 个地方。然后除去这一行和这一列以外的部分判断是否有 0,如果有 0,将它们所在的行第一个元素标记为 0,所在列的第一个元素标记为 0 。最后通过标记,将对应的行列置 0 即可。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func setZeroes(matrix [][]int) {
|
||||
if len(matrix) == 0 || len(matrix[0]) == 0 {
|
||||
return
|
||||
}
|
||||
isFirstRowExistZero, isFirstColExistZero := false, false
|
||||
for i := 0; i < len(matrix); i++ {
|
||||
if matrix[i][0] == 0 {
|
||||
isFirstColExistZero = true
|
||||
break
|
||||
}
|
||||
}
|
||||
for j := 0; j < len(matrix[0]); j++ {
|
||||
if matrix[0][j] == 0 {
|
||||
isFirstRowExistZero = true
|
||||
break
|
||||
}
|
||||
}
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
if matrix[i][j] == 0 {
|
||||
matrix[i][0] = 0
|
||||
matrix[0][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
// 处理[1:]行全部置 0
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
if matrix[i][0] == 0 {
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
matrix[i][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
// 处理[1:]列全部置 0
|
||||
for j := 1; j < len(matrix[0]); j++ {
|
||||
if matrix[0][j] == 0 {
|
||||
for i := 1; i < len(matrix); i++ {
|
||||
matrix[i][j] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
if isFirstRowExistZero {
|
||||
for j := 0; j < len(matrix[0]); j++ {
|
||||
matrix[0][j] = 0
|
||||
}
|
||||
}
|
||||
if isFirstColExistZero {
|
||||
for i := 0; i < len(matrix); i++ {
|
||||
matrix[i][0] = 0
|
||||
}
|
||||
}
|
||||
}
|
||||
```
|
@ -1,16 +1,28 @@
|
||||
package leetcode
|
||||
|
||||
func sortColors(nums []int) {
|
||||
zero, one := 0, 0
|
||||
for i, n := range nums {
|
||||
nums[i] = 2
|
||||
if n <= 1 {
|
||||
nums[one] = 1
|
||||
one++
|
||||
}
|
||||
if n == 0 {
|
||||
nums[zero] = 0
|
||||
zero++
|
||||
if len(nums) == 0 {
|
||||
return
|
||||
}
|
||||
|
||||
r := 0
|
||||
w := 0
|
||||
b := 0 // label the end of different colors;
|
||||
for _, num := range nums {
|
||||
if num == 0 {
|
||||
nums[b] = 2
|
||||
b++
|
||||
nums[w] = 1
|
||||
w++
|
||||
nums[r] = 0
|
||||
r++
|
||||
} else if num == 1 {
|
||||
nums[b] = 2
|
||||
b++
|
||||
nums[w] = 1
|
||||
w++
|
||||
} else if num == 2 {
|
||||
b++
|
||||
}
|
||||
}
|
||||
}
|
||||
|
@ -32,7 +32,9 @@ func minWindow(s string, t string) string {
|
||||
}
|
||||
}
|
||||
if finalLeft != -1 {
|
||||
result = string(s[finalLeft : finalRight+1])
|
||||
for i := finalLeft; i < finalRight+1; i++ {
|
||||
result += string(s[i])
|
||||
}
|
||||
}
|
||||
return result
|
||||
}
|
||||
|
@ -1,12 +1,35 @@
|
||||
package leetcode
|
||||
|
||||
func removeDuplicates(nums []int) int {
|
||||
slow := 0
|
||||
for fast, v := range nums {
|
||||
if fast < 2 || nums[slow-2] != v {
|
||||
nums[slow] = v
|
||||
slow++
|
||||
func removeDuplicates80(nums []int) int {
|
||||
if len(nums) == 0 {
|
||||
return 0
|
||||
}
|
||||
last, finder := 0, 0
|
||||
for last < len(nums)-1 {
|
||||
startFinder := -1
|
||||
for nums[finder] == nums[last] {
|
||||
if startFinder == -1 || startFinder > finder {
|
||||
startFinder = finder
|
||||
}
|
||||
if finder == len(nums)-1 {
|
||||
break
|
||||
}
|
||||
finder++
|
||||
}
|
||||
if finder-startFinder >= 2 && nums[finder-1] == nums[last] && nums[finder] != nums[last] {
|
||||
nums[last+1] = nums[finder-1]
|
||||
nums[last+2] = nums[finder]
|
||||
last += 2
|
||||
} else {
|
||||
nums[last+1] = nums[finder]
|
||||
last++
|
||||
}
|
||||
if finder == len(nums)-1 {
|
||||
if nums[finder] != nums[last-1] {
|
||||
nums[last] = nums[finder]
|
||||
}
|
||||
return last + 1
|
||||
}
|
||||
}
|
||||
return slow
|
||||
return last + 1
|
||||
}
|
||||
|
@ -61,7 +61,7 @@ func Test_Problem80(t *testing.T) {
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans80, q.para80
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p.one, removeDuplicates(p.one))
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p.one, removeDuplicates80(p.one))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
||||
|
@ -51,6 +51,6 @@ for (int i = 0; i < len; i++) {
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 问题提示有序数组,一般最容易想到使用双指针的解法,双指针的关键点:移动两个指针的条件。
|
||||
- 在该题中移动的条件:快指针从头遍历数组,慢指针指向修改后的数组的末端,当慢指针指向倒数第二个数与快指针指向的数不相等时,才移动慢指针,同时赋值慢指针。
|
||||
- 处理边界条件:当数组小于两个元素时,不做处理。
|
||||
这道题和第 26 题很像。是第 26 题的加强版。这道题和第 283 题,第 27 题基本一致,283 题是删除 0,27 题是删除指定元素,这一题是删除重复元素,实质是一样的。
|
||||
|
||||
这里数组的删除并不是真的删除,只是将删除的元素移动到数组后面的空间内,然后返回数组实际剩余的元素个数,OJ 最终判断题目的时候会读取数组剩余个数的元素进行输出。
|
||||
|
@ -1,25 +1,32 @@
|
||||
package leetcode
|
||||
|
||||
import "fmt"
|
||||
|
||||
func largestRectangleArea(heights []int) int {
|
||||
maxArea := 0
|
||||
n := len(heights) + 2
|
||||
// Add a sentry at the beginning and the end
|
||||
getHeight := func(i int) int {
|
||||
if i == 0 || n-1 == i {
|
||||
return 0
|
||||
maxArea, stack, height := 0, []int{}, 0
|
||||
for i := 0; i <= len(heights); i++ {
|
||||
if i == len(heights) {
|
||||
height = 0
|
||||
} else {
|
||||
height = heights[i]
|
||||
}
|
||||
return heights[i-1]
|
||||
}
|
||||
st := make([]int, 0, n/2)
|
||||
for i := 0; i < n; i++ {
|
||||
for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
|
||||
// pop stack
|
||||
idx := st[len(st)-1]
|
||||
st = st[:len(st)-1]
|
||||
maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
|
||||
if len(stack) == 0 || height >= heights[stack[len(stack)-1]] {
|
||||
stack = append(stack, i)
|
||||
} else {
|
||||
tmp := stack[len(stack)-1]
|
||||
fmt.Printf("1. tmp = %v stack = %v\n", tmp, stack)
|
||||
stack = stack[:len(stack)-1]
|
||||
length := 0
|
||||
if len(stack) == 0 {
|
||||
length = i
|
||||
} else {
|
||||
length = i - 1 - stack[len(stack)-1]
|
||||
fmt.Printf("2. length = %v stack = %v i = %v\n", length, stack, i)
|
||||
}
|
||||
maxArea = max(maxArea, heights[tmp]*length)
|
||||
fmt.Printf("3. maxArea = %v heights[tmp]*length = %v\n", maxArea, heights[tmp]*length)
|
||||
i--
|
||||
}
|
||||
// push stack
|
||||
st = append(st, i)
|
||||
}
|
||||
return maxArea
|
||||
}
|
||||
|
@ -40,10 +40,6 @@ func Test_Problem84(t *testing.T) {
|
||||
para84{[]int{1, 1}},
|
||||
ans84{2},
|
||||
},
|
||||
{
|
||||
para84{[]int{2, 1, 2}},
|
||||
ans84{3},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 84------------------------\n")
|
||||
|
@ -1,16 +1,29 @@
|
||||
package leetcode
|
||||
|
||||
func merge(nums1 []int, m int, nums2 []int, n int) {
|
||||
for p := m + n; m > 0 && n > 0; p-- {
|
||||
if nums1[m-1] <= nums2[n-1] {
|
||||
nums1[p-1] = nums2[n-1]
|
||||
n--
|
||||
if m == 0 {
|
||||
copy(nums1, nums2)
|
||||
return
|
||||
}
|
||||
// 这里不需要,因为测试数据考虑到了第一个数组的空间问题
|
||||
// for index := 0; index < n; index++ {
|
||||
// nums1 = append(nums1, nums2[index])
|
||||
// }
|
||||
i := m - 1
|
||||
j := n - 1
|
||||
k := m + n - 1
|
||||
// 从后面往前放,只需要循环一次即可
|
||||
for ; i >= 0 && j >= 0; k-- {
|
||||
if nums1[i] > nums2[j] {
|
||||
nums1[k] = nums1[i]
|
||||
i--
|
||||
} else {
|
||||
nums1[p-1] = nums1[m-1]
|
||||
m--
|
||||
nums1[k] = nums2[j]
|
||||
j--
|
||||
}
|
||||
}
|
||||
for ; n > 0; n-- {
|
||||
nums1[n-1] = nums2[n-1]
|
||||
for ; j >= 0; k-- {
|
||||
nums1[k] = nums2[j]
|
||||
j--
|
||||
}
|
||||
}
|
||||
|
@ -29,10 +29,20 @@ func Test_Problem88(t *testing.T) {
|
||||
|
||||
qs := []question88{
|
||||
|
||||
{
|
||||
para88{[]int{0}, 0, []int{1}, 1},
|
||||
ans88{[]int{1}},
|
||||
},
|
||||
// question{
|
||||
// para{[]int{0}, 0, []int{1}, 1},
|
||||
// ans{[]int{1}},
|
||||
// },
|
||||
//
|
||||
// question{
|
||||
// para{[]int{1, 3, 5, 7}, 4, []int{2, 4}, 2},
|
||||
// ans{[]int{1, 2, 3, 4}},
|
||||
// },
|
||||
//
|
||||
// question{
|
||||
// para{[]int{1, 3, 5, 7}, 4, []int{2, 2}, 2},
|
||||
// ans{[]int{1, 2, 2, 3}},
|
||||
// },
|
||||
|
||||
{
|
||||
para88{[]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3},
|
||||
|
@ -1,16 +1,29 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"strconv"
|
||||
)
|
||||
|
||||
func numDecodings(s string) int {
|
||||
n := len(s)
|
||||
dp := make([]int, n+1)
|
||||
if len(s) == 0 {
|
||||
return 0
|
||||
}
|
||||
dp := make([]int, len(s)+1)
|
||||
dp[0] = 1
|
||||
for i := 1; i <= n; i++ {
|
||||
if s[i-1] != '0' {
|
||||
if s[:1] == "0" {
|
||||
dp[1] = 0
|
||||
} else {
|
||||
dp[1] = 1
|
||||
}
|
||||
for i := 2; i <= len(s); i++ {
|
||||
lastNum, _ := strconv.Atoi(s[i-1 : i])
|
||||
if lastNum >= 1 && lastNum <= 9 {
|
||||
dp[i] += dp[i-1]
|
||||
}
|
||||
if i > 1 && s[i-2] != '0' && (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
|
||||
lastNum, _ = strconv.Atoi(s[i-2 : i])
|
||||
if lastNum >= 10 && lastNum <= 26 {
|
||||
dp[i] += dp[i-2]
|
||||
}
|
||||
}
|
||||
return dp[n]
|
||||
return dp[len(s)]
|
||||
}
|
||||
|
@ -1,35 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
func isInterleave(s1 string, s2 string, s3 string) bool {
|
||||
if len(s1)+len(s2) != len(s3) {
|
||||
return false
|
||||
}
|
||||
visited := make(map[int]bool)
|
||||
return dfs(s1, s2, s3, 0, 0, visited)
|
||||
}
|
||||
|
||||
func dfs(s1, s2, s3 string, p1, p2 int, visited map[int]bool) bool {
|
||||
if p1+p2 == len(s3) {
|
||||
return true
|
||||
}
|
||||
if _, ok := visited[(p1*len(s3))+p2]; ok {
|
||||
return false
|
||||
}
|
||||
visited[(p1*len(s3))+p2] = true
|
||||
var match1, match2 bool
|
||||
if p1 < len(s1) && s3[p1+p2] == s1[p1] {
|
||||
match1 = true
|
||||
}
|
||||
if p2 < len(s2) && s3[p1+p2] == s2[p2] {
|
||||
match2 = true
|
||||
}
|
||||
if match1 && match2 {
|
||||
return dfs(s1, s2, s3, p1+1, p2, visited) || dfs(s1, s2, s3, p1, p2+1, visited)
|
||||
} else if match1 {
|
||||
return dfs(s1, s2, s3, p1+1, p2, visited)
|
||||
} else if match2 {
|
||||
return dfs(s1, s2, s3, p1, p2+1, visited)
|
||||
} else {
|
||||
return false
|
||||
}
|
||||
}
|
@ -1,54 +0,0 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"testing"
|
||||
)
|
||||
|
||||
type question97 struct {
|
||||
para97
|
||||
ans97
|
||||
}
|
||||
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para97 struct {
|
||||
s1 string
|
||||
s2 string
|
||||
s3 string
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans97 struct {
|
||||
one bool
|
||||
}
|
||||
|
||||
func Test_Problem97(t *testing.T) {
|
||||
|
||||
qs := []question97{
|
||||
|
||||
{
|
||||
para97{"aabcc", "dbbca", "aadbbcbcac"},
|
||||
ans97{true},
|
||||
},
|
||||
|
||||
{
|
||||
para97{"aabcc", "dbbca", "aadbbbaccc"},
|
||||
ans97{false},
|
||||
},
|
||||
|
||||
{
|
||||
para97{"", "", ""},
|
||||
ans97{true},
|
||||
},
|
||||
}
|
||||
|
||||
fmt.Printf("------------------------Leetcode Problem 97------------------------\n")
|
||||
|
||||
for _, q := range qs {
|
||||
_, p := q.ans97, q.para97
|
||||
fmt.Printf("【input】:%v 【output】:%v\n", p, isInterleave(p.s1, p.s2, p.s3))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
@ -1,104 +0,0 @@
|
||||
# [97. Interleaving String](https://leetcode.com/problems/interleaving-string/)
|
||||
|
||||
|
||||
## 题目
|
||||
|
||||
Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an **interleaving** of `s1` and `s2`.
|
||||
|
||||
An **interleaving** of two strings `s` and `t` is a configuration where they are divided into **non-empty** substrings such that:
|
||||
|
||||
- `s = s1 + s2 + ... + sn`
|
||||
- `t = t1 + t2 + ... + tm`
|
||||
- `|n - m| <= 1`
|
||||
- The **interleaving** is `s1 + t1 + s2 + t2 + s3 + t3 + ...` or `t1 + s1 + t2 + s2 + t3 + s3 + ...`
|
||||
|
||||
**Note:** `a + b` is the concatenation of strings `a` and `b`.
|
||||
|
||||
**Example 1:**
|
||||
|
||||

|
||||
|
||||
```
|
||||
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
|
||||
Output: true
|
||||
|
||||
```
|
||||
|
||||
**Example 2:**
|
||||
|
||||
```
|
||||
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
|
||||
Output: false
|
||||
|
||||
```
|
||||
|
||||
**Example 3:**
|
||||
|
||||
```
|
||||
Input: s1 = "", s2 = "", s3 = ""
|
||||
Output: true
|
||||
|
||||
```
|
||||
|
||||
**Constraints:**
|
||||
|
||||
- `0 <= s1.length, s2.length <= 100`
|
||||
- `0 <= s3.length <= 200`
|
||||
- `s1`, `s2`, and `s3` consist of lowercase English letters.
|
||||
|
||||
**Follow up:** Could you solve it using only `O(s2.length)` additional memory space?
|
||||
|
||||
## 题目大意
|
||||
|
||||
给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:
|
||||
|
||||
- s = s1 + s2 + ... + sn
|
||||
- t = t1 + t2 + ... + tm
|
||||
- |n - m| <= 1
|
||||
- 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
|
||||
|
||||
提示:a + b 意味着字符串 a 和 b 连接。
|
||||
|
||||
## 解题思路
|
||||
|
||||
- 深搜或者广搜暴力解题。笔者用深搜实现的。记录 s1 和 s2 串当前比较的位置 p1 和 p2。如果 s3[p1+p2] 的位置上等于 s1[p1] 或者 s2[p2] 代表能匹配上,那么继续往后移动 p1 和 p2 相应的位置。因为是交错字符串,所以判断匹配的位置是 s3[p1+p2] 的位置。如果仅仅这么写,会超时,s1 和 s2 两个字符串重复交叉判断的位置太多了。需要加上记忆化搜索。可以用 visited[i][j] 这样的二维数组来记录是否搜索过了。笔者为了压缩空间,将 i 和 j 编码压缩到一维数组了。i * len(s3) + j 是唯一下标,所以可以用这种方式存储是否搜索过。具体代码见下面的实现。
|
||||
|
||||
## 代码
|
||||
|
||||
```go
|
||||
package leetcode
|
||||
|
||||
func isInterleave(s1 string, s2 string, s3 string) bool {
|
||||
if len(s1)+len(s2) != len(s3) {
|
||||
return false
|
||||
}
|
||||
visited := make(map[int]bool)
|
||||
return dfs(s1, s2, s3, 0, 0, visited)
|
||||
}
|
||||
|
||||
func dfs(s1, s2, s3 string, p1, p2 int, visited map[int]bool) bool {
|
||||
if p1+p2 == len(s3) {
|
||||
return true
|
||||
}
|
||||
if _, ok := visited[(p1*len(s3))+p2]; ok {
|
||||
return false
|
||||
}
|
||||
visited[(p1*len(s3))+p2] = true
|
||||
var match1, match2 bool
|
||||
if p1 < len(s1) && s3[p1+p2] == s1[p1] {
|
||||
match1 = true
|
||||
}
|
||||
if p2 < len(s2) && s3[p1+p2] == s2[p2] {
|
||||
match2 = true
|
||||
}
|
||||
if match1 && match2 {
|
||||
return dfs(s1, s2, s3, p1+1, p2, visited) || dfs(s1, s2, s3, p1, p2+1, visited)
|
||||
} else if match1 {
|
||||
return dfs(s1, s2, s3, p1+1, p2, visited)
|
||||
} else if match2 {
|
||||
return dfs(s1, s2, s3, p1, p2+1, visited)
|
||||
} else {
|
||||
return false
|
||||
}
|
||||
}
|
||||
```
|
@ -1,8 +1,8 @@
|
||||
package leetcode
|
||||
|
||||
import (
|
||||
"math"
|
||||
import "math"
|
||||
|
||||
import (
|
||||
"github.com/halfrost/LeetCode-Go/structures"
|
||||
)
|
||||
|
||||
|
@ -16,26 +16,7 @@ type TreeNode = structures.TreeNode
|
||||
* }
|
||||
*/
|
||||
|
||||
// 解法一 dfs
|
||||
func isSymmetric(root *TreeNode) bool {
|
||||
if root == nil {
|
||||
return true
|
||||
}
|
||||
return isMirror(root.Left, root.Right)
|
||||
}
|
||||
|
||||
func isMirror(left *TreeNode, right *TreeNode) bool {
|
||||
if left == nil && right == nil {
|
||||
return true
|
||||
}
|
||||
if left == nil || right == nil {
|
||||
return false
|
||||
}
|
||||
return (left.Val == right.Val) && isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
|
||||
}
|
||||
|
||||
// 解法二
|
||||
func isSymmetric1(root *TreeNode) bool {
|
||||
if root == nil {
|
||||
return true
|
||||
}
|
||||
|
@ -21,42 +21,50 @@ func levelOrder(root *TreeNode) [][]int {
|
||||
if root == nil {
|
||||
return [][]int{}
|
||||
}
|
||||
queue := []*TreeNode{root}
|
||||
res := make([][]int, 0)
|
||||
for len(queue) > 0 {
|
||||
l := len(queue)
|
||||
tmp := make([]int, 0, l)
|
||||
for i := 0; i < l; i++ {
|
||||
if queue[i].Left != nil {
|
||||
queue = append(queue, queue[i].Left)
|
||||
queue := []*TreeNode{}
|
||||
queue = append(queue, root)
|
||||
curNum, nextLevelNum, res, tmp := 1, 0, [][]int{}, []int{}
|
||||
for len(queue) != 0 {
|
||||
if curNum > 0 {
|
||||
node := queue[0]
|
||||
if node.Left != nil {
|
||||
queue = append(queue, node.Left)
|
||||
nextLevelNum++
|
||||
}
|
||||
if queue[i].Right != nil {
|
||||
queue = append(queue, queue[i].Right)
|
||||
if node.Right != nil {
|
||||
queue = append(queue, node.Right)
|
||||
nextLevelNum++
|
||||
}
|
||||
tmp = append(tmp, queue[i].Val)
|
||||
curNum--
|
||||
tmp = append(tmp, node.Val)
|
||||
queue = queue[1:]
|
||||
}
|
||||
if curNum == 0 {
|
||||
res = append(res, tmp)
|
||||
curNum = nextLevelNum
|
||||
nextLevelNum = 0
|
||||
tmp = []int{}
|
||||
}
|
||||
queue = queue[l:]
|
||||
res = append(res, tmp)
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
||||
// 解法二 DFS
|
||||
func levelOrder1(root *TreeNode) [][]int {
|
||||
var res [][]int
|
||||
var dfsLevel func(node *TreeNode, level int)
|
||||
dfsLevel = func(node *TreeNode, level int) {
|
||||
if node == nil {
|
||||
return
|
||||
}
|
||||
if len(res) == level {
|
||||
res = append(res, []int{node.Val})
|
||||
} else {
|
||||
res[level] = append(res[level], node.Val)
|
||||
}
|
||||
dfsLevel(node.Left, level+1)
|
||||
dfsLevel(node.Right, level+1)
|
||||
}
|
||||
dfsLevel(root, 0)
|
||||
return res
|
||||
levels := [][]int{}
|
||||
dfsLevel(root, -1, &levels)
|
||||
return levels
|
||||
}
|
||||
|
||||
func dfsLevel(node *TreeNode, level int, res *[][]int) {
|
||||
if node == nil {
|
||||
return
|
||||
}
|
||||
currLevel := level + 1
|
||||
for len(*res) <= currLevel {
|
||||
*res = append(*res, []int{})
|
||||
}
|
||||
(*res)[currLevel] = append((*res)[currLevel], node.Val)
|
||||
dfsLevel(node.Left, currLevel, res)
|
||||
dfsLevel(node.Right, currLevel, res)
|
||||
}
|
||||
|
@ -81,40 +81,3 @@ func search(root *TreeNode, depth int, res *[][]int) {
|
||||
search(root.Left, depth+1, res)
|
||||
search(root.Right, depth+1, res)
|
||||
}
|
||||
|
||||
// 解法三 BFS
|
||||
func zigzagLevelOrder1(root *TreeNode) [][]int {
|
||||
res := [][]int{}
|
||||
if root == nil {
|
||||
return res
|
||||
}
|
||||
q := []*TreeNode{root}
|
||||
size, i, j, lay, tmp, flag := 0, 0, 0, []int{}, []*TreeNode{}, false
|
||||
for len(q) > 0 {
|
||||
size = len(q)
|
||||
tmp = []*TreeNode{}
|
||||
lay = make([]int, size)
|
||||
j = size - 1
|
||||
for i = 0; i < size; i++ {
|
||||
root = q[0]
|
||||
q = q[1:]
|
||||
if !flag {
|
||||
lay[i] = root.Val
|
||||
} else {
|
||||
lay[j] = root.Val
|
||||
j--
|
||||
}
|
||||
if root.Left != nil {
|
||||
tmp = append(tmp, root.Left)
|
||||
}
|
||||
if root.Right != nil {
|
||||
tmp = append(tmp, root.Right)
|
||||
}
|
||||
|
||||
}
|
||||
res = append(res, lay)
|
||||
flag = !flag
|
||||
q = tmp
|
||||
}
|
||||
return res
|
||||
}
|
||||
|
@ -16,23 +16,7 @@ type TreeNode = structures.TreeNode
|
||||
* }
|
||||
*/
|
||||
|
||||
// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, 内存使用(leetcode test case) 4.7MB -> 4.3MB.
|
||||
func buildTree(preorder []int, inorder []int) *TreeNode {
|
||||
if len(preorder) == 0 {
|
||||
return nil
|
||||
}
|
||||
root := &TreeNode{Val: preorder[0]}
|
||||
for pos, node := range inorder {
|
||||
if node == root.Val {
|
||||
root.Left = buildTree(preorder[1:pos+1], inorder[:pos])
|
||||
root.Right = buildTree(preorder[pos+1:], inorder[pos+1:])
|
||||
}
|
||||
}
|
||||
return root
|
||||
}
|
||||
|
||||
// 解法二
|
||||
func buildTree1(preorder []int, inorder []int) *TreeNode {
|
||||
inPos := make(map[int]int)
|
||||
for i := 0; i < len(inorder); i++ {
|
||||
inPos[inorder[i]] = i
|
||||
|
@ -16,25 +16,7 @@ type TreeNode = structures.TreeNode
|
||||
* }
|
||||
*/
|
||||
|
||||
// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, 内存使用(leetcode test case) 4.7MB -> 4.3MB.
|
||||
func buildTree(inorder []int, postorder []int) *TreeNode {
|
||||
postorderLen := len(postorder)
|
||||
if len(inorder) == 0 {
|
||||
return nil
|
||||
}
|
||||
root := &TreeNode{Val: postorder[postorderLen-1]}
|
||||
postorder = postorder[:postorderLen-1]
|
||||
for pos, node := range inorder {
|
||||
if node == root.Val {
|
||||
root.Left = buildTree(inorder[:pos], postorder[:len(inorder[:pos])])
|
||||
root.Right = buildTree(inorder[pos+1:], postorder[len(inorder[:pos]):])
|
||||
}
|
||||
}
|
||||
return root
|
||||
}
|
||||
|
||||
// 解法二
|
||||
func buildTree1(inorder []int, postorder []int) *TreeNode {
|
||||
inPos := make(map[int]int)
|
||||
for i := 0; i < len(inorder); i++ {
|
||||
inPos[inorder[i]] = i
|
||||
|
@ -18,21 +18,23 @@ type TreeNode = structures.TreeNode
|
||||
|
||||
// 解法一 非递归
|
||||
func flatten(root *TreeNode) {
|
||||
list := preorder(root)
|
||||
list, cur := []int{}, &TreeNode{}
|
||||
preorder(root, &list)
|
||||
cur = root
|
||||
for i := 1; i < len(list); i++ {
|
||||
prev, cur := list[i-1], list[i]
|
||||
prev.Left, prev.Right = nil, cur
|
||||
cur.Left = nil
|
||||
cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil}
|
||||
cur = cur.Right
|
||||
}
|
||||
return
|
||||
}
|
||||
|
||||
func preorder(root *TreeNode) (ans []*TreeNode) {
|
||||
func preorder(root *TreeNode, output *[]int) {
|
||||
if root != nil {
|
||||
ans = append(ans, root)
|
||||
ans = append(ans, preorder(root.Left)...)
|
||||
ans = append(ans, preorder(root.Right)...)
|
||||
*output = append(*output, root.Val)
|
||||
preorder(root.Left, output)
|
||||
preorder(root.Right, output)
|
||||
}
|
||||
return
|
||||
}
|
||||
|
||||
// 解法二 递归
|
||||
|
@ -15,13 +15,13 @@ type question114 struct {
|
||||
// para 是参数
|
||||
// one 代表第一个参数
|
||||
type para114 struct {
|
||||
one []string
|
||||
one []int
|
||||
}
|
||||
|
||||
// ans 是答案
|
||||
// one 代表第一个答案
|
||||
type ans114 struct {
|
||||
one []string
|
||||
one []int
|
||||
}
|
||||
|
||||
func Test_Problem114(t *testing.T) {
|
||||
@ -29,18 +29,8 @@ func Test_Problem114(t *testing.T) {
|
||||
qs := []question114{
|
||||
|
||||
{
|
||||
para114{[]string{"1", "2", "5", "3", "4", "null", "6"}},
|
||||
ans114{[]string{"1", "null", "2", "null", "3", "null", "4", "null", "5", "null", "6"}},
|
||||
},
|
||||
|
||||
{
|
||||
para114{[]string{"0"}},
|
||||
ans114{[]string{"0"}},
|
||||
},
|
||||
|
||||
{
|
||||
para114{[]string{"1", "2", "3", "4", "5", "6"}},
|
||||
ans114{[]string{"1", "2", "4", "5", "3", "6", "null"}},
|
||||
para114{[]int{1, 2, 3, 4, 5, 6}},
|
||||
ans114{[]int{1, 2, 3, 4, 5, 6}},
|
||||
},
|
||||
}
|
||||
|
||||
@ -49,10 +39,9 @@ func Test_Problem114(t *testing.T) {
|
||||
for _, q := range qs {
|
||||
_, p := q.ans114, q.para114
|
||||
fmt.Printf("【input】:%v \n", p)
|
||||
rootOne := structures.Strings2TreeNode(p.one)
|
||||
rootOne := structures.Ints2TreeNode(p.one)
|
||||
flatten(rootOne)
|
||||
fmt.Printf("【levelorder output】:%v \n", structures.Tree2LevelOrderStrings(rootOne))
|
||||
fmt.Printf("【preorder output】:%v \n", structures.Tree2PreOrderStrings(rootOne))
|
||||
fmt.Printf("【output】:%v \n", structures.Tree2Preorder(rootOne))
|
||||
}
|
||||
fmt.Printf("\n\n\n")
|
||||
}
|
||||
|
Some files were not shown because too many files have changed in this diff Show More
Reference in New Issue
Block a user