math

package
v0.0.0-...-eb09a2a Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 19, 2022 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func AddBinary

func AddBinary(a string, b string) string
Example
package main

import (
	"fmt"
)

type question67 struct {
	para67
	ans67
}

// para 是参数
// one 代表第一个参数
type para67 struct {
	a string
	b string
}

// ans 是答案
// one 代表第一个答案
type ans67 struct {
	one string
}

func main() {

	qs := []question67{

		{
			para67{"11", "1"},
			ans67{"100"},
		},

		{
			para67{"1010", "1011"},
			ans67{"10101"},
		},
	}

	for _, q := range qs {
		_, p := q.ans67, q.para67
		fmt.Println(p, AddBinary(p.a, p.b))
	}
}
Output:

{11 1} 100
{1010 1011} 10101

func ClimbStairs

func ClimbStairs(n int) int
Example
package main

import (
	"fmt"
)

type question70 struct {
	para70
	ans70
}

// para 是参数
// one 代表第一个参数
type para70 struct {
	n int
}

// ans 是答案
// one 代表第一个答案
type ans70 struct {
	one int
}

func main() {

	qs := []question70{

		{
			para70{2},
			ans70{2},
		},

		{
			para70{3},
			ans70{3},
		},
	}

	for _, q := range qs {
		_, p := q.ans70, q.para70
		fmt.Println(p, ClimbStairs(p.n))
	}
}
Output:

{2} 2
{3} 3

func Divide

func Divide(dividend int, divisor int) int

解法一 递归版的二分搜索

Example
package main

import (
	"fmt"
)

type question29 struct {
	para29
	ans29
}

// para 是参数
// one 代表第一个参数
type para29 struct {
	dividend int
	divisor  int
}

// ans 是答案
// one 代表第一个答案
type ans29 struct {
	one int
}

func main() {

	qs := []question29{

		{
			para29{10, 3},
			ans29{3},
		},

		{
			para29{7, -3},
			ans29{-2},
		},

		{
			para29{-1, 1},
			ans29{-1},
		},

		{
			para29{1, -1},
			ans29{-1},
		},
	}

	for _, q := range qs {
		_, p := q.ans29, q.para29
		fmt.Println(p, Divide(p.dividend, p.divisor))
	}

}
Output:

{10 3} 3
{7 -3} -2
{-1 1} -1
{1 -1} -1

func Divide1

func Divide1(divided int, divisor int) int

解法二 非递归版的二分搜索

func FourSum

func FourSum(nums []int, target int) (quadruplets [][]int)

解法一 双指针

Example
package main

import (
	"fmt"
)

type question18 struct {
	para18
	ans18
}

// para 是参数
// one 代表第一个参数
type para18 struct {
	a []int
	t int
}

// ans 是答案
// one 代表第一个答案
type ans18 struct {
	one [][]int
}

func main() {

	qs := []question18{

		{
			para18{[]int{1, 1, 1, 1}, 4},
			ans18{[][]int{{1, 1, 1, 1}}},
		},

		{
			para18{[]int{0, 1, 5, 0, 1, 5, 5, -4}, 11},
			ans18{[][]int{{-4, 5, 5, 5}, {0, 1, 5, 5}}},
		},

		{
			para18{[]int{1, 0, -1, 0, -2, 2}, 0},
			ans18{[][]int{{-1, 0, 0, 1}, {-2, -1, 1, 2}, {-2, 0, 0, 2}}},
		},

		{
			para18{[]int{1, 0, -1, 0, -2, 2, 0, 0, 0, 0}, 0},
			ans18{[][]int{{-1, 0, 0, 1}, {-2, -1, 1, 2}, {-2, 0, 0, 2}, {0, 0, 0, 0}}},
		},

		{
			para18{[]int{1, 0, -1, 0, -2, 2, 0, 0, 0, 0}, 1},
			ans18{[][]int{{-1, 0, 0, 2}, {-2, 0, 1, 2}, {0, 0, 0, 1}}},
		},
	}

	for _, q := range qs {
		_, p := q.ans18, q.para18
		fmt.Println(p, FourSum(p.a, p.t))
	}

}
Output:

{[1 1 1 1] 4} [[1 1 1 1]]
{[-4 0 0 1 1 5 5 5] 11} [[-4 5 5 5] [0 1 5 5]]
{[-2 -1 0 0 1 2] 0} [[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]]
{[-2 -1 0 0 0 0 0 0 1 2] 0} [[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] [0 0 0 0]]
{[-2 -1 0 0 0 0 0 0 1 2] 1} [[-2 0 1 2] [-1 0 0 2] [0 0 0 1]]

func FourSum1

func FourSum1(nums []int, target int) [][]int

解法二 kSum

func FourSum2

func FourSum2(nums []int, target int) [][]int

解法三

func MinPathSum

func MinPathSum(grid [][]int) int

解法一 原地 DP,无辅助空间

Example
package main

import (
	"fmt"
)

type question64 struct {
	para64
	ans64
}

// para 是参数
// one 代表第一个参数
type para64 struct {
	og [][]int
}

// ans 是答案
// one 代表第一个答案
type ans64 struct {
	one int
}

func main() {

	qs := []question64{

		{
			para64{[][]int{
				{1, 3, 1},
				{1, 5, 1},
				{4, 2, 1},
			}},
			ans64{7},
		},
	}

	for _, q := range qs {
		_, p := q.ans64, q.para64
		fmt.Println(p, MinPathSum(p.og))
	}
}
Output:

{[[1 4 5] [2 7 6] [6 8 7]]} 7

func MinPathSum1

func MinPathSum1(grid [][]int) int

解法二 最原始的方法,辅助空间 O(n^2)

func Palindrome

func Palindrome(x int) bool

解法一

Example
package main

import (
	"fmt"
)

type question9 struct {
	para9
	ans9
}

// para 是参数
// one 代表第一个参数
type para9 struct {
	one int
}

// ans 是答案
// one 代表第一个答案
type ans9 struct {
	one bool
}

func main() {

	qs := []question9{

		{
			para9{121},
			ans9{true},
		},

		{
			para9{-121},
			ans9{false},
		},

		{
			para9{10},
			ans9{false},
		},

		{
			para9{321},
			ans9{false},
		},

		{
			para9{-123},
			ans9{false},
		},

		{
			para9{120},
			ans9{false},
		},

		{
			para9{1534236469},
			ans9{false},
		},
	}

	for _, q := range qs {
		_, p := q.ans9, q.para9
		fmt.Println(p.one, Palindrome(p.one))
	}

}
Output:

	121 true
-121 false
10 false
321 false
-123 false
120 false
1534236469 false

func Palindrome1

func Palindrome1(x int) bool

解法二 数字转字符串

func Pow

func Pow(x float64, n int) float64

时间复杂度 O(log n),空间复杂度 O(1)

Example
package main

import (
	"fmt"
)

type question50 struct {
	para50
	ans50
}

// para 是参数
// one 代表第一个参数
type para50 struct {
	x float64
	n int
}

// ans 是答案
// one 代表第一个答案
type ans50 struct {
	one float64
}

func main() {

	qs := []question50{

		{
			para50{2.00000, 10},
			ans50{1024.00000},
		},

		{
			para50{2.10000, 3},
			ans50{9.26100},
		},

		{
			para50{2.00000, -2},
			ans50{0.25000},
		},
	}

	for _, q := range qs {
		_, p := q.ans50, q.para50
		fmt.Println(p, Pow(p.x, p.n))
	}
}
Output:

{2 10} 1024
{2.1 3} 9.261000000000001
{2 -2} 0.25

func Reverse7

func Reverse7(x int) int
Example
package main

import (
	"fmt"
)

type question7 struct {
	para7
	ans7
}

// para 是参数
// one 代表第一个参数
type para7 struct {
	one int
}

// ans 是答案
// one 代表第一个答案
type ans7 struct {
	one int
}

func main() {

	qs := []question7{

		{
			para7{321},
			ans7{123},
		},

		{
			para7{-123},
			ans7{-321},
		},

		{
			para7{120},
			ans7{21},
		},

		{
			para7{1534236469},
			ans7{0},
		},
	}

	for _, q := range qs {
		_, p := q.ans7, q.para7
		fmt.Println(p.one, Reverse7(p.one))
	}

}
Output:

	321 123
-123 -321
120 21
1534236469 0

func Sqrt

func Sqrt(x int) int

解法一 二分, 找到最后一个满足 n^2 <= x 的整数n

Example
package main

import (
	"fmt"
)

type question69 struct {
	para69
	ans69
}

// para 是参数
// one 代表第一个参数
type para69 struct {
	one int
}

// ans 是答案
// one 代表第一个答案
type ans69 struct {
	one int
}

func main() {

	qs := []question69{

		{
			para69{4},
			ans69{2},
		},

		{
			para69{8},
			ans69{2},
		},
	}

	for _, q := range qs {
		_, p := q.ans69, q.para69
		fmt.Println(p, Sqrt(p.one))
	}
}
Output:

{4} 2
{8} 2

func Sqrt1

func Sqrt1(x int) int

解法二 牛顿迭代法 https://en.wikipedia.org/wiki/Integer_square_root

func ThreeSum

func ThreeSum(nums []int) [][]int

解法一 最优解,双指针 + 排序

Example
package main

import (
	"fmt"
)

type question15 struct {
	para15
	ans15
}

// para 是参数
// one 代表第一个参数
type para15 struct {
	a []int
}

// ans 是答案
// one 代表第一个答案
type ans15 struct {
	one [][]int
}

func main() {

	qs := []question15{

		{
			para15{[]int{0, 0, 0}},
			ans15{[][]int{{0, 0, 0}}},
		},

		{
			para15{[]int{-1, 0, 1, 2, -1, -4}},
			ans15{[][]int{{-1, 0, 1}, {-1, -1, 2}}},
		},

		{
			para15{[]int{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6}},
			ans15{[][]int{{-4, -2, 6}, {-4, 0, 4}, {-4, 1, 3}, {-4, 2, 2}, {-2, -2, 4}, {-2, 0, 2}}},
		},

		{
			para15{[]int{5, -7, 3, -3, 5, -10, 4, 8, -3, -8, -3, -3, -1, -8, 6, 4, -4, 7, 2, -5, -2, -7, -3, 7, 2, 4, -6, 5}},
			ans15{[][]int{{-10, 2, 8}, {-10, 3, 7}, {-10, 4, 6}, {-10, 5, 5}, {-8, 2, 6}, {-8, 3, 5}, {-8, 4, 4}, {-7, -1, 8},
				{-7, 2, 5}, {-7, 3, 4}, {-6, -2, 8}, {-6, -1, 7}, {-6, 2, 4}, {-5, -3, 8}, {-5, -2, 7}, {-5, -1, 6}, {-5, 2, 3},
				{-4, -3, 7}, {-4, -2, 6}, {-4, -1, 5}, {-4, 2, 2}, {-3, -3, 6}, {-3, -2, 5}, {-3, -1, 4}, {-2, -1, 3}}},
		},
	}

	for _, q := range qs {
		_, p := q.ans15, q.para15
		fmt.Println(p, ThreeSum(p.a))
	}

}
Output:

{[0 0 0]} [[0 0 0]]
{[-4 -1 -1 0 1 2]} [[-1 -1 2] [-1 0 1]]
{[-4 -2 -2 -2 0 1 2 2 2 3 3 4 4 6 6]} [[-4 -2 6] [-2 -2 4] [-4 0 4] [-2 0 2] [-4 1 3] [-4 2 2]]
{[-10 -8 -8 -7 -7 -6 -5 -4 -3 -3 -3 -3 -3 -2 -1 2 2 3 4 4 4 5 5 5 6 7 7 8]} [[-5 -3 8] [-4 -3 7] [-3 -3 6] [-6 -2 8] [-5 -2 7] [-4 -2 6] [-3 -2 5] [-7 -1 8] [-6 -1 7] [-5 -1 6] [-4 -1 5] [-3 -1 4] [-2 -1 3] [-10 2 8] [-8 2 6] [-7 2 5] [-6 2 4] [-5 2 3] [-4 2 2] [-10 3 7] [-8 3 5] [-7 3 4] [-10 4 6] [-8 4 4] [-10 5 5]]

func ThreeSum1

func ThreeSum1(nums []int) [][]int

解法二

func ThreeSumClosest

func ThreeSumClosest(nums []int, target int) int

解法一 O(n^2)

Example
package main

import (
	"fmt"
)

type question16 struct {
	para16
	ans16
}

// para 是参数
// one 代表第一个参数
type para16 struct {
	a      []int
	target int
}

// ans 是答案
// one 代表第一个答案
type ans16 struct {
	one int
}

func main() {

	qs := []question16{

		{
			para16{[]int{-1, 0, 1, 1, 55}, 3},
			ans16{2},
		},

		{
			para16{[]int{0, 0, 0}, 1},
			ans16{0},
		},

		{
			para16{[]int{-1, 2, 1, -4}, 1},
			ans16{2},
		},

		{
			para16{[]int{1, 1, -1}, 0},
			ans16{1},
		},

		{
			para16{[]int{-1, 2, 1, -4}, 1},
			ans16{2},
		},
	}

	for _, q := range qs {
		_, p := q.ans16, q.para16
		fmt.Println(p, ThreeSumClosest(p.a, p.target))
	}
}
Output:

{[-1 0 1 1 55] 3} 2
{[0 0 0] 1} 0
{[-4 -1 1 2] 1} 2
{[-1 1 1] 0} 1
{[-4 -1 1 2] 1} 2

func ThreeSumClosest1

func ThreeSumClosest1(nums []int, target int) int

解法二 暴力解法 O(n^3)

func TwoSum

func TwoSum(nums []int, target int) []int
Example
package main

import (
	"fmt"
)

type question1 struct {
	para1
	ans1
}

// para 是参数
// one 代表第一个参数
type para1 struct {
	nums   []int
	target int
}

// ans 是答案
// one 代表第一个答案
type ans1 struct {
	one []int
}

func main() {

	qs := []question1{
		{
			para1{[]int{3, 2, 4}, 6},
			ans1{[]int{1, 2}},
		},

		{
			para1{[]int{3, 2, 4}, 5},
			ans1{[]int{0, 1}},
		},

		{
			para1{[]int{0, 8, 7, 3, 3, 4, 2}, 11},
			ans1{[]int{1, 3}},
		},

		{
			para1{[]int{0, 1}, 1},
			ans1{[]int{0, 1}},
		},

		{
			para1{[]int{0, 3}, 5},
			ans1{[]int{}},
		},
		// 如需多个测试,可以复制上方元素。
	}

	for _, q := range qs {
		_, p := q.ans1, q.para1
		fmt.Println(p, TwoSum(p.nums, p.target))
	}

}
Output:

{[3 2 4] 6} [1 2]
{[3 2 4] 5} [0 1]
{[0 8 7 3 3 4 2] 11} [1 3]
{[0 1] 1} [0 1]
{[0 3] 5} []

func UniquePaths

func UniquePaths(m int, n int) int
Example
package main

import (
	"fmt"
)

type question62 struct {
	para62
	ans62
}

// para 是参数
// one 代表第一个参数
type para62 struct {
	m int
	n int
}

// ans 是答案
// one 代表第一个答案
type ans62 struct {
	one int
}

func main() {

	qs := []question62{

		{
			para62{3, 2},
			ans62{3},
		},

		{
			para62{7, 3},
			ans62{28},
		},

		{
			para62{1, 2},
			ans62{1},
		},
	}

	for _, q := range qs {
		_, p := q.ans62, q.para62
		fmt.Println(p, UniquePaths(p.m, p.n))
	}
}
Output:

{3 2} 3
{7 3} 28
{1 2} 1

func UniquePathsWithObstacles

func UniquePathsWithObstacles(obstacleGrid [][]int) int
Example
package main

import (
	"fmt"
)

type question63 struct {
	para63
	ans63
}

// para 是参数
// one 代表第一个参数
type para63 struct {
	og [][]int
}

// ans 是答案
// one 代表第一个答案
type ans63 struct {
	one int
}

func main() {

	qs := []question63{

		{
			para63{[][]int{
				{0, 0, 0},
				{0, 1, 0},
				{0, 0, 0},
			}},
			ans63{2},
		},

		{
			para63{[][]int{
				{0, 0},
				{1, 1},
				{0, 0},
			}},
			ans63{0},
		},

		{
			para63{[][]int{
				{0, 1, 0, 0},
				{1, 0, 0, 0},
				{0, 0, 0, 0},
			}},
			ans63{0},
		},
	}

	for _, q := range qs {
		_, p := q.ans63, q.para63
		fmt.Println(p, UniquePathsWithObstacles(p.og))
	}
}
Output:

{[[0 0 0] [0 1 0] [0 0 0]]} 2
{[[0 0] [1 1] [0 0]]} 0
{[[0 1 0 0] [1 0 0 0] [0 0 0 0]]} 0

Types

type ListNode

type ListNode = structures.ListNode

ListNode define

func AddTwoNumbers

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode
Example
package main

import (
	"fmt"

	"github.com/gopperin/leetcode/structures"
)

type question2 struct {
	para2
	ans2
}

// para 是参数
// one 代表第一个参数
type para2 struct {
	one     []int
	another []int
}

// ans 是答案
// one 代表第一个答案
type ans2 struct {
	one []int
}

func main() {

	qs := []question2{

		{
			para2{[]int{}, []int{}},
			ans2{[]int{}},
		},

		{
			para2{[]int{1}, []int{1}},
			ans2{[]int{2}},
		},

		{
			para2{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}},
			ans2{[]int{2, 4, 6, 8}},
		},

		{
			para2{[]int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},
			ans2{[]int{2, 4, 6, 8, 0, 1}},
		},

		{
			para2{[]int{1}, []int{9, 9, 9, 9, 9}},
			ans2{[]int{0, 0, 0, 0, 0, 1}},
		},

		{
			para2{[]int{9, 9, 9, 9, 9}, []int{1}},
			ans2{[]int{0, 0, 0, 0, 0, 1}},
		},

		{
			para2{[]int{2, 4, 3}, []int{5, 6, 4}},
			ans2{[]int{7, 0, 8}},
		},

		{
			para2{[]int{1, 8, 3}, []int{7, 1}},
			ans2{[]int{8, 9, 3}},
		},
		// 如需多个测试,可以复制上方元素。
	}

	for _, q := range qs {
		_, p := q.ans2, q.para2
		fmt.Println(p, structures.List2Ints(AddTwoNumbers(structures.Ints2List(p.one), structures.Ints2List(p.another))))
	}

}
Output:

{[] []} []
{[1] [1]} [2]
{[1 2 3 4] [1 2 3 4]} [2 4 6 8]
{[1 2 3 4 5] [1 2 3 4 5]} [2 4 6 8 0 1]
{[1] [9 9 9 9 9]} [0 0 0 0 0 1]
{[9 9 9 9 9] [1]} [0 0 0 0 0 1]
{[2 4 3] [5 6 4]} [7 0 8]
{[1 8 3] [7 1]} [8 9 3]

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL