algorithm/LeetCode-Go
1
0
Fork 0
mirror of https://github.com/halfrost/LeetCode-Go.git synced 2025-07-08 10:24:58 +08:00
Code Issues Packages Projects Releases Wiki Activity

Compare commits

base: algorithm:dependabot/go_modules/golang.org/x/net-0.17.0
Branches Tags
algorithm:master algorithm:dependabot/go_modules/golang.org/x/net-0.17.0 algorithm:revert-175-leetcode0492 algorithm:change_zdoc
algorithm:1.7.1 algorithm:1.7.0 algorithm:1.6.6 algorithm:Special algorithm:1.5.20
..
compare: algorithm:revert-175-leetcode0492
Branches Tags
algorithm:master algorithm:dependabot/go_modules/golang.org/x/net-0.17.0 algorithm:revert-175-leetcode0492 algorithm:change_zdoc
algorithm:1.7.1 algorithm:1.7.0 algorithm:1.6.6 algorithm:Special algorithm:1.5.20

1 Commits
dependabot ... revert-175

Author SHA1 Message Date
halfrost
be6831e5e3 Revert "add: leetcode 0492 solution" 2021-11-06 19:07:44 -07:00
518 changed files with 4749 additions and 22810 deletions
Expand all files Collapse all files

13
.github/FUNDING.yml vendored
View File

@ -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']

4467
README.md
View File

File diff suppressed because it is too large Load Diff

2
ctl/meta/PDFPreface
View File

@ -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 。

7
ctl/models/go.mod
View File

@ -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

2
ctl/models/go.sum
View File

@ -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=

4
ctl/models/lcproblems.go
View File

@ -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

4
ctl/models/mdrow.go
View File

@ -29,7 +29,7 @@ func GenerateMdRows(solutionIds []int, mdrows []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)),
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,
@ -52,7 +52,7 @@ func GenerateMdRows(solutionIds []int, mdrows []Mdrow) {
// 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)
}

6
ctl/models/tagproblem.go
View File

@ -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"`
}
@ -180,8 +180,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"

6
ctl/models/user.go
View File

@ -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 |

7
ctl/pdf.go
View File

@ -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 。

3
ctl/render.go
View File

@ -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
ctl/request.go
View File

@ -3,10 +3,9 @@ package main
import (
"bytes"
"fmt"
"github.com/mozillazg/request"
"io/ioutil"
"net/http"
"github.com/mozillazg/request"
)
const (

3
ctl/statistic.go
View File

@ -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) {

18
ctl/template/template.markdown
View File

@ -10,9 +10,9 @@
![](./website/static/wechat-qr-code.png)
<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">
@ -23,7 +23,7 @@
</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 +32,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 +42,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 +550,7 @@ Problems List in [there](https://books.halfrost.com/leetcode/ChapterTwo/Bit_Mani
![](./topic/Union_Find.png)
- 灵活使用并查集的思想，熟练掌握并查集的[模板](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 +630,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/)

5
ctl/template_render.go
View File

@ -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) {

3
ctl/util/go.mod
View File

@ -1,3 +0,0 @@
module github.com/halfrost/LeetCode-Go/ctl/util
go 1.19

29
go.mod
View File

@ -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
View File

@ -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=

9
leetcode/0003.Longest-Substring-Without-Repeating-Characters/3. Longest Substring Without Repeating Characters.go
View File

@ -31,16 +31,15 @@ func lengthOfLongestSubstring1(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)

2
leetcode/0003.Longest-Substring-Without-Repeating-Characters/README.md
View File

@ -34,7 +34,7 @@ Explanation: The answer is "wke", with the length of 3.
## 题目大意
在一个字符串中寻找没有重复字母的最长子串。
在一个字符串重寻找没有重复字母的最长子串。
## 解题思路

16
leetcode/0014.Longest-Common-Prefix/14.Longest Common Prefix.go
View File

@ -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
}

50
leetcode/0014.Longest-Common-Prefix/14.Longest Common Prefix_test.go
View File

@ -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")
}

57
leetcode/0014.Longest-Common-Prefix/README.md
View File

@ -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
}
```

0
leetcode/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/28. Find the Index of the First Occurrence in a String.go → leetcode/0028.Implement-strStr/28. Implement strStr().go
View File

0
leetcode/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/28. Find the Index of the First Occurrence in a String_test.go → leetcode/0028.Implement-strStr/28. Implement strStr()_test.go
View File

2
leetcode/0028.Find-the-Index-of-the-First-Occurrence-in-a-String/README.md → leetcode/0028.Implement-strStr/README.md
View File

@ -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/)
## 题目

41
leetcode/0031.Next-Permutation/31. Next Permutation.go
View File

@ -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
}

2
leetcode/0040.Combination-Sum-II/README.md
View File

@ -45,4 +45,4 @@ candidates 中的每个数字在每个组合中只能使用一次。
## 解题思路
- 题目要求出总和为 sum 的所有组合，组合需要去重。这一题是第 39 题的加强版，第 39 题中元素可以重复利用(重复元素可无限次使用)，这一题中元素只能有限次数的利用，因为存在重复元素，并且每个元素只能用一次(重复元素只能使用有限次)
- 这一题和第 47 题类似。
- 这一题和第 47 题类似，只不过元素可以反复使用。

44
leetcode/0048.Rotate-Image/48. Rotate Image.go
View File

@ -1,6 +1,5 @@
package leetcode
// 解法一
func rotate(matrix [][]int) {
length := len(matrix)
// rotate by diagonal 对角线变换
@ -16,46 +15,3 @@ func rotate(matrix [][]int) {
}
}
}
// 解法二
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
}

4
leetcode/0098.Validate-Binary-Search-Tree/98. Validate Binary Search Tree.go
View File

@ -1,8 +1,8 @@
package leetcode
import (
"math"
import "math"
import (
"github.com/halfrost/LeetCode-Go/structures"
)

18
leetcode/0114.Flatten-Binary-Tree-to-Linked-List/114. Flatten Binary Tree to Linked List.go
View File

@ -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
}
// 解法二 递归

23
leetcode/0114.Flatten-Binary-Tree-to-Linked-List/114. Flatten Binary Tree to Linked List_test.go
View File

@ -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")
}

2
leetcode/0116.Populating-Next-Right-Pointers-in-Each-Node/116.Populating Next Right Pointers in Each Node.go
View File

@ -7,7 +7,7 @@ type Node struct {
Next *Node
}
// 解法一：迭代
//解法一：迭代
func connect(root *Node) *Node {
if root == nil {
return root

6
leetcode/0116.Populating-Next-Right-Pointers-in-Each-Node/116.Populating Next Right Pointers in Each Node_test.go
View File

@ -22,7 +22,7 @@ type ans116 struct {
one *Node
}
func newQuestionNode() *Node {
func newQuestionNode()*Node{
node7 := &Node{}
node7.Val = 7
@ -55,7 +55,7 @@ func newQuestionNode() *Node {
return node1
}
func newResultNode() *Node {
func newResultNode()*Node{
node7 := &Node{}
node7.Val = 7
@ -114,4 +114,4 @@ func Test_Problem116(t *testing.T) {
fmt.Printf("【output】:%v \n", connect(p.one))
}
fmt.Printf("\n\n\n")
}
}

0
leetcode/0118.Pascals-Triangle/118. Pascals Triangle.go → leetcode/0118.Pascals-Triangle/118. Pascal's Triangle.go
View File

0
leetcode/0118.Pascals-Triangle/118. Pascals Triangle_test.go → leetcode/0118.Pascals-Triangle/118. Pascal's Triangle_test.go
View File

0
leetcode/0119.Pascals-Triangle-II/119. Pascals Triangle II.go → leetcode/0119.Pascals-Triangle-II/119. Pascal's Triangle II.go
View File

0
leetcode/0119.Pascals-Triangle-II/119. Pascals Triangle II_test.go → leetcode/0119.Pascals-Triangle-II/119. Pascal's Triangle II_test.go
View File

4
leetcode/0124.Binary-Tree-Maximum-Path-Sum/124. Binary Tree Maximum Path Sum.go
View File

@ -1,8 +1,8 @@
package leetcode
import (
"math"
import "math"
import (
"github.com/halfrost/LeetCode-Go/structures"
)

2
leetcode/0143.Reorder-List/README.md
View File

@ -31,4 +31,4 @@ Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
更好的做法是结合之前几道题的操作：链表逆序，找中间结点。
先找到链表的中间结点，然后利用逆序区间的操作，如 [第 92 题](https://github.com/halfrost/leetcode-go/tree/master/leetcode/0092.Reverse-Linked-List-II) 里的 reverseBetween() 操作，只不过这里的反转区间是从中点一直到末尾。最后利用 2 个指针，一个指向头结点，一个指向中间结点，开始拼接最终的结果。这种做法的时间复杂度是 O(n)，空间复杂度是 O(1)。
先找到链表的中间结点，然后利用逆序区间的操作，如 [第 92 题](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0092.Reverse-Linked-List-II) 里的 reverseBetween() 操作，只不过这里的反转区间是从中点一直到末尾。最后利用 2 个指针，一个指向头结点，一个指向中间结点，开始拼接最终的结果。这种做法的时间复杂度是 O(n)，空间复杂度是 O(1)。

4
leetcode/0160.Intersection-of-Two-Linked-Lists/160. Intersection of Two Linked Lists.go
View File

@ -1,8 +1,8 @@
package leetcode
import (
"fmt"
import "fmt"
import (
"github.com/halfrost/LeetCode-Go/structures"
)

9
leetcode/0190.Reverse-Bits/190. Reverse Bits_test.go
View File

@ -2,7 +2,6 @@ package leetcode
import (
"fmt"
"strconv"
"testing"
)
@ -24,6 +23,7 @@ type ans190 struct {
}
func Test_Problem190(t *testing.T) {
qs := []question190{
{
@ -41,12 +41,7 @@ func Test_Problem190(t *testing.T) {
for _, q := range qs {
_, p := q.ans190, q.para190
input := strconv.FormatUint(uint64(p.one), 2) // 32位无符号整数转换为二进制字符串
input = fmt.Sprintf("%0*v", 32, input) // 格式化输出32位,保留前置0
output := reverseBits(p.one)
outputBin := strconv.FormatUint(uint64(output), 2) // 32位无符号整数转换为二进制字符串
outputBin = fmt.Sprintf("%0*v", 32, outputBin) // 格式化输出32位,保留前置0
fmt.Printf("【input】:%v 【output】:%v (%v)\n", input, output, outputBin)
fmt.Printf("【input】:%v 【output】:%v\n", p, reverseBits(p.one))
}
fmt.Printf("\n\n\n")
}

5
leetcode/0191.Number-of-1-Bits/191. Number of 1 Bits_test.go
View File

@ -2,7 +2,6 @@ package leetcode
import (
"fmt"
"strconv"
"testing"
)
@ -41,9 +40,7 @@ func Test_Problem191(t *testing.T) {
for _, q := range qs {
_, p := q.ans191, q.para191
input := strconv.FormatUint(uint64(p.one), 2) // 32位无符号整数转换为二进制字符串
input = fmt.Sprintf("%0*v", 32, input) // 格式化输出32位,保留前置0
fmt.Printf("【input】:%v 【output】:%v\n", input, hammingWeight(p.one))
fmt.Printf("【input】:%v 【output】:%v\n", p, hammingWeight(p.one))
}
fmt.Printf("\n\n\n")
}

2
leetcode/0215.Kth-Largest-Element-in-an-Array/README.md
View File

@ -29,5 +29,5 @@ You may assume k is always valid, 1 ≤ k ≤ array's length.
## 解题思路
在快速选择 quickselect 的 partition 操作中，每次 partition 操作结束都会返回一个点，这个标定点的下标和最终排序之后有序数组中这个元素所在的下标是一致的。利用这个特性，我们可以不断的划分数组区间，最终找到第 K 大的元素。执行一次 partition 操作以后，如果这个元素的下标比 K 小，那么接着就在后边的区间继续执行 partition 操作；如果这个元素的下标比 K 大，那么就在左边的区间继续执行 partition 操作；如果相等就直接输出这个下标对应的数组元素即可。
在快排的 partition 操作中，每次 partition 操作结束都会返回一个点，这个标定点的下标和最终排序之后有序数组中这个元素所在的下标是一致的。利用这个特性，我们可以不断的划分数组区间，最终找到第 K 大的元素。执行一次 partition 操作以后，如果这个元素的下标比 K 小，那么接着就在后边的区间继续执行 partition 操作；如果这个元素的下标比 K 大，那么就在左边的区间继续执行 partition 操作；如果相等就直接输出这个下标对应的数组元素即可。

2
leetcode/0257.Binary-Tree-Paths/257. Binary Tree Paths.go
View File

@ -2,7 +2,9 @@ package leetcode
import (
"strconv"
)
import (
"github.com/halfrost/LeetCode-Go/structures"
)

10
leetcode/0297.Serialize-and-Deserialize-Binary-Tree/297.Serialize and Deserialize Binary Tree_test.go
View File

@ -31,12 +31,12 @@ func Test_Problem297(t *testing.T) {
ans297{[]int{}},
},
{
para297{[]int{1, 2, 3, -1, -1, 4, 5}},
ans297{[]int{1, 2, 3, -1, -1, 4, 5}},
para297{[]int{1,2,3,-1,-1,4,5}},
ans297{[]int{1,2,3,-1,-1,4,5}},
},
{
para297{[]int{1, 2}},
ans297{[]int{1, 2}},
para297{[]int{1,2}},
ans297{[]int{1,2}},
},
}
@ -52,4 +52,4 @@ func Test_Problem297(t *testing.T) {
fmt.Printf("【output】:%v \n", structures.Tree2Preorder(tree297.deserialize(serialized)))
}
fmt.Printf("\n\n\n")
}
}

31
leetcode/0299.Bulls-and-Cows/299.Bulls and Cows.go
View File

@ -1,31 +0,0 @@
package leetcode
import "strconv"
func getHint(secret string, guess string) string {
cntA, cntB := 0, 0
mpS := make(map[byte]int)
var strG []byte
n := len(secret)
var ans string
for i := 0; i < n; i++ {
if secret[i] == guess[i] {
cntA++
} else {
mpS[secret[i]] += 1
strG = append(strG, guess[i])
}
}
for _, v := range strG {
if _, ok := mpS[v]; ok {
if mpS[v] > 1 {
mpS[v] -= 1
} else {
delete(mpS, v)
}
cntB++
}
}
ans += strconv.Itoa(cntA) + "A" + strconv.Itoa(cntB) + "B"
return ans
}

56
leetcode/0299.Bulls-and-Cows/299.Bulls and Cows_test.go
View File

@ -1,56 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question299 struct {
para299
ans299
}
// para 是参数
type para299 struct {
secret string
guess string
}
// ans 是答案
type ans299 struct {
ans string
}
func Test_Problem299(t *testing.T) {
qs := []question299{
{
para299{"1807", "7810"},
ans299{"1A3B"},
},
{
para299{"1123", "0111"},
ans299{"1A1B"},
},
{
para299{"1", "0"},
ans299{"0A0B"},
},
{
para299{"1", "1"},
ans299{"1A0B"},
},
}
fmt.Printf("------------------------Leetcode Problem 299------------------------\n")
for _, q := range qs {
_, p := q.ans299, q.para299
fmt.Printf("【input】:%v 【output】:%v\n", p, getHint(p.secret, p.guess))
}
fmt.Printf("\n\n\n")
}

114
leetcode/0299.Bulls-and-Cows/README.md
View File

@ -1,114 +0,0 @@
# [299. Bulls and Cows](https://leetcode.com/problems/bulls-and-cows/)
## 题目
You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
The number of "bulls", which are digits in the guess that are in the correct position.
The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.
**Example 1:**
```
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"
```
**Example 2:**
```
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123" "1123"
| or |
"0111" "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
```
**Example 3:**
```
Input: secret = "1", guess = "0"
Output: "0A0B"
```
**Example 4:**
```
Input: secret = "1", guess = "1"
Output: "1A0B"
```
**Constraints:**
- 1 <= secret.length, guess.length <= 1000
- secret.length == guess.length
- secret and guess consist of digits only.
## 题目大意
你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls", 公牛），
有多少位属于数字猜对了但是位置不对（称为 "Cows", 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字secret 和朋友猜测的数字guess ，请你返回对朋友这次猜测的提示。
提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
## 解题思路
- 计算下标一致并且对应下标的元素一致的个数，即 x
- secret 和 guess 分别去除 x 个公牛的元素,剩下 secret 和 guess 求共同的元素个数就是 y
- 把 x， y 转换成字符串，分别与 "A" 和 "B" 进行拼接返回结果
## 代码
```go
package leetcode
import "strconv"
func getHint(secret string, guess string) string {
cntA, cntB := 0, 0
mpS := make(map[byte]int)
var strG []byte
n := len(secret)
var ans string
for i := 0; i < n; i++ {
if secret[i] == guess[i] {
cntA++
} else {
mpS[secret[i]] += 1
strG = append(strG, guess[i])
}
}
for _, v := range strG {
if _, ok := mpS[v]; ok {
if mpS[v] > 1 {
mpS[v] -= 1
} else {
delete(mpS, v)
}
cntB++
}
}
ans += strconv.Itoa(cntA) + "A" + strconv.Itoa(cntB) + "B"
return ans
}
```

2
leetcode/0306.Additive-Number/306. Additive Number.go
View File

@ -35,7 +35,7 @@ func max(a int, b int) int {
return b
}
// Propagate for rest of the string
//Propagate for rest of the string
func recursiveCheck(num string, x1 int, x2 int, left int) bool {
if left == len(num) {
return true

7
leetcode/0319.Bulb-Switcher/319.Bulb Switcher.go
View File

@ -1,7 +0,0 @@
package leetcode
import "math"
func bulbSwitch(n int) int {
return int(math.Sqrt(float64(n)))
}

50
leetcode/0319.Bulb-Switcher/319.Bulb Switcher_test.go
View File

@ -1,50 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question319 struct {
para319
ans319
}
// para 是参数
type para319 struct {
n int
}
// ans 是答案
type ans319 struct {
ans int
}
func Test_Problem319(t *testing.T) {
qs := []question319{
{
para319{3},
ans319{1},
},
{
para319{0},
ans319{0},
},
{
para319{1},
ans319{1},
},
}
fmt.Printf("------------------------Leetcode Problem 319------------------------\n")
for _, q := range qs {
_, p := q.ans319, q.para319
fmt.Printf("【input】:%v 【output】:%v\n", p, bulbSwitch(p.n))
}
fmt.Printf("\n\n\n")
}

58
leetcode/0319.Bulb-Switcher/README.md
View File

@ -1,58 +0,0 @@
# [319. Bulb Switcher](https://leetcode.com/problems/bulb-switcher/)
## 题目
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
**Example 1:**
Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
**Example 2:**
Input: n = 0
Output: 0
**Example 3:**
Input: n = 1
Output: 1
## 题目大意
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。
第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
## 解题思路
- 计算 1 到 n 中有奇数个约数的个数
- 1 到 n 中的某个数 x 有奇数个约数,也即 x 是完全平方数
- 计算 1 到 n 中完全平方数的个数 sqrt(n)
## 代码
```go
package leetcode
import "math"
func bulbSwitch(n int) int {
return int(math.Sqrt(float64(n)))
}
```

7
leetcode/0372.Super-Pow/372. Super Pow.go
View File

@ -8,11 +8,10 @@ package leetcode
// 模运算性质五：ab % p = ((a % p) * ( b % p)) % p, 其中 ab 是一个数字，如:2874，98374 等等
// 举个例子
// 12345^678 % 1337 = (12345^670 * 12345^8) % 1337
//
// = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337 ---> 利用性质 三
// = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337 ---> 利用性质 三
// = (((12345^67)^10 % 1337) * (12345^8 % 1337)) % 1337 ---> 乘方性质
// = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337 ---> 利用性质 四
// = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337 ---> 反向利用性质 三
// = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337 ---> 利用性质 四
// = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337 ---> 反向利用性质 三
func superPow(a int, b []int) int {
res := 1
for i := 0; i < len(b); i++ {

48
leetcode/0382.Linked-List-Random-Node/382. Linked List Random Node.go
View File

@ -1,48 +0,0 @@
package leetcode
import (
"math/rand"
"github.com/halfrost/LeetCode-Go/structures"
)
// ListNode define
type ListNode = structures.ListNode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type Solution struct {
head *ListNode
}
/*
- @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node.
*/
func Constructor(head *ListNode) Solution {
return Solution{head: head}
}
/** Returns a random node's value. */
func (this *Solution) GetRandom() int {
scope, selectPoint, curr := 1, 0, this.head
for curr != nil {
if rand.Float64() < 1.0/float64(scope) {
selectPoint = curr.Val
}
scope += 1
curr = curr.Next
}
return selectPoint
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(head);
* param_1 := obj.GetRandom();
*/

28
leetcode/0382.Linked-List-Random-Node/382. Linked List Random Node_test.go
View File

@ -1,28 +0,0 @@
package leetcode
import (
"fmt"
"testing"
"github.com/halfrost/LeetCode-Go/structures"
)
func Test_Problem382(t *testing.T) {
header := structures.Ints2List([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 0})
obj := Constructor(header)
fmt.Printf("obj = %v\n", structures.List2Ints(header))
param1 := obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
param1 = obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
param1 = obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
param1 = obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
param1 = obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
param1 = obj.GetRandom()
fmt.Printf("param_1 = %v\n", param1)
fmt.Printf("\n\n\n")
}

105
leetcode/0382.Linked-List-Random-Node/README.md
View File

@ -1,105 +0,0 @@
# [382. Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/)
## 题目
Given a singly linked list, return a random node's value from the linked list. Each node must have the **same probability** of being chosen.
Implement the `Solution` class:
- `Solution(ListNode head)` Initializes the object with the integer array nums.
- `int getRandom()` Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.
**Example 1:**
![https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg](https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg)
```
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
```
**Constraints:**
- The number of nodes in the linked list will be in the range `[1, 104]`.
- `-10^4 <= Node.val <= 10^4`
- At most `10^4` calls will be made to `getRandom`.
**Follow up:**
- What if the linked list is extremely large and its length is unknown to you?
- Could you solve this efficiently without using extra space?
## 题目大意
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶: 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
## 解题思路
- rand.Float64() 可以返回 [0.0,1.0) 之间的随机数。利用这个函数完成我们的随机化取节点的过程。
## 代码
```go
package leetcode
import (
"math/rand"
"github.com/halfrost/LeetCode-Go/structures"
)
// ListNode define
type ListNode = structures.ListNode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type Solution struct {
head *ListNode
}
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
func Constructor(head *ListNode) Solution {
return Solution{head: head}
}
/** Returns a random node's value. */
func (this *Solution) GetRandom() int {
scope, selectPoint, curr := 1, 0, this.head
for curr != nil {
if rand.Float64() < 1.0/float64(scope) {
selectPoint = curr.Val
}
scope += 1
curr = curr.Next
}
return selectPoint
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(head);
* param_1 := obj.GetRandom();
*/
```

18
leetcode/0383.Ransom-Note/383.Ransom Note.go
View File

@ -1,18 +0,0 @@
package leetcode
func canConstruct(ransomNote string, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
var cnt [26]int
for _, v := range magazine {
cnt[v-'a']++
}
for _, v := range ransomNote {
cnt[v-'a']--
if cnt[v-'a'] < 0 {
return false
}
}
return true
}

51
leetcode/0383.Ransom-Note/383.Ransom Note_test.go
View File

@ -1,51 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question383 struct {
para383
ans383
}
// para 是参数
type para383 struct {
ransomNote string
magazine string
}
// ans 是答案
type ans383 struct {
ans bool
}
func Test_Problem383(t *testing.T) {
qs := []question383{
{
para383{"a", "b"},
ans383{false},
},
{
para383{"aa", "ab"},
ans383{false},
},
{
para383{"aa", "aab"},
ans383{true},
},
}
fmt.Printf("------------------------Leetcode Problem 383------------------------\n")
for _, q := range qs {
_, p := q.ans383, q.para383
fmt.Printf("【input】:%v 【output】:%v\n", p, canConstruct(p.ransomNote, p.magazine))
}
fmt.Printf("\n\n\n")
}

64
leetcode/0383.Ransom-Note/README.md
View File

@ -1,64 +0,0 @@
# [383. Ransom Note](https://leetcode.com/problems/ransom-note/)
## 题目
Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
**Example 1**:
Input: ransomNote = "a", magazine = "b"
Output: false
**Example 2**:
Input: ransomNote = "aa", magazine = "ab"
Output: false
**Example 3**:
Input: ransomNote = "aa", magazine = "aab"
Output: true
**Constraints:**
- 1 <= ransomNote.length, magazine.length <= 100000
- ransomNote and magazine consist of lowercase English letters.
## 题目大意
为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
## 解题思路
- ransomNote 和 magazine 都是由小写字母组成，所以用数组进行简单的字符统计
## 代码
````go
package leetcode
func canConstruct(ransomNote string, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
var cnt [26]int
for _, v := range magazine {
cnt[v-'a']++
}
for _, v := range ransomNote {
cnt[v-'a']--
if cnt[v-'a'] < 0 {
return false
}
}
return true
}
````

28
leetcode/0384.Shuffle-an-Array/384.Shuffle an Array.go
View File

@ -1,28 +0,0 @@
package leetcode
import "math/rand"
type Solution struct {
nums []int
}
func Constructor(nums []int) Solution {
return Solution{
nums: nums,
}
}
/** Resets the array to its original configuration and return it. */
func (this *Solution) Reset() []int {
return this.nums
}
/** Returns a random shuffling of the array. */
func (this *Solution) Shuffle() []int {
arr := make([]int, len(this.nums))
copy(arr, this.nums)
rand.Shuffle(len(arr), func(i, j int) {
arr[i], arr[j] = arr[j], arr[i]
})
return arr
}

50
leetcode/0384.Shuffle-an-Array/384.Shuffle an Array_test.go
View File

@ -1,50 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question384 struct {
para384
ans384
}
// para 是参数
type para384 struct {
ops []string
value [][]int
}
// ans 是答案
type ans384 struct {
ans [][]int
}
func Test_Problem384(t *testing.T) {
qs := []question384{
{
para384{ops: []string{"Solution", "shuffle", "reset", "shuffle"}, value: [][]int{{1, 2, 3}, {}, {}, {}}},
ans384{[][]int{nil, {3, 1, 2}, {1, 2, 3}, {1, 3, 2}}},
},
}
fmt.Printf("------------------------Leetcode Problem 384------------------------\n")
for _, q := range qs {
sol := Constructor(nil)
_, p := q.ans384, q.para384
for _, op := range p.ops {
if op == "Solution" {
sol = Constructor(q.value[0])
} else if op == "reset" {
fmt.Printf("【input】:%v 【output】:%v\n", op, sol.Reset())
} else {
fmt.Printf("【input】:%v 【output】:%v\n", op, sol.Shuffle())
}
}
}
fmt.Printf("\n\n\n")
}

82
leetcode/0384.Shuffle-an-Array/README.md
View File

@ -1,82 +0,0 @@
# [384.Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/)
## 题目
Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution class:
- Solution(int[] nums) Initializes the object with the integer array nums.
- int[] reset() Resets the array to its original configuration and returns it.
- int[] shuffle() Returns a random shuffling of the array.
**Example 1**:
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
**Constraints:**
- 1 <= nums.length <= 200
- -1000000 <= nums[i] <= 1000000
- All the elements of nums are unique.
- At most 5 * 10000 calls in total will be made to reset and shuffle.
## 题目大意
给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:
- Solution(int[] nums) 使用整数数组 nums 初始化对象
- int[] reset() 重设数组到它的初始状态并返回
- int[] shuffle() 返回数组随机打乱后的结果
## 解题思路
- 使用 rand.Shuffle 进行数组随机打乱
## 代码
```go
package leetcode
import "math/rand"
type Solution struct {
nums []int
}
func Constructor(nums []int) Solution {
return Solution{
nums: nums,
}
}
/** Resets the array to its original configuration and return it. */
func (this *Solution) Reset() []int {
return this.nums
}
/** Returns a random shuffling of the array. */
func (this *Solution) Shuffle() []int {
arr := make([]int, len(this.nums))
copy(arr, this.nums)
rand.Shuffle(len(arr), func(i, j int) {
arr[i], arr[j] = arr[j], arr[i]
})
return arr
}
```

18
leetcode/0390.Elimination-Game/390. Elimination Game.go
View File

@ -1,18 +0,0 @@
package leetcode
func lastRemaining(n int) int {
start, dir, step := 1, true, 1
for n > 1 {
if dir { // 正向
start += step
} else { // 反向
if n%2 == 1 {
start += step
}
}
dir = !dir
n >>= 1
step <<= 1
}
return start
}

47
leetcode/0390.Elimination-Game/390. Elimination Game_test.go
View File

@ -1,47 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question390 struct {
para390
ans390
}
// para 是参数
// one 代表第一个参数
type para390 struct {
n int
}
// ans 是答案
// one 代表第一个答案
type ans390 struct {
one int
}
func Test_Problem390(t *testing.T) {
qs := []question390{
{
para390{9},
ans390{6},
},
{
para390{1},
ans390{1},
},
}
fmt.Printf("------------------------Leetcode Problem 390------------------------\n")
for _, q := range qs {
_, p := q.ans390, q.para390
fmt.Printf("【input】:%v 【output】:%v\n", p, lastRemaining(p.n))
}
fmt.Printf("\n\n\n")
}

74
leetcode/0390.Elimination-Game/README.md
View File

@ -1,74 +0,0 @@
# [390. Elimination Game](https://leetcode.com/problems/elimination-game/)
## 题目
You have a list `arr` of all integers in the range `[1, n]` sorted in a strictly increasing order. Apply the following algorithm on `arr`:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer `n`, return *the last number that remains in* `arr`.
**Example 1:**
```
Input: n = 9
Output: 6
Explanation:
arr = [1, 2,3, 4,5, 6,7, 8,9]
arr = [2,4, 6,8]
arr = [2, 6]
arr = [6]
```
**Example 2:**
```
Input: n = 1
Output: 1
```
**Constraints:**
- `1 <= n <= 109`
## 题目大意
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
- 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
- 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
- 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
给你整数 n ，返回 arr 最后剩下的数字。
## 解题思路
- 模拟题。按照题意，第一轮从左往右删除数字，第二轮从右往左删除数字。题目要求最后剩下的数字，模拟过程中不需要真的删除元素。只需要标记起始元素，该轮步长和方向即可。最后总元素只剩下一个即为所求。
## 代码
```go
package leetcode
func lastRemaining(n int) int {
start, dir, step := 1, true, 1
for n > 1 {
if dir { // 正向
start += step
} else { // 反向
if n%2 == 1 {
start += step
}
}
dir = !dir
n >>= 1
step <<= 1
}
return start
}
```

53
leetcode/0391.Perfect-Rectangle/391.Perfect Rectangle.go
View File

@ -1,53 +0,0 @@
package leetcode
type point struct {
x int
y int
}
func isRectangleCover(rectangles [][]int) bool {
minX, minY, maxA, maxB := rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
area := 0
cnt := make(map[point]int)
for _, v := range rectangles {
x, y, a, b := v[0], v[1], v[2], v[3]
area += (a - x) * (b - y)
minX = min(minX, x)
minY = min(minY, y)
maxA = max(maxA, a)
maxB = max(maxB, b)
cnt[point{x, y}]++
cnt[point{a, b}]++
cnt[point{x, b}]++
cnt[point{a, y}]++
}
if area != (maxA-minX)*(maxB-minY) ||
cnt[point{minX, minY}] != 1 || cnt[point{maxA, maxB}] != 1 ||
cnt[point{minX, maxB}] != 1 || cnt[point{maxA, minY}] != 1 {
return false
}
delete(cnt, point{minX, minY})
delete(cnt, point{maxA, maxB})
delete(cnt, point{minX, maxB})
delete(cnt, point{maxA, minY})
for _, v := range cnt {
if v != 2 && v != 4 {
return false
}
}
return true
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}

55
leetcode/0391.Perfect-Rectangle/391.Perfect Rectangle_test.go
View File

@ -1,55 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question391 struct {
para391
ans391
}
// para 是参数
type para391 struct {
rectangles [][]int
}
// ans 是答案
type ans391 struct {
ans bool
}
func Test_Problem391(t *testing.T) {
qs := []question391{
{
para391{[][]int{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}},
ans391{true},
},
{
para391{[][]int{{1, 1, 2, 3}, {1, 3, 2, 4}, {3, 1, 4, 2}, {3, 2, 4, 4}}},
ans391{false},
},
{
para391{[][]int{{1, 1, 3, 3}, {3, 1, 4, 2}, {1, 3, 2, 4}, {3, 2, 4, 4}}},
ans391{false},
},
{
para391{[][]int{{1, 1, 3, 3}, {3, 1, 4, 2}, {1, 3, 2, 4}, {2, 2, 4, 4}}},
ans391{false},
},
}
fmt.Printf("------------------------Leetcode Problem 391------------------------\n")
for _, q := range qs {
_, p := q.ans391, q.para391
fmt.Printf("【input】:%v 【output】:%v\n", p, isRectangleCover(p.rectangles))
}
fmt.Printf("\n\n\n")
}

114
leetcode/0391.Perfect-Rectangle/README.md
View File

@ -1,114 +0,0 @@
# [391. Perfect Rectangle](https://leetcode.com/problems/perfect-rectangle/)
## 题目
Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).
Return true if all the rectangles together form an exact cover of a rectangular region.
**Example1:**
![https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg](https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg)
Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.
**Example2:**
![https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg](https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg)
Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.
**Example3:**
![https://assets.leetcode.com/uploads/2021/03/27/perfectrec3-plane.jpg](https://assets.leetcode.com/uploads/2021/03/27/perfectrec3-plane.jpg)
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
Output: false
Explanation: Because there is a gap in the top center.
**Example4:**
![https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg](https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg)
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.
**Constraints:**
- 1 <= rectangles.length <= 2 * 10000
- rectangles[i].length == 4
- -100000 <= xi, yi, ai, bi <= 100000
## 题目大意
给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
## 解题思路
- 矩形区域的面积等于所有矩形的面积之和并且满足矩形区域四角的顶点只能出现一次，且其余顶点的出现次数只能是两次或四次则返回 true,否则返回 false
## 代码
```go
package leetcode
type point struct {
x int
y int
}
func isRectangleCover(rectangles [][]int) bool {
minX, minY, maxA, maxB := rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
area := 0
cnt := make(map[point]int)
for _, v := range rectangles {
x, y, a, b := v[0], v[1], v[2], v[3]
area += (a - x) * (b - y)
minX = min(minX, x)
minY = min(minY, y)
maxA = max(maxA, a)
maxB = max(maxB, b)
cnt[point{x, y}]++
cnt[point{a, b}]++
cnt[point{x, b}]++
cnt[point{a, y}]++
}
if area != (maxA - minX) * (maxB - minY) ||
cnt[point{minX, minY}] != 1 || cnt[point{maxA, maxB}] != 1 ||
cnt[point{minX, maxB}] != 1 || cnt[point{maxA, minY}] != 1 {
return false
}
delete(cnt, point{minX, minY})
delete(cnt, point{maxA, maxB})
delete(cnt, point{minX, maxB})
delete(cnt, point{maxA, minY})
for _, v := range cnt {
if v != 2 && v != 4 {
return false
}
}
return true
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
```

18
leetcode/0396.Rotate-Function/396. Rotate Function.go
View File

@ -1,18 +0,0 @@
package leetcode
func maxRotateFunction(nums []int) int {
n := len(nums)
var sum, f int
for i, num := range nums {
sum += num
f += i * num // F(0)
}
ans := f
for i := 1; i < n; i++ {
f += sum - n*nums[n-i] // F(i) = F(i-1) + sum - n*nums[n-i]
if f > ans {
ans = f
}
}
return ans
}

46
leetcode/0396.Rotate-Function/396. Rotate Function_test.go
View File

@ -1,46 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question396 struct {
para396
ans396
}
// para 是参数
// one 代表第一个参数
type para396 struct {
one []int
}
// ans 是答案
// one 代表第一个答案
type ans396 struct {
one int
}
func Test_Problem396(t *testing.T) {
qs := []question396{
{
para396{[]int{4, 3, 2, 6}},
ans396{26},
},
{
para396{[]int{100}},
ans396{0},
},
}
fmt.Printf("------------------------Leetcode Problem 396------------------------\n")
for _, q := range qs {
_, p := q.ans396, q.para396
fmt.Printf("【input】:%v 【output】:%v\n", p, maxRotateFunction(p.one))
}
fmt.Printf("\n\n\n")
}

110
leetcode/0396.Rotate-Function/README.md
View File

@ -1,110 +0,0 @@
# [396. Rotate Function](https://leetcode.com/problems/rotate-function/)
## 题目
You are given an integer array `nums` of length `n`.
Assume `arrk` to be an array obtained by rotating `nums` by `k` positions clock-wise. We define the **rotation function** `F` on `nums` as follow:
- `F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]`.
Return the maximum value of `F(0), F(1), ..., F(n-1)`.
The test cases are generated so that the answer fits in a **32-bit** integer.
**Example 1:**
```c
Input: nums = [4,3,2,6]
Output: 26
Explanation:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
```
**Example 2:**
```c
Input: nums = [100]
Output: 0
```
**Constraints:**
- `n == nums.length`
- `1 <= n <= 105`
- `-100 <= nums[i] <= 100`
## 题目大意
给定一个长度为`n`的整数数组`nums`，设`arrk`是数组`nums`顺时针旋转`k`个位置后的数组。
定义`nums`的旋转函数`F`为：
- `F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]`
返回`F(0), F(1), ..., F(n-1)`中的最大值。
## 解题思路
**抽象化观察：**
```c
nums = [A0, A1, A2, A3]
sum = A0 + A1 + A2+ A3
F(0) = 0*A0 +0*A0 + 1*A1 + 2*A2 + 3*A3
F(1) = 0*A3 + 1*A0 + 2*A1 + 3*A2
= F(0) + (A0 + A1 + A2) - 3*A3
= F(0) + (sum-A3) - 3*A3
= F(0) + sum - 4*A3
F(2) = 0*A2 + 1*A3 + 2*A0 + 3*A1
= F(1) + A3 + A0 + A1 - 3*A2
= F(1) + sum - 4*A2
F(3) = 0*A1 + 1*A2 + 2*A3 + 3*A0
= F(2) + A2 + A3 + A0 - 3*A1
= F(2) + sum - 4*A1
// 记sum为nums数组中所有元素和
// 可以猜测当0 ≤ i < n时存在公式:
F(i) = F(i-1) + sum - n * A(n-i)
```
**数学归纳法证明迭代公式：**
根据题目中给定的旋转函数公式可得已知条件：
- `F(0) = 0×nums[0] + 1×nums[1] + ... + (n−1)×nums[n−1]`；
- `F(1) = 1×nums[0] + 2×nums[1] + ... + 0×nums[n-1]`。
令数组`nums`中所有元素和为`sum`，用数学归纳法验证：当`1 ≤ k < n`时，`F(k) = F(k-1) + sum - n×nums[n-k]`成立。
**归纳奠基**：证明`k=1`时命题成立。
```c
F(1) = 1×nums[0] + 2×nums[1] + ... + 0×nums[n-1]
= F(0) + sum - n×nums[n-1]
```
**归纳假设**：假设`F(k) = F(k-1) + sum - n×nums[n-k]`成立。
**归纳递推**：由归纳假设推出`F(k+1) = F(k) + sum - n×nums[n-(k+1)]`成立，则假设的递推公式成立。
```c
F(k+1) = (k+1)×nums[0] + k×nums[1] + ... + 0×nums[n-1]
= F(k) + sum - n×nums[n-(k+1)]
```
因此可以得到递推公式：
- 当`n = 0`时，`F(0) = 0×nums[0] + 1×nums[1] + ... + (n−1)×nums[n−1]`
- 当`1 ≤ k < n`时，`F(k) = F(k-1) + sum - n×nums[n-k]`成立。
循环遍历`0 ≤ k < n`，计算出不同的`F(k)`并不断更新最大值，就能求出`F(0), F(1), ..., F(n-1)`中的最大值。

19
leetcode/0400.Nth-Digit/400.Nth Digit.go
View File

@ -1,19 +0,0 @@
package leetcode
import "math"
func findNthDigit(n int) int {
if n <= 9 {
return n
}
bits := 1
for n > 9*int(math.Pow10(bits-1))*bits {
n -= 9 * int(math.Pow10(bits-1)) * bits
bits++
}
idx := n - 1
start := int(math.Pow10(bits - 1))
num := start + idx/bits
digitIdx := idx % bits
return num / int(math.Pow10(bits-digitIdx-1)) % 10
}

45
leetcode/0400.Nth-Digit/400.Nth Digit_test.go
View File

@ -1,45 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question400 struct {
para400
ans400
}
// para 是参数
type para400 struct {
n int
}
// ans 是答案
type ans400 struct {
ans int
}
func Test_Problem400(t *testing.T) {
qs := []question400{
{
para400{3},
ans400{3},
},
{
para400{11},
ans400{0},
},
}
fmt.Printf("------------------------Leetcode Problem 400------------------------\n")
for _, q := range qs {
_, p := q.ans400, q.para400
fmt.Printf("【input】:%v 【output】:%v\n", p.n, findNthDigit(p.n))
}
fmt.Printf("\n\n\n")
}

67
leetcode/0400.Nth-Digit/README.md
View File

@ -1,67 +0,0 @@
# [400. Nth Digit](https://leetcode.com/problems/nth-digit/)
## 题目
Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
**Example 1**:
Input: n = 3
Output: 3
**Example 2**:
Input: n = 11
Output: 0
Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
**Constraints:**
- 1 <= n <= int(math.Pow(2, 31)) - 1
## 题目大意
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位数字。
## 解题思路
- bits = 1 的时候有 1,2,3,4,5,6,7,8,9 这 9 个数; 9 = math.Pow10(bits - 1) * bits
- bits = 2 的时候有 10-99 这 90 个数; 90 = math.Pow10(bits - 1) * bits
- n 不断减去 bits 从 1 开始的数字总数,求出 n 所在的数字是几位数即 bits
- 计算 n 所在的数字 num，等于初始值加上 (n - 1) / bits
- 计算 n 所在这个数字的第几位 digitIdx 等于 (n - 1) % bits
- 计算出 digitIdx 位的数字
### 以11 为例:
11 - 9 = 2
(2 - 1) / 2 = 0
(2 - 1) % 2 = 1
也就是说第 11 位数字是位数是 2 的第一个数字的第二位，即是 0
## 代码
```go
package leetcode
import "math"
func findNthDigit(n int) int {
if n <= 9 {
return n
}
bits := 1
for n > 9*int(math.Pow10(bits-1))*bits {
n -= 9 * int(math.Pow10(bits-1)) * bits
bits++
}
idx := n - 1
start := int(math.Pow10(bits - 1))
num := start + idx/bits
digitIdx := idx % bits
return num / int(math.Pow10(bits-digitIdx-1)) % 10
}
```

10
leetcode/0401.Binary-Watch/401. Binary Watch.go
View File

@ -76,11 +76,11 @@ func readBinaryWatch1(num int) []string {
return res
}
// / ---------------------------------------
// / ---------------------------------------
// / ---------------------------------------
// / ---------------------------------------
// / ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
// 以下是打表用到的函数
// 调用 findReadBinaryWatchMinute(num, 0, c, &res) 打表
func findReadBinaryWatchMinute(target, index int, c []int, res *[]string) {

21
leetcode/0419.Battleships-in-a-Board/419. Battleships in a Board.go
View File

@ -1,21 +0,0 @@
package leetcode
func countBattleships(board [][]byte) (ans int) {
if len(board) == 0 || len(board[0]) == 0 {
return 0
}
for i := range board {
for j := range board[i] {
if board[i][j] == 'X' {
if i > 0 && board[i-1][j] == 'X' {
continue
}
if j > 0 && board[i][j-1] == 'X' {
continue
}
ans++
}
}
}
return
}

59
leetcode/0419.Battleships-in-a-Board/419. Battleships in a Board_test.go
View File

@ -1,59 +0,0 @@
package leetcode
import (
"fmt"
"testing"
"unsafe"
)
type question419 struct {
para419
ans419
}
// para 是参数
// one 代表第一个参数
type para419 struct {
one [][]byte
}
// ans 是答案
// one 代表第一个答案
type ans419 struct {
one int
}
func Test_Problem419(t *testing.T) {
qs := []question419{
{
para419{[][]byte{{'X', '.', '.', 'X'}, {'.', '.', '.', 'X'}, {'.', '.', '.', 'X'}}},
ans419{2},
},
{
para419{[][]byte{{'.'}}},
ans419{0},
},
}
fmt.Printf("------------------------Leetcode Problem 419------------------------\n")
for _, q := range qs {
_, p := q.ans419, q.para419
fmt.Printf("【input】:%v 【output】:%v\n", bytesArrayToStringArray(p.one), countBattleships(p.one))
}
fmt.Printf("\n\n\n")
}
// 在运行go test时 为了更直观地显示[][]byte中的字符而非ASCII码数值
// bytesArrayToStringArray converts [][]byte to []string
func bytesArrayToStringArray(b [][]byte) []string {
s := make([]string, len(b))
for i := range b {
s[i] = fmt.Sprintf("[%v]", *(*string)(unsafe.Pointer(&b[i])))
}
return s
}

51
leetcode/0419.Battleships-in-a-Board/README.md
View File

@ -1,51 +0,0 @@
# [419. Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)
## 题目
Given an `m x n` matrix `board` where each cell is a battleship `'X'` or empty `'.'`, return the number of the **battleships** on `board`.
**Battleships** can only be placed horizontally or vertically on `board`. In other words, they can only be made of the shape `1 x k` (`1` row, `k` columns) or `k x 1` (`k` rows, `1` column), where `k` can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
**Example 1:**
![img](https://assets.leetcode.com/uploads/2021/04/10/battelship-grid.jpg)
```c
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2
```
**Example 2:**
```c
Input: board = [["."]]
Output: 0
```
**Constraints:**
- `m == board.length`
- `n == board[i].length`
- `1 <= m, n <= 200`
- `board[i][j] is either '.' or 'X'`.
**Follow up:** Could you do it in one-pass, using only `O(1)` extra memory and without modifying the values `board`?
## 题目大意
给定一个大小为`m × n`的矩阵 称之为甲板，矩阵单元格中的`'X'`表示战舰，`'.'`表示空位。
战舰只能水平或竖直摆放在甲板上（换句话说，可以理解为联通的同一行`'X'`或同一列`'X'`只算作一个“战舰群”），任意俩个“战舰群”间都是不相邻的。返回甲板上“战舰群”的数量。
## 解题思路
题目进阶要求一次扫描算法，空间复杂度为`O(1)`，且不能修改矩阵中的值。
因为题目中给定的两个“战舰群”间至少有一个水平或垂直的空位分隔，所以可以通过枚举每个战舰的左上顶点即可统计“战舰群”的个数。
假设当前遍历到矩阵中`'X'`的位置为`(i, j)`，即 `board[i][j]='X'`。如果当前战舰属于一个新的“战舰群”，则需要满足以下条件：
- 当前位置的上方位为空，即 `board[i-1][j]='.'`；
- 当前位置的左方位为空，即 `board[i][j-1]='.'`；
统计出所有左方位和上方位为空的战舰个数，即可得到“战舰群”的数量。

10
leetcode/0429.N-ary-Tree-Level-Order-Traversal/429. N-ary Tree Level Order Traversal_test.go
View File

@ -1,10 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
func Test_Problem429(t *testing.T) {
fmt.Printf("success\n")
}

8
leetcode/0458.Poor-Pigs/458.Poor Pigs.go
View File

@ -1,8 +0,0 @@
package leetcode
import "math"
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
base := minutesToTest/minutesToDie + 1
return int(math.Ceil(math.Log10(float64(buckets)) / math.Log10(float64(base))))
}

52
leetcode/0458.Poor-Pigs/458.Poor Pigs_test.go
View File

@ -1,52 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question458 struct {
para458
ans458
}
// para 是参数
type para458 struct {
buckets int
minutesToDie int
minutesToTest int
}
// ans 是答案
type ans458 struct {
ans int
}
func Test_Problem458(t *testing.T) {
qs := []question458{
{
para458{1000, 15, 60},
ans458{5},
},
{
para458{4, 15, 15},
ans458{2},
},
{
para458{4, 15, 30},
ans458{2},
},
}
fmt.Printf("------------------------Leetcode Problem 458------------------------\n")
for _, q := range qs {
_, p := q.ans458, q.para458
fmt.Printf("【input】:%v 【output】:%v\n", p, poorPigs(p.buckets, p.minutesToDie, p.minutesToTest))
}
fmt.Printf("\n\n\n")
}

77
leetcode/0458.Poor-Pigs/README.md
View File

@ -1,77 +0,0 @@
# [458. Poor Pigs](https://leetcode.com/problems/poor-pigs/)
## 题目
There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.
You can feed the pigs according to these steps:
- Choose some live pigs to feed.
- For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time.
- Wait for minutesToDie minutes. You may not feed any other pigs during this time.
- After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
- Repeat this process until you run out of time.
Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.
**Example 1**:
Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output: 5
**Example 2**:
Input: buckets = 4, minutesToDie = 15, minutesToTest = 15
Output: 2
**Example 3**:
Input: buckets = 4, minutesToDie = 15, minutesToTest = 30
Output: 2
**Constraints:**
- 1 <= buckets <= 1000
- 1 <= minutesToDie <= minutesToTest <= 100
## 题目大意
有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
- 选择若干活猪进行喂养
- 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
- 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
- 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
- 重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
## 解题思路
使用数学方法,以 minutesToDie=15, minutesToTest=60, 1 只小猪为例,可以测试 5 只桶
- 0-15 小猪吃第一个桶中的液体,如果死去，则第一个桶有毒,否则继续测试
- 15-30 小猪吃第二个桶中的液体，如果死去，则第二个桶有毒,否则继续测试
- 30-45 小猪吃第三个桶中的液体，如果死去，则第三个桶有毒,否则继续测试
- 45-60 小猪吃第四个桶中的液体，如果死去，则第四个桶有毒
- 如果最后小猪没有死去，则第五个桶有毒
所以一只小猪在 minutesToDie 和 minutesToTest 时间一定的情况下可以最多判断 base = minutesToTest / minutesToDie + 1 个桶
假设小猪的数量是 num,那么 pow(base, num) >= buckets,根据对数运算规则，两边分别取对数得到: num >= Log10(buckets) / Log10(base)
## 代码
```go
package leetcode
import "math"
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
base := minutesToTest/minutesToDie + 1
return int(math.Ceil(math.Log10(float64(buckets)) / math.Log10(float64(base))))
}
```

50
leetcode/0488.Zuma-Game/488.Zuma Game.go
View File

@ -1,50 +0,0 @@
package leetcode
func findMinStep(board string, hand string) int {
q := [][]string{{board, hand}}
mp := make(map[string]bool)
minStep := 0
for len(q) > 0 {
length := len(q)
minStep++
for length > 0 {
length--
cur := q[0]
q = q[1:]
curB, curH := cur[0], cur[1]
for i := 0; i < len(curB); i++ {
for j := 0; j < len(curH); j++ {
curB2 := del3(curB[0:i] + string(curH[j]) + curB[i:])
curH2 := curH[0:j] + curH[j+1:]
if len(curB2) == 0 {
return minStep
}
if _, ok := mp[curB2+curH2]; ok {
continue
}
mp[curB2+curH2] = true
q = append(q, []string{curB2, curH2})
}
}
}
}
return -1
}
func del3(str string) string {
cnt := 1
for i := 1; i < len(str); i++ {
if str[i] == str[i-1] {
cnt++
} else {
if cnt >= 3 {
return del3(str[0:i-cnt] + str[i:])
}
cnt = 1
}
}
if cnt >= 3 {
return str[0 : len(str)-cnt]
}
return str
}

56
leetcode/0488.Zuma-Game/488.Zuma Game_test.go
View File

@ -1,56 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question488 struct {
para488
ans488
}
// para 是参数
type para488 struct {
board string
hand string
}
// ans 是答案
type ans488 struct {
ans int
}
func Test_Problem488(t *testing.T) {
qs := []question488{
{
para488{"WRRBBW", "RB"},
ans488{-1},
},
{
para488{"WWRRBBWW", "WRBRW"},
ans488{2},
},
{
para488{"G", "GGGGG"},
ans488{2},
},
{
para488{"RBYYBBRRB", "YRBGB"},
ans488{3},
},
}
fmt.Printf("------------------------Leetcode Problem 488------------------------\n")
for _, q := range qs {
_, p := q.ans488, q.para488
fmt.Printf("【input】:%v 【output】:%v\n", p, findMinStep(p.board, p.hand))
}
fmt.Printf("\n\n\n")
}

141
leetcode/0488.Zuma-Game/README.md
View File

@ -1,141 +0,0 @@
# [488. Zuma Game](https://leetcode.com/problems/zuma-game/)
## 题目
You are playing a variation of the game Zuma.
In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.
Your goal is to clear all of the balls from the board. On each turn:
Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.
If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.
If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.
If there are no more balls on the board, then you win the game.
Repeat this process until you either win or do not have any more balls in your hand.
Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.
**Example 1**:
```
Input: board = "WRRBBW", hand = "RB"
Output: -1
Explanation: It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the board becomes WRRRBBW. WRRRBBW -> WBBW.
- Insert 'B' so the board becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the board, and you are out of balls to insert.
```
**Example 2**:
```
Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Explanation: To make the board empty:
- Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW.
- Insert 'B' so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty.
2 balls from your hand were needed to clear the board.
```
**Example 3**:
```
Input: board = "G", hand = "GGGGG"
Output: 2
Explanation: To make the board empty:
- Insert 'G' so the board becomes GG.
- Insert 'G' so the board becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the board.
```
**Example 4**:
```
Input: board = "RBYYBBRRB", hand = "YRBGB"
Output: 3
Explanation: To make the board empty:
- Insert 'Y' so the board becomes RBYYYBBRRB. RBYYYBBRRB -> RBBBRRB -> RRRB -> B.
- Insert 'B' so the board becomes BB.
- Insert 'B' so the board becomes BBB. BBB -> empty.
3 balls from your hand were needed to clear the board.
```
**Constraints**:
- 1 <= board.length <= 16
- 1 <= hand.length <= 5
- board and hand consist of the characters 'R', 'Y', 'B', 'G', and 'W'.
- The initial row of balls on the board will not have any groups of three or more consecutive balls of the same color.
## 题目大意
你正在参与祖玛游戏的一个变种。
在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。
你的目标是 清空 桌面上所有的球。每一回合：
从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
如果桌面上所有球都被移除，则认为你赢得本场游戏。
重复这个过程，直到你赢了游戏或者手中没有更多的球。
给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。
## 解题思路
- 使用广度优先搜索和剪枝
## 代码
```go
package leetcode
func findMinStep(board string, hand string) int {
q := [][]string{{board, hand}}
mp := make(map[string]bool)
minStep := 0
for len(q) > 0 {
length := len(q)
minStep++
for length > 0 {
length--
cur := q[0]
q = q[1:]
curB, curH := cur[0], cur[1]
for i := 0; i < len(curB); i++ {
for j := 0; j < len(curH); j++ {
curB2 := del3(curB[0:i] + string(curH[j]) + curB[i:])
curH2 := curH[0:j] + curH[j+1:]
if len(curB2) == 0 {
return minStep
}
if _, ok := mp[curB2+curH2]; ok {
continue
}
mp[curB2+curH2] = true
q = append(q, []string{curB2, curH2})
}
}
}
}
return -1
}
func del3(str string) string {
cnt := 1
for i := 1; i < len(str); i++ {
if str[i] == str[i-1] {
cnt++
} else {
if cnt >= 3 {
return del3(str[0:i-cnt] + str[i:])
}
cnt = 1
}
}
if cnt >= 3 {
return str[0 : len(str)-cnt]
}
return str
}
```

0
leetcode/0491.Non-decreasing-Subsequences/491. Non-decreasing Subsequences.go → leetcode/0491.Increasing-Subsequences/491. Increasing Subsequences.go
View File

0
leetcode/0491.Non-decreasing-Subsequences/491. Non-decreasing Subsequences_test.go → leetcode/0491.Increasing-Subsequences/491. Increasing Subsequences_test.go
View File

2
leetcode/0491.Non-decreasing-Subsequences/README.md → leetcode/0491.Increasing-Subsequences/README.md
View File

@ -1,4 +1,4 @@
# [491. Non-decreasing Subsequences](https://leetcode.com/problems/non-decreasing-subsequences/)
# [491. Increasing Subsequences](https://leetcode.com/problems/increasing-subsequences/)
## 题目

16
leetcode/0492.Construct-the-Rectangle/492.Construct the Rectangle.go
View File

@ -1,16 +0,0 @@
package leetcode
import "math"
func constructRectangle(area int) []int {
ans := make([]int, 2)
W := int(math.Sqrt(float64(area)))
for W >= 1 {
if area%W == 0 {
ans[0], ans[1] = area/W, W
break
}
W -= 1
}
return ans
}

50
leetcode/0492.Construct-the-Rectangle/492.Construct the Rectangle_test.go
View File

@ -1,50 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question492 struct {
para492
ans492
}
// area 是参数
type para492 struct {
area int
}
// ans 是答案
type ans492 struct {
ans []int
}
func Test_Problem492(t *testing.T) {
qs := []question492{
{
para492{4},
ans492{[]int{2, 2}},
},
{
para492{37},
ans492{[]int{37, 1}},
},
{
para492{122122},
ans492{[]int{427, 286}},
},
}
fmt.Printf("------------------------Leetcode Problem 492------------------------\n")
for _, q := range qs {
_, p := q.ans492, q.para492
fmt.Printf("【input】:%v 【output】:%v\n", p, constructRectangle(p.area))
}
fmt.Printf("\n\n\n")
}

72
leetcode/0492.Construct-the-Rectangle/README.md
View File

@ -1,72 +0,0 @@
# [492. Construct the Rectangle](https://leetcode.com/problems/construct-the-rectangle/)
## 题目
A web developer needs to know how to design a web page's size.
So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page,
whose length L and width W satisfy the following requirements:
The area of the rectangular web page you designed must equal to the given target area.
The width W should not be larger than the length L, which means L >= W.
The difference between length L and width W should be as small as possible.
Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.
**Example 1:**
Input: area = 4
Output: [2,2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
**Example 2:**
Input: area = 37
Output: [37,1]
**Example 3:**
Input: area = 122122
Output: [427,286]
**Constraints**
- 1 <= area <= 10000000
## 题目大意
作为一位 web 开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。
你需要按顺序输出你设计的页面的长度 L 和宽度 W。
## 解题思路
- 令 W 等于根号 area
- 在 W 大于等于 1 的情况下,判断 area%W 是否等于 0,如果不相等 W 就减 1 继续循环,如果相等就返回 [area/W, W]
## 代码
```go
package leetcode
import "math"
func constructRectangle(area int) []int {
ans := make([]int, 2)
W := int(math.Sqrt(float64(area)))
for W >= 1 {
if area%W == 0 {
ans[0], ans[1] = area/W, W
break
}
W -= 1
}
return ans
}
``

16
leetcode/0495.Teemo-Attacking/495.Teemo Attacking.go
View File

@ -1,16 +0,0 @@
package leetcode
func findPoisonedDuration(timeSeries []int, duration int) int {
var ans int
for i := 1; i < len(timeSeries); i++ {
t := timeSeries[i-1]
end := t + duration - 1
if end < timeSeries[i] {
ans += duration
} else {
ans += timeSeries[i] - t
}
}
ans += duration
return ans
}

46
leetcode/0495.Teemo-Attacking/495.Teemo Attacking_test.go
View File

@ -1,46 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question495 struct {
para495
ans495
}
// para 是参数
type para495 struct {
timeSeries []int
duration int
}
// ans 是答案
type ans495 struct {
ans int
}
func Test_Problem495(t *testing.T) {
qs := []question495{
{
para495{[]int{1, 4}, 2},
ans495{4},
},
{
para495{[]int{1, 2}, 2},
ans495{3},
},
}
fmt.Printf("------------------------Leetcode Problem 495------------------------\n")
for _, q := range qs {
_, p := q.ans495, q.para495
fmt.Printf("【input】:%v 【output】:%v\n", p, findPoisonedDuration(p.timeSeries, p.duration))
}
fmt.Printf("\n\n\n")
}

85
leetcode/0495.Teemo-Attacking/README.md
View File

@ -1,85 +0,0 @@
# [495. Teemo Attacking](https://leetcode.com/problems/teemo-attacking/)
## 题目
Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds.
More formally, an attack at second t will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1].
If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration seconds after the new attack.
You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at second timeSeries[i], and an integer duration.
Return the total number of seconds that Ashe is poisoned.
**Example 1**:
```
Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.
```
**Example 2**:
```
Input: timeSeries = [1,2], duration = 2
Output: 3
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3.
Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.
```
**Constraints**:
- 1 <= timeSeries.length <= 10000
- 0 <= timeSeries[i], duration <= 10000000
- timeSeries is sorted in non-decreasing order.
## 题目大意
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续duration 秒。
正式地讲，提莫在t发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。
如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在duration秒后结束。
给你一个非递减的整数数组timeSeries，其中timeSeries[i]表示提莫在timeSeries[i]秒时对艾希发起攻击，以及一个表示中毒持续时间的整数duration 。
返回艾希处于中毒状态的总秒数。
## 解题思路
- i 从 1 开始计数，令 t 等于 timeSeries[i - 1]
- 比较 end(t + duration - 1) 和 timeSeries[i] 的大小，
- 如果 end 小于 timeSeries[i],ans+=duration
- 否则 ans += timeSeries[i] - t
- ans += duration 并返回 ans
## 代码
```go
package leetcode
func findPoisonedDuration(timeSeries []int, duration int) int {
var ans int
for i := 1; i < len(timeSeries); i++ {
t := timeSeries[i-1]
end := t + duration - 1
if end < timeSeries[i] {
ans += duration
} else {
ans += timeSeries[i] - t
}
}
ans += duration
return ans
}
```

28
leetcode/0504.Base-7/504.Base 7.go
View File

@ -1,28 +0,0 @@
package leetcode
import "strconv"
func convertToBase7(num int) string {
if num == 0 {
return "0"
}
negative := false
if num < 0 {
negative = true
num = -num
}
var ans string
var nums []int
for num != 0 {
remainder := num % 7
nums = append(nums, remainder)
num = num / 7
}
if negative {
ans += "-"
}
for i := len(nums) - 1; i >= 0; i-- {
ans += strconv.Itoa(nums[i])
}
return ans
}

46
leetcode/0504.Base-7/504.Base 7_test.go
View File

@ -1,46 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question504 struct {
para504
ans504
}
// para 是参数
type para504 struct {
num int
}
// ans 是答案
type ans504 struct {
ans string
}
func Test_Problem504(t *testing.T) {
qs := []question504{
{
para504{100},
ans504{"202"},
},
{
para504{-7},
ans504{"-10"},
},
}
fmt.Printf("------------------------Leetcode Problem 504------------------------\n")
for _, q := range qs {
_, p := q.ans504, q.para504
fmt.Printf("【input】:%v ", p.num)
fmt.Printf("【output】:%v \n", convertToBase7(p.num))
}
fmt.Printf("\n\n\n")
}

60
leetcode/0504.Base-7/README.md
View File

@ -1,60 +0,0 @@
# [504. Base 7](https://leetcode.com/problems/base-7/)
## 题目
Given an integer num, return a string of its base 7 representation.
**Example 1:**
Input: num = 100
Output: "202"
**Example 2:**
Input: num = -7
Output: "-10"
**Constraints:**
- -10000000 <= num <= 10000000
## 题目大意
给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
## 解题思路
num反复除以7，然后倒排余数
# 代码
```go
package leetcode
import "strconv"
func convertToBase7(num int) string {
if num == 0 {
return "0"
}
negative := false
if num < 0 {
negative = true
num = -num
}
var ans string
var nums []int
for num != 0 {
remainder := num % 7
nums = append(nums, remainder)
num = num / 7
}
if negative {
ans += "-"
}
for i := len(nums) - 1; i >= 0; i-- {
ans += strconv.Itoa(nums[i])
}
return ans
}
```

29
leetcode/0506.Relative-Ranks/506.Relative Ranks.go
View File

@ -1,29 +0,0 @@
package leetcode
import (
"sort"
"strconv"
)
func findRelativeRanks(score []int) []string {
mp := make(map[int]int)
for i, v := range score {
mp[v] = i
}
sort.Slice(score, func(i, j int) bool {
return score[i] > score[j]
})
ans := make([]string, len(score))
for i, v := range score {
if i == 0 {
ans[mp[v]] = "Gold Medal"
} else if i == 1 {
ans[mp[v]] = "Silver Medal"
} else if i == 2 {
ans[mp[v]] = "Bronze Medal"
} else {
ans[mp[v]] = strconv.Itoa(i + 1)
}
}
return ans
}

45
leetcode/0506.Relative-Ranks/506.Relative Ranks_test.go
View File

@ -1,45 +0,0 @@
package leetcode
import (
"fmt"
"testing"
)
type question506 struct {
para506
ans506
}
// para 是参数
type para506 struct {
score []int
}
// ans 是答案
type ans506 struct {
ans []string
}
func Test_Problem506(t *testing.T) {
qs := []question506{
{
para506{[]int{5, 4, 3, 2, 1}},
ans506{[]string{"Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"}},
},
{
para506{[]int{10, 3, 8, 9, 4}},
ans506{[]string{"Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"}},
},
}
fmt.Printf("------------------------Leetcode Problem 506------------------------\n")
for _, q := range qs {
_, p := q.ans506, q.para506
fmt.Printf("【input】:%v 【output】:%v\n", p.score, findRelativeRanks(p.score))
}
fmt.Printf("\n\n\n")
}

Some files were not shown because too many files have changed in this diff Show More