leetcode（简单）_leetcode简单

两数之和

解法1：

func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				return []int{i,j}
			}
		}
	}
	return nil
}
1
2
3
4
5
6
7
8
9
10

解法2：

func twoSum(nums []int, target int) []int {
	var tmp = make(map[int]int, len(nums))
	for index, v := range nums {
		index2, ok := tmp[target-v]
		if ok {
			return []int{index2, index}
		}
		tmp[v] = index
	}
	return nil
}
1
2
3
4
5
6
7
8
9
10
11

回文数

解法1：

func isPalindrome(x int) bool {
	var num = 0
	var tmp = x
	if x < 0 {
		return false
	}
	for tmp > 0 {
		num = num*10 + tmp%10
		tmp /= 10
	}
	return x == num
}

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

解法2：

func isPalindrome(x int) bool {
	s := strconv.Itoa(x)
	lenS := len(s)
	for i := 0; i < (lenS >> 1); i++ {
		if s[i] != s[lenS-i-1] {
			return false
		}
	}
	return true
}
1
2
3
4
5
6
7
8
9
10

罗马数字转整数

func romanToInt(s string) int {
	var sum = 0
	var weight = make(map[uint8]int, 7)
	weight['I'] = 1
	weight['V'] = 5
	weight['X'] = 10
	weight['L'] = 50
	weight['C'] = 100
	weight['D'] = 500
	weight['M'] = 1000

	var lenS = len(s)
	for i := 0; i < lenS; i++ {
		if i == lenS-1 {
			return sum + weight[s[i]]
		}
		if s[i] == 'I' && (s[i+1] == 'X' || s[i+1] == 'V') {
			sum += weight[s[i+1]] - weight[s[i]]
			i++
		} else if s[i] == 'X' && (s[i+1] == 'L' || s[i+1] == 'C') {
			sum += weight[s[i+1]] - weight[s[i]]
			i++
		} else if s[i] == 'C' && (s[i+1] == 'D' || s[i+1] == 'M') {
			sum += weight[s[i+1]] - weight[s[i]]
			i++
		} else {
			sum += weight[s[i]]
		}
	}
	return 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

最长公共前缀

解法1：分治

func solve(strs []string, l int, r int) string {
	if l == r {
		return strs[l]
	}
	mid := (l + r) >> 1
	var lComment string
	var rComment string
	if l <= mid {
		lComment = solve(strs, l, mid)
	}
	if r >= mid+1 {
		rComment = solve(strs, mid+1, r)
	}
	if len(lComment) > len(rComment) {
		tmp := lComment
		lComment = rComment
		rComment = tmp
	}
	for i := 0; i < len(lComment); i++ {
		if lComment[i] != rComment[i] {
			return rComment[0:i]
		}
	}
	return lComment
}

func longestCommonPrefix(strs []string) string {
	lenS := len(strs)
	ans := solve(strs, 0, lenS-1)
	return ans
}
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

解法2：纵向扫描

func longestCommonPrefix(strs []string) string {
	var tmp = ""
	lenS := len(strs[0])
	for i := 0; i < lenS; i++ {
		var cur = string(strs[0][i])
		for _, v := range strs {
			if !strings.HasPrefix(v, tmp+cur) {
				return tmp
			}
		}
		tmp = tmp + cur
	}
	return tmp
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法3：横向扫描

func longestCommonPrefix(strs []string) string {
	var ans = strs[0]
	for _, v := range strs {
		if ans == "" {
			return ans
		}
		var tmp = ""
		var lenA = len(ans)
		for i := 0; i < lenA; i++ {
			var cur = string(ans[i])
			if !strings.HasPrefix(v, tmp+cur) {
				ans = tmp
				break
			}
			tmp = tmp + cur
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

有效的括号

func isValid(s string) bool {
	var Stack []uint8
	Stack = make([]uint8, len(s))
	var top = 0
	for i := 0; i < len(s); i++ {
		if top == 0 {
			Stack[top] = s[i]
			top++
		} else if s[i] == ')' {
			if Stack[top-1] == '(' {
				top--
			} else {
				return false
			}
		} else if s[i] == ']' {
			if Stack[top-1] == '[' {
				top--
			} else {
				return false
			}
		} else if s[i] == '}' {
			if Stack[top-1] == '{' {
				top--
			} else {
				return false
			}
		} else {
			Stack[top] = s[i]
			top++
		}
	}
	return top == 0
}
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 mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	var pre *ListNode
	var head *ListNode
	if list1.Val <= list2.Val {
		head = list1
	} else {
		head = list2
	}
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			pre = list1
			list1 = list1.Next
		} else {
			if pre == nil {
				next := list2.Next
				list2.Next = list1
				pre = list2
				list2 = next
			} else {
				next := list2.Next
				list2.Next = list1
				pre.Next = list2
				pre = list2
				list2 = next
			}
		}
	}
	if list2 != nil && pre != nil {
		pre.Next = list2
	}
	return 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

删除有序数组中的重复项

func removeDuplicates(nums []int) int {
	var cnt = 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == nums[i-1] {
			continue
		}
		nums[cnt] = nums[i]
		cnt++
	}
	return cnt
}

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

移除元素

func removeElement(nums []int, val int) int {
	var cnt = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != val {
			nums[cnt] = nums[i]
			cnt++
		}
	}
	return cnt
}
1
2
3
4
5
6
7
8
9
10

实现strStr

解法1：暴力

func strStr(haystack string, needle string) int {
	var cnt int
	var cur int
	var lenH = len(haystack)
	var lenN = len(needle)
	for i := 0; i < lenH; i++ {
		cur = i
		cnt = 0
		for cur < lenH && cnt < lenN && haystack[cur] == needle[cnt] {
			cur++
			cnt++
		}
		if cnt == lenN {
			return i
		}
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法2：KMP

func getNext(needle string) []int {
	var i = 0
	var j = -1
	var next = make([]int, len(needle))
	next[0] = -1
	for i < len(needle)-1 {
		if j == -1 || needle[i] == needle[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
	return next
}

func strStr(haystack string, needle string) int {
	next := getNext(needle)
	var j = 0
	var i = 0
	for i < len(haystack) {
		if j == -1 || haystack[i] == needle[j] {
			i++
			j++
			if j == len(needle) {
				return i - len(needle)
			}
		} else {
			j = next[j]
		}
	}
	return -1
}

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 searchInsert(nums []int, target int) int {
	for i := 0; i < len(nums); i++ {
		if nums[i] >= target {
			return i
		}
	}
	return len(nums)
}
1
2
3
4
5
6
7
8

最大数组和

解法1：贪心

func maxSubArray(nums []int) int {
	lenN := len(nums)
	if lenN == 0 {
		return 0
	}
	var ans = nums[0]
	var cur = ans
	if cur < 0 {
		cur = 0
	}
	for i := 1; i < lenN; i++ {
		cur += nums[i]
		if ans < cur {
			ans = cur
		}
		if cur < 0 {
			cur = 0
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2：分治

func f(nums []int, l int, r int) int {
	var m = (l + r) >> 1
	sumL := 0
	ansL := nums[m]
	sumR := 0
	ansR := nums[m+1]
	for i := m; i >= l; i-- {
		sumL += nums[i]
		if sumL > ansL {
			ansL = sumL
		}
	}
	for i := m + 1; i <= r; i++ {
		sumR += nums[i]
		if sumR > ansR {
			ansR = sumR
		}
	}
	return ansR + ansL
}

func MaxSum(nums []int, l int, r int) int {
	if l == r {
		return nums[l]
	}
	m := (l + r) >> 1
	lMax := MaxSum(nums, l, m)
	rMax := MaxSum(nums, m+1, r)
	cMax := lMax
	if rMax > lMax {
		cMax = rMax
	}
	lrMax := f(nums, l, r)
	if lrMax > cMax {
		cMax = lrMax
	}
	return cMax
}

func maxSubArray(nums []int) int {
	return MaxSum(nums, 0, len(nums)-1)
}

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 lengthOfLastWord(s string) int {
	s = strings.TrimSpace(s)
	list := strings.Split(s, " ")
	return len(list[len(list)-1])
}
1
2
3
4
5

加一

func plusOne(digits []int) []int {
	var toward = 1
	var lenS = len(digits)
	var cur = lenS - 1
	for cur >= 0 {
		digits[cur] += toward
		if digits[cur] != 10 {
			return digits
		} else {
			digits[cur] = 0
			cur--
		}
	}
	digits = make([]int, lenS+1)
	digits[0] = 1
	return digits
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二进制求和

func addBinary(a string, b string) string {
	var ans = ""
	var flag = 0
	var cur = 0
	lenA, lenB := len(a), len(b)
	n := lenA
	if lenB > lenA {
		n = lenB
	}
	for i := 0; i < n; i++ {
		if i < lenA {
			cur += int(a[lenA-i-1] - '0')
		}
		if i < lenB {
			cur += int(b[lenB-i-1] - '0')
		}
		cur += flag
		flag = cur / 2
		ans = strconv.Itoa(cur%2) + ans
		cur = 0
	}
	if flag != 0 {
		ans = "1" + ans
	}
	return ans
}

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

x的平方根

解法1：直接调库

func mySqrt(x int) int {
	y := float64(x)
	return int(math.Sqrt(y))
}
1
2
3
4

解法2：袖珍计算器算法

func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	ans := int(math.Exp(0.5 * math.Log(float64(x))))
	if (ans+1)*(ans+1) <= x {
		ans++
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10

解法3：二分法

func mySqrt(x int) int {
	var l = 0
	var r = x
	var mid int
	for l <= r {
		mid = (l + r) >> 1
		if mid*mid > x {
			r = mid - 1
		} else if mid*mid < x {
			l = mid + 1
		} else {
			return mid
		}
	}
	return r
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

爬楼梯

解法1：非递归

func climbStairs(n int) int {
	p, q, r := 1, 1, 1
	for i := 1; i < n; i++ {
		p = q + r
		r = q
		q = p
	}
	return p
}
1
2
3
4
5
6
7
8
9

解法2：非递归

func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	return climbStairs(n-1) + climbStairs(n-2)
}
1
2
3
4
5
6
7
8
9

解法3：矩阵快速幂

func pow(a [2][2]int, b [2][2]int) (res [2][2]int) {
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			tmp := 0
			for k := 0; k < 2; k++ {
				tmp += a[i][k] * b[k][j]
			}
			res[i][j] = tmp
		}
	}
	return
}

func climbStairs(n int) int {
	res := [2][2]int{
		{1, 0},
		{0, 1},
	}
	tmp := [2][2]int{
		{1, 1},
		{1, 0},
	}
	for ; n > 0; n >>= 1 {
		if n&1 == 1 {
			res = pow(tmp, res)
		}
		tmp = pow(tmp, tmp)
	}
	return res[0][0]
}
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 deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	p := head
	pre := p
	p = p.Next
	for p != nil {
		if pre.Val == p.Val {
			pre.Next = p.Next
			p = p.Next
		} else {
			pre = p
			p = p.Next
		}
	}
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

合并两个有序数组

func merge(nums1 []int, m int, nums2 []int, n int) {
	if m == 0 {
		copy(nums1, nums2)
		return
	} else if n == 0 {
		return
	}
	cur := n + m - 1
	cur_nums1 := m - 1
	cur_nums2 := n - 1
	for cur_nums1 >= 0 && cur_nums2 >= 0 {
		if nums1[cur_nums1] > nums2[cur_nums2] {
			nums1[cur] = nums1[cur_nums1]
			cur_nums1--
		} else {
			nums1[cur] = nums2[cur_nums2]
			cur_nums2--
		}
		cur--
	}
	for cur_nums2 >= 0 {
		nums1[cur] = nums2[cur_nums2]
		cur_nums2--
		cur--
	}
}
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

二叉树的中序遍历

解法1：递归

func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	left_arr := inorderTraversal(root.Left)
	right_arr := inorderTraversal(root.Right)
	left_arr = append(left_arr, root.Val)
	left_arr = append(left_arr, right_arr...)
	return left_arr
}

1
2
3
4
5
6
7
8
9
10
11

解法2：非递归

func inorderTraversal(root *TreeNode) []int {
	var Stack []*TreeNode
	var res []int
	for root != nil || len(Stack) > 0 {
		for root != nil {
			Stack = append(Stack, root)
			root = root.Left
		}
		root = Stack[len(Stack)-1]
		Stack = Stack[:len(Stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

相同的树

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil || q == nil {
		if p == nil && q == nil {
			return true
		}
		return false
	}
	if p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12

对称二叉树

func check(left *TreeNode, right *TreeNode) bool {
	if left == nil || right == nil {
		if left == nil && right == nil {
			return true
		}
		return false
	}
	return left.Val == right.Val && check(left.Left, right.Right) && check(left.Right, right.Left)
}

func isSymmetric(root *TreeNode) bool {
	if root.Left == nil || root.Right == nil {
		if root.Left == nil && root.Right == nil {
			return true
		}
		return false
	}
	return check(root.Left, root.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树的最大深度

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l_deep := maxDepth(root.Left) + 1
	r_deep := maxDepth(root.Right) + 1
	if r_deep > l_deep {
		return r_deep
	}
	return l_deep
}
1
2
3
4
5
6
7
8
9
10
11

将有序数组转换为二叉搜索树

func build(nums []int, l int, r int) *TreeNode {
	if l >= r {
		return nil
	}
	cur := new(TreeNode)
	mid := (l + r) >> 1
	cur.Val = nums[mid]
	cur.Left = build(nums, l, mid)
	cur.Right = build(nums, mid+1, r)
	return cur
}

func sortedArrayToBST(nums []int) *TreeNode {
	return build(nums, 0, len(nums))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

平衡二叉树

func height(root *TreeNode) int {
	if root == nil {
		return 0
	}
	lh := height(root.Left)
	rh := height(root.Right)
	if lh == -1 || rh == -1 || lh > rh+1 || rh > lh+1 {
		return -1
	}
	if rh > lh {
		lh = rh
	}
	return lh + 1
}

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	lh := height(root.Left)
	rh := height(root.Right)
	if lh == -1 || rh == -1 || lh > rh+1 || rh > lh+1 {
		return false
	}
	return true
}

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 minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	}
	lh := 1000000
	rh := 1000000
	if root.Left != nil {
		lh = minDepth(root.Left)
	}
	if root.Right != nil {
		rh = minDepth(root.Right)
	}
	if rh < lh {
		lh = rh
	}
	return lh + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

路径总和

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	targetSum -= root.Val
	if root.Left == nil || root.Right == nil {
		if root.Left == nil && root.Right == nil {
			if targetSum == 0 {
				return true
			}
			return false
		} else if root.Left != nil {
			return hasPathSum(root.Left, targetSum)
		} else {
			return hasPathSum(root.Right, targetSum)
		}
	}
	return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

杨辉三角

func generate(numRows int) [][]int {
	ans := make([][]int, numRows)
	for i := range ans {
		ans[i] = make([]int, i+1)
		ans[i][0] = 1
		ans[i][i] = 1
		for j := 1; j < i; j++ {
			ans[i][j] = ans[i-1][j] + ans[i-1][j-1]
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12

杨辉三角Ⅱ

解法1：

func getRow(rowIndex int) []int {
	ans := make([][]int, rowIndex+1)
	for i := range ans {
		ans[i] = make([]int, i+1)
		ans[i][0] = 1
		ans[i][i] = 1
		for j := 1; j < i; j++ {
			ans[i][j] = ans[i-1][j] + ans[i-1][j-1]
		}
	}
	return ans[rowIndex]
}
1
2
3
4
5
6
7
8
9
10
11
12

解法2：

func getRow(rowIndex int) []int {
	before := make([]int, rowIndex+1)
	now := make([]int, rowIndex+1)
	before[0] = 1
	now[0] = 1
	for i := 1; i <= rowIndex; i++ {
		now[0] = 1
		now[i] = 1
		for j := 1; j < i; j++ {
			now[j] = before[j-1] + before[j]
		}
		copy(before, now)
	}
	return now
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

买卖股票的最佳时机

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

func maxProfit(prices []int) int {
	buy := prices[0]
	sel := prices[0]
	ans := 0
	for _, v := range prices {
		sel = v
		ans = max(ans, sel-buy)
		buy = min(buy, v)
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

验证回文串

解法1：

func isPalindrome(s string) bool {
	var changed string
	for _, v := range s {
		if v >= 'A' && v <= 'Z' {
			changed += string(v + 32)
		} else if (v >= 'a' && v <= 'z') || (v >= '0' && v <= '9') {
			changed += string(v)
		}
	}
	fmt.Println(changed)
	l := 0
	r := len(changed) - 1
	for l < r {
		if changed[l] != changed[r] {
			return false
		}
		l++
		r--
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2：

func is_numoral(ch uint8) bool {
	if (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') {
		return true
	}
	return false
}

func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	l := 0
	r := len(s) - 1
	for l < r {
		if !is_numoral(s[l]) {
			l++
			continue
		}
		if !is_numoral(s[r]) {
			r--
			continue
		}
		if s[l] != s[r] {
			return false
		}
		l++
		r--
	}
	return true
}

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 singleNumber(nums []int) int {
	var singular = 0
	for _, v := range nums {
		singular ^= v
	}
	return singular
}
1
2
3
4
5
6
7

环形链表

解法1：set标记

func hasCycle(head *ListNode) bool {
	set := make(map[*ListNode]struct{})
	for head != nil {
		if _, ok := set[head]; ok {
			return true
		}
		set[head] = struct{}{}
		head = head.Next
	}
	return false
}

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

解法2：快慢指针

func hasCycle(head *ListNode) bool {
	fast := head
	slow := head
	for fast != nil && slow != nil {
		fast = fast.Next
		if fast == nil {
			return false
		}
		fast = fast.Next
		slow = slow.Next
		if fast == slow {
			return true
		}
	}
	return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树的前序遍历：

解法1：递归

func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var ans []int
	ans = append(ans, root.Val)
	ans = append(ans, preorderTraversal(root.Left)...)
	ans = append(ans, preorderTraversal(root.Right)...)
	return ans
}
1
2
3
4
5
6
7
8
9
10

解法2：非递归

func preorderTraversal(root *TreeNode) []int {
	var stack = make([]*TreeNode, 100)
	var cnt = 0
	var next = root
	var ans []int
	for cnt > 0 || next != nil {
		for next != nil {
			ans = append(ans, next.Val)
			stack[cnt] = next
			cnt++
			next = next.Left
		}
		next = stack[cnt-1].Right
		cnt--
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树的后序遍历

解法1：递归

func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var ans []int
	ans = append(ans, postorderTraversal(root.Left)...)
	ans = append(ans, postorderTraversal(root.Right)...)
	ans = append(ans, root.Val)
	return ans
}
1
2
3
4
5
6
7
8
9
10

解法2：非递归

func postorderTraversal(root *TreeNode) []int {
	var cnt = 0
	var len = 0
	var stack = make([]*TreeNode, 100)
	var ans []int
	var next = root
	for next != nil || cnt > 0 {
		for next != nil {
			len++
			stack[cnt] = next
			cnt++
			ans = append(ans, next.Val)
			next = next.Right
		}
		next = stack[cnt-1].Left
		cnt--
	}
	var left = 0
	var right = len - 1
	for left < right {
		var t = ans[left]
		ans[left] = ans[right]
		ans[right] = t
		left++
		right--
	}
	return ans
}
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 getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenA, lenB := 0, 0
	pA, pB := headA, headB
	for pA != nil {
		lenA++
		pA = pA.Next
	}
	for pB != nil {
		lenB++
		pB = pB.Next
	}
	for lenA < lenB {
		if headA == nil {
			return nil
		}
		headB = headB.Next
		lenA++
	}
	for lenB < lenA {
		if headB == nil {
			return nil
		}
		headA = headA.Next
		lenB++
	}
	for headA != headB {
		if headA == nil || headB == nil {
			return nil
		}
		headA = headA.Next
		headB = headB.Next
	}
	return headA
}
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

EXCEL表列名称：

func convertToTitle(columnNumber int) string {
	transfer := []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"}
	var s string = ""
	for columnNumber > 0 {
		columnNumber -= 1
		s = transfer[(columnNumber)%26] + s
		columnNumber = (columnNumber) / 26
	}
	return s
}
1
2
3
4
5
6
7
8
9
10

多数元素

func majorityElement(nums []int) int {
	element := nums[0]
	var cnt = 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == element {
			cnt++
		} else {
			cnt--
		}
		if cnt == 0 {
			cnt = 1
			element = nums[i]
		}
	}
	cnt = 0
	for _, v := range nums {
		if v == element {
			cnt++
		}
	}
	if cnt > len(nums)/2 {
		return element
	}
	return 0
}
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

超过经理收入的员工

SELECT a.name As "Employee" FROM Employee  a,Employee  b
Where a.managerId=b.id AND a.salary>b.salary
1
2

查找重复的电子邮箱

SELECT Email FROM Person
GROUP BY Email
HAVING COUNT(Email)>1
1
2
3

从不订购的客户

Select Name As Customers
FROM Customers
WHERE Customers.Id
Not in(
    Select CustomerId
    FROM Orders
)
1
2
3
4
5
6
7

颠倒二进制位

解法1：循环

func reverseBits(num uint32) uint32 {
	var ans uint32 = 0
	for i := 0; i < 32; i++ {
		ans = ans*2 + num&1
		num >>= 1
	}
	return ans
}
1
2
3
4
5
6
7
8

解法2：分治法+位运算

func reverseBits(num uint32) uint32 {
	const (
		base1 = 0x55555555
		base2 = 0x33333333
		base3 = 0x0f0f0f0f
		base4 = 0x00ff00ff
	)
	num = num>>1&base1 | num&base1<<1
	num = num>>2&base2 | num&base2<<2
	num = num>>4&base3 | num&base3<<4
	num = num>>8&base4 | num&base4<<8
	return num<<16 | num>>16
}
1
2
3
4
5
6
7
8
9
10
11
12
13

位1的个数

解法1：循环法

func hammingWeight(num uint32) int {
	var ans = 0
	for num > 0 {
		if num&1 != 0 {
			ans++
		}
		num >>= 1
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10

解法2：位运算

func hammingWeight(num uint32) int {
	var ans = 0
	for num > 0 {
		ans++
		num = num & (num - 1)
	}
	return ans
}
1
2
3
4
5
6
7
8

快乐数

解法1：模拟

func isHappy(n int) bool {
	var vis = make(map[int]struct{}, 1000)
	for n != 1 {
		var num = 0
		for n > 0 {
			num += (n % 10) * (n % 10)
			n /= 10
		}
		if _, ok := vis[num]; ok {
			return false
		}
		vis[num] = struct{}{}
		n = num
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法2：快慢指针

func isHappy(n int) bool {
	var slow = n
	var fast = n
	for fast != 1 {
		fast = next(fast)
		fast = next(fast)
		slow = next(slow)
		if slow == fast && fast != 1 {
			return false
		}
	}
	return true
}

func next(n int) (num int) {
	for n > 0 {
		num += (n % 10) * (n % 10)
		n /= 10
	}
	return num
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

移除链表元素

func removeElements(head *ListNode, val int) *ListNode {
	for head != nil&&head.Val == val  {
		head = head.Next
	}
	if head == nil {
		return head
	}
	pre := head
	p := head.Next
	for p != nil {
		if p.Val == val {
			pre.Next = p.Next
			p = p.Next
		} else {
			pre = p
			p = p.Next
		}
	}
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

同构字符串

func isIsomorphic(s string, t string) bool {
	lenS := len(s)
	lenT := len(t)
	if lenS != lenT {
		return false
	}
	f1 := map[uint8]uint8{}
	f2 := map[uint8]uint8{}
	for i := 0; i < lenS; i++ {
		if (f1[s[i]] != 0 && f1[s[i]] != t[i]) || (f2[t[i]] != 0 && f2[t[i]] != s[i]) {
			return false
		} else {
			f1[s[i]] = t[i]
			f2[t[i]] = s[i]
		}
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

存在重复元素 Ⅱ

解法1：

func containsNearbyDuplicate(nums []int, k int) bool {
	set := map[int]int{}
	for i := 0; i < len(nums); i++ {
		if v, ok := set[nums[i]]; ok {
			if i-v <= k {
				return true
			}
		}
		set[nums[i]] = i
	}
	return false
}

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

解法2：

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

用队列实现栈

type MyStack struct {
	queue1 []int
	queue2 []int
	front1 int
	tail1  int
}

func Constructor() MyStack {
	stack := MyStack{}
	return stack
}

func (this *MyStack) Push(x int) {
	this.queue1 = append(this.queue1, x)
	this.tail1++
}

func (this *MyStack) Pop() int {
	if this.tail1 == 0 {
		return 0
	}
	this.queue2 = append(this.queue2, this.queue1[this.front1:this.tail1-1]...)
	ans := this.queue1[this.tail1-1]
	this.queue1 = this.queue2
	this.queue2 = []int{}
	this.tail1--
	return ans
}

func (this *MyStack) Top() int {
	if this.tail1 == 0 {
		return 0
	}
	this.queue2 = append(this.queue2, this.queue1[this.front1:this.tail1-1]...)
	ans := this.queue1[this.tail1-1]
	this.queue2 = append(this.queue2, this.queue1[this.tail1-1:this.tail1]...)
	this.queue1 = this.queue2
	this.queue2 = []int{}
	return ans
}

func (this *MyStack) Empty() bool {
	return this.front1 == this.tail1
}
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 invertTree(root *TreeNode) *TreeNode {
     if root==nil{
         return nil
     }
     root.Left,root.Right=root.Right,root.Left
     invertTree(root.Left)
     invertTree(root.Right)
     return root
}
1
2
3
4
5
6
7
8
9

汇总区间

func summaryRanges(nums []int) []string {
	if len(nums) == 0 {
		return nil
	}
	var ans []string
	min, max := nums[0], nums[0]
	for i := 0; i < len(nums); i++ {
		if i == len(nums)-1 || nums[i] != nums[i+1]-1 {
			if min == max {
				ans = append(ans, fmt.Sprintf("%d", min))
			} else {
				ans = append(ans, fmt.Sprintf("%d->%d", min, max))
			}
			if i+1 < len(nums) {
				min = nums[i+1]
				max = nums[i+1]
			}
		} else {
			max = nums[i+1]
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2的幂

func isPowerOfTwo(n int) bool {
	if n == 0 {
		return false
	}
	return n&(n-1) == 0
}
1
2
3
4
5
6

用栈实现队列

type MyQueue struct {
	stack1 []int
	stack2 []int
	top1   int
	top2   int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (this *MyQueue) Push(x int) {
	this.stack1 = append(this.stack1[:this.top1], x)
	this.top1++
}

func (this *MyQueue) Pop() int {
	if this.Empty() {
		return -1
	}
	if this.top2 == 0 {
		for this.top1 != 0 {
			this.stack2 = append(this.stack2[:this.top2], this.stack1[this.top1-1])
			this.top1--
			this.top2++
		}
	}
	this.top2--
	return this.stack2[this.top2]

}

func (this *MyQueue) Peek() int {
	if this.Empty() {
		return -1
	}
	if this.top2 == 0 {
		for this.top1 != 0 {
			this.stack2 = append(this.stack2[:this.top2], this.stack1[this.top1-1])
			this.top1--
			this.top2++
		}
	}
	return this.stack2[this.top2-1]
}

func (this *MyQueue) Empty() bool {
	return this.top1 == 0 && this.top2 == 0
}

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

回文链表

解法1：中间数组法

func isPalindrome(head *ListNode) bool {
	var num = []int{}
	for head != nil {
		num = append(num, head.Val)
		head = head.Next
	}
	l, r := 0, len(num)-1
	for l < r {
		if num[l] != num[r] {
			return false
		}
		l++
		r--
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法2：快慢指针法

func reverse(head *ListNode) *ListNode {
	p := head.Next
	head.Next = nil
	for p != nil {
		t := p.Next
		p.Next = head
		head = p
		p = t
	}
	return head
}

func isPalindrome(head *ListNode) bool {
	slow := head
	fast := head
	for slow != nil && fast != nil {
		fast = fast.Next
		if fast == nil {
			break
		}
		fast = fast.Next
		slow = slow.Next
	}
	slow = reverse(slow)
	return compare(slow, head)
}

func compare(slow *ListNode, head *ListNode) bool {
	for slow != nil {
		if slow.Val != head.Val {
			return false
		}
		slow = slow.Next
		head = head.Next
	}
	return true
}
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 solve(root *TreeNode, min, max int) *TreeNode {
	if root.Val >= min && root.Val <= max {
		return root
	}
	if root.Val > min {
		return solve(root.Left, min, max)
	} else {
		return solve(root.Right, min, max)
	}
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if p.Val > q.Val {
		p, q = q, p
	}
	return solve(root, p.Val, q.Val)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

删除链表中的结点

func deleteNode(node *ListNode) {
    node.Val=node.Next.Val
    node.Next=node.Next.Next
}
1
2
3
4

有效的字母异次词

func isAnagram(s string, t string) bool {
	var vis = map[int32]int{}
	for _, v := range s {
		vis[v]++
	}
	for _, v := range t {
		vis[v]--
		if vis[v] == 0 {
			delete(vis, v)
		}
	}
	if len(vis) == 0 {
		return true
	}
	return false

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树的所有路径

func solve(root *TreeNode, ans *[]string, cur string) {
	if root == nil {
		return
	}
	if root.Left == nil && root.Right == nil {
		cur = cur + strconv.Itoa(root.Val)
		*ans = append(*ans, cur)
		return
	}
	cur = cur + strconv.Itoa(root.Val) + "->"
	if root.Left != nil {
		solve(root.Left, ans, cur)
	}
	if root.Right != nil {
		solve(root.Right, ans, cur)
	}
}

func binaryTreePaths(root *TreeNode) []string {
	var ans = []string{}
	var cur string
	solve(root, &ans, cur)
	return ans
}

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

各位相加

解法1：循环模拟

func addDigits(num int) int {
	for num >= 10 {
		var next = 0
		for num > 0 {
			next += num % 10
			num /= 10
		}
		num = next
	}
	return num
}

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

解法2：数学推导

假设有一个三位数（其实几位数都行）
n1 = 100 * a + 10 * b + c ====> 变化之后 n2 = a + b + c =====> n1 - n2 = 99a + 9b 由此可以得到二者每次的变化就是将其缩小9的倍数
相当于是n1只要各个位上的数字相加，就是缩小9的倍数，直到最后得到的是一个个位数，这样我们如果不用循环，不停的除以9，那么我们就可以使用取余操作，取到最后的结果
我们对 num取余后的结果分类讨论：
1.如果num 不是9的倍数时，其数根即为num除以9的余数。
2.如果num 是9的倍数时：
如果 num= 0，则其数根是 00；
如果num > 0则各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。

func addDigits(num int) int {
	return (num-1)%9+1
}

1
2
3
4

丑数

func isUgly(n int) bool {
	if n == 0 {
		return false
	}
	var nums = []int{2, 3, 5}
	for _, v := range nums {
		for n%v == 0 {
			n /= v
		}
	}
	return n == 1
}

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

丢失的数字

解法1：标记数组

func missingNumber(nums []int) int {
	var vis = map[int]struct{}{}
	for _, v := range nums {
		vis[v] = struct{}{}
	}
	for i := 0; i < len(nums); i++ {
		if _, ok := vis[i]; !ok {
			return i
		}
	}
	return len(nums)
}
1
2
3
4
5
6
7
8
9
10
11
12

解法2：位运算

func missingNumber(nums []int) int {
	var tmp = 0
	for _, v := range nums {
		tmp ^= v
	}
	for i := 0; i <= len(nums); i++ {
		tmp ^= i
	}
	return tmp
}

1
2
3
4
5
6
7
8
9
10
11

解法3：求和相减

func missingNumber(nums []int) int {
	var sum = 0
	var len_n = len(nums)
	for _, v := range nums {
		sum += v
	}
	return len_n*(len_n+1)/2 - sum
}
1
2
3
4
5
6
7
8

第一个错误的版本

func isBadVersion(version int) bool

func firstBadVersion(n int) int {
	return sort.Search(n, func(i int) bool {
		return isBadVersion(i)
	})
}
1
2
3
4
5
6
7

移动零

解法1：

func moveZeroes(nums []int) {
	var cnt = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			continue
		}
		nums[cnt] = nums[i]
		cnt++
	}
	for i := cnt; i < len(nums); i++ {
		nums[i] = 0
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单词规律

func wordPattern(pattern string, s string) bool {
	words := strings.Split(s, " ")
	var set = map[uint8]string{}
	var fset = map[string]uint8{}
	if len(words) != len(pattern) {
		return false
	}
	for i := 0; i < len(pattern); i++ {
		if v, ok := set[pattern[i]]; ok {
			if v != words[i] {
				return false
			}
		} else {
			set[pattern[i]] = words[i]
		}
		if v, ok := fset[words[i]]; ok {
			if v != pattern[i] {
				return false
			}
		} else {
			fset[words[i]] = pattern[i]
		}
	}
	return true
}

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

Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：
桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

思路：当到你的回合，石头为4时，必输。4~7

func canWinNim(n int) bool {
    return n%4!=0
}
1
2
3

区域和检索

type NumArray struct {
	sum []int
}

func Constructor(nums []int) NumArray {
	var tmp = NumArray{
		sum: make([]int, len(nums)),
	}
	if len(nums) == 0 {
		return tmp
	}
	tmp.sum[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		tmp.sum[i] = tmp.sum[i-1] + nums[i]
	}
	return tmp
}

func (this *NumArray) SumRange(left int, right int) int {
	if left == 0 {
		return this.sum[right]
	}
	return this.sum[right] - this.sum[left-1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3的幂

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}
1
2
3

比特位计数

解法1：

func countBits(n int) (ans []int) {
	for i := 0; i <= n; i++ {
		cnt := 0
		var num = i
		for num > 0 {
			cnt++
			num = num & (num - 1)
		}
		ans = append(ans, cnt)
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12

解法2：动态规划

对于一个正整数数i，存在着一个数j，j小于等于i且是2的正整数次方。那么i的1比特数等于就等于j的1比特数加1（例如i=1100，j=1000）。如何判断一个数是否是2的整数次方呢？只需判断i&（i-1）是否为0

func countBits(n int) []int {
	var high = 0
	ans := make([]int, n+1)
	ans[0] = 0
	for i := 1; i <= n; i++ {
		if i&(i-1) == 0 {
			high = i
		}
		ans[i] = ans[i-high] + 1
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12

解法3：动态规划2

类似解法二，只不过j为i>>1，是否加1取决于i&1是否为0

func countBits(n int) []int {
	ans := make([]int, n+1)
	ans[0] = 0
	for i := 1; i <= n; i++ {
		ans[i] = ans[i>>1] + i&1
	}
	return ans
}
1
2
3
4
5
6
7
8

解法4：动态规划3

j为i&（i-1），然后加1

func countBits(n int) []int {
	ans := make([]int, n+1)
	ans[0] = 0
	for i := 1; i <= n; i++ {
		ans[i] = ans[i&(i-1)] + 1
	}
	return ans
}
1
2
3
4
5
6
7
8

4的幂

解法1：

4的整数幂对应的二进制有且只有一个1且1在奇数位

func isPowerOfFour(n int) bool {
	return n > 0 && n&(n-1) == 0 && (n&0xaaaaaaaa) == 0
}
1
2
3

解法2：

func isPowerOfFour(n int) bool {
    return n > 0 && n&(n-1) == 0 && n%3 == 1
}
1
2
3

两个数组的交集

func intersection(nums1 []int, nums2 []int) (ans []int) {
	var set = map[int]struct{}{}
	for _, v := range nums1 {
		set[v] = struct{}{}
	}
	for _, v := range nums2 {
		if _, ok := set[v]; ok {
			ans = append(ans, v)
			delete(set, v)
		}
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13

两个数的交集Ⅱ

func intersect(nums1 []int, nums2 []int) (ans []int) {
	var set = map[int]int{}
	for _, v := range nums1 {
		set[v]++
	}
	for _, v := range nums2 {
		if _, ok := set[v]; ok {
			ans = append(ans, v)
			set[v]--
			if set[v] == 0 {
				delete(set, v)
			}
		}
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

有效的完全平方和

func isPerfectSquare(num int) bool {
	l, r := 0, num
	var mid int
	for l <= r {
		mid = (l + r) >> 1
		if mid*mid > num {
			r = mid - 1
		} else if mid*mid < num {
			l = mid + 1
		} else {
			return true
		}
	}
	return mid*mid == num
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

找不同

解法1：ASCLL码相加

func findTheDifference(s string, t string) byte {
	var ans byte
	for _, v := range t {
		ans += byte(v)
	}
	for _, v := range s {
		ans -= byte(v)
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10

解法2：位运算

func findTheDifference(s string, t string) byte {
	var ans byte
	for i := range s {
		ans ^= s[i] ^ t[i]
	}
	return ans ^ t[len(t)-1]
}

1
2
3
4
5
6
7
8

判断子序列

func isSubsequence(s string, t string) bool {
	var cur = 0
	if s == "" {
		return true
	}
	for _, v := range t {
		if s[cur] == uint8(v) {
			cur++
		}
		if cur == len(s) {
			return true
		}
	}
	return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二进制手表

func readBinaryWatch(turnedOn int) (ans []string) {
	for h := uint8(0); h < 12; h++ {
		for m := uint8(0); m < 60; m++ {
			if bits.OnesCount8(h)+bits.OnesCount8(m) == turnedOn {
				ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
			}
		}
	}
	return
}
1
2
3
4
5
6
7
8
9
10

第三大的数

func thirdMax(nums []int) int {
	first, second, third := math.MinInt64, math.MinInt64, math.MinInt64
	for _, v := range nums {
		if v > first {
			first, second, third = v, first, second
		} else if v < first && v > second {
			second, third = v, second
		} else if v<second&&v > third {
			third = v
		}
	}
	if third == math.MinInt64 {
		return first
	}
	return third
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

字符相加

func addStrings(num1 string, num2 string) string {
	var add = 0
	var num_1 int
	var num_2 int
	ans := ""
	for i, j := len(num1)-1, len(num2)-1; i >= 0 || j >= 0 || add > 0; i, j = i-1, j-1 {
		num_1, num_2 = 0, 0
		if i >= 0 {
			num_1 = int(num1[i] - '0')
		}
		if j >= 0 {
			num_2 = int(num2[j] - '0')
		}
		result := num_1 + num_2 + add
		add = result / 10
		ans = strconv.Itoa(result%10) + ans
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

字符串中的单词数

func countSegments(s string) int {
	ans := 0
	for i := 0; i < len(s); i++ {
		if (i == 0 || s[i-1] == ' ') && s[i] != ' ' {
			ans++
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9

排列硬币

解法1：二分查找

func arrangeCoins(n int) int {
	return sort.Search(n, func(i int) bool {
		return (i+1)*(i+2)/2 > n
	})
}
1
2
3
4
5

解法2：数学法

func arrangeCoins(n int) int {
	return int((math.Sqrt(float64(8*n+1)) - 1) / 2)
}
1
2
3

分发饼干

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	var cnt = 0
	var cur = 0
	for i := 0; i < len(g) && cur < len(s); i++ {
		for cur < len(s) && g[i] > s[cur] {
			cur++
		}
		if cur < len(s) {
			cnt++
			cur++
		}
	}
	return cnt
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

重复的字符串

解：KMP

用KMP算法来对s和s+s[1,len-2]进行匹配，匹配上的话就返回true

func getNext(s string) []int {
	var ans = make([]int, len(s))
	i, j := -1, 0
	ans[0] = -1
	for j < len(s)-1 {
		if i == -1 || s[i] == s[j] {
			i++
			j++
			if s[i] != s[j] {
				ans[j] = i
			} else {
				ans[j] = ans[i]
			}
		} else {
			i = ans[i]
		}
	}
	return ans
}

func repeatedSubstringPattern(s string) bool {
	next := getNext(s)
	return match(s, s+s, next)
}

func match(tmp string, pattern string, next []int) bool {
	var j = -1
	var i = 0
	for i < len(pattern)-1 && j < len(tmp) {
		if j == -1 || tmp[j] == pattern[i] {
			j++
			i++
		} else {
			j = next[j]
		}
	}
	return j == len(tmp)
}

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 hammingDistance(x int, y int) int {
	tmp := x ^ y
	cnt := 0
	for tmp > 0 {
		cnt++
		tmp = tmp & (tmp - 1)
	}
	return cnt
}

1
2
3
4
5
6
7
8
9
10

岛屿的周长

func islandPerimeter(grid [][]int) int {
	var size = len(grid)
	if size == 0 {
		return 0
	}
	var size2 = len(grid[0])
	var area = 0
	for i := 0; i < size; i++ {
		for j := 0; j < size2; j++ {
			if grid[i][j] != 1 {
				continue
			}
			if i == 0 {
				area++
			}
			if i == size-1 {
				area++
			}
			if j == 0 {
				area++
			}
			if j == size2-1 {
				area++
			}
			if i != 0 && grid[i-1][j] == 0 {
				area++
			}
			if j != 0 && grid[i][j-1] == 0 {
				area++
			}
			if i != size-1 && grid[i+1][j] == 0 {
				area++
			}
			if j != size2-1 && grid[i][j+1] == 0 {
				area++
			}
		}
	}
	return area
}
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

数字的补数

func findComplement(num int) int {
	highbit := 0
	tmp := num
	for tmp > 0 {
		highbit++
		tmp >>= 1
	}
	return num ^ (1<<highbit - 1)
}
1
2
3
4
5
6
7
8
9

密钥格式化

func licenseKeyFormatting(s string, k int) string {
	var tmp = []uint8{}
	for i := 0; i < len(s); i++ {
		if s[i] != '-' {
			tmp = append(tmp, s[i])
		}
	}
	head := len(tmp) % k
	var ans string
	ans = string(tmp[:head])
	for i := head; i < len(tmp); i += k {
		if ans != "" {
			ans = ans + "-" + string(tmp[i:i+k])
		} else {
			ans = string(tmp[i : i+k])
		}
	}
	return strings.ToUpper(ans)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

构造矩形

func constructRectangle(area int) []int {
	for i := int(math.Sqrt(float64(area))); i > 0; i-- {
		if area == (area/i)*i {
			return []int{area / i, i}
		}
	}
	return []int{area, 1}
}
1
2
3
4
5
6
7
8

下一个更大元素Ⅰ

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	ans := []int{}
	stack, top := make([]int, len(nums2)), -1
	next := map[int]int{}
	var cur int
	for i := len(nums2) - 1; i >= 0; i-- {
		cur = nums2[i]
		for top > -1 && stack[top] < cur {
			top--
		}
		if top == -1 {
			next[cur] = -1
		} else {
			next[cur] = stack[top]
		}
		top++
		stack[top] = cur
	}
	for _, v := range nums1 {
		ans = append(ans, next[v])
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最长特殊序列

func findLUSlength(a string, b string) int {
	len_a, len_b := len(a), len(b)
	if len_a > len_b {
		return len_a
	} else if len_b > len_a {
		return len_b
	}
	for i := len_b - 1; i >= 0; i-- {
		if a[i] != b[i] {
			return i + 1
		}
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二叉树的最小绝对差

func getMinimumDifference(root *TreeNode) int {
	ans := math.MaxInt
	var dfs func(node *TreeNode) (min, max int)
	dfs = func(cur *TreeNode) (min, max int) {
		if cur.Left == nil && cur.Right == nil {
			return cur.Val, cur.Val
		}
		var l_min int
		var l_max int
		var r_min int
		var r_max int
		//1 nil 3 2
		if cur.Left == nil {
			l_min, l_max = cur.Val, cur.Val //1 1
		} else {
			l_min, l_max = dfs(cur.Left)
		}

		if cur.Right == nil {
			r_min, r_max = cur.Val, cur.Val
		} else {
			r_min, r_max = dfs(cur.Right)
		}
		if cur.Left != nil && cur.Val-l_max < ans {
			ans = cur.Val - l_max
		}
		if cur.Right != nil && r_min-cur.Val < ans {
			ans = r_min - cur.Val
		}
		return l_min, r_max
	}
	dfs(root)
	return ans
}
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 reverseStr(s string, k int) string {
	t := []byte(s)
	len_t := len(t)
	for i := 0; i < len_t; i += 2 * k {
		num := k
		if len_t-i < num {
			num = len_t - i
		}
		front, after := i, i+num-1
		for front < after {
			t[front], t[after] = t[after], t[front]
			front++
			after--
		}
	}
	return string(t)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树的直径

func diameterOfBinaryTree(root *TreeNode) int {
	var ans int
	var dfs func(root *TreeNode) int
	dfs = func(cur *TreeNode) int {
		if cur == nil {
			return 0
		}
		var l_max int
		var r_max int
		l_max = dfs(cur.Left)
		r_max = dfs(cur.Right)
		if l_max+r_max+1 > ans {
			ans = l_max + r_max + 1
		}
		return max(l_max, r_max) + 1
	}
	dfs(root)
	return ans - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

反转字符串中的单词Ⅲ

func reverseWords(s string) string {
	arr := strings.Split(s, " ")
	var ans = ""
	for _, v := range arr {
		var t = []byte(v)
		front, after := 0, len(t)-1
		for front < after {
			t[front], t[after] = t[after], t[front]
			front++
			after--
		}
		ans = ans + " " + string(t)
	}
	if len(ans) == 1 {
		return ""
	}
	return ans[1:len(ans)]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

数组拆分

func arrayPairSum(nums []int) int {
	sort.Ints(nums)
	var ans int
	for i := 0; i < len(nums); i += 2 {
		ans += nums[i]
	}
	return ans
}
1
2
3
4
5
6
7
8

二叉树的坡度

func findTilt(root *TreeNode) int {
	var ans int
	var dfs func(node *TreeNode) int
	dfs = func(cur *TreeNode) int {
		if cur == nil {
			return 0
		}
		l_sum := dfs(cur.Left)
		r_sum := dfs(cur.Right)
		if l_sum < r_sum {
			l_sum, r_sum = r_sum, l_sum
		}
		ans += l_sum - r_sum
		return l_sum + r_sum + cur.Val
	}
	dfs(root)
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

重塑矩阵

func matrixReshape(mat [][]int, r int, c int) [][]int {
	var ans = make([][]int, r)
	cur_r := len(mat)
	if cur_r == 0 {
		return mat
	}
	cur_c := len(mat[0])
	if cur_c*cur_r != r*c {
		return mat
	}
	var cur_i int
	var cur_j int
	for i := 0; i < r; i++ {
		ans[i] = make([]int, c)
		for j := 0; j < c; j++ {
			ans[i][j] = mat[cur_i][cur_j]
			cur_j++
			if cur_j == cur_c {
				cur_i++
				cur_j = 0
			}
		}
	}
	return ans
}
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

另一棵树的子树

解法1：暴力

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	var compare func(r1 *TreeNode, r2 *TreeNode) bool
	compare = func(r1 *TreeNode, r2 *TreeNode) bool {
		if r1 == nil && r2 == nil {
			return true
		}
		if r1 == nil || r2 == nil {
			return false
		}
		if r1.Val != r2.Val {
			return false
		}
		return compare(r1.Left, r2.Left) && compare(r1.Right, r2.Right)
	}
	ans := false
	var dfs func(cur *TreeNode, val int)
	dfs = func(cur *TreeNode, val int) {
		if cur == nil {
			return
		}
		if cur.Val == val {
			if compare(cur, subRoot) {
				ans = true
			}
		}
		dfs(cur.Left, val)
		dfs(cur.Right, val)
	}
	dfs(root, subRoot.Val)
	return ans
}
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

解法2：后序序列匹配

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	var PreOrder func(cur *TreeNode) []int
	PreOrder = func(cur *TreeNode) (order []int) {
		if cur == nil {
			return []int{10001}
		}
		order = append(order, PreOrder(cur.Left)...)
		order = append(order, PreOrder(cur.Right)...)
		order = append(order, cur.Val)
		return
	}
	root_order := PreOrder(root)
	sub_order := PreOrder(subRoot)
	var cur_sub int
	len_sub, len_root := len(sub_order), len(root_order)
	for i := 0; i < len_root; i++ {
		cur_root := i
		for cur_sub < len_sub && cur_root < len_root && root_order[cur_root] == sub_order[cur_sub] {
			cur_sub++
			cur_root++
		}
		if cur_sub == len_sub {
			return true
		} else {
			cur_sub = 0
		}
	}
	return false
}

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

解法3：对解法二的匹配 使用KMP算法

func KMP(root, sub []int) bool {
	len_sub, len_root := len(sub), len(root)
	next := make([]int, len_sub)
	i, j := 0, -1
	next[0] = -1
	for i < len_sub-1 {
		if j == -1 || sub[i] == sub[j] {
			i++
			j++
			if sub[i] != sub[j] {
				next[i] = j
			} else {
				next[i] = next[j]
			}
		} else {
			j = next[j]
		}
	}
	cur_root, cur_sub := -1, -1
	for cur_root < len_root {
		if cur_sub == -1 || sub[cur_sub] == root[cur_root] {
			cur_sub++
			cur_root++
		} else {
			cur_sub = next[cur_sub]
		}
		if cur_sub == len_sub {
			return true
		}
	}
	return false
}

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	var PreOrder func(cur *TreeNode) []int
	PreOrder = func(cur *TreeNode) (order []int) {
		if cur == nil {
			return []int{10001}
		}
		order = append(order, PreOrder(cur.Left)...)
		order = append(order, PreOrder(cur.Right)...)
		order = append(order, cur.Val)
		return
	}
	root_order := PreOrder(root)
	sub_order := PreOrder(subRoot)
	return KMP(root_order, sub_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
41
42
43
44
45
46
47
48

N叉树的前序遍历

解法1：递归

func preorder(root *Node) []int {
	ans := []int{}
	cur := root
	tmp := []*Node{}
	for cur != nil || len(tmp) > 0 {
		ans = append(ans, cur.Val)
		for i := len(cur.Children) - 1; i >= 0; i-- {
			tmp = append(tmp, cur.Children[i])
		}
		if len(tmp) == 0 {
			return ans
		}
		cur = tmp[len(tmp)-1]
		tmp = tmp[:len(tmp)-1]
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法2：非递归

func preorder(root *Node) []int {
	ans := []int{}
	cur := root
	tmp := []*Node{}
	for cur != nil || len(tmp) > 0 {
		ans = append(ans, cur.Val)
		for i := len(cur.Children) - 1; i >= 0; i-- {
			tmp = append(tmp, cur.Children[i])
		}
		if len(tmp) == 0 {
			return ans
		}
		cur = tmp[len(tmp)-1]
		tmp = tmp[:len(tmp)-1]
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

N叉树的后序遍历

func postorder(root *Node) []int {
	if root == nil {
		return []int{}
	}
	ans := []int{}
	list := []*Node{}
	list = append(list, root)
	for len(list) > 0 {
		cur := list[len(list)-1]
		list = list[0 : len(list)-1]
		ans = append(ans, cur.Val)
		for i := 0; i < len(cur.Children); i++ {
			list = append(list, cur.Children[i])
		}
	}
	low := 0
	hight := len(ans) - 1
	for low < hight {
		ans[low], ans[hight] = ans[hight], ans[low]
		hight--
		low++
	}
	return ans
}

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 findRestaurant(list1 []string, list2 []string) (ans []string) {
	vis := map[string]int{}
	for i, v := range list1 {
		vis[v] = i
	}
	min := len(list1) + len(list2)
	for i, v := range list2 {
		if index, ok := vis[v]; ok {
			if index+i < min {
				min = index + i
				ans = []string{v}
			} else if index+i == min {
				ans = append(ans, v)
			}
		}
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

种花问题

解法1：贪心

func canPlaceFlowers(flowerbed []int, n int) bool {
	if len(flowerbed) == 0 {
		return n == 0
	}
	ans := 0
	index := 0
	for index < len(flowerbed) {
		if flowerbed[index] == 0 && (index == len(flowerbed)-1 || flowerbed[index+1] != 1) {
			ans++
			index++
		} else if flowerbed[index] == 1 {
			index++
		}
		index++
	}
	return ans >= n
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法2：

数学规律求解：

func canPlaceFlowers(flowerbed []int, n int) bool {
	if len(flowerbed) == 0 {
		return n == 0
	}
	pre := -1
	ans := 0
	if flowerbed[0] == 0 {
		ans++
		flowerbed[0] = 1
	}
	if flowerbed[len(flowerbed)-1] == 0 && len(flowerbed) > 2 {
		ans++
		flowerbed[len(flowerbed)-1] = 1
	}
	for index, value := range flowerbed {
		if value == 1 {
			if pre != -1 {
				span := index - pre - 1
				if span%2 == 0 {
					ans += span/2 - 1
				} else {
					ans += span / 2
				}
			}
			pre = index
		}
	}
	return ans >= n
}

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

根据二叉树创建字符串

解法1：递归

func tree2str(root *TreeNode) string {
	var preOrder func(node *TreeNode) string
	preOrder = func(node *TreeNode) string {
		if node == nil {
			return ""
		}
		left := preOrder(node.Left)
		right := preOrder(node.Right)
		if left == "" && right != "" {
			left = "()"
		} else if left != "" {
			left = "(" + left + ")"
		}
		if right != "" {
			right = "(" + right + ")"
		}
		return strconv.Itoa(node.Val) + left + right
	}
	return preOrder(root)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解法2：迭代

func tree2str(root *TreeNode) string {
	stack := []*TreeNode{root}
	vis := map[*TreeNode]bool{}
	if root == nil {
		return ""
	}
	ans := ""
	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		if vis[cur] {
			if cur != root {
				ans += ")"
			}
			stack = stack[:len(stack)-1]
			continue
		}
		if cur != root {
			ans += "("
		}
		ans += strconv.Itoa(cur.Val)
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}
		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}
		if cur.Left == nil && cur.Right != nil {
			ans += "()"
		}
		vis[cur] = true
	}
	return ans
}
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 getMax(num1, num2, num3 int) (min, mid, max int) {
	if num1 >= num2 && num1 >= num3 {
		if num2 >= num3 {
			min, mid, max = num3, num2, num1
		} else {
			min, mid, max = num2, num3, num1
		}
	} else if num2 > num1 && num2 >= num3 {
		if num1 >= num3 {
			min, mid, max = num3, num1, num2
		} else {
			min, mid, max = num1, num3, num2
		}
	} else {
		if num2 >= num1 {
			min, mid, max = num1, num2, num3
		} else {
			min, mid, max = num2, num1, num3
		}
	}
	return
}

func getMin(num1, num2 int) (small, big int) {
	if num1 > num2 {
		small = num2
		big = num1
	} else {
		small = num1
		big = num2
	}
	return
}

func maximumProduct(nums []int) int {
	min, mid, max := getMax(nums[0], nums[1], nums[2])
	max_tree := [3]int{min, mid, max}
	small, big := getMin(nums[0], nums[1])
	min_two := [2]int{small, big}
	for i := 2; i < len(nums); i++ {
		if nums[i] > max_tree[0] && i != 2 {
			max_tree[0], max_tree[1], max_tree[2] = getMax(nums[i], max_tree[1], max_tree[2])
		} else if nums[i] < min_two[1] {
			min_two[0], min_two[1] = getMin(nums[i], min_two[0])
		}
	}
	//fmt.Println(min_two[0])
	//fmt.Println(min_two[1])
	ans1 := max_tree[0] * max_tree[1] * max_tree[2]
	ans2 := min_two[0] * min_two[1] * max_tree[2]
	if ans2 > ans1 {
		return ans2
	}
	if ans1 > ans2 {
		return ans1
	}
	return ans1
}

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

二叉树的层平均值

func averageOfLevels(root *TreeNode) (ans []float64) {
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		sum := 0
		tmp_queue := []*TreeNode{}
		for _,v:=range queue {
			cur := v
			sum += cur.Val
			if cur.Left != nil {
				tmp_queue = append(tmp_queue, cur.Left)
			}
			if cur.Right != nil {
				tmp_queue = append(tmp_queue, cur.Right)
			}
		}
		ans = append(ans, float64(sum)/float64(len(queue)))
		queue = tmp_queue
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

子数组最大平均数

func findMaxAverage(nums []int, k int) float64 {
	sum := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		if i == 0 {
			sum[i] = nums[i]
		} else {
			sum[i] = sum[i-1] + nums[i]
		}
	}
	if k == 0 {
		return 0
	}
	ans := sum[k-1]
	for i := k; i < len(sum); i++ {
		if sum[i]-sum[i-k] > ans {
			ans = sum[i] - sum[i-k]
		}
	}
	fmt.Println(ans)
	return float64(ans) / float64(k)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

错误的集合

解法1：哈希表

func findErrorNums(nums []int) (ans []int) {
	vis := map[int]struct{}{}
	for _, v := range nums {
		if _, ok := vis[v]; ok {
			ans = append(ans, v)
		} else {
			vis[v] = struct{}{}
		}
	}
	for i := 1; i <= len(nums); i++ {
		if _, ok := vis[i]; !ok {
			ans = append(ans, i)
		}
	}
	return
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法2：异或运算

首先将所给的数组nums的所有值和1~len(nums)中的值进行一轮异或运算。因为除了缺少的值和重复的值出现了奇数次之外，其它的值都出现了偶数次（两次），异或后为0。所以最后的结果为缺失值和重复值的异或结果。然后根据结果中的最低位（cur&-cur），将nums和1-len（nums）数组中的值分为两组。而其中一组中除了缺失值（出现一次）之外其他值均出现两次，另外一组除了重复值（出现三次）之外其它值都出现两次。然后分别进行异或运算，得到两个值num1，num2，最后再遍历一遍数组，进行对比，来找出重复值，另外一个就是缺失值

func findErrorNums(nums []int) (ans []int) {
	cur := 0
	for _, v := range nums {
		cur ^= v
	}
	for i := 1; i <= len(nums); i++ {
		cur ^= i
	}
	low_bit := cur & -cur
	num1, num2 := 0, 0
	for _, v := range nums {
		if v&low_bit == 0 {
			num1 ^= v
		} else {
			num2 ^= v
		}
	}
	for i := 1; i <= len(nums); i++ {
		if i&low_bit == 0 {
			num1 ^= i
		} else {
			num2 ^= i
		}
	}
	for _, v := range nums {
		if v == num1 {
			ans = append(ans, num1, num2)
			break
		} else if v == num2 {
			ans = append(ans, num2, num1)
			break
		}
	}
	return
}

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 findTarget(root *TreeNode, k int) bool {
	vis := map[int]struct{}{}
	var dfs func(cur *TreeNode) bool
	dfs = func(cur *TreeNode) bool {
		if cur == nil {
			return false
		}
		if _, ok := vis[k-cur.Val]; ok {
			return true
		}
		vis[cur.Val] = struct{}{}
		return dfs(cur.Left) || dfs(cur.Right)
	}
	return dfs(root)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树中第二小的节点

func findSecondMinimumValue(root *TreeNode) int {
	var dfs func(cur *TreeNode)
	var root_val = root.Val
	ans := -1
	dfs = func(cur *TreeNode) {
		if cur == nil || ans != -1 && cur.Val >= ans {
			return
		}
		if cur.Val > root_val {
			ans = cur.Val
		}
		dfs(cur.Left)
		dfs(cur.Right)
	}
	dfs(root)
	return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

最长连续递增序列

解法1：贪心

func findLengthOfLCIS(nums []int) int {
	len_nums := len(nums)
	if len_nums <= 1 {
		return len_nums
	}
	cur, ans, index := 1, 1, 1
	for index < len_nums {
		if nums[index-1] < nums[index] {
			cur++
		} else {
			if cur > ans {
				ans = cur
			}
			cur = 1
		}
		index++
	}
	if cur > ans {
		ans = cur
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解法2：并查集

var f []int

func Init(n int) {
	f = make([]int, n)
	for i := 0; i < n; i++ {
		f[i] = i
	}
}

func find(x int) int {
	if x != f[x] {
		f[x] = find(f[x])
	}
	return f[x]
}

func unit(x, y int) {
	fx, fy := find(x), find(y)
	f[fx] = fy
}

func findLengthOfLCIS(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := make([]int, n)
	Init(n)
	ans[0] = 1
	for i := 1; i < n; i++ {
		if nums[i] > nums[i-1] {
			unit(i, i-1)
		}
	}
	ret := 0
	set := make([]int, n)
	for i := 0; i < n; i++ {
		cur := set[f[i]] + 1
		set[f[i]] = cur
		if cur > ret {
			ret = cur
		}
	}
	return ret
}
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

验证回文串II

func validPalindrome(s string) bool {
	l, r := 0, len(s)-1
	for l < r {
		if s[l] == s[r] {
			l++
			r--
		} else {
			break
		}
	} //bddb
	if l >= r {
		return true
	}
	left, right := l+1, r
	for left < right {
		if s[left] == s[right] {
			left++
			right--
		} else {
			break
		}
	}
	if left >= right {
		return true
	}
	left, right = l, r-1
	for left < right {
		if s[left] == s[right] {
			left++
			right--
		} else {
			break
		}
	}
	if left >= right {
		return true
	}
	return false
}

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

交替二进制数

func hasAlternatingBits(n int) bool {
	cur := n ^ (n >> 1)
	for cur > 0 {
		if cur&1 != 1 {
			return false
		}
		cur >>= 1
	}
	return true
}

1
2
3
4
5
6
7
8
9
10
11

计数的二进制子串

只需要找出每一个连续且值相同的子串，并把长度存起来，比如到num中，结果就是所有相邻的num中的min（num[i-1],num[i]）相加

func countBinarySubstrings(s string) int {
	len_s := len(s)
	num := []int{}
	if len_s <= 1 {
		return 0
	}
	cnt := 1
	for i := 0; i < len_s-1; i++ {
		if s[i] == s[i+1] {
			cnt++
		} else {
			num = append(num, cnt)
			cnt = 1
		}
	}
	if cnt != 0 {
		num = append(num, cnt)
	} else {
		num = append(num, 1)
	}
	ans := 0
	for i := 0; i < len(num)-1; i++ {
		tmp := 0
		if num[i] > num[i+1] {
			tmp = num[i+1]
		} else {
			tmp = num[i]
		}
		ans += tmp
	}
	return ans
}
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

数组的度

解：
用一个结构体num，里面三个字段l，r，cnt，三者分别代表着数组中数第一次出现的位置，最后出现的位置，以及出现的次数。第一次遍历nums，计算每个数对应的num结构体的值，并进行hash存储。用两个变量ans和max分别存储问题的解和最大的出现次数。第二次遍历，根据cnt来判断，cnt=max时，查看r-l+1，也就是包含所有该数的序列长度是否小于ans，是的话则更新ans，否则跳过。当cnt>max时，更新max，并更新ans为该数的r-l+1。

type num struct {
	cnt int
	l   int
	r   int
}

func findShortestSubArray(nums []int) int {
	tmp := map[int]num{}
	for i, v := range nums {
		if value, ok := tmp[v]; ok {
			value.cnt++
			value.r = i
			tmp[v] = value
		} else {
			value.cnt = 1
			value.l = i
			value.r = i
			tmp[v] = value
		}
	}
	max := 0
	ans := len(nums)
	for _, v := range tmp {
		if v.cnt > max {
			max = v.cnt
			ans = v.r - v.l + 1
		} else if v.cnt == max && v.r-v.l+1 < ans {
			ans = v.r - v.l + 1
		}
	}
	return ans
}
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

数据流中第K大元素

解法1：链表模拟

type node struct {
	val  int
	next *node
}

type KthLargest struct {
	k    int
	head *node
}

func Constructor(k int, nums []int) KthLargest {
	head := new(node)
	num := new(KthLargest)
	num.head = head
	num.k = k
	sort.Ints(nums)
	for i := len(nums) - 1; i >= 0; i-- {
		cur := new(node)
		cur.val = nums[i]
		head.next = cur
		head = cur
	}
	return *num
}

func (this *KthLargest) Add(val int) int {
	k := this.k
	head := this.head
	cur := new(node)
	cur.val = val

	for head.next != nil && head.next.val > val {
		head = head.next
	}
	if head.next != nil {
		cur.next = head.next
	} else {
		cur.next = nil
	}
	head.next = cur
	head = this.head
	for head.next != nil && k > 0 {
		k--
		head = head.next
		if k == 0 {
			return head.val
		}
	}
	return 0
}

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

解法2：优先队列

type KthLargest struct {
	k int
	sort.IntSlice
}

func Constructor(k int, nums []int) KthLargest {
	var num = KthLargest{k: k}
	for _, v := range nums {
		num.Add(v)
	}
	return num
}

func (this *KthLargest) Push(val interface{}) {
	this.IntSlice = append(this.IntSlice, val.(int))
}

func (this *KthLargest) Pop() interface{} {
	len_num := len(this.IntSlice)
	v := this.IntSlice[len_num-1]
	this.IntSlice = this.IntSlice[:len_num-1]
	return v
}

func (this *KthLargest) Add(val int) int {
	heap.Push(this, val)
	if this.Len() > this.k {
		heap.Pop(this)
	}
	return this.IntSlice[0]
}

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

设计哈希集合

type node struct {
	val  int
	next *node
}

type MyHashSet struct {
	head *node
	tail *node
}

func Constructor() MyHashSet {
	head := new(node)
	tail := new(node)
	return MyHashSet{
		head: head,
		tail: tail,
	}
}

func (this *MyHashSet) Add(key int) {
	if this.Contains(key) {
		return
	}
	cur := &node{
		val: key,
	}
	if this.head.next == nil {
		this.head.next = cur
	}
	this.tail.next = cur
	this.tail = cur
}

func (this *MyHashSet) Remove(key int) {
	head := this.head
	for head.next != nil && head.next.val != key {
		head = head.next
	}
	if head.next == nil {
		return
	}
	if this.tail == head.next {
		this.tail = head
	}
	head.next = head.next.next
}

func (this *MyHashSet) Contains(key int) bool {
	head := this.head.next
	for head != nil {
		if head.val == key {
			return true
		}
		head = head.next
	}
	return false
}
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

设计哈希映射

const base = 799

type entry struct {
	key, value int
}

type MyHashMap struct {
	data []list.List
}

func Constructor() MyHashMap {
	return MyHashMap{
		data: make([]list.List, base),
	}
}

func (this *MyHashMap) hash(key int) int {
	return key % base
}

func (this *MyHashMap) Put(key int, value int) {
	m := this.hash(key)
	for node := this.data[m].Front(); node != nil; node = node.Next() {
		if node.Value.(entry).key == key {
			node.Value = entry{key: key, value: value}
			return
		}
	}
	this.data[m].PushBack(entry{
		key:   key,
		value: value,
	})
}

func (this *MyHashMap) Get(key int) int {
	m := this.hash(key)
	for node := this.data[m].Front(); node != nil; node = node.Next() {
		if cur := node.Value.(entry); cur.key == key {
			return cur.value
		}
	}
	return -1
}

func (this *MyHashMap) Remove(key int) {
	m := this.hash(key)
	for node := this.data[m].Front(); node != nil; node = node.Next() {
		if node.Value.(entry).key == key {
			this.data[m].Remove(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

寻找数组的中心索引

func pivotIndex(nums []int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	sum2 := 0
	for i, v := range nums {
		if sum2 == sum-sum2-v {
			return i
		}
		sum2 += v
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

图像渲染

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
	if len(image) == 0 {
		return nil
	}
	num := image[sr][sc]
	m, n := len(image), len(image[0])
	if num != color {
		dfs(sr, sc, num, color, m, n, image)
	}
	return image
}

func dfs(x, y, num, color, m, n int, image [][]int) {
	if x < 0 || y < 0 || x >= m || y >= n {
		return
	}
	if image[x][y] == num {
		image[x][y] = color
		dfs(x+1, y, num, color, m, n, image)
		dfs(x-1, y, num, color, m, n, image)
		dfs(x, y+1, num, color, m, n, image)
		dfs(x, y-1, num, color, m, n, image)
	}
	return
}
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 min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	if n == 1 {
		return cost[0]
	} else if n == 2 {
		return min(cost[0], cost[1])
	}
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 0
	for i := 2; i < n+1; i++ {
		dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
	}
	return min(dp[n-1]+cost[n-1], dp[n])
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最短补全词

func shortestCompletingWord(licensePlate string, words []string) string {
	num := make([]int, 30)
	for _, v := range licensePlate {
		if unicode.IsLetter(v) {
			num[unicode.ToLower(v)-'a']++
		}
	}
	ans := ""
	for _, word := range words {
		cur := make([]int, 30)
		for _, ch := range word {
			cur[ch-'a']++
		}
		flag := 0
		for i := 0; i < 26; i++ {
			if cur[i] < num[i] {
				flag = 1
				break
			}
		}
		if flag == 0 {
			if ans == "" || len(ans) > len(word) {
				ans = word
			}
		}
	}
	return ans
}
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

二进制表示中质数个计算置位

解法1：

func is_prime(num int) bool {
	if num < 2 {
		return false
	}
	for i := 2; i*i <= num; i++ {
		if num%i == 0 {
			return false
		}
	}
	return true
}

func countPrimeSetBits(left int, right int) int {
	ans := 0
	for cur := left; cur <= right; cur++ {
		cnt := bits.OnesCount(uint(cur))
		if is_prime(cnt) {
			ans++
		}
	}
	return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法2：
由于right和left<10^6 <2^20,所以二进制数中的1小于19个，不超过19的质数有：2、3、5、7、11、13、17、19，我们可以用mask=665772=10100010100010101100 来存储这些质数（质数位为1，其它位为0）。一个数num的二进制中1的个数为cnt，如果2^cnt&mask不为0则满足条件

func countPrimeSetBits(left int, right int) int {
	ans := 0
	for cur := left; cur <= right; cur++ {
		cnt := bits.OnesCount(uint(cur))
		if 1<<cnt&665772 != 0 {
			ans++
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10

二叉搜索树节点最小距离

func minDiffInBST(root *TreeNode) int {
	ans := -1
	var dfs func(cur *TreeNode) (min, max int)
	dfs = func(cur *TreeNode) (min, max int) {
		if cur == nil {
			return -1, -1
		}
		if cur.Left == nil && cur.Right == nil {
			return cur.Val, cur.Val
		}
		min_l, max_l := dfs(cur.Left)
		if max_l != -1 && (ans == -1 || cur.Val-max_l < ans) {
			ans = cur.Val - max_l
		}
		min_r, max_r := dfs(cur.Right)
		if min_r != -1 && (ans == -1 || min_r-cur.Val < ans) {
			ans = min_r - cur.Val
		}
		if min_l == -1 {
			min_l = cur.Val
		}
		if max_r == -1 {
			max_r = cur.Val
		}
		return min_l, max_r
	}
	dfs(root)
	return ans
}
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

旋转字符串

解：直接与两个goal拼接的字符串进行匹配即可

func rotateString(s string, goal string) bool {
	if len(s) != len(goal) {
		return false
	}
	goal = goal + goal
	if strings.Contains(goal, s) {
		return true
	}
	return false
}
1
2
3
4
5
6
7
8
9
10

解法2：手写扩展KMP

var next []int

func getnext(s string) {
	next[0] = -1
	i, j := 0, -1
	for i < len(s)-1 {
		if j == -1 || s[i] == s[j] {
			i++
			j++
			if s[i] == s[j] {
				next[i] = next[j]
			} else {
				next[i] = j
			}
		} else {
			j = next[j]
		}
	}
}

func rotateString(s string, goal string) bool {
	next = make([]int, len(s))
	getnext(s)
	if len(s) != len(goal) {
		return false
	}
	goal = goal + goal
	i, j := 0, -1
	for i < len(goal) {
		if j == -1 || s[j] == goal[i] {
			i++
			j++
		} else {
			j = next[j]
		}
		if j == len(s) {
			return true
		}
	}
	return false
}
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 mostCommonWord(paragraph string, banned []string) string {
	ban := make(map[string]struct{}, len(banned))
	for _, v := range banned {
		ban[v] = struct{}{}
	}
	max := 0
	str := ""
	s := []byte{}
	paragraph = strings.ToLower(paragraph)
	cnt := make(map[string]int, len(paragraph))
	for i := 0; i <= len(paragraph); i++ {
		if i < len(paragraph) && unicode.IsLetter(rune(paragraph[i])) {
			s = append(s, paragraph[i])
		} else if len(s) > 0 {
			t := string(s)
			if _, ok := ban[t]; !ok {
				cnt[t]++
				if cnt[t] > max {
					max = cnt[t]
					str = t
				}
			}
			s = []byte{}
		}
	}
	return str
}
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

字符的最短距离

解法1：两次遍历

func shortestToChar(s string, c byte) []int {
	n := len(s)
	ans := make([]int, n)
	cur := -n
	for i := 0; i < len(s); i++ {
		if s[i] == c {
			cur = i
		}
		ans[i] = i - cur
	}
	cur = 2 * n
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == c {
			cur = i
		}
		if cur != -1 && cur-i < ans[i] {
			ans[i] = cur - i
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2：单调栈思想

func absSub(x, y int) int {
	if x > y {
		return x - y
	}
	return y - x
}

func shortestToChar(s string, c byte) (ans []int) {
	c_pos := []int{}
	for i := 0; i < len(s); i++ {
		if s[i] == c {
			c_pos = append(c_pos, i)
		}
	}
	cur := 0
	len_pos := len(c_pos)
	if len_pos == 0 {
		return nil
	}
	for i := 0; i < len(s); i++ {
		left, right := len(s), len(s)
		left = absSub(c_pos[cur], i)
		if cur+1 != len_pos {
			right = absSub(c_pos[cur+1], i)
		}
		if left < right {
			ans = append(ans, left)
		} else {
			ans = append(ans, right)
			if cur+1 < len_pos {
				cur++
			}
		}
	}
	return
}
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

山羊拉丁文

var vowels = map[byte]struct{}{'a': {}, 'e': {}, 'i': {}, 'o': {}, 'u': {}, 'A': {}, 'E': {}, 'I': {}, 'O': {}, 'U': {}}

func toGoatLatin(sentence string) string {
	ans := &strings.Builder{}
	cnt := 0
	for i := 0; i < len(sentence); i++ {
		if cnt != 0 {
			ans.WriteString(" ")
		}
		start := i
		for i < len(sentence) && sentence[i] != ' ' {
			i++
		}
		cnt++
		if _, ok := vowels[sentence[start]]; ok {
			ans.WriteString(sentence[start:i])
		} else {
			ans.WriteString(sentence[start+1 : i])
			ans.WriteByte(sentence[start])
		}
		ans.WriteString("ma")
		ans.WriteString(strings.Repeat("a", cnt))
	}
	return ans.String()
}
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 largeGroupPositions(s string) [][]int {
    ans:=[][]int{}
    i:=0;
    for i<len(s){
        start:=i
        ch:=s[i]
        for i<len(s)&&s[i]==ch{
            i++
        } 
        len_cur:=i-start
        if len_cur>=3{
            cur:=make([]int,2)
            cur[0]=start
            cur[1]=i-1
            ans=append(ans,cur)
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

翻转图像

func flipAndInvertImage(image [][]int) [][]int {
	n := len(image)
	for i := 0; i < n; i++ {
		left, right := 0, n-1
		for left < right {
			if image[i][left] == image[i][right] {
				image[i][left] = image[i][left] ^ 1
				image[i][right] = image[i][right] ^ 1
			}
			left++
			right--
		}
		if left == right {
			image[i][left] = image[i][left] ^ 1
		}
	}
	return image
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

比较含退格的字符串

func backspaceCompare(s string, t string) bool {
	cur_s, cur_t := len(s)-1, len(t)-1
	flag_s, flag_t := 0, 0
	for cur_s >= 0 || cur_t >= 0 {
		for cur_s >= 0 {
			if s[cur_s] == '#' {
				cur_s--
				flag_s++
			} else if flag_s > 0 {
				cur_s--
				flag_s--
			} else {
				break
			}
		}
		for cur_t >= 0 {
			if t[cur_t] == '#' {
				cur_t--
				flag_t++
			} else if flag_t > 0 {
				cur_t--
				flag_t--
			} else {
				break
			}
		}
		if cur_t >= 0 && cur_s >= 0 {
			if t[cur_t] != s[cur_s] {
				return false
			}
		} else if cur_t >= 0 || cur_s >= 0 {
			return false
		}
		cur_t--
		cur_s--
	}
	return true
}
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 buddyStrings(s string, goal string) bool {
	pos1, pos2 := -1, -1
	len_s, len_goal := len(s), len(goal)
	if len_s != len_goal {
		return false
	}
	for i := 0; i < len_s; i++ {
		if s[i] != goal[i] {
			if pos1 == -1 {
				pos1 = i
			} else if pos2 == -1 {
				pos2 = i
			} else {
				return false
			}
		}
	}
	if pos1 != -1 && pos2 != -1 {
		return s[pos1] == goal[pos2] && s[pos2] == goal[pos1]
	} else if pos1 == -1 && pos2 == -1 {
		vis := make(map[int]struct{}, 30)
		for _, v := range s {
			num := int(v - 'a')
			if _, ok := vis[num]; ok {
				return true
			} else {
				vis[num] = struct{}{}
			}
		}
	}
	return false
}
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 binaryGap(n int) int {
	before, cur := 0, 0
	ans := 0
	for n > 0 {
		cur++
		if n&1 != 0 {
			if before != 0 {
				if cur-before > ans {
					ans = cur - before
				}
			}
			before = cur
		}
		n >>= 1
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

叶子相似的树

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
	var dfs func(node *TreeNode, val *[]int)
	dfs = func(node *TreeNode, val *[]int) {
		if node == nil {
			return
		}
		if node.Left == nil && node.Right == nil {
			*val = append(*val, node.Val)
			return
		}
		dfs(node.Left, val)
		dfs(node.Right, val)
	}
	val1, val2 := []int{}, []int{}
	dfs(root1, &val1)
	dfs(root2, &val2)
	if len(val1) != len(val2) {
		return false
	}
	n := len(val1)
	for i := 0; i < n; i++ {
		if val1[i] != val2[i] {
			return false
		}
	}
	return true
}
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 projectionArea(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	top, left, right := 0, 0, 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] > 0 {
				top++
			}
		}
	}
	for j := 0; j < m; j++ {
		max := 0
		for i := 0; i < n; i++ {
			if grid[i][j] > max {
				max = grid[i][j]
			}
		}
		left += max
	}
	for i := 0; i < n; i++ {
		max := 0
		for j := 0; j < m; j++ {
			if grid[i][j] > max {
				max = grid[i][j]
			}
		}
		right += max
	}
	return right + left + top
}

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 fairCandySwap(aliceSizes []int, bobSizes []int) []int {
	sum1, sum2 := 0, 0
	for _, v := range aliceSizes {
		sum1 += v
	}
	for _, v := range bobSizes {
		sum2 += v
	}
	sub := sum1 - sum2
	if sub == 0 {
		return []int{0, 0}
	}

	vis := make(map[int]struct{}, len(bobSizes))
	for _, v := range bobSizes {
		vis[v] = struct{}{}
	}
	for _, v := range aliceSizes {
		other := 2*v - sub
		if _, ok := vis[other/2]; ok {
			return []int{v, other / 2}
		}
	}
	return []int{-1, -1}
}

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 surfaceArea(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	ans := 0
	cnt := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			base := grid[i][j]
			if base == 0 {
				cnt++
			}
			if i == 0 {
				ans += base
			} else {
				base2 := base - grid[i-1][j]
				if base2 > 0 {
					ans += base2
				}
			}
			if i == n-1 {
				ans += base
			} else {
				base2 := base - grid[i+1][j]
				if base2 > 0 {
					ans += base2
				}
			}
			if j == 0 {
				ans += base
			} else {
				base2 := base - grid[i][j-1]
				if base2 > 0 {
					ans += base2
				}
			}
			if j == m-1 {
				ans += base
			} else {
				base2 := base - grid[i][j+1]
				if base2 > 0 {
					ans += base2
				}
			}
			//fmt.Printf("x:%v y:%v val:%v\n", i, j, ans)
		}
	}
	return ans + 2*(n*m-cnt)
}
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 isMonotonic(nums []int) bool {
	n := len(nums)
	if n <= 2 {
		return true
	}
	start := 1
	flag := 0
	for start < n {
		if nums[start-1] < nums[start] {
			break
		} else if nums[start-1] > nums[start] {
			flag = 1
			break
		}
		start++
	}
	if flag == 0 {
		for i := start; i < n; i++ {
			if nums[i] < nums[i-1] {
				return false
			}
		}
	} else {
		for i := start; i < n; i++ {
			if nums[i] > nums[i-1] {
				return false
			}
		}
	}
	return true
}
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 increasingBST(root *TreeNode) *TreeNode {
	var node *TreeNode
	var head *TreeNode
	var dfs func(cur *TreeNode)
	dfs = func(cur *TreeNode) {
		if cur == nil {
			return
		}
		dfs(cur.Left)
		cur.Left = nil
		if node == nil {
			node = cur
			head = cur
		} else {
			node.Right = cur
			node = cur
		}
		dfs(cur.Right)
	}
	dfs(root)
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

卡牌分组

func gcd(x, y int) int {
	if x < y {
		x, y = y, x
	}
	for y != 0 {
		x, y = y, x%y
	}
	return x
}

func hasGroupsSizeX(deck []int) bool {
	n := len(deck)
	cnt := make(map[int]int, n)
	max := 0
	for i := 0; i < n; i++ {
		cnt[deck[i]]++
		if deck[i] > max {
			max = deck[i]
		}
	}
	var ans int
	for i := 0; i <= max; i++ {
		if _, ok := cnt[i]; ok {
			if ans == 0 {
				ans = cnt[i]
			} else {
				ans = gcd(ans, cnt[i])
			}
		}
	}
	return ans != 1

}
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 reverseOnlyLetters(s string) string {
	ans := []byte(s)
	i, j := 0, len(ans)-1
	for i < j {
		for i < j && !unicode.IsLetter(rune(ans[i])) {
			i++
		}
		for i < j && !unicode.IsLetter(rune(ans[j])) {
			j--
		}
		if i < j {
			ans[i], ans[j] = ans[j], ans[i]
			i++
			j--
		}
	}
	return string(ans)

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

按奇偶排序数组Ⅱ

func sortArrayByParityII(nums []int) []int {
	odd, even, n := 0, 1, len(nums)
	if n < 2 {
		return nums
	}
	for even < n && odd < n {
		for even < n && nums[even]%2 == 1 {
			even += 2
		}
		for odd < n && nums[odd]%2 == 0 {
			odd += 2
		}
		if even < n && odd < n {
			nums[even], nums[odd] = nums[odd], nums[even]
			even += 2
			odd += 2
		}
	}
	return nums
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

长按键入

func isLongPressedName(name string, typed string) bool {
	n, m := len(name), len(typed)
	i, j := 0, 0
	if n == 0 {
		return m == 0
	}
	for i < n || j < m {
		if i < n {
			if j >= m {
				return false
			} else if name[i] == typed[j] {
				i++
				j++
			} else if j > 0 && typed[j] == typed[j-1] {
				j++
			} else {
				return false
			}
		} else {
			if typed[j] == typed[j-1] {
				j++
			} else {
				return false
			}
		}
	}
	return true
}
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 numUniqueEmails(emails []string) int {
	vis := make(map[string]struct{}, len(emails))
	for _, v := range emails {
		all := strings.Split(v, "@")
		if len(all) < 2 {
			continue
		}
		tmp := ""
		for i := 0; i < len(all[0]); i++ {
			if all[0][i] == '+' {
				break
			} else if all[0][i] != '.' {
				tmp += string(all[0][i])
			}
		}
		real := tmp + "@" + all[1]
		if _, ok := vis[real]; !ok {
			vis[real] = struct{}{}
		}
	}
	return len(vis)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最近的请求次数

type RecentCounter struct {
	count []int
}

func Constructor() RecentCounter {
	recentCounter := RecentCounter{
		count: []int{},
	}
	return recentCounter
}

func (this *RecentCounter) Ping(t int) int {
	this.count = append(this.count, t)
	for this.count[0] < t-3000 {
		this.count = this.count[1:]
	}
	return len(this.count)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

有效的山脉数组

func validMountainArray(arr []int) bool {
	cur := 0
	n := len(arr)
	if n == 0 {
		return true
	}
	for cur+1 < n && arr[cur+1] > arr[cur] {
		cur++
	}
	if cur == 0 || cur+1 == n {
		return false
	}
	for cur+1 < n && arr[cur] > arr[cur+1] {
		cur++
	}
	return cur+1 >= n
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递增字符串匹配

贪心：当s[0]="I"时，那么使ans[0]=0，则无论ans[1]取何值，都会满足条件，同理s[0]=“D”时，使ans[0]=n。对于剩余的也是同理。

func diStringMatch(s string) []int {
	n := len(s)
	ans := make([]int, n+1)
	cnt := 0
	min, max := 0, n
	for _, v := range s {
		if v == 'I' {
			ans[cnt] = min
			min++
		} else {
			ans[cnt] = max
			max--
		}
		cnt++
	}
	ans[n] = min
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

验证外星语词典

func isAlienSorted(words []string, order string) bool {
	n := len(order)
	cnt := make([]int, n)
	for i := 0; i < n; i++ {
		cnt[order[i]-'a'] = i
	}
	for i := 1; i < len(words); i++ {
		m := len(words[i-1])
		m2 := len(words[i])
		for j := 0; j < m; j++ {
			if j+1 > m2 {
				return false
			}
			if cnt[words[i][j]-'a'] < cnt[words[i-1][j]-'a'] {
				return false
			} else if cnt[words[i][j]-'a'] > cnt[words[i-1][j]-'a'] {
				break
			}
		}
	}
	return true
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在长度2N的数组找出重复N次的元素

解法1：哈希数组标记：
略
解法2：n>2时，该元素必然存在两个重复值之间的间隔一定小于等于2，若重复值间隔都大于2，则元素一共有（n-1）*3+1个，n>2时，（n-1）3+1>2n的，所以一定存在重复值间隔小于等于2的。
n=2时，只需要特判第一个和最后一个是否相等。

func repeatedNTimes(nums []int) int {
	n := len(nums)
	if n < 4 {
		return 0
	}
	for i := 0; i < n-1; i++ {
		if (i+2 < n && nums[i] == nums[i+2]) || nums[i] == nums[i+1] {
			return nums[i]
		}
	}
	if nums[0] == nums[n-1] {
		return nums[0]
	}
	return 0
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三角形的最大周长

func largestPerimeter(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	for i := n - 1; i >= 2; i-- {
		if nums[i] < nums[i-1]+nums[i-2] {
			return nums[i] + nums[i-1] + nums[i-2]
		}
	}
	return 0
}

1
2
3
4
5
6
7
8
9
10
11

有序数组的平方

func quickSort(nums []int, l int, r int) {
	if l >= r {
		return
	}
	index := nums[l]
	left, right := l, r
	for left < right {
		for left < right && nums[right] >= index {
			right--
		}
		if left < right {
			nums[left] = nums[right]
		}
		for left < right && nums[left] < index {
			left++
		}
		if left < right {
			nums[right] = nums[left]
		}
	}
	nums[left] = index
	//fmt.Printf("l:%v r:%v val:%v\n", l, r, nums)
	quickSort(nums, l, left-1)
	quickSort(nums, left+1, r)
}

func sortedSquares(nums []int) []int {
	for i, v := range nums {
		nums[i] = v * v
	}
	quickSort(nums, 0, len(nums)-1)
	return nums
}

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 reverse(num []int) {
	for l, r := 0, len(num)-1; l < r; l, r = l+1, r-1 {
		num[l], num[r] = num[r], num[l]
	}
}

func addToArrayForm(num []int, k int) []int {
	reverse(num)
	n := len(num)
	for i := 0; i < n; i++ {
		k += num[i]
		num[i] = k % 10
		k = k / 10
	}
	for k != 0 {
		num = append(num, k%10)
		k /= 10
	}
	reverse(num)
	return num
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可以被进一步捕获的棋子数

func numRookCaptures(board [][]byte) int {
	cur_x, cur_y := -1, -1
	n := len(board)
	if n == 0 {
		return 0
	}
	m := len(board[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'R' {
				cur_x, cur_y = i, j
				break
			}
		}
	}
	if cur_x == -1 {
		return 0
	}
	ans := 0
	toward := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for _, v := range toward {
		for step := 1; ; step++ {
			x, y := cur_x+step*v[0], cur_y+step*v[1]
			if x < 0 || y < 0 || x >= n || y >= m || board[x][y] == 'B' {
				break
			} else if board[x][y] == 'p' {
				ans++
				break
			}
		}
	}
	return ans
}
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 commonChars(words []string) []string {
	minFreq := [26]int{}
	for i := range minFreq {
		minFreq[i] = math.MaxInt
	}
	for _, word := range words {
		fre := [26]int{}
		for _, v := range word {
			fre[v-'a']++
		}
		for i, f := range fre {
			if f < minFreq[i] {
				minFreq[i] = f
			}
		}
	}
	ans := []string{}
	for i := 0; i < 26; i++ {
		for j := 0; j < minFreq[i]; j++ {
			ans = append(ans, string('a'+i))
		}
	}
	return ans
}

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

K次取反后最大化的数组和

func sum(nums []int) int {
	ans := 0
	for _, v := range nums {
		ans += v
	}
	return ans
}

func largestSumAfterKNegations(nums []int, k int) int {
	if k == 0 {
		return sum(nums)
	}
	sort.Ints(nums)
	zero := false
	var i int
	var v int
	for i, v = range nums {
		if v > 0 {
			break
		} else if v == 0 {
			zero = true
			break
		} else {
			nums[i] = -v
			k--
			if k == 0 {
				break
			}
		}
	}
	if k > 0 && !zero {
		if k%2 == 0 {
			return sum(nums)
		} else {
			min := nums[i]
			if i > 0 && nums[i-1] < min {
				min = nums[i-1]
			}
			return sum(nums) - 2*min
		}
	}
	return sum(nums)
}

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 bitwiseComplement(n int) int {
	if n == 0 {
		return 1
	}
	tmp := n
	base := 1
	for tmp > 0 {
		tmp >>= 1
		n ^= base
		base = base << 1
		//fmt.Println(tmp)
	}
	return n ^ tmp
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

将数组分成和相等的三个部分

func canThreePartsEqualSum(arr []int) bool {
	n := len(arr)
	if n == 0 {
		return false
	}
	sum := make([]int, n)
	sum[0] = arr[0]
	for i := 1; i < n; i++ {
		sum[i] = sum[i-1] + arr[i]
	}
	for i := 0; i < n-1; i++ {
		suffiex := sum[n-1] - sum[i]
		for j := 0; j < i; j++ {
			if sum[i]-sum[j] == suffiex && sum[j] == suffiex {
				return true
			}
		}
	}
	return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

可被5整除的二进制前缀

func prefixesDivBy5(nums []int) []bool {
	ans := make([]bool, len(nums))
	cur := 0
	for i, v := range nums {
		cur = (cur<<1 | v) % 5
		if cur == 0 {
			ans[i] = true
		} else {
			ans[i] = false
		}
	}
	return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除最外层的括号

func removeOuterParentheses(s string) string {
	cnt := 0
	start := 0
	var ans strings.Builder
	byte_data := []byte(s)
	for i, v := range byte_data {
		if v == '(' {
			cnt++
		} else if v == ')' {
			cnt--
			if cnt == 0 {
				tmp := byte_data[start+1 : i]
				//fmt.Printf("i:%v tmp:%v\n", i, string(tmp))
				start = i + 1
				ans.Write(tmp)
			}
		}
	}
	return ans.String()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

从根到叶的二进制数之和

func sumRootToLeaf(root *TreeNode) int {
	if root == nil {
		return 0
	}
	ans := 0
	var dfs func(cur *TreeNode, sum int)
	dfs = func(cur *TreeNode, sum int) {
		if cur.Left == nil && cur.Right == nil {
			ans += sum*2 + cur.Val
			return
		}
		sum = sum*2 + cur.Val
		if cur.Left != nil {
			dfs(cur.Left, sum)
		}
		if cur.Right != nil {
			dfs(cur.Right, sum)
		}
	}
	dfs(root, root.Val)
	return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

除数博弈

先看一下n=1、2、3时的胜败情况，然后大胆根据规律猜测，最后数学验证法验证
解法1：数学分析

func divisorGame(n int) bool {
    return n%2==0
}
1
2
3

解法2：动态规划

func divisorGame(n int) bool {
	dp := make([]bool, n+3)
	dp[1], dp[2] = false, true
	for i := 3; i <= n; i++ {
		for j := 1; j < i; j++ {
			if i%j == 0 && !dp[i-j] {
				dp[i] = true
				break
			}
		}
	}
	return dp[n]

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

距离顺序排序矩阵单元格

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) [][]int {
	ans := make([][]int, 0, rows*cols)
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			ans = append(ans, []int{i, j})
		}
	}
	sort.Slice(ans, func(i, j int) bool {
		return abs(ans[i][0]-rCenter)+abs(ans[i][1]-cCenter) < abs(ans[j][0]-rCenter)+abs(ans[j][1]-cCenter)
	})
	return ans
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

有效的回旋镖

func isBoomerang(points [][]int) bool {
	return (points[2][1]-points[1][1])*(points[2][0]-points[0][0]) != (points[2][1]-points[0][1])*(points[2][0]-points[1][0])
}
1
2
3

最后一块石头的重量

type Maxheap struct {
	sort.IntSlice
}

func (m Maxheap) Less(i, j int) bool {
	return m.IntSlice[i] > m.IntSlice[j]
}

func (m *Maxheap) Push(x any) {
	m.IntSlice = append(m.IntSlice, x.(int))
}

func (h *Maxheap) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}


func lastStoneWeight(stones []int) int {
	if len(stones) == 0 {
		return 0
	}
	hp := &Maxheap{stones}
	heap.Init(hp)
	var v1 int
	var v2 int
	for hp.Len() > 1 {
		v1 = heap.Pop(hp).(int)
		v2 = heap.Pop(hp).(int)
		if v1 > v2 {
			heap.Push(hp, v1-v2)
		}
	}
	if hp.Len() == 0 {
		return 0
	}
	return hp.IntSlice[0]
}

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

手写堆

var n int

func down(cur int, stone []int) {
	base := stone[cur] //9
	tmp := 2*cur + 1   //10
	for tmp < n {
		if tmp+1 < n && stone[tmp] < stone[tmp+1] {
			tmp++
		}
		if stone[tmp] < base {
			stone[cur] = base
			return
		}
		stone[cur] = stone[tmp]
		cur = tmp
		tmp = tmp*2 + 1
	}
	stone[cur] = base
}

func heapsort(stone []int) {
	for i := n / 2; i >= 0; i-- {
		down(i, stone)
	}
}

func pop(stone []int) int {
	val := stone[0]
	stone[0] = stone[n-1]
	n--
	heapsort(stone)
	return val
}

func push(stone []int, val int) {
	stone[n] = val
	n++
	heapsort(stone)
}

func lastStoneWeight(stones []int) int {
	n = len(stones)
	heapsort(stones)
	if n == 0 {
		return 0
	}
	for n > 1 {
		v1 := pop(stones)
		v2 := pop(stones)
		//fmt.Println(v1, v2)
		if v1 > v2 {
			push(stones, v1-v2)
		}
		//fmt.Println("v1:", v1, "v2:", v2, "n:", n, "stone:", stones)
	}
	if n == 1 {
		return stones[0]
	}
	return 0
}
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

找出所有数组中消失的数字

原地找出

func findDisappearedNumbers(nums []int) (ans []int) {
	n := len(nums)
	if n == 0 {
		return nil
	}
	for _, v := range nums {
		v = (v - 1) % n
		nums[v] += n
	}
	for i, v := range nums {
		if v <= n {
			ans = append(ans, i+1)
		}
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

反转链表

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	p := head.Next
	head.Next = nil
	for p != nil {
		tmp := p.Next
		p.Next = head
		head = p
		p = tmp
	}
	return head
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Excel表列序号

func titleToNumber(columnTitle string) int {
	ans := 0
	for _, v := range columnTitle {
		ans = ans*26 + int(v-'A') + 1
	}
	return ans
}
1
2
3
4
5
6
7

替换空格

func replaceSpace(s string) string {
	index := strings.Index(s, " ")
	var ret strings.Builder
	for index >= 0 {
		ret.WriteString(s[:index])
		ret.WriteString("%20")
		s = s[index+1:]
		index = strings.Index(s, " ")
	}
	if s != "" {
		ret.WriteString(s)
	}
	return ret.String()
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

用两个栈实现队列

type CQueue struct {
	inStack, outStack []int
}

func Constructor() CQueue {
	return CQueue{
		inStack:  []int{},
		outStack: []int{},
	}
}

func (this *CQueue) AppendTail(value int) {
	this.inStack = append(this.inStack, value)
}

func (this *CQueue) DeleteHead() int {
	if len(this.outStack) == 0 && len(this.inStack) == 0 {
		return -1
	}
	if len(this.outStack) == 0 {
		for len(this.inStack) > 0 {
			this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
			this.inStack = this.inStack[:len(this.inStack)-1]
		}
	}
	val := this.outStack[len(this.outStack)-1]
	this.outStack = this.outStack[:len(this.outStack)-1]
	return val
}
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 findRepeatNumber(nums []int) int {
	i, n := 0, len(nums)
	for i < n {
		if nums[i] == i {
			i++
			continue
		}
		if nums[i] == nums[nums[i]] {
			return nums[i]
		}
		nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

旋转数组的最小数字

func minArray(numbers []int) int {
	n := len(numbers)
	if n == 0 {
		return 0
	}
	l, r := 0, n-1
	var mid int
	for l < r {
		mid = (l + r) >> 1
		if numbers[mid] > numbers[r] {
			l = mid + 1
		} else if numbers[mid] < numbers[r] {
			r = mid
		} else {
			r--
		}
	}
	return numbers[l]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除列表节点

解1：

func deleteNode(head *ListNode, val int) *ListNode {
	if head.Val == val {
		return head.Next
	}
	pre := head
	for pre.Next != nil && pre.Next.Val != val {
		pre = pre.Next
	}
	if pre.Next == nil {
		return head
	}
	pre.Next = pre.Next.Next
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法2：哨兵节点

func deleteNode(head *ListNode, val int) *ListNode {
	tmp := &ListNode{Val: -1, Next: head}
	pre := tmp
	for pre.Next != nil && pre.Next.Val != val {
		pre = pre.Next
	}
	if pre.Next == nil {
		return head
	}
	pre.Next = pre.Next.Next
	return tmp.Next
}
1
2
3
4
5
6
7
8
9
10
11
12

找出中枢整数

func pivotInteger(n int) int {
	num := (n*n + n) / 2
	sqrt_num := int(math.Sqrt(float64(num)))
	if sqrt_num*sqrt_num != num {
		return -1
	}
	return sqrt_num
}
1
2
3
4
5
6
7
8

按分隔符拆分字符串

func splitWordsBySeparator(words []string, separator byte) []string {
	ans := []string{}
	for _, v := range words {
		tmp := []string{}
		before, after := 0, 0
		for after < len(v) {
			if v[after] == separator {
				//fmt.Println(before, after, v)
				if after == before {
					before++
				} else {
					tmp = append(tmp, v[before:after])
					before = after + 1
				}
			} else if after == len(v)-1 {
				tmp = append(tmp, v[before:after+1])
			}
			after++
		}
		ans = append(ans, tmp...)
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

对称的二叉树

func isSymmetric(root *TreeNode) bool {
	var dfs func(c1 *TreeNode, c2 *TreeNode) bool
	dfs = func(c1 *TreeNode, c2 *TreeNode) bool {
		if c1 == nil && c2 == nil {
			return true
		}
		if c1 == nil || c2 == nil {
			return false
		}
		return c1.Val == c2.Val && dfs(c1.Left, c2.Right) && dfs(c1.Right, c2.Left)
	}
	return dfs(root, root)
}
1
2
3
4
5
6
7
8
9
10
11
12
13

顺时针打印矩阵

func spiralOrder(matrix [][]int) []int {
	n := len(matrix)
	if n == 0 {
		return nil
	}
	m := len(matrix[0])
	ans := []int{}
	total := n * m
	k := 0
	row, col := 0, 0
	for i := 0; i < total; i++ {
		//fmt.Println(row, col)
		ans = append(ans, matrix[row][col])
		if row == k && col < m-k-1 {
			col++
		} else if col == m-k-1 && row < n-k-1 {
			row++
		} else if row == n-k-1 && col > k {
			col--
		} else if col == k && row >= k {
			row--
		}
		if row == k && col == k {
			k++
			row, col = k, k
		}
	}
	return ans
}

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

包含min函数的栈

解法1：辅助数组

type MinStack struct {
	array     []int
	min_array []int
	len       int
	min_len   int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{
		array:     []int{},
		min_array: []int{},
		len:       0,
		min_len:   0,
	}
}

func (this *MinStack) Push(x int) {
	if this.array == nil {
		return
	}
	if this.min_len == 0 {
		this.array = append(this.array, x)
		this.min_array = append(this.min_array, x)
		this.len++
		this.min_len++
		return
	}
	m := this.min_array[this.min_len-1]
	if x < m {
		m = x
	}
	this.array = append(this.array, x)
	this.min_array = append(this.min_array, m)
	this.len++
	this.min_len++
	return
}

func (this *MinStack) Pop() {
	this.len--
	this.min_len--
	this.array = this.array[:this.len]
	this.min_array = this.min_array[:this.min_len]
}

func (this *MinStack) Top() int {
	if this.len == 0 {
		return -1
	}
	return this.array[this.len-1]
}

func (this *MinStack) Min() int {
	if this.min_len == 0 {
		return -1
	}
	return this.min_array[this.min_len-1]
}
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

只需要维护两个栈，第一个栈存值，第二个栈存遍历到这个数时的最小值。

解法2：差分数组

type MinStack struct {
	Stack []int
	Miner int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{
		Stack: []int{},
	}
}

func (this *MinStack) Push(x int) {
	if len(this.Stack) == 0 {
		this.Miner = x
		this.Stack = append(this.Stack, 0)
	} else {
		this.Stack = append(this.Stack, x-this.Miner)
		if this.Miner > x {
			this.Miner = x
		}
	}
}

func (this *MinStack) Pop() {
	l := len(this.Stack)
	if l == 0 {
		return
	}
	t := this.Stack[l-1]
	if t < 0 {
		this.Miner = this.Miner - t
	}
	this.Stack = this.Stack[:l-1]
}

func (this *MinStack) Top() int {
	if len(this.Stack) == 0 {
		return -1
	}

	tmp := this.Stack[len(this.Stack)-1]
	if tmp > 0 {
		return this.Miner + tmp
	} else {
		return this.Miner
	}
}

func (this *MinStack) Min() int {
	return this.Miner
}

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 validateStackSequences(pushed []int, popped []int) bool {
	n := len(pushed)
	if len(popped) != n {
		return false
	}
	if n == 0 {
		return len(popped) == 0
	}
	stack := []int{}
	vis := make(map[int]struct{}, n)
	cur := 0
	for _, v := range popped {
		if _, ok := vis[v]; ok {
			if len(stack) == 0 || stack[len(stack)-1] != v {
				return false
			}
			stack = stack[:len(stack)-1]
			delete(vis, v)
		} else {
			for cur < n && stack[cur] != v {
				stack = append(stack, pushed[cur])
				vis[pushed[cur]] = struct{}{}
				cur++
			}
			if cur == n {
				return false
			} else {
				cur++
			}
		}
	}
	return true
}
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 passThePillow(n int, time int) int {
	mul, left := time/(n-1), time%(n-1)
	if mul%2 == 0 {
		return left + 1
	} else {
		return n - left
	}
}
 
1
2
3
4
5
6
7
8
9

最长平衡子字符串

func findTheLongestBalancedSubstring(s string) int {
	ans := 0
	cnt0, cnt1 := 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == '0' && i != 0 && s[i-1] == '1' {
			cnt0 = 1
			cnt1 = 0
			continue
		}
		if s[i] == '0' {
			cnt0++
		} else if s[i] == '1' {
			cnt1++
			ans = max(ans, 2*min(cnt1, cnt0))
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当遇到10时，将cnt0=1，cnt1=0
当遇到1时，尝试更新答案2*min(cnt1,cnt0)
当遇到0时，cnt0++

时间复杂度：O(n)
空间复杂度：O(1)

字典序最小回文串

func makeSmallestPalindrome(s string) string {
    l,r:=0,len(s)-1
    ans:=make([]byte,len(s))
    for l<r{
        if s[l]!=s[r]{
            if s[l]>s[r]{
                ans[l],ans[r]=s[r],s[r]
            }else{
                ans[l],ans[r]=s[l],s[l]
            }
        }else{
            ans[l],ans[r]=s[l],s[r]
        }
        l++
        r--
    }
    if l==r{
        ans[l]=s[l]
    }
    return string(ans)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

数组中重复的数字

func duplicate( numbers []int ) int {
    // write code here
    for i:=0;i<len(numbers);i++{
        for i!=numbers[i]{
            if numbers[i]==numbers[numbers[i]]{
                return numbers[i]
            }
            tmp:=numbers[i]
            numbers[i]=numbers[tmp]
            numbers[tmp]=tmp
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果不存在重复的数字，则最终一定是所有的numbers[i]=i。我们只需要在遇到numers[i]时把它放到numbers[numbers[i]]，如果已经那个位置已经是numbers[i]则代表重复

时间复杂度：O(n)
空间复杂度：O(1)

不修改数组找出重复的数字

func getDuplication(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if is_ok(nums, mid) {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}
1
2
3
4
5
6
7
8
9
10
11
12

思路：
在没有重复值的情况下1~n各一个，加入一个数字cur后，数组中小于等于cur的数字就大于cur。
二分一个答案index，如果数组中小于等于index的数字大于inde，说明重复的数字是小于等于index，否则则大于index。

时间复杂度：O(nlogn)
空间复杂度：O(1)

复杂链表的复制

func Clone( head *RandomListNode ) *RandomListNode {
    //write your code here
    RandonMap:=make(map[*RandomListNode]*RandomListNode)
    cur:=head
    var newHead *RandomListNode
    var newCur *RandomListNode
    for cur!=nil{
        if newHead==nil{
            newHead=&RandomListNode{
                Label: cur.Label,
            }
            newCur=newHead
        }else{
            newCur.Next=&RandomListNode{
                Label: cur.Label,
            }
            newCur=newCur.Next
        }
        RandonMap[cur]=newCur
        cur=cur.Next
    }
    cur=head
    newCur=newHead
    for cur!=nil{
        newCur.Random=RandonMap[cur.Random]
        cur=cur.Next
        newCur=newCur.Next
    }
    return newHead
}
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

用一个map来记录原链表节点与新建链表节点的映射便于random指针的赋值

二叉搜索树与双向链表

func Convert( pRootOfTree *TreeNode ) *TreeNode {
    // write code here
    var dfs func(cur *TreeNode)(*TreeNode,*TreeNode)
    dfs=func(cur *TreeNode) (*TreeNode,*TreeNode) {
        if cur==nil{
            return nil,nil
        }
        leftHead,leftTail:=cur,cur
        rightHead,rightTail:=cur,cur
        if cur.Left!=nil{
            leftHead,leftTail=dfs(cur.Left)
            cur.Left=leftTail
            leftTail.Right=cur
        }
        if cur.Right!=nil{
            rightHead,rightTail=dfs(cur.Right)
            cur.Right=rightHead
            rightHead.Left=cur
        }
        return leftHead,rightTail
    }
    head,_:=dfs(pRootOfTree)
    return 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