Brantou的日常

二三事


  • 首页

  • 归档

  • 分类

  • 标签

  • 关于

  • 搜索

Emacs支持gomodifytags

发表于 2017-12-05 | 分类于 emacs-plugin |

受到《Go 终极指南:编写一个 Go 工具》的启发,萌生了把 gomodifytags 封装成emacs-plugin的想法, 然后经过两周的努力,诞生了emacs-go-tag。 emacs-go-tag 实现了两个命令: go-tag-add 添加结构体字段tag, go-tag-remove 删除结构体字段tag。

1 安装依赖

emacs-go-tag 有两个依赖项, gomodifytags 和 go-mode.el,若使用emacs做Go开发 go-mode.el 应该已经在使用了。 gomodifytags安装如下:

go get -u github.com/fatih/gomodifytags

2 安装

目前emacs-go-tag已发布到了MELPA上,可使用如下命令安装: M-x package-install [RET] go-tag [RET] 若是没发现go-tag,你需要使用如下命令来刷新,然后在使用上面的命令进行安装: M-x package-refresh-contents [RET]

3 配置

目前 gomodifytags 支持三种转换如下:

  • snakecase: BaseDomain -> base_domain
  • camelcase: BaseDomain -> baseDomain
  • lispcase: BaseDomain -> base-domain

默认使用 snakecase , 若你准备使用 camelcase, 可配置如下:

(setq go-tag-args (list "-transform" "camelcase"))

快捷键配置示例:

(with-eval-after-load 'go-mode
  (define-key go-mode-map (kbd "C-c t") #'go-tag-add)
  (define-key go-mode-map (kbd "C-c T") #'go-tag-remove))

4 使用说明

若是你有使用 vim-go 的 GoAddTags 和 GoRemoveTags 命令的经验, 那么你会很快上手 emacs-go-tag, 因为两者的行为完全一致(若有不同,请反馈)。

4.1 go-tag-add

:[range] go-tag-add [key],[option] [key1],[option] … 为结构体字段添加tag。如果在一个结构中调用,会自动添加json字段tag。 若在结构体之外调用,或者文件格式不正确,则会给出错误消息。

如果给出 [range] ,则只有选定的字段将被改变。

默认的json可以通过提供一个或多个 [key] 参数来改变。 添加xml和db的例子是: :go-tag-add xml db

若提供了 [option] 也提供了,会在添加tag时,一同添加 option , 或者修改已存在的tag。 如下: :go-tag-add json,omitempty

也可以定义一个常数值而不是默认的基于字段的值。 例如,以下命令将添加`valid:“1”`到所有字段。 :go-tag-add valid=1

<img src="go-tag-add.gif” />

4.2 go-tag-remove

:[range] go-tag-add [key],[option] [key1],[option] … 移除结构字段的字段标记。 如果在一个结构中调用,它会自动删除所有的字段tag。 如果在结构体定义之外调用,或者文件格式不正确,则会给出错误消息。

如果给出 [range] ,则只有选定的字段将被改变。

如果给出 [key] ,则只会删除这些key相关的tag。 如下只删除json相关的tag: :go-tag-remove json

如果 [option] 和 [key] 一同传递,则只会删除 option 。 例如,下面命令只会从包含json的字段中删除omitempty选项: :go-tag-remove json,omitempty

<img src="go-tag-remove.gif” />

5 最后

感谢 GoCN每日新闻 的每日推送,让我得以读到 《Go 终极指南:编写一个 Go 工具》, 然后我才得以写出这个emacs-plugin。 这里给出项目地址:https://github.com/brantou/emacs-go-tag, 欢迎大家来使用和来提问题,若是你觉得对你有帮助, 就给颗星 吧。

Last Updated 2017-12-08 Fri 12:31.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

Go语言不完全工具列表

发表于 2017-11-24 | 分类于 技术积累 |

1 impl

go get -u github.com/josharian/impl
impl -h
Usage of impl:
  -dir string
      package source directory, useful for vendored code
impl 'f *File' io.ReadWriteCloser
1
2
3
4
5
6
7
8
9
10
11
func (f *File) Read(p []byte) (n int, err error) {
panic("not implemented")
}

func (f *File) Write(p []byte) (n int, err error) {
panic("not implemented")
}

func (f *File) Close() error {
panic("not implemented")
}

2 gomodifytags

请参见之前的文章gomodifytags。

3 go-outline

go get -u github.com/lukehoban/go-outline
go-outline -h
Usage of go-outline:
  -f string
      the path to the file to outline
  -imports-only
      parse imports only
  -src string
      source code of the file to outline
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import "fmt"

type Outline struct {
Label string
Type string
}

func (ol *Outline) Label() string {
return ol.Label
}

const (
name = "brantou"
)

const email = "brantou89@gmail.com"

var (
cmd string
args string
)

func main() {
fmt.Printf("hello world!")
}
go-outline -f main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
[
{
"label": "main",
"type": "package",
"start": 1,
"end": 290,
"children": [
{
"label": "\"fmt\"",
"type": "import",
"start": 23,
"end": 28
},

{
"label": "Outline",
"type": "type",
"start": 35,
"end": 83
},

{
"label": "Label",
"type": "function",
"receiverType": "*Outline",
"start": 85,
"end": 140
},

{
"label": "name",
"type": "constant",
"start": 152,
"end": 156
},

{
"label": "email",
"type": "constant",
"start": 178,
"end": 183
},

{
"label": "cmd",
"type": "variable",
"start": 217,
"end": 220
},

{
"label": "args",
"type": "variable",
"start": 231,
"end": 235
},

{
"label": "main",
"type": "function",
"start": 246,
"end": 290
}

]
}

]
go-outline -f main.go -imports-only

4 go-symbols

go get -u github.com/newhook/go-symbols
go-symbols -h
Usage of go-symbols:
  -tags build tags
      a list of build tags to consider satisfied during the build. For more information about build tags, see the description of build constraints in the documentation for the go/build package
go-symbols $GOPATH/src/github.com/astaxie/beego beego
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
[
{
"name": "BeegoOutput",
"kind": "type",
"package": "context",
"path": "/home/parallels/.gvm/pkgsets/go1.9/global/src/github.com/astaxie/beego/context/output.go",
"line": 35,
"character": 0
},

{
"name": "BeegoInput",
"kind": "type",
"package": "context",
"path": "/home/parallels/.gvm/pkgsets/go1.9/global/src/github.com/astaxie/beego/context/input.go",
"line": 43,
"character": 0
},

{
"name": "NewBeegoRequest",
"kind": "func",
"package": "httplib",
"path": "/home/parallels/.gvm/pkgsets/go1.9/global/src/github.com/astaxie/beego/httplib/httplib.go",
"line": 80,
"character": 0
},

{
"name": "BeegoHTTPSettings",
"kind": "type",
"package": "httplib",
"path": "/home/parallels/.gvm/pkgsets/go1.9/global/src/github.com/astaxie/beego/httplib/httplib.go",
"line": 130,
"character": 0
},

{
"name": "BeegoHTTPRequest",
"kind": "type",
"package": "httplib",
"path": "/home/parallels/.gvm/pkgsets/go1.9/global/src/github.com/astaxie/beego/httplib/httplib.go",
"line": 146,
"character": 0
}

]

5 gocode

An autocompletion daemon for the Go programming language.

go get -u -v github.com/nsf/gocode
gocode -h
Usage: gocode [-s] [-f=<format>] [-in=<path>] [-sock=<type>] [-addr=<addr>]
     <command> [<args>]

Flags:
  -addr string
      address for tcp socket (default "127.0.0.1:37373")
  -debug
      enable server-side debug mode
  -f string
      output format (vim | emacs | nice | csv | csv-with-package | json) (default "nice")
  -in string
      use this file instead of stdin input
  -profile int
      port on which to expose profiling information for pprof; 0 to disable profiling
  -s	run a server instead of a client
  -sock string
      socket type (unix | tcp) (default "unix")

Commands:
  autocomplete [<path>] <offset>     main autocompletion command
  close                              close the gocode daemon
  status                             gocode daemon status report
  drop-cache                         drop gocode daemon's cache
  set [<name> [<value>]]             list or set config options

6 godef

Print where symbols are defined in Go source code.

go get -u -v github.com/rogpeppe/godef
godef -h
usage: godef [flags] [expr]
  -A	print all type and members information
  -a	print public type and member information
  -acme
      use current acme window
  -debug
      debug mode
  -f string
      Go source filename
  -i	read file from stdin
  -json
      output location in JSON format (-t flag is ignored)
  -o int
      file offset of identifier in stdin (default -1)
  -t	print type information

7 gogetdoc

Retrieve documentation for items in Go source code.

go get -u -v github.com/zmb3/gogetdoc
gogetdoc -h
Usage of gogetdoc
  -cpuprofile string
      write cpu profile to file
  -json
      enable extended JSON output
  -linelength int
      maximum length of a line in the output (in Unicode code points) (default 80)
  -modified
      read an archive of modified files from standard input
  -pos string
      Filename and byte offset of item to document, e.g. foo.go:#123
  -tags build tags
      a list of build tags to consider satisfied during the build. For more information about build tags, see the description of build constraints in the documentation for the go/build package
  -u	show unexported fields

The archive format for the -modified flag consists of the file name, followed
by a newline, the decimal file size, another newline, and the contents of the file.

This allows editors to supply gogetdoc with the contents of their unsaved buffers.

8 golint

Golint is a linter for Go source code.

go get -u github.com/golang/lint/golint
golint -h
Usage of golint:
	golint [flags] # runs on package in current directory
	golint [flags] [packages]
	golint [flags] [directories] # where a '/...' suffix includes all sub-directories
	golint [flags] [files] # all must belong to a single package
Flags:
  -min_confidence float
      minimum confidence of a problem to print it (default 0.8)
  -set_exit_status
      set exit status to 1 if any issues are found
golint google.go
google.go:19:1: exported function Search should have comment or be unexported

9 gopkgs

Gopkgs is tools that provide list of available Go packages that can be imported. This are alternative to go list all, it just faster.

go get github.com/uudashr/gopkgs/cmd/gopkgs
gopkgs -help
Usage of gopkgs:
  -format string
      custom output format (default "{ {.ImportPath} }")
  -help
      show this message


Use -format to custom the output using template syntax. The struct being passed to template is:

  type Pkg struct {
      Dir        string // directory containing package sources
      ImportPath string // import path of package in dir
      Name       string // package name
  }
gopkgs -format "{ {.Name} };{ {.ImportPath} }"

10 gorename

go get -u -v golang.org/x/tools/cmd/gorename
gorename -help
gorename: precise type-safe renaming of identifiers in Go source code.

Usage:

 gorename (-from <spec> | -offset <file>:#<byte-offset>) -to <name> [-force]

You must specify the object (named entity) to rename using the -offset
or -from flag.  Exactly one must be specified.

Flags:

  -offset    specifies the filename and byte offset of an identifier to rename.
             This form is intended for use by text editors.

  -from      specifies the object to rename using a query notation;
             This form is intended for interactive use at the command line.
             A legal -from query has one of the following forms:

    "encoding/json".Decoder.Decode        method of package-level named type
    (*"encoding/json".Decoder).Decode     ditto, alternative syntax
    "encoding/json".Decoder.buf           field of package-level named struct type
    "encoding/json".HTMLEscape            package member (const, func, var, type)
    "encoding/json".Decoder.Decode::x     local object x within a method
    "encoding/json".HTMLEscape::x         local object x within a function
    "encoding/json"::x                    object x anywhere within a package
    json.go::x                            object x within file json.go

             Double-quotes must be escaped when writing a shell command.
             Quotes may be omitted for single-segment import paths such as "fmt".

             For methods, the parens and '*' on the receiver type are both
             optional.

             It is an error if one of the ::x queries matches multiple
             objects.

  -to        the new name.

  -force     causes the renaming to proceed even if conflicts were reported.
             The resulting program may be ill-formed, or experience a change
             in behaviour.

             WARNING: this flag may even cause the renaming tool to crash.
             (In due course this bug will be fixed by moving certain
             analyses into the type-checker.)

  -d         display diffs instead of rewriting files

  -v         enables verbose logging.

gorename automatically computes the set of packages that might be
affected.  For a local renaming, this is just the package specified by
-from or -offset, but for a potentially exported name, gorename scans
the workspace ($GOROOT and $GOPATH).

gorename rejects renamings of concrete methods that would change the
assignability relation between types and interfaces.  If the interface
change was intentional, initiate the renaming at the interface method.

gorename rejects any renaming that would create a conflict at the point
of declaration, or a reference conflict (ambiguity or shadowing), or
anything else that could cause the resulting program not to compile.


Examples:

$ gorename -offset file.go:#123 -to foo

  Rename the object whose identifier is at byte offset 123 within file file.go.

$ gorename -from '"bytes".Buffer.Len' -to Size

  Rename the "Len" method of the *bytes.Buffer type to "Size".

---- TODO ----

Correctness:
- handle dot imports correctly
- document limitations (reflection, 'implements' algorithm).
- sketch a proof of exhaustiveness.

Features:
- support running on packages specified as *.go files on the command line
- support running on programs containing errors (loader.Config.AllowErrors)
- allow users to specify a scope other than "global" (to avoid being
  stuck by neglected packages in $GOPATH that don't build).
- support renaming the package clause (no object)
- support renaming an import path (no ident or object)
  (requires filesystem + SCM updates).
- detect and reject edits to autogenerated files (cgo, protobufs)
  and optionally $GOROOT packages.
- report all conflicts, or at least all qualitatively distinct ones.
  Sometimes we stop to avoid redundancy, but
  it may give a disproportionate sense of safety in -force mode.
- support renaming all instances of a pattern, e.g.
  all receiver vars of a given type,
  all local variables of a given type,
  all PkgNames for a given package.
- emit JSON output for other editors and tools.

11 godoctor

go get -u -v github.com/godoctor/godoctor
godoctor -h
Usage: godoctor [<flag> ...] <refactoring> [<args> ...]

Each <flag> must be one of the following:
    -complete Output entire modified source files instead of displaying a diff
    -doc      Output documentation (install, user, man, or vim) and exit
    -file     Filename containing an element to refactor (default: stdin)
    -json     Accept commands in OpenRefactory JSON protocol format
    -list     List all refactorings and exit
    -pos      Position of a syntax element to refactor (default: entire file)
    -scope    Package name(s), or source file containing a program entrypoint
    -v        Verbose: list affected files
    -vv       Very verbose: list individual edits (implies -v)
    -w        Modify source files on disk (write) instead of displaying a diff


The <refactoring> argument determines the refactoring to perform:
    rename          Changes the name of an identifier
    extract         Extracts statements to a new function/method
    var             Extracts an expression, assigning it to a variable
    toggle          Toggles between a var declaration and := statement
    godoc           Adds stub GoDoc comments where they are missing

The <args> following the refactoring name vary depending on the refactoring.

To display usage information for a particular refactoring, such as rename, use:
    %% godoctor rename

For complete usage information, see the user manual: http://gorefactor.org/doc.html

12 goreturns

A gofmt/goimports-like tool for Go programmers that fills in Go return statements with zero values to match the func return types

go get -u sourcegraph.com/sqs/goreturns
1
2
3
4
5
package goreturnsdemo

import "errors"

func F() (int, error) { return errors.New("foo") }
goreturns -h
usage: goreturns [flags] [path ...]
  -b	remove bare returns
  -d	display diffs instead of rewriting files
  -e	report all errors (not just the first 10 on different lines)
  -i	run goimports on the file prior to processing (default true)
  -l	list files whose formatting differs from goreturns's
  -local string
put imports beginning with this string after 3rd-party packages (see goimports)
  -p	print non-fatal typechecking errors to stderr
  -w	write result to (source) file instead of stdout
goreturns goreturnsdemo.go
1
2
3
4
5
package goreturnsdemo

import "errors"

func F() (int, error) { return 0, errors.New("foo") }
goreturns -d goreturnsdemo.go
1
2
3
4
5
6
7
8
9
10
11
diff goreturnsdemo.go gofmt/goreturnsdemo.go
--- /tmp/gofmt948886532 2017-11-26 18:59:03.671955645 +0800
+++ /tmp/gofmt584282515 2017-11-26 18:59:03.671955645 +0800
@@ -1,6 +1,5 @@
package goreturnsdemo

-
import "errors"

-func F() (int, error) { return errors.New("foo") }
+func F() (int, error) { return 0, errors.New("foo") }

13 gotests

Generate Go tests from your source code.

go get -u -v github.com/cweill/gotests/...
gotests -h
Usage of gotests:
  -all
      generate tests for all functions and methods
  -excl string
      regexp. generate tests for functions and methods that don't match. Takes precedence over -only, -exported, and -all
  -exported
      generate tests for exported functions and methods. Takes precedence over -only and -all
  -i	print test inputs in error messages
  -nosubtests
      disable generating tests using the Go 1.7 subtests feature
  -only string
      regexp. generate tests for functions and methods that match only. Takes precedence over -all
  -w	write output to (test) files instead of stdout
gotests -all ./

14 guru

guru: a tool for answering questions about Go source code.

15 godepgraph

godepgraph is a program for generating a dependency graph of Go packages.

go get github.com/kisielk/godepgraph
godepgraph -h
Usage of godepgraph:
  -d	show dependencies of packages in the Go standard library
  -horizontal
      lay out the dependency graph horizontally instead of vertically
  -i string
      a comma-separated list of packages to ignore
  -l int
      max level of go dependency graph (default 256)
  -o string
      a comma-separated list of prefixes to include
  -p string
      a comma-separated list of prefixes to ignore
  -s	ignore packages in the Go standard library
  -t	include test packages
  -tags string
      a comma-separated list of build tags to consider satisified during the build
godepgraph github.com/kisielk/godepgraph
digraph godep {
_0 [label="flag" style="filled" color="palegreen"];
_1 [label="fmt" style="filled" color="palegreen"];
_2 [label="github.com/kisielk/godepgraph" style="filled" color="paleturquoise"];
_2 -> _0;
_2 -> _1;
_2 -> _3;
_2 -> _4;
_2 -> _5;
_2 -> _6;
_2 -> _7;
_3 [label="go/build" style="filled" color="palegreen"];
_4 [label="log" style="filled" color="palegreen"];
_5 [label="os" style="filled" color="palegreen"];
_6 [label="sort" style="filled" color="palegreen"];
_7 [label="strings" style="filled" color="palegreen"];
}
godepgraph github.com/kisielk/godepgraph | dot -Tpng -o godepgraph.png

<img src="/images/go-tool/godepgraph.png” />

16 go-callvis

go get -u github.com/TrueFurby/go-callvis
go-callvis -h
Usage of go-callvis:
  -debug
      Enable verbose log.
  -focus string
      Focus package with name or import path. (default "main")
  -group string
      Grouping functions by [pkg, type] (separate multiple by comma).
  -ignore string
      Ignore package paths with prefix (separate multiple by comma).
  -limit string
      Limit package paths to prefix. (separate multiple by comma)
  -minlen uint
      Minimum edge length (for wider output). (default 2)
  -nodesep float
      Minimum space between two adjacent nodes in the same rank (for taller output). (default 0.35)
  -nostd
      Omit calls to/from std packages.
  -tests
      Include test code.
  -version
      Show version and exit.
go-callvis github.com/TrueFurby/go-callvis | dot -Tpng -o go-callvis.png

<img src="/images/go-tool/go-callvis.png” />

17 depth

go get -u github.com/KyleBanks/depth/cmd/depth
depth -h
Usage of depth:
  -explain string
      If set, show which packages import the specified target
  -internal
      If set, resolves dependencies of internal (stdlib) packages.
  -json
      If set, outputs the depencies in JSON format.
  -max int
      Sets the maximum depth of dependencies to resolve.
  -test
      If set, resolves dependencies used for testing.
depth github.com/KyleBanks/depth/cmd/depth
github.com/KyleBanks/depth/cmd/depth
  ├ encoding/json
  ├ flag
  ├ fmt
  ├ io
  ├ os
  ├ strings
  └ github.com/KyleBanks/depth
    ├ bytes
    ├ errors
    ├ go/build
    ├ os
    ├ path
    ├ sort
    └ strings
12 dependencies (11 internal, 1 external, 0 testing).
depth -internal strings
strings
  ├ errors
  ├ internal/cpu
  ├ io
    ├ errors
    └ sync
      ├ internal/race
        └ unsafe
      ├ runtime
        ├ runtime/internal/atomic
          └ unsafe
        ├ runtime/internal/sys
        └ unsafe
      ├ sync/atomic
        └ unsafe
      └ unsafe
  ├ unicode
  └ unicode/utf8
12 dependencies (12 internal, 0 external, 0 testing).
strings
  ├ errors
  ├ internal/cpu
  ├ io
  ├ unicode
  └ unicode/utf8
5 dependencies (5 internal, 0 external, 0 testing).

18 interface

go get -u -v mvdan.cc/interfacer
interfacer -h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package single

func Empty() {
}

type Closer interface {
Close()
}

type ReadCloser interface {
Closer
Read()
}

func Basic(c Closer) {
c.Close()
}

func BasicWrong(rc ReadCloser) { // WARN rc can be Closer
rc.Close()
}

func OtherWrong(s St) { // WARN s can be Closer
s.Close()
}
interfacer simple.go

simple.go:24:19: undeclared name: St

19 safesql

go get -u github.com/stripe/safesql
safesql
Usage: safesql [-q] [-v] package1 [package2 ...]
  -q	Only print on failure
  -v	Verbose mode

20 aligncheck

go get github.com/opennota/check/cmd/aligncheck
aligncheck  github.com/astaxie/beego
github.com/astaxie/beego: config.go:33:6: struct Config could have size 520 (currently 552)
github.com/astaxie/beego: config.go:51:6: struct Listen could have size 120 (currently 152)
github.com/astaxie/beego: config.go:71:6: struct WebConfig could have size 264 (currently 288)
github.com/astaxie/beego: config.go:89:6: struct SessionConfig could have size 104 (currently 128)
github.com/astaxie/beego: controller.go:67:6: struct Controller could have size 224 (currently 232)
github.com/astaxie/beego: router.go:124:6: struct ControllerRegister could have size 168 (currently 176)

21 structcheck

go get github.com/opennota/check/cmd/structcheck
structcheck -h
Usage of structcheck:
  -a	Count assignments only
  -e	Report exported fields
  -t	Load test files too
  -tags string
      Build tags
structcheck fmt
fmt: ~/.gvm/gos/go1.9/src/fmt/scan.go:169:2: fmt.ssave.nlIsEnd
fmt: ~/.gvm/gos/go1.9/src/fmt/scan.go:170:2: fmt.ssave.nlIsSpace
fmt: ~/.gvm/gos/go1.9/src/fmt/scan.go:171:2: fmt.ssave.argLimit
fmt: ~/.gvm/gos/go1.9/src/fmt/scan.go:172:2: fmt.ssave.limit
fmt: ~/.gvm/gos/go1.9/src/fmt/scan.go:173:2: fmt.ssave.maxWid
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:30:2: fmt.fmtFlags.zero
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:35:2: fmt.fmtFlags.plusV
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:36:2: fmt.fmtFlags.sharpV
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:25:2: fmt.fmtFlags.precPresent
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:27:2: fmt.fmtFlags.plus
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:29:2: fmt.fmtFlags.space
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:24:2: fmt.fmtFlags.widPresent
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:26:2: fmt.fmtFlags.minus
fmt: ~/.gvm/gos/go1.9/src/fmt/format.go:28:2: fmt.fmtFlags.sharp

22 varcheck

go get github.com/opennota/check/cmd/varcheck
varcheck -h
Usage of varcheck:
  -e	Report exported variables and constants
varcheck image/jpeg
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/reader.go:74:2: adobeTransformYCbCr
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/reader.go:75:2: adobeTransformYCbCrK
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:54:2: quantIndexLuminance
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:55:2: quantIndexChrominance
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:91:2: huffIndexLuminanceDC
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:92:2: huffIndexLuminanceAC
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:93:2: huffIndexChrominanceDC
image/jpeg: ~/.gvm/gos/go1.9/src/image/jpeg/writer.go:94:2: huffIndexChrominanceAC

23 eg

go get golang.org/x/tools/cmd/eg
1
2
3
4
5
6
7
package main

import "time"

func ExtendWith50000ns(t time.Time) time.Time {
return t.Add(time.Duration(50000))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
package template

import (
"time"
)

func before(t time.Time, d time.Duration) time.Time {
// if already time.Duration, do not cast.
return t.Add(time.Duration(d))
}

func after(t time.Time, d time.Duration) time.Time {
return t.Add(d * time.Nanosecond)
}
eg -t T.template .
1
2
3
4
5
6
7
package main

import "time"

func ExtendWith50000ns(t time.Time) time.Time {
return t.Add(50000 * time.Nanosecond)
}
Last Updated 2017-12-13 Wed 18:24.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

gomodifytags

发表于 2017-11-07 | 分类于 技术积累 |

1 StructTag

1
2
3
4
5
6
7
8
9
10
11
package main

import (
"fmt"
"reflect"
)

func main() {
tag := reflect.StructTag(`species:"gopher" color:"blue"`)
fmt.Println(tag.Get("color"), tag.Get("species"))
}
blue gopher
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package main

import (
"fmt"

"github.com/fatih/structtag"
)

func main() {
tag := `json:"foo,omitempty,string" xml:"foo"`

// parse the tag
tags, err := structtag.Parse(string(tag))
if err != nil {
panic(err)
}

// iterate over all tags
for _, t := range tags.Tags() {
fmt.Printf("tag: %+v\n", t)
}

// get a single tag
jsonTag, err := tags.Get("json")
if err != nil {
panic(err)
}

// change existing tag
jsonTag.Name = "foo_bar"
jsonTag.Options = nil
tags.Set(jsonTag)

// add new tag
tags.Set(&structtag.Tag{
Key: "hcl",
Name: "foo",
Options: []string{"squash"},
})

// print the tags
fmt.Println(tags) // Output: json:"foo_bar" xml:"foo" hcl:"foo,squash"
}
tag: json:"foo,omitempty,string"
tag: xml:"foo"
json:"foo_bar" xml:"foo" hcl:"foo,squash"

2 AST(抽象语法树)

遍历语法树,展示结构体字段列表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import (
"fmt"
"go/ast"
"go/parser"
"go/token"
)

func main() {
src := `package main
type Example struct {
Foo string` + " `json:\"foo\"` }"


fset := token.NewFileSet()
file, err := parser.ParseFile(fset, "demo", src, parser.ParseComments)
if err != nil {
panic(err)
}

ast.Inspect(file, func(x ast.Node) bool {
s, ok := x.(*ast.StructType)
if !ok {
return true
}

for _, field := range s.Fields.List {
fmt.Printf("Field: %s\n", field.Names[0].Name)
fmt.Printf("Tag: %s\n", field.Tag.Value)
}
return false
})
}
Field: Foo
Tag:   `json:"foo"`

3 gomodifytags

1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string
Port int
EnableLogs bool
BaseDomain string
Credentials struct {
Username string
Password string
}
}

3.1 Struct based modification

gomodifytags -file demo.go -struct Server -add-tags json -w
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name"`
Port int `json:"port"`
EnableLogs bool `json:"enable_logs"`
BaseDomain string `json:"base_domain"`
Credentials struct {
Username string `json:"username"`
Password string `json:"password"`
} `json:"credentials"`
}

支持三种 transform , 如下所示:

  • snakecase: “BaseDomain” -> “base_domain”
  • camelcase: “BaseDomain” -> “baseDomain”
  • lispcase: “BaseDomain” -> “base-domain”
gomodifytags -file demo.go -struct Server -add-tags xml -transform camelcase
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name" xml:"name"`
Port int `json:"port" xml:"port"`
EnableLogs bool `json:"enable_logs" xml:"enableLogs"`
BaseDomain string `json:"base_domain" xml:"baseDomain"`
Credentials struct {
Username string `json:"username" xml:"username"`
Password string `json:"password" xml:"password"`
} `json:"credentials" xml:"credentials"`
}
gomodifytags -file demo.go -struct Server -add-tags xml -transform camelcase
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name" xml:"name"`
Port int `json:"port" xml:"port"`
EnableLogs bool `json:"enable_logs" xml:"enableLogs"`
BaseDomain string `json:"base_domain" xml:"baseDomain"`
Credentials struct {
Username string `json:"username" xml:"username"`
Password string `json:"password" xml:"password"`
} `json:"credentials" xml:"credentials"`
}
gomodifytags -file demo.go -struct Server -add-tags validate:gt=1,scope:read-only
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name" validate:"gt=1" scope:"read-only"`
Port int `json:"port" validate:"gt=1" scope:"read-only"`
EnableLogs bool `json:"enable_logs" validate:"gt=1" scope:"read-only"`
BaseDomain string `json:"base_domain" validate:"gt=1" scope:"read-only"`
Credentials struct {
Username string `json:"username" validate:"gt=1" scope:"read-only"`
Password string `json:"password" validate:"gt=1" scope:"read-only"`
} `json:"credentials" validate:"gt=1" scope:"read-only"`
}
gomodifytags -file demo.go -struct Server -add-tags json --add-options json=omitempty -w
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name,omitempty"`
Port int `json:"port,omitempty"`
EnableLogs bool `json:"enable_logs,omitempty"`
BaseDomain string `json:"base_domain,omitempty"`
Credentials struct {
Username string `json:"username,omitempty"`
Password string `json:"password,omitempty"`
} `json:"credentials,omitempty"`
}
gomodifytags -file demo.go -struct Server -remove-tags json
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string
Port int
EnableLogs bool
BaseDomain string
Credentials struct {
Username string
Password string
}
}
gomodifytags -file demo.go -struct Server -clear-tags
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string
Port int
EnableLogs bool
BaseDomain string
Credentials struct {
Username string
Password string
}
}
gomodifytags -file demo.go -struct Server -remove-options json=omitempty
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name"`
Port int `json:"port"`
EnableLogs bool `json:"enable_logs"`
BaseDomain string `json:"base_domain"`
Credentials struct {
Username string `json:"username"`
Password string `json:"password"`
} `json:"credentials"`
}
gomodifytags -file demo.go -struct Server -clear-options
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name"`
Port int `json:"port"`
EnableLogs bool `json:"enable_logs"`
BaseDomain string `json:"base_domain"`
Credentials struct {
Username string `json:"username"`
Password string `json:"password"`
} `json:"credentials"`
}

3.2 Line based modification

gomodifytags -file demo.go -line 8,11 -clear-tags json
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name,omitempty"`
Port int `json:"port,omitempty"`
EnableLogs bool `json:"enable_logs,omitempty"`
BaseDomain string `json:"base_domain,omitempty"`
Credentials struct {
Username string
Password string
}
}
gomodifytags -file demo.go -line 6,7 -remove-tags json
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name,omitempty"`
Port int `json:"port,omitempty"`
EnableLogs bool
BaseDomain string
Credentials struct {
Username string `json:"username,omitempty"`
Password string `json:"password,omitempty"`
} `json:"credentials,omitempty"`
}
gomodifytags -file demo.go -line 2,7 -add-tags bson
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name,omitempty" bson:"name"`
Port int `json:"port,omitempty" bson:"port"`
EnableLogs bool `json:"enable_logs,omitempty" bson:"enable_logs"`
BaseDomain string `json:"base_domain,omitempty" bson:"base_domain"`
Credentials struct {
Username string `json:"username,omitempty"`
Password string `json:"password,omitempty"`
} `json:"credentials,omitempty"`
}
gomodifytags -file demo.go -offset 100 -add-tags bson
1
2
3
4
5
6
7
8
9
10
11
12
package main

type Server struct {
Name string `json:"name,omitempty" bson:"name"`
Port int `json:"port,omitempty" bson:"port"`
EnableLogs bool `json:"enable_logs,omitempty" bson:"enable_logs"`
BaseDomain string `json:"base_domain,omitempty" bson:"base_domain"`
Credentials struct {
Username string `json:"username,omitempty" bson:"username"`
Password string `json:"password,omitempty" bson:"password"`
} `json:"credentials,omitempty" bson:"credentials"`
}

3.3 Shortcoming

1
2
3
4
5
6
7
package main

type User struct {
First_name string
Last_name string
addr string
}
gomodifytags -file user.go -struct User -add-tags json

期望得到的结果是: first_name ,但是却得到了 first___name, 同时 addr 字段不导出也生成了 tag, 如下所示:

1
2
3
4
5
6
7
package main

type User struct {
First_name string `json:"first___name"`
Last_name string `json:"last___name"`
addr string `json:"addr"`
}
Last Updated 2017-11-09 Thu 15:00.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

org-babel有趣的事

发表于 2017-10-31 | 分类于 org-mode |

1 数据格式化(:wrap)

1.1 json格式化

#+BEGIN_SRC sh :results code :wrap SRC js :exports both
  curl http://httpbin.org/get
#+END_SRC

#+RESULTS:
#+BEGIN_SRC js
{
  "args": {},
  "headers": {
    "Accept": "*/*",
    "Connection": "close",
    "Host": "httpbin.org",
    "User-Agent": "curl/7.47.0"
  },
  "origin": "180.167.20.58",
  "url": "http://httpbin.org/get"
}
#+END_SRC

1.2 其他格式化

#+BEGIN_SRC sh :wrap QUOTE :results raw :exports both
  date
#+END_SRC

#+RESULTS:
#+BEGIN_QUOTE
Fri Nov  3 23:05:34 CST 2017
#+END_QUOTE

2 变量设置在Header中

** 变量设置在Header中
   :PROPERTIES:
   :ID:       d7b197d7-f925-47b7-bcc0-37e182761619
   :header-args:shell: :var host="google.com" :results pp :session brantou :exports both
   :END:
   #+BEGIN_SRC shell
     ping $host -c 2
   #+END_SRC

   #+RESULTS:
   :
   : $ PING google.com (192.168.83.230) 56(84) bytes of data.
   : 64 bytes from 192.168.83.230: icmp_seq=1 ttl=128 time=9.60 ms
   : 64 bytes from 192.168.83.230: icmp_seq=2 ttl=128 time=25.4 ms
   :
   : --- google.com ping statistics ---
   : packet loss, time 1001ms
   : rtt min/avg/max/mdev = 9.609/17.508/25.408/7.900 ms

   覆盖变量 *host* 和 *session* 置为空!
   #+BEGIN_SRC shell :var host="baidu.com" :session none
     ping $host -c 2
   #+END_SRC

   #+RESULTS:
   : PING baidu.com (111.13.101.208) 56(84) bytes of data.
   : 64 bytes from 111.13.101.208: icmp_seq=1 ttl=128 time=35.5 ms
   : 64 bytes from 111.13.101.208: icmp_seq=2 ttl=128 time=49.2 ms
   :
   : --- baidu.com ping statistics ---
   : 2 packets transmitted, 2 received, 0% packet loss, time 1002ms
   : rtt min/avg/max/mdev = 35.517/42.361/49.206/6.847 ms

3 结果的预处理(:post)

#+NAME: img_wrap
#+BEGIN_SRC python :var img_path="" :results output
  img_path=img_path.replace('[[file:..', '').replace(']]', '')
  print('<img src="'+img_path+'" />')
#+END_SRC

#+HEADER: :file ../images/devOps/just-try-post.png :exports both
#+BEGIN_SRC plantuml :mkdirp yes :post img_wrap(img_path=*this*) :wrap EXPORT html
  @startuml
  cli -> serv:  auth req
  serv --> cli: auth res
  @enduml
#+END_SRC

#+RESULTS:
#+BEGIN_EXPORT html
<img src="/images/devOps/just-try-post.png" />
#+END_EXPORT

4 noweb的引用(:noweb-ref)

#+HEADER: :tangle ../src/devOps/noweb_ref.sh :mkdirp yes
#+BEGIN_SRC shell :noweb yes :shebang #!/bin/sh
  <<fullest-disk>>
#+END_SRC

** the mount point of the fullest disk
   :PROPERTIES:
   :header-args:shell: :noweb-ref fullest-disk
   :END:

*** query all mounted disks
    #+BEGIN_SRC shell
        df \
    #+END_SRC
*** strip the header row
    #+BEGIN_SRC shell
        |sed '1d' \
    #+END_SRC
*** sort by the percent full
    #+BEGIN_SRC shell
        |awk '{print $5 " " $6}' | sort -n | tail -1 \
    #+END_SRC
*** extract the mount point
    #+BEGIN_SRC shell
      |awk '{print $2}'
    #+END_SRC

tangle出的代码如下:

#!/bin/sh
df \
|sed '1d' \
|awk '{print $5 " " $6}' | sort -n | tail -1 \
|awk '{print $2}'

5 预处理/后置操作(:prologue/:epilogue)

在做相关操作时,可能需要预先初始化,同时又不想这些初始化过程出现在代码流程中,
这个时候你可使用 *:prologue* 来关联相关语句来达到预处理的效果。
#+NAME: prologue-example
#+BEGIN_SRC shell :prologue "echo yep; exit 0" :exports both
  echo "nope"
#+END_SRC

#+RESULTS: prologue-example
: yep

*:epilogue* 正好和 *:prologue* 完成的功能相反,用于后置处理,完成清理工作。
#+BEGIN_SRC shell :epilogue "exit 0; echo yep" :exports both
  echo "nope"
#+END_SRC

#+RESULTS:
: nope

6 批量执行

可在命令行中调用代码块实现的函数,如下面所示:

#!/bin/sh
# -*- mode: shell-script -*-
#
# tangle files with org-mode
#

DIR='pwd'
FILES=""
# wrap each argument in the code required to call tangle on it
for i in $@; do
    FILES="$FILES \"$i\""
done

emacs -Q --batch \
      --eval "(progn
(require 'org)(require 'ob)(require 'ob-tangle)
(mapc (lambda (file)
       (find-file (expand-file-name file \"$DIR\"))
       (org-babel-tangle)
       (kill-buffer)) '($FILES)))" 2>&1 | grep tangled

7 连接mysql

#+BEGIN_SRC sql
  show tables;
#+END_SRC

#+RESULTS:
| Tables_in_mysql           |
|---------------------------|
| columns_priv              |
| db                        |
| engine_cost               |
| event                     |
| func                      |
| general_log               |
| gtid_executed             |
| help_category             |
| help_keyword              |
| help_relation             |
| help_topic                |
| innodb_index_stats        |
| innodb_table_stats        |
| ndb_binlog_index          |
| plugin                    |
| proc                      |
| procs_priv                |
| proxies_priv              |
| server_cost               |
| servers                   |
| slave_master_info         |
| slave_relay_log_info      |
| slave_worker_info         |
| slow_log                  |
| tables_priv               |
| time_zone                 |
| time_zone_leap_second     |
| time_zone_name            |
| time_zone_transition      |
| time_zone_transition_type |
| user                      |

#+BEGIN_SRC sql
  SELECT host, user FROM user WHERE 1;
#+END_SRC

#+RESULTS:
| host      | user             |
|-----------+------------------|
| %         | brantou          |
| localhost | debian-sys-maint |
| localhost | mysql.session    |
| localhost | mysql.sys        |
| localhost | root             |
Last Updated 2017-12-05 Tue 23:20.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

写Python的新方式

发表于 2017-08-30 | 分类于 org-mode |

Org mode is for keeping notes, maintaining TODO lists, planning projects, and authoring documents with a fast and effective plain-text system.

Org-mode 类似于 Markdown , 但是远胜于 Markdown 。 曾有小伙伴说过, Org-mode 是 Markdown 的封神模式, 个人觉得这话一点不夸张, 相比较而言, Markdown 只是一套简洁的文档格式, 而 Org-mode 除了涵盖作为文档格式的简洁之外, 还可用于记笔记,维护 TODO 列表, 工程管理,以及可用于元编程。 对于元编程的支持请阅读我之前的译文, Babel: org-mode的元编程。

所谓的元编程,即是 Org-mode 搭建了一个多语言可以交互执行的环境, 在这个环境中,可选用各语言的特性,来分解执行一个大型任务。

<img src="/images/babel-fish.jpg” />

The Babel Fish is small, yellow, and simultaneously translates from
one spoken language to another.
– The Hitchhiker’s Guide to the Galaxy, Douglas Adams

Org-mode 对于比较流行的语言都有很好的支持, 而且对于新语言,也可以很容易添加支持,本人就给两种语言添加过支持。 本文章主要讲述 Org-mode 对于 Python 源代码块的支持, Python 相当的流行, 所以在 Org-mode 中被很完美的支持。 Org-mode 中的 Python 源代码块可用于定义函数、过滤器和数据分析、创建图表以及生成可重现的研究论文。

1 配置

这里假设 Python 的开发环境已配置完毕,若是还没配置,请自行google。

Org-mode 已内置在新的 Emacs 中,但是默认情况下, 只有 emacs-lisp 可被执行。 要启用或禁用其他语言, 可通过 Emacs 自定义交互界面来配置 org-babel-load-languages 变量, 或者将代码添加到 init 文件中, 启用python的代码如下所示:

1
2
3
(org-babel-do-load-languages
'org-babel-load-languages
'((python . t)))

2 Org-mode对于Python源码块的支持

2.1 头参数

2.1.1 语言特定的头参数

  • :results {output, value}: 默认 value 模式, 即 functional mode, 像函数一样执行,然后返回计算结果。
  • :preamble: 前导代码,插入到最前面(不常用)。 默认为空。
  • :return: 要返回的值(仅用于result-type为 value 时,不在 session 模式下;不常用)。 默认值为空,在 Non-session 模式下,使用 return() 返回值。
  • :python: 执行Python代码的程序名称。

2.1.2 公共头参数

  • :seesion [name]: 默认非 session 模式。
  • :var data=data-table: Org-mode 的 table 可被当做列表传递给Python代码块。
  • :exports {code, results, both, none}: 完全支持 babel 的导出选项。

2.2 Sessions

python完全支持 session 模式,包括命名 session 。 在 session 模式下,代码块都运行在同一个长时间运行的 python 的交互式解释器 session 中,就像你在交互式 python 键入的一样。 可以拥有多个 session ,而且它们是完全相互独立。

session 可用于定义函数,设置变量和在源块之间共享代码。

python中的 session 模式与 non-session 模式略有不同,因为在 session 模式下, 你正在与单个“交互式” python session 交互。 在 python 的交互模式中,空行是特殊的:它们表示缩进代码块的结束, 所以会写出一些稍微不同的 python 代码。

另外,在 non-session 模式下,python代码块将被包装在一个函数中, 所以要返回一个值( :result value mode ),你必须使用一个return语句。 在 session 模式下, python 代码由解释器直接评估,而不是在一个函数的上下文中, 最后一个语句的值将被自动返回,因此不能使用 return 语句。

2.2.1 Session mode

# blank lines not OK in indented blocks, and don't use return()
# Source block is passed directly to interactive python;
# value is value of _ at end.
#+begin_src python :session
def foo(x):
  if x>0:
    return x+1
  else:
    return x-1

foo(1)
#+end_src

#+RESULTS:
: 2

2.2.2 Non-session mode

# blank lines OK in indented blocks, and use return()
# Entire source block will get indented and used as the body of main()
#+begin_src python
def foo(x):
  if x>0:
    return x+1

  else:
    return x-1

return foo(5)
#+end_src

#+RESULTS:
: 6

最后,如果你使用 matplotlib 的图形功能,同时使用 seesion 模式, 必须显式设置后端, 例如 PDF , PNG 或其他文件导出后端。 见下面示例:

#+begin_src python :session :results file
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
fig=plt.figure(figsize=(3,2))
plt.plot([1,3,2])
fig.tight_layout()
plt.savefig('images/myfig.pdf')
'images/myfig.pdf' # return this to org-mode
#+end_src

#+RESULTS:
[[file:images/myfig.pdf]]

2.3 返回类型

  • value:=value= 结果是代码块中求值的最后一个表达式的值。 session 模式下使用的python解释器特殊变量“_” 来引用最后一个表达式的值。
  • output:=output= 结果来自 python 代码打印到 stdout 上任意信息。

3 使用示例

  • Hello World!
    #+begin_src python :results output
      print "Hello, world!"
    #+end_src
    
    #+RESULTS:
    : Hello, world!
    
  • 参数
    #+NAME: square
    #+BEGIN_SRC python :var num=5
      def square(x):
          return x*x
    
      return square(num)
    #+END_SRC
    
    #+RESULTS: square
    : 25
    
    #+CALL: square(num=10)
    
    #+RESULTS:
    : 100
    
  • 文学编程
    #+NAME: square
    #+BEGIN_SRC python
      def square(x):
          return x*x
    #+END_SRC
    
    #+NAME: calc-square
    #+BEGIN_SRC python :var num=5 :noweb strip-export :results output
      <<square>>
      print(square(num))
    #+END_SRC
    
    #+RESULTS: calc-square
    : 25
    
    #+CALL: calc-square(num=7)
    
    #+RESULTS:
    : 49
    
  • 内联调用(Inline calling):
    2 加 2 等于 src_python{return(2+2)}
    

    当导出 HTML 或者 LaTeX/PDF 时,如下所示:

    2 加 2 等于 4
    
  • 使用Org-mode的table作为参数
    #+tblname: data_table
    | a | 1 |
    | b | 2 |
    | c | 3 |
    #+begin_src python :var val=1 :var data=data_table
    # Return row specified by val.
    # In non-session mode, use return to return results.
    return(data[val])
    #+end_src
    
    #+RESULTS:
    | b | 2 |
    
  • 绘图
    #+begin_src python :results file
      import matplotlib, numpy
      matplotlib.use('Agg')
      import matplotlib.pyplot as plt
      fig=plt.figure(figsize=(4,2))
      x=numpy.linspace(-15,15)
      plt.plot(numpy.sin(x)/x)
      fig.tight_layout()
      plt.savefig('../images/python-matplot-fig.png')
      return '../images/python-matplot-fig.png'
    #+end_src
    
    #+RESULTS:
    [[file:../images/python-matplot-fig.png]]
    

    <img src="/images/python-matplot-fig.png” />

  • 词云
    #+BEGIN_SRC python :preamble "# -*- coding: utf-8 -*-" :results value file
      import jieba.analyse
      from wordcloud import WordCloud, ImageColorGenerator
      import numpy as np
      from PIL import Image
      import random
    
      font_path = '../resource/tyzkaishu.ttf'
      width = 640
      height = 480
    
      text = open('../resource/xiyouji.txt').read()
      words = jieba.analyse.extract_tags(text, topK=200, withWeight=True)
    
      word_freqs = {}
      for word in words:
          word_freqs[word[0]] = word[1]
    
      mask = np.array(Image.open('../resource/stormtrooper_mask.png'))
      wordcloud = WordCloud(
          font_path=font_path, width=width, height=height,
          mask=mask).generate_from_frequencies(word_freqs)
      wordcloud.to_file('../images/xiyouji-mask.png')
      return '../images/xiyouji-mask.png'
    #+END_SRC
    
    #+RESULTS:
    [[file:../images/xiyouji-mask.png]]
    

    <img src="/images/xiyouji-mask.png” />

4 前方预警

当把 utf-8 的字符串传给 Python , 需要格外小心。

4.1 传递utf-8字符串到Python

#+NAME: unicode_str
#+BEGIN_EXAMPLE
  “this string is not ascii!”
#+END_EXAMPLE
#+NAME: error-in-passing-var
#+BEGIN_SRC python :var data=unicode_str
  return data
#+END_SRC
#+RESULTS: error-in-passing-var

上面代码不会生成任何输出, 并在 *Org-Babel Error Output* 的缓冲区中打印以下消息:

File “<stdin>”, line 3 SyntaxError: Non-ASCII character ‘\xe2’ in file <stdin> on line 3, but no encoding declared; see http://python.org/dev/peps/pep-0263/ for details

4.2 传递utf-8字符串到Python的变通方法

一个变通方法是使用 :preamble ,如下所示:

#+NAME: ok-in-passing-var
#+BEGIN_SRC python :preamble "# -*- coding: utf-8 -*-" :var data=unicode_str
  return data
#+END_SRC
#+RESULTS: ok-in-passing-var
: “this string is not ascii!”

5 参考文档

  • Python Source Code Blocks in Org Mode
  • Babel: org-mode的元编程
  • 在Org-mode中执行Go代码
  • Working with source code
  • Babel: active code in Org-mode
Last Updated 2018-04-23 Mon 15:36.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

玩转词云

发表于 2017-08-25 | 分类于 技术积累 |

1 jieba中文分词

1.1 分词

1
2
3
4
5
6
7
8
9
10
import jieba

seg_list = jieba.cut(srcWd, cut_all=True)
print(u'Full mode:' + u'/ '.join(seg_list))

seg_list = jieba.cut(srcWd, cut_all=False)
print(u'Default mode:' + u'/ '.join(seg_list))

seg_list = jieba.cut_for_search(srcWd)
print(u', '.join(seg_list))
Full mode:做/ 最好/ 的/ Python/ 中文/ 分词/ 词组/ 组件
Default mode:做/ 最好/ 的/ Python/ 中文/ 分词/ 组件
做, 最好, 的, Python, 中文, 分词, 组件
Full mode:我/ 目前/ 在/ 学习/ Golang/ 和/ Python/
Default mode:我/ 目前/ 在/ 学习/ Golang/ 和/ Python/ 。
我, 目前, 在, 学习, Golang, 和, Python, 。

1.2 自定义词典

招聘信息收集了很多,但是关键字提取却不是很理想,我查看了jiaba的词典里,基本没有对英文专有名词的支持, 这可苦煞了我,但是jieba支持自定义词典,我来生成英文的专有名词的词典好了。一行一行的加,难为我这个懒人了, 但总有好心人,已经整理好了,试想这个名词是不是招聘网站已经整理好了,而且分门别类的,只需要把它们取回来就好了。

1
2
3
4
5
6
7
8
9
10
11
12
def get_html(url):
request = urllib2.Request(url)
request.add_header(
'User-Agent',
'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.90 Safari/537.36'
)
html = urllib2.urlopen(request)
return html.read()

def get_soup(url):
soup = BeautifulSoup(get_html(url), 'lxml')
return soup
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def fetch_lagou():
words = []
url = 'https://www.lagou.com/'
soup = get_soup(url)
category_list = soup.find_all('div', attrs={'class': 'menu_sub dn'})
for category in category_list:
dls = category.find_all('dl')
for dl in dls:
names = dl.dd.find_all('a')
for name in names:
words.append(name.text)
return words


def fetch_zhipin():
words = []
url = 'http://www.zhipin.com/'
soup = get_soup(url)
job_menu = soup.find('div', attrs={'class': 'job-menu'})
dls = job_menu.find_all('dl')
for dl in dls:
divs = dl.find_all('div', attrs={'class': 'text'})
for div in divs:
names = div.find_all('a')
for name in names:
words.append(name.text)
return words

看来我思维受限了,招聘网站整理的信息都是高频信息,但是广度肯定是不够的,那怎么办呢。 这个时候 stackoverflow 闪现在我的脑海中,没有那个网站里有关技术的广度,能和它匹敌了。

1
2
3
4
5
6
7
8
9
10
11
12
def fetch_stackoverflow():
words = []
for pageNo in range(1, 20):
url = 'https://stackoverflow.com/tags?page=%d&tab=popular' % (pageNo)
soup = get_soup(url)
tags_list = soup.find('div', attrs={'id': 'tags_list'})
trs = tags_list.table.find_all('tr')
for tr in trs:
tds = tr.find_all('td')
for td in tds:
words.append(td.a.text)
return words

1.3 调整词典

1
2
3
4
5
6
7
8
import jieba
import jieba.analyse

print(', '.join(
jieba.analyse.extract_tags(srcWd, allowPOS=('n', 'nz', 'eng', 'vn'))))
jieba.load_userdict('../resource/userdict.txt')
print(', '.join(
jieba.analyse.extract_tags(srcWd, allowPOS=('n', 'nz', 'eng', 'vn'))))
理解能力, 经验, 数据挖掘, 敏锐度, 平台, odps, hadoop, 数据仓库, hive, 建模, 业务, 海量, 能力, 数据, 协作, 优先, 团队, 模型, 计算机, 学科
理解能力, 经验, 数据挖掘, 敏锐度, 平台, odps, hadoop, 数据仓库, hive, 建模, 业务, 海量, 能力, 数据, 协作, 优先, 团队, 模型, 计算机, 学科

1.4 关键词提取

1
2
3
4
5
6
7
8
9
10
11
import jieba.analyse

print(', '.join(jieba.analyse.extract_tags(srcWd, allowPOS=())))
print(', '.join(
jieba.analyse.extract_tags(srcWd, allowPOS=('n', 'nt', 'nz', 'eng', 'vn'
))))
wordlst = jieba.analyse.extract_tags(
srcWd, withWeight=True, allowPOS=('n', 'nt', 'nz', 'eng', 'vn'))

for word in wordlst:
print(word[0] + ": " + str(word[1]))
1
2
3
4
5
import jieba.analyse

print(', '.join(jieba.analyse.textrank(srcWd)))
print(', '.join(
jieba.analyse.textrank(srcWd, allowPOS=('n', 'nz', 'eng', 'vn'))))

1.5 词性标注

1
2
3
4
5
6
7
import jieba
import jieba.posseg as pseg

jieba.load_userdict('../resource/userdict.txt')
words = pseg.cut(srcWd)
for word, flag in words:
print('%s %s' % (word, flag))

2 wordcloud词云

2.1 简单词云–美国宪法的词云

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
Minimal Example
===============
Generating a square wordcloud from the US constitution using default arguments.
"""


from wordcloud import WordCloud

# Read the whole text.
text = open('../resource/constitution.txt').read()

# Generate a word cloud image
wordcloud = WordCloud(width=640, height=480).generate(text)
wordcloud.to_file('../images/constitution-n.png')

wordcloud = WordCloud(width=640, height=480, max_font_size=80).generate(text)
wordcloud.to_file('../images/constitution-s.png')

<img src="/images/constitution-n.png” />

<img src="/images/constitution-s.png” />

2.2 Colored by Group

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from wordcloud import (WordCloud, get_single_color_func)
import matplotlib.pyplot as plt


class SimpleGroupedColorFunc(object):
"""Create a color function object which assigns EXACT colors
to certain words based on the color to words mapping

Parameters
----------
color_to_words : dict(str -> list(str))
A dictionary that maps a color to the list of words.

default_color : str
Color that will be assigned to a word that's not a member
of any value from color_to_words.
"""


def __init__(self, color_to_words, default_color):
self.word_to_color = {
word: color
for (color, words) in color_to_words.items() for word in words
}

self.default_color = default_color

def __call__(self, word, **kwargs):
return self.word_to_color.get(word, self.default_color)


class GroupedColorFunc(object):
"""Create a color function object which assigns DIFFERENT SHADES of
specified colors to certain words based on the color to words mapping.

Uses wordcloud.get_single_color_func

Parameters
----------
color_to_words : dict(str -> list(str))
A dictionary that maps a color to the list of words.

default_color : str
Color that will be assigned to a word that's not a member
of any value from color_to_words.
"""


def __init__(self, color_to_words, default_color):
self.color_func_to_words = [(get_single_color_func(color), set(words))
for (color,
words) in color_to_words.items()]

self.default_color_func = get_single_color_func(default_color)

def get_color_func(self, word):
"""Returns a single_color_func associated with the word"""
try:
color_func = next(
color_func for (color_func, words) in self.color_func_to_words
if word in words)
except StopIteration:
color_func = self.default_color_func

return color_func

def __call__(self, word, **kwargs):
return self.get_color_func(word)(word, **kwargs)


text = """The Zen of Python, by Tim Peters
Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!"""


# Since the text is small collocations are turned off and text is lower-cased
wc = WordCloud(collocations=False).generate(text.lower())

color_to_words = {
# words below will be colored with a green single color function
'#00ff00': [
'beautiful', 'explicit', 'simple', 'sparse', 'readability', 'rules',
'practicality', 'explicitly', 'one', 'now', 'easy', 'obvious', 'better'
],
# will be colored with a red single color function
'red': [
'ugly', 'implicit', 'complex', 'complicated', 'nested', 'dense',
'special', 'errors', 'silently', 'ambiguity', 'guess', 'hard'
]
}

# Words that are not in any of the color_to_words values
# will be colored with a grey single color function
default_color = 'grey'

# Create a color function with single tone
# grouped_color_func = SimpleGroupedColorFunc(color_to_words, default_color)

# Create a color function with multiple tones
grouped_color_func = GroupedColorFunc(color_to_words, default_color)

# Apply our color function
wc.recolor(color_func=grouped_color_func)
wc.to_file('../images/grouped-color.png')

<img src="/images/grouped-color.png” />

2.3 西游记的词云

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import jieba.analyse
from wordcloud import WordCloud, ImageColorGenerator
import numpy as np
from PIL import Image
import random


def grey_color_func(word,
font_size,
position,
orientation,
random_state=None,
**kwargs):

return "hsl(0, 0%%, %d%%)" % random.randint(60, 100)


font_path = '../resource/tyzkaishu.ttf'
width = 640
height = 480

text = open('../resource/xiyouji.txt').read()
words = jieba.analyse.extract_tags(text, topK=200, withWeight=True)

word_freqs = {}
for word in words:
word_freqs[word[0]] = word[1]

wordcloud = WordCloud(
font_path=font_path, width=width,
height=height).generate_from_frequencies(word_freqs)
wordcloud.to_file('../images/xiyouji.png')

mask = np.array(Image.open('../resource/stormtrooper_mask.png'))
wordcloud = WordCloud(
font_path=font_path, width=width, height=height,
mask=mask).generate_from_frequencies(word_freqs)
wordcloud.to_file('../images/xiyouji-mask.png')

# recolor wordcloud
wordcloud.recolor(color_func=grey_color_func, random_state=3)
wordcloud.to_file('../images/xiyouji-custom.png')

alice_coloring = np.array(Image.open('../resource/alice_color.png'))
wordcloud = WordCloud(
font_path=font_path,
width=width,
height=height,
background_color="white",
mask=alice_coloring,
max_font_size=80,
random_state=42).generate_from_frequencies(word_freqs)

# create coloring from image
image_colors = ImageColorGenerator(alice_coloring)

# recolor wordcloud
wordcloud.recolor(color_func=image_colors)
wordcloud.to_file('../images/xiyouji-color.png')

<img src="/images/xiyouji.png” />

<img src="/images/xiyouji-mask.png” />

<img src="/images/xiyouji-custom.png” />

<img src="/images/xiyouji-color.png” />

2.4 阿里招聘的词云

招聘信息是我使用爬虫趴下来的的,这里只做数据的分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# -*- coding: utf-8 -*-
import jieba
import jieba.analyse
from wordcloud import WordCloud
import numpy as np
from PIL import Image
from pymongo import MongoClient

font_path = '../resource/zhengkaishu.ttf'
width = 640
height = 480

client = MongoClient('mongodb://localhost:27017/')
jobs = client.jobs.alibaba
text = ''
for job in jobs.find({u'firstCategory': u'技术类'}):
if job.get('requirement'):
text += job.get('requirement').replace('<br/>', ' ') + '\n'

jieba.load_userdict('../resource/userdict.txt')
words = jieba.analyse.extract_tags(text, topK=2000, withWeight=True)
word_freqs = {}
for word in words:
_word = word[0].lower().capitalize()
if _word not in word_freqs:
word_freqs[_word] = word[1]
else:
word_freqs[_word] += word[1]

mask = np.array(Image.open('../resource/stormtrooper_mask.png'))
wordcloud = WordCloud(
font_path=font_path, width=width, height=height,
mask=mask).generate_from_frequencies(word_freqs)
wordcloud.to_file('../images/alibaba-mask.png')

<img src="/images/alibaba-mask.png” />

Last Updated 2018-04-25 Wed 22:19.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

scrapy模拟登陆知乎

发表于 2017-08-22 | 分类于 技术积累 |

折腾了将近两天,中间数次想要放弃,还好硬着头皮搞下去了,在此分享出来,希望有同等需求的各位能少走一些弯路。 源码放在了github上, 欢迎前往查看。 若是帮你解决了问题,或者给了你启发,不要吝啬给我加一星。

1 工具准备

在开始之前,请确保 scrpay 正确安装,手头有一款简洁而强大的浏览器, 若是你有使用 postman 那就更好了。

scrapy genspider zhihu

使用以上命令生成知乎爬虫,代码如下:

1
2
3
4
5
6
7
8
9
10
11
# -*- coding: utf-8 -*-
import scrapy


class ZhihuSpider(scrapy.Spider):
name = 'zhihu'
allowed_domains = ['www.zhihu.com']
start_urls = ['http://www.zhihu.com/']

def parse(self, response):
pass

有一点切记,不要忘了启用 Cookies, 切记切记 :

1
2
# Disable cookies (enabled by default)
COOKIES_ENABLED = True

2 模拟登陆

过程如下:

  • 进入登录页,获取 Header 和 Cookie 信息, 完善的 Header 信息能尽量伪装爬虫, 有效 Cookie 信息能迷惑知乎服务端,使其认为当前登录非首次登录,若无有效 Cookie 会遭遇验证码。 在抓取数据之前,请在浏览器中登录过知乎,这样才使得 Cookie 是有效的。

    <img src="/images/zhihu-headers-cookies.jpg” />

    Header 和 Cookie 整理如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    headers = {
    'Host':
    'www.zhihu.com',
    'Connection':
    'keep-alive',
    'Origin':
    'https://www.zhihu.com',
    'User-Agent':
    'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.90 Safari/537.36',
    'Content-Type':
    'application/x-www-form-urlencoded; charset=UTF-8',
    'Accept':
    '*/*',
    'X-Requested-With':
    'XMLHttpRequest',
    'DNT':
    1,
    'Referer':
    'https://www.zhihu.com/',
    'Accept-Encoding':
    'gzip, deflate, br',
    'Accept-Language':
    'zh-CN,zh;q=0.8,en;q=0.6',
    }

    cookies = {
    'd_c0':
    '"AHCAtu1iqAmPTped76X1ZdN0X_qAwhjdLUU=|1458699045"',
    '__utma':
    '51854390.1407411155.1458699046.1458699046.1458699046.1',
    '__utmv':
    '51854390.000--|3=entry_date=20160322=1',
    '_zap':
    '850897bb-cba4-4d0b-8653-fd65e7578ac2',
    'q_c1':
    'b7918ff9a5514d2981c30050c8c732e1|1502937247000|1491446589000',
    'aliyungf_tc':
    'AQAAAHVgviiNyQsAOhSntJ5J/coWYtad',
    '_xsrf':
    'b12fdca8-cb35-407a-bc4c-6b05feff37cb',
    'l_cap_id':
    '"MDk0MzRjYjM4NjAwNDU0MzhlYWNlODQ3MGQzZWM0YWU=|1503382513|9af99534aa22d5db92c7f58b45f3f3c772675fed"',
    'r_cap_id':
    '"M2RlNDZjN2RkNTBmNGFmNDk2ZjY4NjIzY2FmNTE4NDg=|1503382513|13370a99ee367273b71d877de17f05b2986ce0ef"',
    'cap_id':
    '"NmZjODUxZjQ0NzgxNGEzNmJiOTJhOTlkMTVjNWIxMDQ=|1503382513|dba2e9c6af7f950547474f827ef440d7a2950163"',
    }
  • 在浏览器中,模拟登陆,抓取登陆请求信息。

    <img src="/images/zhihu-login-args.jpg” />

    从图中可以看到 _xsrf 参数, 这个参数与登陆验证信息无关,但很明显是由登陆页面携带的信息。 Google 了下 xsrf 的含义, 是用于防范 跨站请求伪造 。

    <img src="/images/zhihu-xsrf.jpg” />

  • 整理以上,代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    loginUrl = 'https://www.zhihu.com/#signin'
    siginUrl = 'https://www.zhihu.com/login/email'


    def start_requests(self):
    return [
    scrapy.http.FormRequest(
    self.loginUrl,
    headers=self.headers,
    cookies=self.cookies,
    meta={'cookiejar': 1},
    callback=self.post_login)
    ]


    def post_login(self, response):
    xsrf = response.css(
    'div.view-signin > form > input[name=_xsrf]::attr(value)'
    ).extract_first()
    self.headers['X-Xsrftoken'] = xsrf

    return [
    scrapy.http.FormRequest(
    self.siginUrl,
    method='POST',
    headers=self.headers,
    meta={'cookiejar': response.meta['cookiejar']},
    formdata={
    '_xsrf': xsrf,
    'captcha_type': 'cn',
    'email': 'xxxxxx@163.com',
    'password': 'xxxxxx',
    },
    callback=self.after_login)
    ]

3 设置Bearer Token

经过上述步骤登陆成功了,有点小激动,有没有! 但苦难到此还远没有结束,这个时候尝试抓取最近热门话题,直接返回 code:401 ,未授权的访问。 授权信息未设置,导致了此类错误,莫非遗漏了什么,看来只能在浏览器中追踪请求参数来侦测问题。 在浏览器的请求中,包含了Bearer Token, 而我在scrapy中模拟的请求中未包含此信息,所以我被服务器认定为未授权的。 通过观察发现 Bearer Token 的关键部分,就是 Cookies 中的 z_c0 对应的信息。

<img src="/images/zhihu-bearer-token.png” />

z_c0 包含的信息,是在登陆完成时种下的,所以从登陆完成返回的登陆信息里,获取要设置的 Cookies 信息, 然后拼接出 Bearer Token,最后设置到 Header 中。

代码整理如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def after_login(self, response):
jdict = json.loads(response.body)
print('after_login', jdict)
if jdict['r'] == 0:
z_c0 = response.headers.getlist('Set-Cookie')[2].split(';')[0].split(
'=')[1]
self.headers['authorization'] = 'Bearer ' + z_c0
return scrapy.http.FormRequest(
url=self.feedUrl,
method='GET',
meta={'cookiejar': response.meta['cookiejar']},
headers=self.headers,
formdata={
'action_feed': 'True',
'limit': '10',
'action': 'down',
'after_id': str(self.curFeedId),
'desktop': 'true'
},
callback=self.parse)
else:
print(jdict['error'])

4 获取数据

上述步骤后,数据获取就水到渠成了,为了检测成功与否, 把返回信息写到文件中,而且只获取前五十个,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
feedUrl = 'https://www.zhihu.com/api/v3/feed/topstory'
nextFeedUrl = ''
curFeedId = 0


def parse(self, response):
with open('zhihu.json', 'a') as fd:
fd.write(response.body)
jdict = json.loads(response.body)
jdatas = jdict['data']
for entry in jdatas:
entry['pid'] = entry['id']
yield entry

jpaging = jdict['paging']
self.curFeedId += len(jdatas)
if jpaging['is_end'] == False and self.curFeedId < 50:
self.nextFeedUrl = jpaging['next']
yield self.next_request(response)


def next_request(self, response):
return scrapy.http.FormRequest(
url=self.nextFeedUrl,
method='GET',
meta={'cookiejar': response.meta['cookiejar']},
headers=self.headers,
callback=self.parse)

获取的数据,采用json格式, 如下所示:

<img src="/images/zhihu-feeds.png” />

5 写在最后

知乎的数据,只有登录完成之后,才可有效的获取,所以模拟登陆是无法忽略不管的。 所谓的模拟登陆,只是在scrapy中尽量的模拟在浏览器中的交互过程,使服务端无感抓包过程。 请求中附加有效的 Cookies 和 Headers 头信息,可有效的迷惑服务端, 同时在交互的过程中,获取后续请求必要信息和认证信息,使得整个流程能不断先前。

若是你遇到什么问题,尽量提出来,欢迎一起来讨论解决。 源码放在了github上, 欢迎前往查看。 若是帮你解决了问题,或者给了你启发,不要吝啬给我加一星。

Last Updated 2017-08-23 Wed 15:21.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

Leetcode-tree

发表于 2017-07-16 | 分类于 技术积累 |

LeetCode 编程训练的积累,目前在努力做题中,日后整理!

<!– more –>

1 binary tree traversal

1.1 level order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}

lo_arr := [][]int{
[]int{root.Val},
}

llo_arr := levelOrder(root.Left)
rlo_arr := levelOrder(root.Right)

if len(llo_arr) > 0 || len(rlo_arr) > 0 {
var index int
for {
if index < len(llo_arr) && index < len(rlo_arr) {
lo_arr = append(lo_arr, append(llo_arr[index], rlo_arr[index]...))
} else {
break
}
index += 1
}

if len(llo_arr) > index {
lo_arr = append(lo_arr, llo_arr[index:]...)
}

if len(rlo_arr) > index {
lo_arr = append(lo_arr, rlo_arr[index:]...)
}
}

return lo_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(levelOrder(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(levelOrder(root))
}

1.2 level order bottom

1
2
3
4
5
6
7
8
9
10
<<bt-level-order>>
func levelOrderBottom(root *TreeNode) [][]int {
lo_arr := levelOrder(root)
lob_arr := make([][]int, 0)
for index, _ := range lo_arr {
lob_arr = append([][]int{lo_arr[index]}, lob_arr...)
}

return lob_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(levelOrderBottom(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(levelOrderBottom(root))
}

1.3 zigzag level order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  <<bt-level-order>>
func zigzagLevelOrder(root *TreeNode) [][]int {
lo_arr := levelOrder(root)
zlo_arr := make([][]int, 0)
for index, _ := range lo_arr {
lo := lo_arr[index]
if index % 2 == 1 {
zlo := make([]int, 0)
for index, _ := range lo {
zlo = append([]int{lo[index]}, zlo...)
}
zlo_arr = append(zlo_arr, zlo)
} else {
zlo_arr = append(zlo_arr, lo)
}
}

return zlo_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(zigzagLevelOrder(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(zigzagLevelOrder(root))
}

1.4 inOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append(inorderTraversal(root.Left), root.Val),
inorderTraversal(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(inorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(inorderTraversal(root))
}

1.5 preOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append([]int{root.Val}, preorderTraversal(root.Left)...),
preorderTraversal(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(preorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(preorderTraversal(root))
}

1.6 postOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append(postorderTraversal(root.Left), postorderTraversal(root.Right)...),
root.Val)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(postorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(postorderTraversal(root))
}

2 binary tree

1
2
3
4
5
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
1
2
3
4
5
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
1
2
3
4
5
6
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2.1 max depth

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}

return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(maxDepth(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(maxDepth(root))
}

2.2 paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return []string{}
}

str := fmt.Sprintf("%d", root.Val)
if root.Left == nil && root.Right == nil {
return []string{str}
}

paths := append(
binaryTreePaths(root.Left),
binaryTreePaths(root.Right)...,
)
for index, path := range paths {
paths[index] = str + "->" + path
}

return paths
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(binaryTreePaths(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(binaryTreePaths(root))
}

2.3 isBalanced

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<<bt-max-depth>>
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}

ldepth := maxDepth(root.Left)
rdepth := maxDepth(root.Right)
ddepth := ldepth - rdepth
if ddepth > 1 || ddepth < -1 {
return false
}

return isBalanced(root.Left) && isBalanced(root.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
}

fmt.Println(isBalanced(root))
root.Left.Left = &TreeNode{Val:4}
fmt.Println(isBalanced(root))
}

2.4 invert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(invertTree(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(invertTree(root))
}

2.5 tilt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func sumTree(root *TreeNode) int {
if root == nil {
return 0
}

return root.Val + sumTree(root.Left) + sumTree(root.Right)
}

func abs(num int) int {
if num < 0 {
return -num
} else {
return num
}
}

func findTilt(root *TreeNode) int {
if root == nil {
return 0
}

return abs(sumTree(root.Left)-sumTree(root.Right)) +
findTilt(root.Left) + findTilt(root.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(findTilt(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(findTilt(root))
}

2.6 construct string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func tree2str(t *TreeNode) string {
if t == nil {
return ""
}

str := fmt.Sprintf("%d", t.Val)
if t.Left == nil && t.Right == nil {
return str
}

if t.Left != nil {
str += fmt.Sprintf("(%s)", tree2str(t.Left))
} else {
str += "()"
}

if t.Right != nil {
str += fmt.Sprintf("(%s)", tree2str(t.Right))
}

return str
}

2.7 symmetric

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}

return isMirror(root.Left, root.Right)
}

func isMirror(lr *TreeNode, rr *TreeNode) bool {
if lr == nil && rr == nil {
return true
}

if lr == nil || rr == nil {
return false
}

if lr.Val != rr.Val {
return false
}

return isMirror(lr.Left, rr.Right) && isMirror(lr.Right, rr.Left)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(isSymmetric(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(isSymmetric(root))
}

2.8 subtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isSubtree(s *TreeNode, t *TreeNode) bool {
if t == nil {
return true
}

if s == nil {
return false
}

if s.Val == t.Val {
return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
} else {
return isSubtree(s.Left, t) || isSubtree(s.Right, t)

}
}

func isSame(s *TreeNode, t *TreeNode) bool {
if s == nil && t == nil {
return true
}

if s == nil || t == nil {
return false
}

if s.Val != t.Val {
return false
}

return isSame(s.Left, t.Left) && isSame(s.Right, t.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func main() {
s := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
},
Right: &TreeNode{
Val: 5,
},
}

t := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(isSubtree(s, t))
s.Left.Right = &TreeNode{
Val: 0,
}
fmt.Println(isSubtree(s, t))
}

2.9 diameter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}

if root.Left == nil && root.Right == nil {
return 0
}

if root.Right == nil {
return max(1+maxSide(root.Left), diameterOfBinaryTree(root.Left))
}

if root.Left == nil {
return max(1+maxSide(root.Right), diameterOfBinaryTree(root.Right))
}

return max(
max(
(2+maxSide(root.Left)+maxSide(root.Right)),
diameterOfBinaryTree(root.Left),
), diameterOfBinaryTree(root.Right))
}

func maxSide(root *TreeNode) int {
if root == nil {
return 0
}

if root.Left == nil && root.Right == nil {
return 0
}

return 1 + max(maxSide(root.Left), maxSide(root.Right))
}

func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func main() {
s := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
},
Right: &TreeNode{
Val: 5,
},
}

t := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(diameterOfBinaryTree(s))
fmt.Println(diameterOfBinaryTree(t))
}

2.10 count complete tree nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}

int ldepth = this->getLeftDepth(root);
int rdepth = this->getRightDepth(root);
if (ldepth == rdepth) {
return this->pow(2,ldepth) -1;
}

return countNodes(root->left) + countNodes(root->right)+1;
}

int getLeftDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}

return 1+getLeftDepth(root->left);
}

int getRightDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}

return 1+getRightDepth(root->right);
}

int pow(int base, int exp) {
int p=1;
while (exp>0) {
p = p*base;
exp = exp- 1;
}

return p;
}
};
1
2
3
4
5
6
7
8
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

Solution s;
std::cout << s.countNodes(p);
}

2.11 implement trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
type Trie struct {
is_end int
next map[byte]*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
var trie Trie
trie.next = make(map[byte]*Trie)
return trie
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
byte_arr := []byte(word)
this.insert(byte_arr)
}

func (this *Trie) insert(byte_arr []byte) {
if len(byte_arr) < 1 {
return
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
if len(byte_arr) > 1 {
next_trie.insert(byte_arr[1:])
} else {
next_trie.is_end = 1
}
} else {
trie := Constructor()
next_trie := &trie
this.next[byte_arr[0]] = next_trie
if len(byte_arr) > 1 {
next_trie.insert(byte_arr[1:])
} else {
next_trie.is_end = 1
}
}
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
byte_arr := []byte(word)
return this.search(byte_arr)
}

func (this *Trie) search(byte_arr []byte) bool {
if len(byte_arr) < 1 {
if len(this.next) == 0 {
return true
} else {
return false
}
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
if len(byte_arr) == 1 && next_trie.is_end == 1 {
return true
} else {
return next_trie.search(byte_arr[1:])
}
} else {
return false
}
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
byte_arr := []byte(prefix)
return this.startsWith(byte_arr)
}

func (this *Trie) startsWith(byte_arr []byte) bool {
if len(byte_arr) < 1 {
return true
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
return next_trie.startsWith(byte_arr[1:])
} else {
return false
}
}

/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/

1
2
3
4
5
6
func main() {
trie := Constructor()
trie.Insert("hello")
fmt.Println(trie.Search("hello"))
fmt.Println(trie.StartsWith("hello"))
}

2.12 merge two binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
if t1 == nil && t2 == nil {
return nil
}

if t2 == nil {
return &TreeNode{
Val: t1.Val,
Left: mergeTrees(t1.Left, nil),
Right: mergeTrees(t1.Right, nil),
}
}

if t1 == nil {
return &TreeNode{
Val: t2.Val,
Left: mergeTrees(nil, t2.Left),
Right: mergeTrees(nil, t2.Right),
}
}

return &TreeNode{
Val: t1.Val + t2.Val,
Left: mergeTrees(t1.Left, t2.Left),
Right: mergeTrees(t1.Right, t2.Right),
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
t1 := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
}

t2 := &TreeNode{
Val: 2,
Right: &TreeNode{Val: 3},
}

fmt.Println(tree2str(mergeTrees(t1, t2)))
}

2.13 flatten bt to linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func flatten(root *TreeNode) {
if root == nil {
return
}

flatten(root.Left)
flatten(root.Right)

if root.Left == nil {
return
}

lr_r := root.Left
for {
if lr_r.Right == nil {
break
}
lr_r = lr_r.Right
}
lr_r.Right = root.Right

root.Right = root.Left
root.Left = nil

return
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(tree2str(flatten(t)))
}

2.14 sum of left leaves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}

if root.Left == nil && root.Right == nil {
return 0
}

if root.Left != nil {
if isLeave(root.Left) {
return root.Left.Val + sumOfLeftLeaves(root.Right)
} else {
return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
} else {
return sumOfLeftLeaves(root.Right)
}
}

func isLeave(node *TreeNode) bool {
return node.Left == nil && node.Right == nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
t := &TreeNode{
Val: 3,
Left: &TreeNode{Val: 9},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{Val: 15},
Right: &TreeNode{Val: 7},
},
}

fmt.Println(sumOfLeftLeaves(t))
}

2.15 find bottom left tree value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findBottomLeftValue(root *TreeNode) int {
if root == nil {
return 0
}

lnode_arr := []*TreeNode{root}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
lnode_arr = n_lnode_arr
} else {
break
}
}

return lnode_arr[0].Val
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{
Val: 5,
Left: &TreeNode{Val: 10},
},
}

fmt.Println(findBottomLeftValue(t))
}

2.16 right side view

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}

lnode_arr := []*TreeNode{root}
rsv_arr := []int{root.Val}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
rsv_arr = append(rsv_arr, n_lnode_arr[len(n_lnode_arr)-1].Val)
lnode_arr = n_lnode_arr
} else {
break
}
}

return rsv_arr
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(rightSideView(t))
}

2.17 find largest value in each tree row

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func largestValues(root *TreeNode) []int {
if root == nil {
return []int{}
}

lnode_arr := []*TreeNode{root}
rmax_arr := []int{root.Val}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
rmax_val := n_lnode_arr[0].Val
for index, _ := range n_lnode_arr {
node := n_lnode_arr[index]
if node.Val > rmax_val {
rmax_val = node.Val
}
}
lnode_arr = n_lnode_arr
rmax_arr = append(rmax_arr, rmax_val)
} else {
break
}
}

return rmax_arr
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(largestValues(t))
}

2.18 most frequent subtree sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func findFrequentTreeSum(root *TreeNode) []int {
if root == nil {
return []int{}
}

sum_M := make(map[int]int)
collectTreeSum(root, sum_M)
var max_count int
for _, count := range sum_M {
if count > max_count {
max_count = count
}
}

ft_sum_arr := make([]int, 0)
for sum, count := range sum_M {
if count == max_count {
ft_sum_arr = append(ft_sum_arr, sum)
}
}

return ft_sum_arr
}

func collectTreeSum(root *TreeNode, sum_M map[int]int) int {
if root == nil {
return 0
}

sum := collectTreeSum(root.Left, sum_M) + root.Val + collectTreeSum(root.Right, sum_M)
sum_M[sum] = sum_M[sum] + 1
return sum
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(findFrequentTreeSum(t))
}

2.19 construct binary tree from preorder and inorder traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}

if len(preorder) == 1 {
return &TreeNode{
Val: preorder[0],
}
}

rio_index := find(inorder, preorder[0])
return &TreeNode{
Val: preorder[0],
Left: buildTree(preorder[1:rio_index+1], inorder[0:rio_index]),
Right: buildTree(preorder[rio_index+1:], inorder[rio_index+1:]),
}
}

func find(a []int, x int) int {
for index, _ := range a {
if a[index] == x {
return index
}
}

return -1
}
1
2
3
4
func main() {
fmt.Println(tree2str(buildTree([]int{1,2,3}, []int{2,1,3})))
fmt.Println(tree2str(buildTree([]int{1,2,4,3,5}, []int{4,2,1,3,5})))
}

2.20 construct binary tree from inorder and postorder traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder) == 0 {
return nil
}

if len(inorder) == 1 {
return &TreeNode{Val: inorder[0]}
}

rio_index := find(inorder, postorder[len(postorder)-1])
return &TreeNode{
Val: postorder[len(postorder)-1],
Left: buildTree(inorder[0:rio_index], postorder[0:rio_index]),
Right: buildTree(inorder[rio_index+1:], postorder[rio_index:(len(postorder)-1)]),
}
}

func find(a []int, x int) int {
for index, _ := range a {
if a[index] == x {
return index
}
}

return -1
}
1
2
3
4
func main() {
fmt.Println(tree2str(buildTree([]int{2,1,3}, []int{2,3,1})))
fmt.Println(tree2str(buildTree([]int{4,2,1,3,5}, []int{4,2,5,3,1})))
}

2.21 populating next right pointers in each node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

struct ConnectObj {
TreeLinkNode *left_most;
TreeLinkNode *right_most;
ConnectObj() : left_most(NULL), right_most(NULL) {}
};

std::deque<ConnectObj>
mergeConnect(
std::deque<ConnectObj> lc_dq,
std::deque<ConnectObj> rc_dq)
{
for (std::deque<ConnectObj>::iterator it = lc_dq.begin(); it != lc_dq.end(); ++it) {
if (it->right_most == NULL) {
it->right_most = it->left_most;
}
}

for (std::deque<ConnectObj>::iterator it = rc_dq.begin(); it != rc_dq.end(); ++it) {
if (it->left_most == NULL) {
it->left_most = it->right_most;
}
}

int min_size = lc_dq.size() < rc_dq.size() ? lc_dq.size() : rc_dq.size();
for (int index=0; index < min_size; index+=1) {
if (lc_dq[index].right_most != NULL && rc_dq[index].left_most != NULL){
lc_dq[index].right_most->next = rc_dq[index].left_most;
}

lc_dq[index].right_most = rc_dq[index].right_most;
rc_dq[index].left_most = lc_dq[index].left_most;
}

return lc_dq.size() > rc_dq.size() ? lc_dq : rc_dq;
}

class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) {
return;
}

this->connectHelper(root);
return;
}

std::deque<ConnectObj> connectHelper(TreeLinkNode *root) {
std::deque<ConnectObj> conn_dq;
if (root == NULL) {
return conn_dq;
}

ConnectObj rc_node;
rc_node.left_most = root;
rc_node.right_most = root;
if ((root->left == NULL) && (root->right == NULL)) {
conn_dq.push_back(rc_node);
return conn_dq;
}

std::deque<ConnectObj> lc_dq = connectHelper(root->left);
std::deque<ConnectObj> rc_dq = connectHelper(root->right);
std::deque<ConnectObj> merge_dq = mergeConnect(lc_dq, rc_dq);
merge_dq.push_front(rc_node);
return merge_dq;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
TreeLinkNode* p = new TreeLinkNode(5);
p->left = new TreeLinkNode(3);
p->left->left = new TreeLinkNode(1);
p->left->left->left = new TreeLinkNode(1);
p->left->right = new TreeLinkNode(2);
p->right = new TreeLinkNode(7);
p->right->right = new TreeLinkNode(9);

Solution s;
s.connect(p);
TreeLinkNode *left = p;
while (left != NULL) {
TreeLinkNode *head = left;
while (head !=NULL){
std::cout << head->val << " ";
head = head->next;
}
std::cout << "\n";
left = left->left;
}
return 0;
}

2.22 add one row to tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func addOneRow(root *TreeNode, v int, d int) *TreeNode {
if d == 1 {
return &TreeNode{
Val: v,
Left: root,
}
}

if root == nil || d < 2 {
return nil
}

addOneRowHelper(root, v, d)
return root
}

func addOneRowHelper(root *TreeNode, v int, d int) {
if root == nil {
return
}

if d == 2 {
root.Left = &TreeNode{
Val: v,
Left: root.Left,
}
root.Right = &TreeNode{
Val: v,
Right: root.Right,
}
return
}

addOneRowHelper(root.Left, v, d-1)
addOneRowHelper(root.Right, v, d-1)
return
}
1
2
3
4
5
6
7
8
9
10
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 4},
}

fmt.Println(tree2str(addOneRow(root, 2, 1)))
fmt.Println(tree2str(addOneRow(root, 2, 2)))
}

2.23 lowest common ancestor of a bt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || p == root || q == root) {
return root;
}

TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);

if (left != NULL && right != NULL) {
return root;
}

if (left != NULL) {
return left;
}

if (right != NULL) {
return right;
}

return NULL;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->left->left = new TreeNode(1);
p->left->left->left = new TreeNode(0);
p->left->right = new TreeNode(2);
p->right = new TreeNode(7);
p->right->right = new TreeNode(9);

Solution s;
std::cout << s.lowestCommonAncestor(p, p->left->left, p->right->right)->val;
std::cout << s.lowestCommonAncestor(p, p->left->left, p->left->right)->val;
return 0;
}

2.24 serialize and deserialize bt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
<<bt-node-def-cpp>>

int find_bracket_end(string str, int b_start) {
std::stack<char> b_stack;
int b_end=0;
for (int index = b_start; index < str.size(); index += 1) {
char c = str[index];
switch (c) {
case '(':
b_stack.push(c);
break;
case ')':
b_stack.pop();
break;
default:
break;
}
if (b_stack.empty()==true) {
b_end = index;
break;
}
}
return b_end;
}

string tree2str(TreeNode* t) {
if (t == NULL) {
return "";
}

ostringstream os;
os << t->val;
if (t->left == NULL && t->right == NULL) {
return os.str();
}

if (t->left != NULL) {
os << "(" << tree2str(t->left) << ")";
} else {
os << "()";
}

if (t->right != NULL) {
os << "(" << tree2str(t->right) << ")";
}

return os.str();
}

TreeNode* str2tree(string str) {
if (str == "" || str == "()") {
return NULL;
}

int b_start = str.find("(");
if (b_start < 0) {
int num = std::atoi(str.c_str());
return new TreeNode(num);
}

string num_str = str.substr(0, b_start);
int num = std::atoi(num_str.c_str());
TreeNode* root = new TreeNode(num);

int b_end = find_bracket_end(str, b_start);
if (b_end-b_start > 1) {
root->left = str2tree(str.substr(b_start+1, b_end));
}

b_start = b_end+1;
if (b_start < str.size() && str[b_start]=='('){
b_end = find_bracket_end(str, b_start);
if (b_end-b_start > 1) {
root->right = str2tree(str.substr(b_start+1, b_end));
}
}

return root;
}

class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
return tree2str(root);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return str2tree(data);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 using namespace std;


int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->left->left = new TreeNode(1);
p->left->left->left = new TreeNode(1);
p->left->right = new TreeNode(2);
p->right = new TreeNode(7);
p->right->right = new TreeNode(9);

Codec codec;
string encode_str =codec.serialize(p);
std::cout << encode_str << '\n';

TreeNode* np = codec.deserialize(encode_str);
encode_str = codec.serialize(np);
std::cout << encode_str << '\n';

return 0;
}

2.25 average of levels in binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func averageOfLevels(root *TreeNode) []float64 {
lo_arr := levelOrder(root)
aveOfLevels := make([]float64, 0)
for index, _ := range lo_arr {
lo := lo_arr[index]
var sum int
for _, val := range lo {
sum += val
}
ave := float64(sum) / float64(len(lo))
aveOfLevels = append(aveOfLevels, ave)
}

return aveOfLevels
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(averageOfLevels(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(averageOfLevels(root))
}

2.26 TODO house robber III

3 bst

3.1 BSTIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};

Node* convertBST2SortedLst(TreeNode *lct,TreeNode *pn, TreeNode *rct) {
Node *lhead = NULL;
if (lct != NULL) {
lhead = convertBST2SortedLst(lct->left, lct, lct->right);
}

Node *pln = new Node(pn->val);

Node *rhead = NULL;
if (rct != NULL){
rhead = convertBST2SortedLst(rct->left, rct, rct->right);
}

Node *head = NULL;
if (lhead != NULL) {
pln->next = rhead;
head = lhead;
while (lhead->next != NULL) {
lhead = lhead->next;
}
lhead->next = pln;
} else {
pln->next = rhead;
head = pln;
}
return head;
}

class BSTIterator {
Node* head;
public:
BSTIterator(TreeNode *root) {
if (root != NULL) {
head = convertBST2SortedLst(root->left, root, root->right);
} else {
head = NULL;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
if (this->head != NULL) {
return true;
} else {
return false;
}
}

/** @return the next smallest number */
int next() {
if (this->head== NULL) {
return 0;
}

Node *oldHead = head;
head = head->next;
int num = oldHead->val;
delete oldHead;
oldHead = NULL;
return num;
}

~BSTIterator(){
Node *oldHead = NULL;
while (head != NULL){
oldHead = head;
head = head->next;
delete oldHead;
oldHead = NULL;
}
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

1
2
3
4
5
6
7
8
9
10
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

BSTIterator i = BSTIterator(p);
while (i.hasNext())
std::cout << i.next();
return 0;
}

3.2 to greater tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func convertBST(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

return convertBSTHelper(root, 0)
}

func convertBSTHelper(root *TreeNode, upper int) *TreeNode {
if root == nil {
return nil
}

if root.Left == nil && root.Right == nil {
root.Val += upper
return root
}

if root.Right != nil {
minNode := findMinBST(root.Right)
root.Right = convertBSTHelper(root.Right, upper)
root.Val += minNode.Val
} else {
root.Val += upper
}

if root.Left != nil {
root.Left = convertBSTHelper(root.Left, root.Val)
}

return root
}

func findMinBST(root *TreeNode) *TreeNode {
if root == nil || root.Left == nil {
return root
}

return findMinBST(root.Left)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
root := &TreeNode{
Val: 0,
Left: &TreeNode{
Val: -1,
Left: &TreeNode{
Val: -3,
},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{
Val: 4,
},
},
}

fmt.Println(convertBST(root))
fmt.Println(root.Left)
fmt.Println(root.Left.Left)
fmt.Println(root.Right.Right)
}

3.3 validate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}

return isValidLeftBST(root.Left, root.Val) && isValidRightBST(root.Right, root.Val)
}

func isValidLeftBST(root *TreeNode, upper int) bool {
if root == nil {
return true
}

if root.Val >= upper {
return false
}

return isValidLeftBST(root.Left, root.Val) && isValidSubBST(root.Right, root.Val, upper)
}

func isValidRightBST(root *TreeNode, lower int) bool {
if root == nil {
return true
}

if root.Val <= lower {
return false
}

return isValidRightBST(root.Right, root.Val) && isValidSubBST(root.Left, lower, root.Val)
}

func isValidSubBST(root *TreeNode, lower int, upper int) bool {
if root == nil {
return true
}

if root.Val >= upper || root.Val <= lower {
return false
}

return isValidSubBST(root.Left, lower, root.Val) && isValidSubBST(root.Right, root.Val, upper)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(isValidBST(root))

root = &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 3,
},
}
fmt.Println(isValidBST(root))
}

3.4 find mode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func findMode(root *TreeNode) []int {
if root == nil {
return []int{}
}

modes := collect(root)
if len(modes) < 1 {
return modes
}

for i := 1; i < len(modes); i += 1 {
for j := i; j > 0; j -= 1 {
if modes[j] < modes[j-1] {
modes[j], modes[j-1] = modes[j-1], modes[j]
}
}
}

var max_count int
var count int
var pre int
n_modes := make([]int, 0)
for index, mode := range modes {
if index == 0 {
max_count = 1
pre = mode
count = 1
n_modes = append(n_modes, mode)
continue
}

if mode == pre {
count += 1
}

if mode != pre {
pre = mode
count = 1
}

if count == max_count {
n_modes = append(n_modes, mode)
}
if count > max_count {
max_count = count
n_modes = []int{mode}
}
}

return n_modes
}

func collect(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(append(collect(root.Left), root.Val), collect(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func main() {
root := &TreeNode{
Val: 0,
Left: &TreeNode{
Val: -1,
Left: &TreeNode{
Val: -1,
},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{
Val: 2,
},
},
}

fmt.Println(findMode(root))
}

3.5 convert sorted array to bst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}

if len(nums) == 1 {
return &TreeNode{
Val: nums[0],
}
}

if len(nums) == 2 {
return &TreeNode{
Val: nums[1],
Left: &TreeNode{
Val: nums[0],
},
}
}

mid := len(nums) / 2
return &TreeNode{
Val: nums[mid],
Left: sortedArrayToBST(nums[:mid]),
Right: sortedArrayToBST(nums[mid+1:]),
}
}
1
2
3
4
5
func main() {
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3})))
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3,4,5,6})))
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3,4,5,6,7,8})))
}

3.6 lowest common ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) {
return NULL;
}

if (p->val > q->val) {
TreeNode *tmp = p;
p=q;
q=tmp;
}

if (root->val>p->val && root->val<q->val) {
return root;
}

if (root->val < p->val) {
return lowestCommonAncestor(root->right, p, q);
}

if (root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}

if (root->val == p->val) {
return root;
}

if (root->val == q->val) {
return root;
}

return NULL;
}
};
1
2
3
4
5
6
7
8
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

Solution s;
std::cout << s.lowestCommonAncestor(p, p->left, p->right)->val;
}

3.7 recover binary search tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

type RecoverNode struct {
Pre *TreeNode
Ppre *TreeNode
Is_recover int
Illegal *TreeNode
}

type traversalFunc func(*TreeNode)

func recoverTree(root *TreeNode) {
if root == nil {
return
}

rNode := &RecoverNode{}
tfunc := func(rnode *RecoverNode) traversalFunc {
return func(node *TreeNode) {
recoverFunc(node, rnode)
}
}(rNode)
inorderTraversal(root, tfunc)
if rNode.Is_recover == 0 && rNode.Illegal != nil {
rNode.Pre.Val, rNode.Illegal.Val = rNode.Illegal.Val, rNode.Pre.Val
}
}

func inorderTraversal(root *TreeNode, tfunc traversalFunc) {
if root == nil {
return
}

inorderTraversal(root.Left, tfunc)
tfunc(root)
inorderTraversal(root.Right, tfunc)
}

func recoverFunc(node *TreeNode, rnode *RecoverNode) {
if node == nil {
return
}

if rnode.Is_recover == 1 {
return
}

if rnode.Pre == nil {
rnode.Pre = node
return
}

if node.Val < rnode.Pre.Val {
if rnode.Illegal == nil {
rnode.Illegal = rnode.Pre
} else {
rnode.Illegal.Val, node.Val = node.Val, rnode.Illegal.Val
rnode.Is_recover = 1
}
} else {
if rnode.Illegal != nil {
if rnode.Illegal.Val < node.Val {
rnode.Illegal.Val, rnode.Pre.Val = rnode.Pre.Val, rnode.Illegal.Val
rnode.Is_recover = 1
}
}
}

rnode.Ppre = rnode.Pre
rnode.Pre = node
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
s := &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
},
Right: &TreeNode{
Val: 1,
},
}

fmt.Println(tree2str(s))
recoverTree(s)
fmt.Println(tree2str(s))
}

3.8 delete node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}

if root.Val == key {
if root.Left == nil || root.Right == nil {
if root.Left != nil {
return root.Left
} else if root.Right != nil {
return root.Right
} else {
return nil
}
} else {
successor := treeMinimum(root.Right)
root.Val = successor.Val
root.Right = deleteNode(root.Right, successor.Val)
}
}

if root.Val < key {
root.Right = deleteNode(root.Right, key)
} else {
root.Left = deleteNode(root.Left, key)
}
return root
}

func treeMinimum(node *TreeNode) *TreeNode {
if node.Left != nil {
return treeMinimum(node.Left)
} else {
return node
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
s := &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(tree2str(s))
s = deleteNode(s, 1)
fmt.Println(tree2str(s))
}

3.9 convert sorted list to bst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
type ListNode struct {
Val int
Next *ListNode
}

type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
length := getListLength(head)
return sortedListToBSTHelper(head, length)
}

func getListLength(head *ListNode) int {
if head == nil {
return 0
}

return 1 + getListLength(head.Next)
}

func getListNth(head *ListNode, nth int) *ListNode {
if head == nil {
return nil
}
if nth < 1 {
return head
}

return getListNth(head.Next, nth-1)
}

func sortedListToBSTHelper(head *ListNode, length int) *TreeNode {
if length < 1 {
return nil
}

if length == 1 {
return &TreeNode{
Val: head.Val,
}
}

if length == 1 {
return &TreeNode{
Val: head.Val,
Right: &TreeNode{
Val: head.Next.Val,
},
}
}

mid := length / 2
mid_node := getListNth(head, mid)
return &TreeNode{
Val: mid_node.Val,
Left: sortedListToBSTHelper(head, mid),
Right: sortedListToBSTHelper(mid_node.Next, length-1-mid),
}
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
sortedLst := &ListNode{
Val: 1,
Next: &ListNode{
Val:2,
Next: &ListNode{
Val:3,
},
},
}
fmt.Println(tree2str(sortedListToBST(sortedLst)))
}

3.10 kth smallest elemen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
type KthNode struct {
K int
Val int
}

type traversalFunc func(*TreeNode)

func kthSmallest(root *TreeNode, k int) int {
if root == nil {
return 0
}

kNode := &KthNode{K: k}
tfunc := func(knode *KthNode) traversalFunc {
return func(node *TreeNode) {
kthFunc(node, knode)
}
}(kNode)
inorderTraversal(root, tfunc)
return kNode.Val
}

func inorderTraversal(root *TreeNode, tfunc traversalFunc) {
if root == nil {
return
}

inorderTraversal(root.Left, tfunc)
tfunc(root)
inorderTraversal(root.Right, tfunc)
}

func kthFunc(node *TreeNode, kn *KthNode) {
if node == nil && kn.K == 0 {
return
}

kn.K -= 1
if kn.K == 0 {
kn.Val = node.Val
}
return
}
1
2
3
4
5
6
7
8
9
10
11
func main() {
t := &TreeNode{
Val: 3,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 5},
}

fmt.Println(kthSmallest(t,1))
fmt.Println(kthSmallest(t,2))
fmt.Println(kthSmallest(t,3))
}

3.11 unique bst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numTrees(n int) int {
if n < 1 {
return 1
}

ctl_arr := make([]int, n+1)
ctl_arr[0] = 1
ctl_arr[1] = 1
for i := 2; i < n+1; i += 1 {
for j := 0; j < i; j += 1 {
ctl_arr[i] += ctl_arr[j] * ctl_arr[i-j-1]
}
}

return ctl_arr[n]
}
1
2
3
4
5
func main() {
for _, n := range list{
fmt.Println(numTrees(n))
}
}

3.12 unique bst II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
func generateTrees(n int) []*TreeNode {
if n == 0 {
return []*TreeNode{}
}

tree_arr := []*TreeNode{
&TreeNode{
Val: 1,
},
}

for i := 2; i <= n; i += 1 {
ng_tree_arr := make([]*TreeNode, 0)
for index, _ := range tree_arr {
tree := tree_arr[index]
ng_tree_arr = append(ng_tree_arr, genTreesHelper(tree, i)...)
}
tree_arr = ng_tree_arr
}

return tree_arr
}

func genTreesHelper(root *TreeNode, greater int) []*TreeNode {
if root == nil {
return []*TreeNode{}
}

cr := cloneTree(root)
right := cr
var parent *TreeNode
tree_arr := make([]*TreeNode, 0)
for {
if right != nil {
rval := right.Val
node := &TreeNode{
Val: greater,
Left: right,
}
if parent != nil {
parent.Right = node
} else {
cr = node
}
tree_arr = append(tree_arr, cr)

cr = cloneTree(root)
parent = getNode(cr, rval)
right = parent.Right
} else {
parent.Right = &TreeNode{Val: greater}
tree_arr = append(tree_arr, cr)
break
}
}

return tree_arr
}

func cloneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

return &TreeNode{
Val: root.Val,
Left: cloneTree(root.Left),
Right: cloneTree(root.Right),
}
}

func getNode(root *TreeNode, val int) *TreeNode {
if root == nil {
return nil
}

if root.Val == val {
return root
}

if root.Val < val {
return getNode(root.Right, val)
} else {
return getNode(root.Left, val)
}
}
1
2
3
4
5
6
func main() {
for _, n := range list{
tree_arr := generateTrees(n)
fmt.Println(n, len(tree_arr))
}
}
Last Updated 2017-07-16 Sun 15:30.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

Leetcode-array

发表于 2017-07-16 | 分类于 技术积累 |
1
2
3
4
type Interval struct {
Start int
End int
}

1 best time to buy and sell stock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp int
min_p := prices[0]
for _, price := range prices {
if price-min_p > mp {
mp = price - min_p
}
if price < min_p {
min_p = price
}
}

return mp
}

2 best time to buy and sell stock II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}

if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}

if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}

pre_p = price
}

if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}

return mp
}

3 plus one

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func plusOne(digits []int) []int {
var carry int
carry = 1
for index := len(digits) - 1; index >= 0; index -= 1 {
if carry+digits[index] == 10 {
carry = 1
digits[index] = 0
} else {
digits[index] += carry
carry = 0
}

if carry == 0 {
break
}
}

if carry == 1 {
return append([]int{1}, digits...)
}

return digits
}

4 pascal's triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func generate(numRows int) [][]int {
pt_arr := make([][]int, 0)
if numRows < 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1})
if numRows == 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1, 1})
if numRows < 3 {
return pt_arr
}
for i := 3; i <= numRows; i += 1 {
pt := make([]int, i)
pre_pt := pt_arr[i-2]
var pre int
for index, _ := range pre_pt {
if index == 0 {
pt[index] = pre_pt[index]
pre = pre_pt[index]
continue
}

if index == len(pre_pt)-1 {
pt[index] = pre + pre_pt[index]
pt[index+1] = pre_pt[index]
continue
}

pt[index] = pre + pre_pt[index]
pre = pre_pt[index]
}
pt_arr = append(pt_arr, pt)
}

return pt_arr
}
1
2
3
func main() {
fmt.Println(generate(3))
}

5 pascal's triangle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func getRow(rowIndex int) []int {
rowIndex += 1
pt_row := make([]int, rowIndex)
if rowIndex < 1 {
return pt_row
}
pt_row[0] = 1
if rowIndex == 1 {
return pt_row
}
pt_row[1] = 1

for i := 3; i <= rowIndex; i += 1 {
ptr := pt_row[0:i]
pre_ptr := pt_row[0 : i-1]
var pre int
for index, _ := range pre_ptr {
if index == 0 {
pre = pre_ptr[index]
continue
}

if index == len(pre_ptr)-1 {
ptr[index+1] = pre_ptr[index]
ptr[index] = pre + pre_ptr[index]
continue
}

pre_num := pre_ptr[index]
ptr[index], pre = pre+pre_num, pre_num
}
}

return pt_row
}
1
2
3
func main() {
fmt.Println(getRow(4))
}

6 array partition I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}

func arrayPairSum(nums []int) int {
sort.Ints(nums)
var p_sum int
for index := 0; index < len(nums); index += 2 {
p_sum += min(nums[index], nums[index+1])
}

return p_sum
}

7 find all numbers disappeared in an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func findDisappearedNumbers(nums []int) []int {
if len(nums) < 1 {
return nums
}
dis_nums := make([]int, 0)

var pre, pre_index int
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
if pre == 0 {
return dis_nums
}

for i := 0; i < len(nums); i += 1 {
if nums[pre-1] != pre && nums[pre-1] != 0 {
nums[pre-1], pre = pre, nums[pre-1]
continue
}

if nums[pre-1] == 0 {
nums[pre-1] = pre
}

nums[pre_index] = 0
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
}

nums[pre-1] = pre

for index, num := range nums {
if index+1 != num {
dis_nums = append(dis_nums, index+1)
}
}

return dis_nums
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findDisappearedNumbers(nums []int) []int {
marks := make([]int, 0)
for _, num := range nums {
marks[num-1] = 1
}

dis_nums := make([]int, 0)
for index, mark := range marks {
if mark == 0 {
dis_nums = append(dis_nums, index+1)
}
}
return dis_nums
}
1
2
3
func main() {
fmt.Println(findDisappearedNumbers([]int{4,3,2,7,8,2,3,1}))
}

8 two sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i+1; j < len(nums); j +=1 {
secd := nums[j]
if fir + secd == target {
indices = append(indices, i)
indices = append(indices, j)
break
}
}
}
return indices
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var carry int
var sum_head, sum_curr *ListNode
for {
if l1 == nil && l2 == nil {
if carry > 0 {
sum_node := &ListNode{
Val: carry,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
break
}

var sum int
if l1 != nil && l2 != nil {
sum = l1.Val + l2.Val + carry
l1, l2 = l1.Next, l2.Next
} else if l2 == nil {
sum = l1.Val + carry
l1 = l1.Next
} else if l1 == nil {
sum = l2.Val + carry
l2 = l2.Next
}

if sum > 9 {
carry = 1
sum -= 10
} else {
carry = 0
}

sum_node := &ListNode{
Val: sum,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
return sum_head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
type ListNode struct {
Val int
Next *ListNode
}



func make_list(vals []int) *ListNode{
var lst, lst_c *ListNode
for _, val := range vals {
node := &ListNode{
Val: val,
Next: nil,
}
if lst != nil {
lst_c.Next = node
lst_c = node
} else {
lst = node
lst_c = node
}
}
return lst
}

func print_list(lst *ListNode) {
var str string
for {
if lst == nil {
break
}
str += fmt.Sprintf("%d,", lst.Val)
lst = lst.Next
}
str = strings.Trim(str, ",")
fmt.Printf("[%s]", str)
}

func main() {
l1 := make_list([]int{2,4,3})
l2 := make_list([]int{5,6,4})
sum_lst := addTwoNumbers(l1,l2)
print_list(sum_lst)
}

9 two sum II - input array is sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i + 1; j < len(nums); j += 1 {
secd := nums[j]
if fir+secd == target {
indices = append(indices, i+1)
indices = append(indices, j+1)
break
}
}
}
return indices
}

10 remove duplicates from sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeDuplicates(nums []int) int {
if (len(nums)) <2 {
return len(nums)
}

pre := nums[0]
size := 1
for _, num := range nums {
if pre != num {
pre = num
nums[size] = num
size++
}
}

return size
}

11 remove duplicates from sorted array II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func removeDuplicates(nums []int) int {
if (len(nums)) < 3 {
return len(nums)
}

size := 2
pp_num := nums[0]
p_num := nums[1]
nums_size := len(nums)
for i := 2; i < nums_size; i++ {
if nums[i] == p_num && p_num == pp_num {
continue
}

pp_num = p_num
p_num = nums[i]
nums[size] = nums[i]
size++
}

return size
}

12 remove element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func removeElement(nums []int, val int) int {
var size int
for index, num := range nums {
if index == 0 {
if num == val {
size = 0
} else {
size = 1
}
continue
}

if num != val {
nums[size] = num
size += 1
}
}

return size
}

13 majority element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func majorityElement(nums []int) int {
num_M := make(map[int]int)
for _, num := range nums {
time := num_M[num]
num_M[num] = time + 1
}

var mt_num, max_times int
for num, time := range num_M {
if time > max_times {
mt_num = num
max_times = time
}
}
return mt_num
}

14 DONE shortest unsorted continuous subarray

  • State "DONE" from "STARTED" [2017-07-17 Mon 23:32]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findUnsortedSubarray(nums []int) int {
n_nums := make([]int, len(nums))
copy(n_nums, nums)
sort.Ints(n_nums)
var start, end int
for index, _ := range nums {
if nums[index] != n_nums[index] {
start = index
break
}
}

for index := len(nums) - 1; index >= 0; index -= 1 {
if nums[index] != n_nums[index] {
end = index + 1
break
}
}

return end - start
}

15 reshape the matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func matrixReshape(nums [][]int, r int, c int) [][]int {
if len(nums) < 1 || len(nums[0]) < 1 {
return [][]int{}
}

or := len(nums)
oc := len(nums[0])
if or*oc != r*c {
return nums
}

f_nums := make([]int, 0)
for index, _ := range nums {
row := nums[index]
f_nums = append(f_nums, row...)
}

n_nums := make([][]int, r)
for i := 0; i < r; i += 1 {
row := make([]int, c)
for j := 0; j < c; j += 1 {
row[j] = f_nums[i*c+j]
}
n_nums[i] = row
}

return n_nums
}

16 search insert position

1
2
3
4
5
6
7
8
9
10
11
12
13
func searchInsert(nums []int, target int) int {
for index, num := range nums {
if num == target {
return index
}

if num > target {
return index
}
}

return len(nums)
}

17 merge sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func merge(nums1 []int, m int, nums2 []int, n int) {
if m == 0 {
for i := 0; i < n; i += 1 {
nums1[i] = nums2[i]
}
return
}

if n == 0 {
return
}

n1_index := m - 1
n2_index := n - 1
index := m + n - 1
for {
if n1_index < 0 || n2_index < 0 {
break
}

if nums1[n1_index] > nums2[n2_index] {
nums1[index] = nums1[n1_index]
n1_index -= 1
index -= 1
} else {
nums1[index] = nums2[n2_index]
n2_index -= 1
index -= 1
}
}

if n2_index >= 0 {
for i := 0; i <= n2_index; i += 1 {
nums1[i] = nums2[i]
}
}

return
}

18 maximum product of three numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func maximumProduct(nums []int) int {
sort.Ints(nums)
size := len(nums)
return max(nums[size-1]*nums[size-2]*nums[size-3], nums[0]*nums[1]*nums[size-1])
}

19 maximum average subarray I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findMaxAverage(nums []int, k int) float64 {
var max_average float64
for index := 0; index <= len(nums)-k; index += 1 {
var sub_sum int
for j := 0; j < k; j += 1 {
sub_sum += nums[index+j]
}

average := float64(sub_sum) / float64(k)
if index == 0 {
max_average = average
continue
}

if max_average < average {
max_average = average
}
}

return max_average
}

20 move zeroes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func moveZeroes(nums []int) {
for index, num := range nums {
if num == 0 {
continue
}

for j := index; 0 < j; j -= 1 {
if nums[j-1] == 0 {
nums[j-1], nums[j] = nums[j], nums[j-1]
} else {
break
}
}
}

return
}
1
2
3
4
5
func main() {
nums := []int{0, 1, 0, 3, 12}
moveZeroes(nums)
fmt.Println(nums)
}

21 can place flowers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func canPlaceFlowers(flowerbed []int, n int) bool {
if len(flowerbed) < 1 && n > 0 {
return false
}

if n == 0 {
return true
}

if len(flowerbed) < n {
return false
}

if len(flowerbed) == 1 {
if flowerbed[0] == 0 && n == 1 {
return true
} else {
return false
}
}

for index, _ := range flowerbed {
if flowerbed[index] == 1 {
continue
}

switch index {
case 0:
if flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
case len(flowerbed) - 1:
if flowerbed[index-1] == 0 {
flowerbed[index] = 1
n -= 1
}
default:
if flowerbed[index-1] == 0 && flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
}

if n < 1 {
return true
}
}

return false
}

22 contains duplicate

1
2
3
4
5
6
7
8
func containsDuplicate(nums []int) bool {
num_M := make(map[int]bool)
for _, num := range nums {
num_M[num] = true
}

return len(nums) > len(num_M)
}

23 contains duplicate II

1
2
3
4
5
6
7
8
9
10
11
12
13
func containsNearbyDuplicate(nums []int, k int) bool {
num_M := make(map[int]bool)
for index, num := range nums {
if index > k {
delete(num_M, nums[index-k-1])
}
if num_M[num] {
return true
}
num_M[num] = true
}
return false
}

24 contains duplicate III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func abs(x int) int {
if x < 0 {
return -x
} else {
return x
}
}

func getQuot(i, w int) int {
if i < 0 {
return (i+1)/w - 1
} else {
return i / w
}
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
if t < 0 {
return false
}
num_M := make(map[int]int)
w := t + 1
for index, num := range nums {

quot := getQuot(num, w)
if _, ok := num_M[quot]; ok {
return true
}

if pre_num, ok := num_M[quot-1]; ok && abs(num-pre_num) < w {
return true
}

if pre_num, ok := num_M[quot+1]; ok && abs(num-pre_num) < w {
return true
}

num_M[quot] = num

if index >= k {
delete(num_M, getQuot(nums[index-k], w))
}

}
return false
}

25 k-diff pairs in an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func findPairs(nums []int, k int) int {
sort.Ints(nums)
var base_index, pair_size int
for {
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > k {
break
}
if nums[i]-nums[base_index] == k {
pair_size += 1
break
}
}

old_bi := base_index
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > 0 {
base_index = i
break
}
}

if old_bi == base_index {
break
}

if base_index == len(nums)-1 {
break
}
}

return pair_size
}

26 best time to buy and sell stock II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}

if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}

if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}

pre_p = price
}

if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}

return mp
}

27 DONE maximum subarray

  • State "DONE" from "WAITING" [2017-07-18 Tue 23:30]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}

size := len(nums)
max_sum := nums[0]
pre_sum := nums[0]
for i := 1; i < size; i += 1 {
if pre_sum > 0 {
pre_sum = nums[i] + pre_sum
} else {
pre_sum = nums[i]
}
if pre_sum > max_sum {
max_sum = pre_sum
}
}

return max_sum
}

28 missing number

1
2
3
4
5
6
7
8
9
func missingNumber(nums []int) int {
var sum int
for _, num := range nums {
sum += num
}

size := len(nums)
return size*(size+1)/2 - sum
}

29 max consecutive ones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findMaxCntecutiveOnes(nums []int) int {
var cnt, max_cnt int
for _, num := range nums {
if num == 0 {
if cnt > max_cnt {
max_cnt = cnt
}
cnt = 0
}

if num == 1 {
cnt += 1
}
}
if cnt > max_cnt {
max_cnt = cnt
}

return max_cnt
}

30 rotate array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func reverse(nums []int) {
size := len(nums)
mid := size / 2
for i := 0; i < mid; i += 1 {
nums[i], nums[size-i-1] = nums[size-i-1], nums[i]
}
}

func rotate(nums []int, k int) {
size := len(nums)
if size == 1 {
return
}
k = k % size
reverse(nums[0 : size-k])
reverse(nums[size-k : size])
reverse(nums)
}
1
2
3
4
5
func main() {
arr := []int{1,2,3,4,5,6,7}
rotate(arr, 3)
fmt.Println(arr)
}

31 find peak element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func findPeakElement(nums []int) int {
if len(nums) < 1 {
return -1
}
if len(nums) == 1 {
return 0
}

var pe int
size := len(nums)
for i := 0; i < size; i += 1 {
switch i {
case 0:
if nums[0] > nums[1] {
return 0
}
case size - 1:
if nums[size-1] > nums[size-2] {
return size - 1
}
default:
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
return i
}
}
}

return -1
}

32 maximum product subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}

func maxProduct(nums []int) int {
if len(nums) < 1 {
return 0
}

size := len(nums)
maxp_sub_arr := make([]int, size)
ng_maxp_sub_arr := make([]int, size)
maxp_sub_arr[0] = nums[0]
if maxp_sub_arr[0] < 0 {
ng_maxp_sub_arr[0] = maxp_sub_arr[0]
} else {
ng_maxp_sub_arr[0] = 1
}
for i := 1; i < size; i += 1 {
if nums[i] == 0 {
continue
}

if maxp_sub_arr[i-1] == 0 {
maxp_sub_arr[i] = nums[i]
if nums[i] < 0 {
ng_maxp_sub_arr[i] = maxp_sub_arr[i]
} else {
ng_maxp_sub_arr[i] = 1
}
}

if nums[i] > 0 {
maxp_sub_arr[i] = max(nums[i]*maxp_sub_arr[i-1], nums[i])
ng_maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
}

if nums[i] < 0 {
maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
ng_maxp_sub_arr[i] = min(nums[i]*maxp_sub_arr[i-1], nums[i])
}
}

maxp := maxp_sub_arr[0]
for _, subp := range maxp_sub_arr {
if subp > maxp {
maxp = subp
}
}

return maxp
}
1
2
3
func main() {
fmt.Println(maxProduct([]int{2,3,-2,4,0,-3,-4}))
}

33 minimum size subarray sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func minSubArrayLen(s int, nums []int) int {
if len(nums) < 0 {
return 0
}

var sub_sum, msub_arl, sub_arl int
size := len(nums)
msub_arl = size + 1
for index, num := range nums {
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
continue
}

if sub_sum+num >= s {
for {
if sub_arl < 1 {
break
}

del_num := nums[index-sub_arl]
sub_sum -= del_num
sub_arl -= 1
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
break
}
}

if sub_arl+1 < msub_arl {
msub_arl = sub_arl + 1
}
}
}

if msub_arl == size+1 {
msub_arl = 0
}

return msub_arl
}
1
2
3
func main() {
fmt.Println(minSubArrayLen(15, []int{5,1,3,5,10,7,4,9,2,8}))
}

34 array nesting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func arrayNesting(nums []int) int {
anl_arr := make([]int, len(nums))

var max_anl int
for _, num := range nums {
if anl_arr[num] > 0 {
continue
}

var anl int
next_num := num
for {
anl_arr[next_num] = 1
anl += 1

next_num = nums[next_num]
if next_num == num {
break
}
}

if anl > max_anl {
max_anl = anl
}
}

return max_anl
}
1
2
3
func main() {
fmt.Println(arrayNesting([]int{5,4,0,3,1,6,2}))
}

35 triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}

func minimumTotal(triangle [][]int) int {
pre_nums := triangle[0]
trg_size := len(triangle)
for i := 1; i < trg_size; i += 1 {
nums := triangle[i]
n_size := len(nums)
for j, _ := range nums {
switch j {
case 0:
nums[0] += pre[0]
case n_size - 1:
nums[n_size-1] += pre_nums[n_size-2]
default:
nums[j] += min(pre_nums[j-1], pre_nums[j])
}
}
pre_nums = nums
}

min_total := pre_nums[0]
for _, num := range pre_nums {
if num < min_total {
min_total = num
}
}

return min_total
}

36 subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func subsets(nums []int) [][]int {
if len(nums) < 1 {
return [][]int{[]int{}}
}

sub_sets := subsets(nums[1:])
sets := sub_sets
num := nums[0]
for _, set := range sub_sets {
nset := append([]int{num}, set...)
sets = append(sets, nset)
}

return sets
}

37 subsets II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type Item struct {
Num int
Count int
}

func subsetsWithDup(nums []int) [][]int {
num_M := make(map[int]int)
for _, num := range nums {
num_M[num] += 1
}

items := make([]*Item, 0)
for num, count := range num_M {
item := &Item{
Num: num,
Count: count,
}
items = append(items, item)
}

return subsets(items)
}

func subsetsHelper(item *Item, sub_sets [][]int) [][]int {
sets := sub_sets
for _, set := range sub_sets {
var _count int
for {
if _count == item.Count {
break
}
set = append([]int{item.Num}, set...)
sets = append(sets, set)
_count += 1
}
}
return sets
}

func subsets(items []*Item) [][]int {
if len(items) < 1 {
return [][]int{[]int{}}
}

return subsetsHelper(items[0], subsets(items[1:]))
}

38 search in rotated sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] == target {
return mid
}

if start == end {
break
}

if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}

if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}

return -1
}

39 search in rotated sorted array II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func search(nums []int, target int) bool {
start, end := 0, len(nums)-1
for start <= end {
if nums[start] == nums[end] {
if nums[start] == target {
return true
}

dup_num := nums[start]
for {
if start == end || nums[start] != dup_num {
break
}
start++
}

for {
if start == end || nums[end] != dup_num {
break
}
end--
}
}

mid := start + (end-start)/2
if nums[mid] == target {
return true
}

if start == end {
break
}

if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}

if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}

return false
}

40 search a 2d matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func searchMatrix(matrix [][]int, target int) bool {
length := len(matrix)
if length < 1 {
return false
}
start, end := 0, length-1
width := len(matrix[0])
for start <= end {
if start == end {
break
}
mid := start + (end-start)/2
if matrix[mid][0] > target {
end = mid - 1
} else if matrix[mid][0] < target {
if target > matrix[mid][width-1] {
start = mid + 1
} else {
start = mid
break
}
} else {
return true
}
}

return binary_search(matrix[start], target) != -1
}

func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}

return -1
}

41 sort colors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sortColors(nums []int) {
colors := make([]int, 3)
for _, num := range nums {
colors[num] += 1
}

var base int
for color, count := range colors {
for count > 0 {
nums[base] = color
count--
base++
}
}

return
}

42 set matrix zeroes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func setZeroes(matrix [][]int) {
length := len(matrix)
if length < 1 {
return
}
width := len(matrix[0])
row_M := make(map[int]bool, length)
col_M := make(map[int]bool, width)
for i := 0; i < length; i++ {
for j := 0; j < width; j++ {
if matrix[i][j] == 0 {
row_M[i] = true
col_M[j] = true
}
}
}

if len(row_M) > 0 {
for row, _ := range row_M {
for i := 0; i < width; i++ {
matrix[row][i] = 0
}
}
}

if len(col_M) > 0 {
for col, _ := range col_M {
for i := 0; i < length; i++ {
matrix[i][col] = 0
}
}
}

return
}

43 unique paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func uniquePaths(m int, n int) int {
if m < 2 {
return m
}

matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
matrix[0][i] = 1
}
matrix[1][0] = 1

pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
curr_row[j] = curr_row[j-1] + pre_row[j]
}
pre_row, curr_row = curr_row, pre_row
}

return pre_row[n-1]
}

44 unique paths II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m := len(obstacleGrid)
if m < 1 {
return 0
}
n := len(obstacleGrid[0])
if n < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}

matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
if obstacleGrid[0][i] == 1 {
break
}
matrix[0][i] = 1
}
if m > 1 && obstacleGrid[1][0] == 0 {
matrix[1][0] = 1
}

pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 0 {
if j > 0 {
curr_row[j] = curr_row[j-1] + pre_row[j]
} else {
curr_row[j] = pre_row[j]
}
} else {
curr_row[j] = 0
}
}
pre_row, curr_row = curr_row, pre_row
}

return pre_row[n-1]
}

45 spiral matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func spiralOrder(matrix [][]int) []int {
m := len(matrix)
if m < 1 {
return []int{}
}
n := len(matrix[0])
row_start := 0
row_end := m
col_start := 0
col_end := n
so_arr := make([]int, 0, m*n)
for {
for i := col_start; i < col_end; i++ {
so_arr = append(so_arr, matrix[row_start][i])
}
row_start += 1
if row_start == row_end {
break
}

for i := row_start; i < row_end; i++ {
so_arr = append(so_arr, matrix[i][col_end-1])
}
col_end -= 1
if col_start == col_end {
break
}

for i := col_end - 1; i >= col_start; i-- {
so_arr = append(so_arr, matrix[row_end-1][i])
}
row_end -= 1
if row_start == row_end {
break
}

for i := row_end - 1; i >= row_start; i-- {
so_arr = append(so_arr, matrix[i][col_start])
}
col_start += 1
if col_start == col_end {
break
}
}

return so_arr
}

46 spiral matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func generateMatrix(n int) [][]int {
if n == 0 {
return [][]int{}
}

matrix := make([][]int, n)
for i := 0; i < n; i++ {
matrix[i] = make([]int, n)
}
row_start := 0
row_end := n
col_start := 0
col_end := n
num := 1
for {
for i := col_start; i < col_end; i++ {
matrix[row_start][i] = num
num += 1
}
row_start += 1
if row_start == row_end {
break
}

for i := row_start; i < row_end; i++ {
matrix[i][col_end-1] = num
num += 1
}
col_end -= 1
if col_start == col_end {
break
}

for i := col_end - 1; i >= col_start; i-- {
matrix[row_end-1][i] = num
num += 1
}
row_end -= 1
if row_start == row_end {
break
}

for i := row_end - 1; i >= row_start; i-- {
matrix[i][col_start] = num
num += 1
}
col_start += 1
if col_start == col_end {
break
}
}
return matrix
}

47 merge intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func merge(intervals []Interval) []Interval {
size := len(intervals)
if size < 2 {
return intervals
}

sort.Slice(intervals,
func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})

merge_intervals := make([]Interval, 0)
interval := intervals[0]
for i := 1; i < size; i++ {
if interval.End >= intervals[i].Start {
if interval.End < intervals[i].End {
interval.End = intervals[i].End
}
} else {
merge_intervals = append(merge_intervals, interval)
interval = intervals[i]
}
}
if interval.Start != intervals[0].Start {
merge_intervals = append(merge_intervals, interval)
}
if len(merge_intervals) < 1 {
merge_intervals = append(merge_intervals, interval)
}

return merge_intervals
}

48 jump game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() < 2) {
return true;
}

if (nums[0]==0) {
return false;
}

deque<int> position_deq;
set<int> position_set;
position_deq.push_back(0);
position_set.insert(0);
while (position_deq.size()>0) {
int position = position_deq.front();
position_deq.pop_front();
if (nums[position] > 0) {
for (int i = 1; i <= nums[position]; i++) {
int new_position = position +i;
if (new_position == nums.size()-1) {
return true;
}

if (nums[new_position]>0 &&
position_set.find(new_position) != position_set.end()) {
position_deq.push_back(new_position);
}
}
}
}

return false;
}
};
1
2
3
4
5
6
7
8
9
10
func canJump(nums []int) bool {
size := len(nums)
var i, reach int
for ; i < size && i <= reach; i++ {
if i+nums[i] > reach {
reach = i + nums[i]
}
}
return i == size
}

49 search for a range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func searchRange(nums []int, target int) []int {
target_index := binary_search(nums, target)
if target_index == -1 {
return []int{-1, -1}
}

start_index := target_index
for {
s_index := binary_search(nums[:start_index], target)
if s_index == -1 {
break
}
start_index = s_index
}

end_index := target_index
for {
e_index := binary_search(nums[end_index+1:], target)
if e_index == -1 {
break
}
end_index += 1 + e_index
}

return []int{start_index, end_index}
}

func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}

return -1
}

50 rotate image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func rotate(matrix [][]int) {
if len(matrix) < 2 {
return
}

size := len(matrix)
for i := 0; i < size-1; i++ {
var tmp int
matrix[i][size-1], tmp = matrix[0][i], matrix[i][size-1]
matrix[size-1][size-i-1], tmp = tmp, matrix[size-1][size-i-1]
matrix[size-i-1][0], tmp = tmp, matrix[size-i-1][0]
matrix[0][i] = tmp
}

if size-2 > 0 {
sub_matrix := make([][]int, 0, size-2)
for i := 1; i < size-1; i++ {
sub_matrix = append(sub_matrix, matrix[i][1:size-1])
}
rotate(sub_matrix)
}
return
}

51 valid triangle number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func triangleNumber(nums []int) int {
if len(nums) < 3 {
return 0
}
sort.Ints(nums)
size := len(nums)

var count int
for i := 0; i < size-2; i++ {
for j := i + 1; j < size-1; j++ {
for k := j + 1; k < size; k++ {
if nums[i]+nums[j] <= nums[k] {
break
}
count++
}
}
}

return count
}

52 DONE task scheduler

  • State "DONE" from "TODO" [2018-03-07 Wed 21:55]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}
n += 1

task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}

task_num_arr := make([]int, 0)
for _, task_num := range task_M {
task_num_arr = append(task_num_arr, task_num)
}
sort.Ints(task_num_arr)

remain_tc_num := len(task_num_arr)
var interval_num int
for {
if remain_tc_num < 1 {
break
}
fmt.Println(remain_tc_num, interval_num, task_num_arr)

if remain_tc_num < n {
remain_max_tn := task_num_arr[remain_tc_num-1]
tn_index := remain_tc_num - 2
same_max_tn_num := 1
for {
if tn_index < 0 || task_num_arr[tn_index] < remain_max_tn {
break
}
same_max_tn_num += 1
tn_index -= 1
}
interval_num += (task_num_arr[remain_tc_num-1]-1)*n + same_max_tn_num
break
}

min_tn := task_num_arr[remain_tc_num-n]
tn_index := remain_tc_num - n + 1
same_min_tn_num := 1
for {
if tn_index == remain_tc_num || task_num_arr[tn_index] > min_tn {
break
}
same_min_tn_num += 1
tn_index += 1
}
interval_num += (min_tn) * n

rs_index := remain_tc_num - n
ls_index := rs_index + same_min_tn_num
fmt.Println(rs_index, ls_index, same_min_tn_num)
for {
if ls_index == remain_tc_num {
for {
if rs_index == remain_tc_num {
break
}
task_num_arr[rs_index] = task_num_arr[remain_tc_num-1]
rs_index += 1
}
break
}
task_num_arr[rs_index] = task_num_arr[ls_index] - min_tn
rs_index += 1
ls_index += 1
}
remain_tc_num -= same_min_tn_num
sort.Ints(task_num_arr)
}

return interval_num
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}

task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}

task_num_arr := make([]int, 26)
tn_index := 0
for _, task_num := range task_M {
task_num_arr[tn_index] = task_num
tn_index += 1
}
sort.Ints(task_num_arr)

var interval_num int
for {
if task_num_arr[25] <= 0 {
break
}

var tn_index int
for {
if tn_index > n {
break
}
if task_num_arr[25] == 0 {
break
}

if tn_index < 26 && task_num_arr[25-tn_index] > 0 {
task_num_arr[25-tn_index] -= 1
}
interval_num += 1
tn_index += 1
}
sort.Ints(task_num_arr)
}

return interval_num
}
1
2
3
4
5
6
7
package main



func main() {
fmt.Println(leastInterval([]byte("FJJAJFCHJBEGGFACIFJCJCHCADGHBFGCCAEBHJEIFDEACDBDJJCFDDJHAECDJDGGBCEGHIDHFEIBDEIECJGIDEDJCACCDIJBDHHJGBGAHEHEDEJEJCFCJGBCIIHFADGFCCFGCJBBICJJEGHCIGJIGGJGGEGBIJBHDHGFCHCDAGBHHBJCAFJGFEBFEBBAEFEHIICGJDHEFGGDEBFJJJDHEBDJIFCIEHFEGDECFEDEAIEADHGCIEGAHIGGAGFHJDFAGHBJAHBHCGFACCBIGGBCJJIEGDIJICGAJGFJFCFGJIEBGFADAIAEHFDDCBJIJHICDAGFIBEDCJGIHECEIIBBHJCFIDBFHFACAABDCAGBGFEGAAACJHHGCCBCEBEFIEEDIHGFAHBJBGHCCBGCBAEGAJGDCIGFGGAJEIDEAFAHCEDDDHIFFAFAACJDJHIFACBCACCHAJIBAIFJCIBCEEEJGFEIAAEBJHHHAHJEFEFGJDIDIFBJDAADFGBJHFADHCBAJHIFHEGBAFFACDGIIJHHCJGBADBFJDIAFFFFAEBCGHEBBAGDCCEACFGAIFBHJGCBHDAHBHHCAFICFACJIHHFBBDECJFCEAJECAEBAJFJJJHHCIEGGHJJHHHJHAGICECDGGFHDGHAEIDAHGEABFICAFBAIFGIFDABJBDFGJJAACHGFBIIJAHDFEFJBFCGEAGHEHHFIGCCGJBHFHDIBDIFHIDFGGEACAGHGHJFDFGDDCJCJGGGGHHGDEHGCBFIFCHJIAFDCFCEEDDCGBFEJCIEDBBIIIHCECJFGAIJDICGFIEIEFAGEJAIADAGJFEDIAEJICJBFBECEFGEJJIEDFCHHBGDIIFBGCFJBGJHDGCCIIEIBHBIGFHGCJDCEGFCHDACDHBCHIBAJCBDJDHFBAGGJIEFADHDBCAHFGBFHBHIJDHIBCDGAEAAIFIFBBIFAEIABGCFIAFIDHBIIBJFEBBBDCJEJJGDFFFGIHJJGDGF") 8))
}

53 DONE word search

  • State "DONE" from "TODO" [2017-07-24 Mon 00:27]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Coord {
int x;
int y;
char letter;
int seq_num;
int dir;
};

struct CoordComp {
bool operator() (const Coord& lhs, const Coord& rhs) const {
if (lhs.x<rhs.x) {
return true;
} else if (lhs.x>rhs.x) {
return false;
} else {
return lhs.y<rhs.y;
}
}
};

class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i=0; i < board.size(); i++) {
for (int j=0; j < board[i].size(); j++) {
if (board[i][j]==word[0]) {
Coord coord={i,j,word[0],0,0};
stack<Coord> coord_stk;
set<Coord,CoordComp> coord_set;
coord_stk.push(coord);
coord_set.insert(coord);
while (coord_stk.size()>0) {
Coord coord = coord_stk.top();
if (coord.seq_num == word.size()-1) {
return true;
}
coord_stk.pop();
coord_set.erase(coord);
int x, y;
x = coord.x;
y = coord.y;
for (int dir=coord.dir; dir<4; dir++) {
if (dir == 0 && y > 0 && board[x][y-1]==word[coord.seq_num+1]) {
coord.dir = 1;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y-1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 1 && x > 0 && board[x-1][y]==word[coord.seq_num+1]) {
coord.dir = 2;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x-1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 2
&& y < board[x].size()-1
&& board[x][y+1]==word[coord.seq_num+1]) {
coord.dir = 3;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y+1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 3
&& x < board.size()-1
&& board[x+1][y]==word[coord.seq_num+1]) {
coord.dir = 4;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x+1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
}
}
}
}
}

return false;
}
};

54 TODO next permutation

1
2
3
func nextPermutation(nums []int)  {

}

55 TODO 4sum

1
2
func fourSum(nums []int, target int) [][]int {
}

56 TODO 3sum closest

1
2
3
func threeSumClosest(nums []int, target int) int {

}

57 TODO 3sum

1
2
func threeSum(nums []int) [][]int {
}

58 DONE Image Smoother

  • State "DONE" from "STARTED" [2017-09-20 Wed 10:27]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func imageSmoother(M [][]int) [][]int {
m := len(M)
n := len(M[0])
if m == 0 || n == 0 {
return [][]int{}
}
dirs := [][]int{
[]int{0, 1}, []int{0, -1}, []int{1, 0}, []int{-1, 0},
[]int{-1, -1}, []int{1, 1}, []int{-1, 1}, []int{1, -1}}

sM := make([][]int, m)
for i := 0; i < m; i += 1 {
ar := make([]int, n)
for j := 0; j < n; j += 1 {
sum := M[i][j]
cnt := 1
for k := 0; k < len(dirs); k += 1 {
x := i + dirs[k][0]
y := j + dirs[k][1]
if x < 0 || x > m-1 || y < 0 || y > n-1 {
continue
}
sum += M[x][y]
cnt++
}
ar[j] = sum / cnt
}
sM[i] = ar
}
return sM
}

59 DONE Longest Continuous Increasing Subsequence

  • State "DONE" from [2017-09-20 Wed 22:35]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findLengthOfLCIS(nums []int) int {
if len(nums) < 1 {
return 0
}

var length, sub_length int
pre_num := nums[0]
for _, num := range nums {
if num > pre_num {
sub_length += 1
} else {
if sub_length > length {
length = sub_length
}
sub_length = 1
}
pre_num = num
}

if sub_length > length {
length = sub_length
}

return length
}

60 DONE Non-decreasing Array

  • State "DONE" from "STARTED" [2017-09-21 Thu 09:50]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func checkPossibility(nums []int) bool {
var cnt int
for i := 0; i < len(nums)-1; i += 1 {
if nums[i] > nums[i+1] {
if i == 0 || nums[i-1] <= nums[i+1] {
nums[i] = nums[i+1]
} else {
nums[i+1] = nums[i]
}
cnt += 1
}

if cnt > 1 {
return false
}
}

return true
}

61 Find All Duplicates in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findDuplicates(nums []int) []int {
marks := make([]int, len(nums))
for _, num := range nums {
marks[num-1] += 1
}

dups_nums := make([]int, 0)
for index, mark := range marks {
if mark > 1 {
dups_nums = append(dups_nums, index+1)
}
}
return dups_nums
}

62 TODO Beautiful Arrangement

1
2
3
func countArrangement(N int) int {

}

63 DONE Beautiful Arrangement II

  • State "DONE" from "TODO" [2018-03-09 Fri 23:05]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func constructArray(n int, k int) []int {
arr := make([]int, 0)
l, h := 1, 1+k
for {
arr = append(arr, l)
arr = append(arr, h)
l += 1
h -= 1

if l == h {
arr = append(arr, l)
break
}

if l > h {
break
}
}

for i := k + 2; i <= n; i += 1 {
arr = append(arr, i)
}

return arr
}
1
2
3
4
5
6
7
8
9
10
11
package main



func main() {
fmt.Println(constructArray(10, 1))
fmt.Println(constructArray(10, 3))
fmt.Println(constructArray(10, 5))
fmt.Println(constructArray(10, 7))
fmt.Println(constructArray(10, 9))
}

64 TODO Degree of an Array

1
2
func findShortestSubArray(nums []int) int {
}

65 DONE Toeplitz Matrix

  • State "DONE" from "TODO" [2018-03-07 Wed 22:36]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func isToeplitzMatrix(matrix [][]int) bool {
if len(matrix) < 2 {
return true
}

r_num := len(matrix)
c_num := len(matrix[0])

r_index := r_num - 1
c_index := 0

for {
if r_index == 0 && c_index == c_num {
break
}

rd_index := r_index + 1
cd_index := c_index + 1
num := matrix[r_index][c_index]
for {
if rd_index == r_num || cd_index == c_num {
break
}

if matrix[rd_index][cd_index] != num {
return false
}

rd_index += 1
cd_index += 1
}

if r_index > 0 {
r_index -= 1
} else {
c_index += 1
}
}

return true
}

66 DONE Insert Delete GetRandom O(1) - Duplicates allowed

  • State "DONE" from "TODO" [2018-03-26 Mon 18:07]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
"fmt"
"math/rand"
)

type RcPair struct {
Val int
MIndex int
}

type RandomizedCollection struct {
Nums []RcPair
NumM map[int][]int
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
return RandomizedCollection{
Nums: make([]RcPair, 0),
NumM: make(map[int][]int),
}
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
iArr, bExist := this.NumM[val]
if !bExist {
iArr = make([]int, 0)
}
rcPair := RcPair{
Val: val,
MIndex: len(iArr),
}
this.Nums = append(this.Nums, rcPair)
iArr = append(iArr, len(this.Nums)-1)
this.NumM[val] = iArr

return !bExist
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
if iArr, bExist := this.NumM[val]; bExist {
last_p := this.Nums[len(this.Nums)-1]
this.Nums[iArr[len(iArr)-1]] = last_p
this.NumM[last_p.Val][last_p.MIndex] = iArr[len(iArr)-1]
iArr = iArr[:len(iArr)-1]
this.Nums = this.Nums[:len(this.Nums)-1]
if len(iArr) == 0 {
delete(this.NumM, val)
} else {
this.NumM[val] = iArr
}
return true
} else {
return false
}
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
return this.Nums[rand.Intn(len(this.Nums))].Val
}

func (this *RandomizedCollection) Debug() {
fmt.Println(this.Nums)
fmt.Println(this.NumM)
}

func main() {
rc := Constructor()
rc.Insert(4)
rc.Insert(3)
rc.Insert(4)
rc.Insert(2)
rc.Insert(4)
rc.Debug()
rc.Remove(4)
rc.Debug()
rc.Remove(4)
rc.Remove(4)
rc.Debug()
}

67 DONE 第一个缺失的正数

  • State "DONE" from "TODO" [2018-04-07 Sat 22:41]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func firstMissingPositive(nums []int) int {
length := len(nums)
for i := 0; i < length; i += 1 {
p := nums[i]
for p > 0 && p <= length && nums[p-1] != p {
x := nums[p-1]
nums[p-1] = p
p = x
}
}

for i := 0; i < length; i += 1 {
if nums[i] != i+1 {
return i + 1
}
}

return length + 1
}
Last Updated 2018-04-25 Wed 22:16.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)

在Org-mode中执行Go代码

发表于 2017-06-12 | 分类于 org-mode |

在未使用 org-mode 前,学习和实验Go的特性(例如 context )的步骤如下:

  • 打开终端
  • 跳转到学习示例目录下
  • 创建子目录,例如 context , 然后跳入子目录, 创建 main.go 文件
  • 编写简单的示例代码
  • 编译和运行代码示例,若出错调试,返回上个步骤

上面的过程有些可精简,例如在IDE中,目录跳转可在对话框中完成,代码的编写,编译和运行都可在IDE中完成。 在IDE中流程如下:

  • 在学习示例目录下,创建一个新的示例工程
  • 编写简单的示例代码, 编译和运行

在IDE中,整个流程精简了很多。 作为语言使用者,我们可能需要把实验过的示例代码留存,以便能应用在日后的开发中。 上面的两个流程,都会根据实验的包或者语言特性,创建相应的子目录,经过这样的处理,代码示例都聚合到了一起,方便了翻阅和修改。 示例代码的执行结果,大多是直接输出到终端的,你要验证原有示例代码的执行结果,你必须要重新执行代码,因为执行结果并没有留存。 若是这个示例代码,是很久之前的,可能是一年以前的, 这个时候你看到代码的时候,可能会时一脸懵逼。 这个时候你会想,为什么当时没有多留些信息,让我知道,为什么做这个示例,以及这段代码完成了什么功能。

Org-mode 简单配置后, 可完美的解决以上问题,代码留存,执行结果留存,文学编程(在编码过程中书写文档)。

<img src="/images/go-babel/go-babel-example.jpeg” />

上图展示了一个子问题的各个部分,问题描述,解决方案,代码,以及代码的执行结果。 子问题对应 Org-mode 中的子目录,然后所有问题都可聚合在一个 Org-mode 文档中。 现在流程可简化为:

  • 跳转到 Org-mode 文档中
  • 创建子目录,书写解决方案,编码实现

借助 Org-mode 强大的特性,可很容易的复用代码以及查询。

对于 Org-mode 不熟悉的,可先浏览Org-mode的主页。 Org-mode 通过 Babel 执行代码,对此不熟悉的读者, 可阅读我之前翻译的文档。

1 ob-go

Babel 可执行多种语言的代码, 但官方的收录的语言支持中,没有Go。 但Go是如此的炙手可热,没有官方支持,肯定也会有先行者实现支持。 感谢 pope 在 ob-C 实现了ob-go , 实现了 Babel 对于Go的支持。

1.1 简介

ob-go 使 Org-babel 可执行Go代码。 与解释语言可直接执行不同,Go需要先编译为可执行文件,然后运行。 Go代码通过 go run 命令编译和运行。 若代码中没有 main 函数,默认情况下,代码会被包裹在简单的 main 函数中。 若 :package 选项没设置并且代码中没有声明 package , 则 main package 被声明。 示例如下,代码被执行,执行结果被回写到 buffer 中。

#+BEGIN_SRC go :imports "fmt"
  fmt.Println("Hello, org-mode")
#+END_SRC
#+RESULTS:
: Hello, org-mode

使用快捷键 C-c C-v v 可查看被扩展后的代码。

<img src="/images/go-babel/go-ob-ex.gif” />

1.2 Go特定的头参数(Header Arguments)

除了 Babel 的常规头参数之外,下面是一些Go语言特定的头文件。

:args
传递命令行参数到代码编译后的可执行文件,传递超过多参数,需要使用 list 。
:flags
传递给 go run 或者 go build 的flags(未使用成功)。
:main
若没设置 no , 代码将会被包裹在 main 函数中。默认 yes 。
:imports
为代码提供 imports 的快捷支持。 当处理 main 函数时,应该使用这个选项。 要 import 多个包,请使用 list 。
:package
设置当前代码块 tangle 时的包名。 需要: :main no 。 若没设置,同时代码中没有包名声明, main 包将被声明。
:var
ob-go 支持 Babel 的变量,不过目前还不完备。

2 配置

这里假设Go的开发环境已经配置完毕,同时你的机器上的 Emacs 和 Org-mode 都是最近的版本,对于 Babel 都是完整支持的。 由于 ob-go 没有并入 Org-mode 所以需要单独配置。 步骤如下:

  • M-x find-library ob-C , 找到的目录 org-plus-contrib
  • 新建 ob-go.el , 然后把 github中代码 复制到新建的文件中
  • 配置 org-babel-load-languages, 如下:
    (org-babel-do-load-languages
     'org-babel-load-languages
     '((python . t)
       (C . t)
       (go . t)
       (emacs-lisp . t)
       (shell . t)))

3 编码流程

最近在 LeetCode 上做编程训练,这里就以解决上面的问题的流程来做说明。

  • 在LeetCode页面上,仔细阅读和理解问题,这里以 Merge Two Binary Trees 为例
  • 跳转到 leetcode.org , 创建 merge two binary trees 子目录
  • 创建名为 merge-two-bt 的Go代码块
  • 通过快捷键 C-c '= 打开Go语言特定的编辑模式buffer中,然后编码。 在编码过程完成后, =C-c '= 完成并关闭编辑buffer;或者对自己编辑不满意, =C-c C-k 取消编辑并关闭编辑buffer。

    <img src="/images/go-babel/go-ob-leetcode.gif” />

  • 把定义好的代码块整合到一起,然后执行(完整代码)。

    <img src="/images/go-babel/go-ob-leetcode-cmp.gif” />

4 使用示例

4.1 导入多个包

#+BEGIN_SRC go :imports '("fmt" "time")
  fmt.Println("当前时间:", time.Now())
#+END_SRC
#+RESULTS:
: 当前时间: 2017-06-12 18:04:20.562355811 +0800 CST

4.2 命令行参数传递

#+BEGIN_SRC go :imports '("fmt" "os") :args '("bable" "golang")
  fmt.Println(os.Args[1], os.Args[2])
#+END_SRC
#+RESULTS:
: bable golang

4.3 多入参

#+NAME: sum
#+BEGIN_SRC go :imports "fmt" :var a=12 b=13
  fmt.Println(a+b)
#+END_SRC
#+RESULTS:
: 25
#+call: sum(a=22,b=23)
#+RESULTS:
: 45

4.4 代码组织

#+NAME: min
#+BEGIN_SRC  go
  func min(a, b int) int {
    if a > b {
      return b
    } else {
      return a
    }
  }
#+END_SRC
#+NAME: get-min
#+BEGIN_SRC go :var a=0 b=0 :imports "fmt" :noweb strip-export
  <<min>>
  func main() {
    fmt.Println(min(a,b))
  }
#+END_SRC
#+call: get-min(27, 23)
#+RESULTS:
: 23

5 总结

Org-mode于我来说,就是一个神器,打破了我对一个编辑器的认知,打破了我对一个信息收集器的认知。 Org-mode依托于强大的 Emacs, 借助于 Babel, 使文档和代码无缝的结合在了一起, 一会编码,一会记录, 一会调试,一会执行。 不失为,学习语言,尝试新工具的不二神器。 再来一段Go代码:

#+BEGIN_SRC go :imports "fmt"
  fmt.Println("Goodbye, Gopher!")
#+END_SRC
Last Updated 2017-12-24 Sun 23:05.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)
1234
Brantou

Brantou

39 日志
5 分类
46 标签
RSS
GitHub Twitter E-Mail Jianshu
© 2017 — 2018 Brantou
由 Hexo 强力驱动
|
主题 — NexT.Pisces v5.1.3
Hosted by GitHub Pages