Categorygithub.com/yiranzai/algo-golangleetcode
package
1.0.7
Repository: https://github.com/yiranzai/algo-golang.git
Documentation: pkg.go.dev
Overview
Dependencies
6
Dependents
0

# README

Leetcode

目录

64. 最小路径和

Difficulty: 中等

给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Solution

Language: GO

func minPathSum(grid [][]int) int {
	lengY := len(grid)-1
	lengX := len(grid[0])-1
	for y := 0; y <= lengY; y++ {
		for x := 1; x <= lengX; x++ {
			if y == 0 {
				grid[y][x] += grid[y][x-1]
				continue
			}
			grid[y][x] += MinInt(grid[y-1][x], grid[y][x-1])
		}
		if y == lengY {
			continue
		}
		grid[y+1][0] += grid[y][0]
	}

	return grid[lengY][lengX]
}

func MinInt(vars ...int) int {
	min := vars[0]

	for _, i := range vars {
		if min > i {
			min = i
		}
	}

	return min
}

62. 不同路径

Difficulty: 中等

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1\. 向右 -> 向下 -> 向下
2\. 向下 -> 向下 -> 向右
3\. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10<sup>9</sup>

Solution

Language: GO

func uniquePaths(m int, n int) int {
	if m == 1 && n == 1 {
		return 1
	}
	lenY := m - 1
	lenX := n - 1
	dp := make([]int, n)
	dp[0] = 1
	for y := 0; y <= lenY; y++ {
		for x := 1; x <= lenX; x++ {
			if y == 0 {
				dp[x] = 1
				continue
			}
			dp[x] += dp[x-1]
		}
	}

	return dp[lenX]
}

63. 不同路径 II

Difficulty: 中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1\. 向右 -> 向右 -> 向下 -> 向下
2\. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

Solution

Language: GO

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	lenY := len(obstacleGrid) - 1
	lenX := len(obstacleGrid[0]) - 1
	dp := make([]int, lenX+1)
	dp[0] = 1
	boolY0 := false
	for y := 0; y <= lenY; y++ {
		boolY := 0
		if obstacleGrid[y][0] == 1 {
			boolY0 = true
		}
		if boolY0 {
			dp[0] = 0
			boolY = 1
		}
		for x := 1; x <= lenX; x++ {
			b := obstacleGrid[y][x] == 1
			if b {
				boolY++
				dp[x] = 0
				continue
			}
			if y == 0 {
				if boolY > 0 {
					dp[x] = 0
				}else {
					dp[x] = 1
				}
				continue
			}
			dp[x] += dp[x-1]
		}
		if boolY == lenY + 1 {
			return 0
		}
	}

	return dp[lenX]
}

82. 删除排序链表中的重复元素 II

Difficulty: 中等

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

Solution

Language: GO

​/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *leetcode.ListNode
 * }
 */
func deleteDuplicates(head *leetcode.ListNode) *leetcode.ListNode {
	if head == nil {
		return head
	}
	slow := head
	node := head
	fast := head.Next
	for {
		// 一直遍历快指针直到下一个不同的值出现
		for fast != nil && fast.Val == slow.Val {
			fast = fast.Next
		}

		// 如果快慢指针不相同 且慢指针是head，且快指针动过了，移动head
		if slow.Val == head.Val && slow.Next != fast {
			head = fast
			node = fast
		}
		// 快指针跑完了
		if fast == nil {
			if node != nil {
				node.Next = nil
			}
			return head
		}

		// 移动快慢指针
		slow = fast
		fast = fast.Next

		// 移动node指针
		if (fast == nil || (fast != nil && slow.Val != fast.Val)) && slow != node {
			node.Next = slow
			node = slow
		}

		continue
	}
}

83. 删除排序链表中的重复元素

Difficulty: 简单

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

Solution

Language: GO

​/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *leetcode.ListNode
 * }
 */
func deleteDuplicates(head *leetcode.ListNode) *leetcode.ListNode {
	if head == nil {
		return head
	}
	slow := head
	fast := head.Next
	for {
		// 一直遍历快指针直到下一个不同的值出现
		for fast != nil && fast.Val == slow.Val {
			fast = fast.Next
			continue
		}
		slow.Next = fast
		slow = fast
		if slow == nil {
			return head
		}
		continue
	}
}

70. 爬楼梯

Difficulty: 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1\.  1 阶 + 1 阶
2\.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1\.  1 阶 + 1 阶 + 1 阶
2\.  1 阶 + 2 阶
3\.  2 阶 + 1 阶

Solution

Language: ****

package main

func climbStairs(n int) int {
	if n == 0 || n == 1 {
		return n
	}
	a := 1
	b := 2
	c := 2
	for i := 3; i <= n; i++ {
		c = a + b
		a, b = b, c
	}

	return c
}

55. 跳跃游戏

Difficulty: 中等

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 10<sup>4</sup>
  • 0 <= nums[i] <= 10<sup>5</sup>

Solution

Language: ****

package main

func canJump(nums []int) bool {
	length := len(nums) - 1
	if length == 0 {
		return true
	}
	dps := make([]bool, length)
dd:
	for i := length - 1; i >= 0; i-- {
		if length-i <= nums[i] {
			dps[i] = true
			continue
		}
		for j := nums[i]; j > 0; j-- {
			if dps[i+j] {
				dps[i] = true
				continue dd
			}
		}
		dps[i] = false
	}

	return dps[0]
}

45. 跳跃游戏 II

Difficulty: 中等

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

Solution

Language: ****

package main

func jump(nums []int) int {
	length := len(nums) - 1
	if length == 0 {
		return 0
	}
	dps := make([]int, length+1)

	for i := 0; i <= length; i++ {
		for j := 1; j <= nums[i]; j++ {
			if dps[i] == 0 || dps[i+j] == 0 || dps[i+j] > dps[i] {
				dps[i+j] = dps[i] + 1
			}

			if i+j >= length {
				return dps[length]
			}
		}
	}

	return dps[length]
}

139. 单词拆分

Difficulty: 中等

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

Solution

Language: ****

package main

var (
	dict      map[string]bool
	dp        map[int]int
	maxLength int
)

func wordBreak(s string, wordDict []string) bool {
	dp = make(map[int]int)
	dict = make(map[string]bool)
	for _, s2 := range wordDict {
		maxLength = MaxInt(len(s2), maxLength)
		dict[s2] = true
	}

	return deepWordBreak(s, -1)
}

func deepWordBreak(s string, last int) bool {
	length := len(s)
	if len(s) == 0 {
		return true
	}
	start := last + 1
	for i := 0; i < length; i++ {
		if i > maxLength {
			break
		}
		if dict[s[0:i+1]] {
			if dp[start+i] == 1 {
				return true
			}
			if dp[start+i] == 2 {
				continue
			}
			if deepWordBreak(s[i+1:], start+i) {
				dp[start+i] = 1
				return true
			}
		}
	}
	dp[last] = 2
	return false
}

func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

1143. 最长公共子序列

Difficulty: 中等

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 _子序列 _是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。

Solution

Language: ****

package main

func longestCommonSubsequence(text1 string, text2 string) int {
	var t1Len, t2Len int
	t1Len = len(text1)
	t2Len = len(text2)
	dp := make([][]int, t1Len+1)
	for i := 0; i <= 1; i++ {
		dp[i] = make([]int, t2Len+1)
	}
	k, l := 0, 1
	for i := 1; i <= t1Len; i++ {
		for j := 1; j <= t2Len; j++ {
			if text1[i-1] == text2[j-1] {
				dp[k][j] = dp[l][j-1] + 1
			} else {
				dp[k][j] = MaxInt(dp[l][j], dp[k][j-1])
			}
		}
		l, k = k, l
	}

	return dp[l][t2Len]
}

func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

72. 编辑距离

Difficulty: 困难

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

Solution

Language: ****

package main

func minDistance(word1 string, word2 string) int {
	var t1Len, t2Len int
	t1Len = len(word1)
	t2Len = len(word2)
	if t1Len == 0 {
		return t2Len
	}
	if t2Len == 0 {
		return t1Len
	}
	dp := make([][]int, t1Len+1)
	for i := 0; i <= 1; i++ {
		dp[i] = make([]int, t2Len+1)
		for j := 1; j <= t2Len; j++ {
			dp[i][j] = j
		}
	}
	k, l := 0, 1
	for i := 1; i <= t1Len; i++ {
		dp[k][0] = i
		for j := 1; j <= t2Len; j++ {
			if word1[i-1] == word2[j-1] {
				dp[k][j] = dp[l][j-1]
			} else {
				dp[k][j] = MinInt(dp[l][j], dp[k][j-1], dp[l][j-1]) + 1
			}
		}
		l, k = k, l
	}

	return dp[l][t2Len]
}

func MinInt(vars ...int) int {
	min := vars[0]

	for _, i := range vars {
		if min > i {
			min = i
		}
	}

	return min
}

322. 零钱兑换

Difficulty: 中等

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2<sup>31</sup> - 1
  • 0 <= amount <= 10<sup>4</sup>

Solution

Language: ****

package main

func coinChange(coins []int, amount int) int {
	dps := make(map[int]int, amount)
	return deepCoinChange(coins, amount, dps)
}

func deepCoinChange(coins []int, amount int, dps map[int]int) int {
	if amount == 0 {
		return 0
	}
	if amount < 0 {
		return -1
	}

	if v, ok := dps[amount]; ok {
		return v
	}
	var min *int
	for i := 0; i < len(coins); i++ {
		a := deepCoinChange(coins, amount-coins[i], dps)
		if a != -1 {
			if min == nil {
				min = &a
				*min += 1
			} else {
				if *min > a+1 {
					*min = a + 1
				}
			}
		}
	}
	if min == nil {
		dps[amount] = -1
		return -1
	}
	dps[amount] = *min
	return dps[amount]
}

func MinInt(vars ...int) int {
	min := vars[0]

	for _, i := range vars {
		if min > i {
			min = i
		}
	}

	return min
}

120. 三角形最小路径和

Difficulty: 中等

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -10<sup>4</sup> <= triangle[i][j] <= 10<sup>4</sup>

进阶：

  • 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

Solution

Language: ****

package main

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([]int, n)
	f[0] = triangle[0][0]
	for i := 1; i < n; i++ {
		f[i] = f[i-1] + triangle[i][i]
		for j := i - 1; j > 0; j-- {
			f[j] = min(f[j-1], f[j]) + triangle[i][j]
		}
		f[0] += triangle[i][0]
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		ans = min(ans, f[i])
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

104. 二叉树的最大深度

Difficulty: 简单

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *leetcode.TreeNode
 *     Right *leetcode.TreeNode
 * }
 */
func maxDepth(root *leetcode.TreeNode) int {
	if root == nil {
		return 0
	}

	return MaxInt(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

300. 最长递增子序列

Difficulty: 中等

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

进阶：

  • 你可以设计时间复杂度为 O(n<sup>2</sup>) 的解决方案吗？
  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

Solution

Language: ****

package main

func lengthOfLIS(nums []int) int {
	dp := []int{^(1 << 32)}
	j := 0
	for _, num := range nums {
		if dp[j] < num {
			dp = append(dp, num)
			j++
		} else {
			l, r := 0, j+1
			for l < r {
				m := l + (r-l)/2
				if dp[m] < num {
					l = m + 1
				} else {
					r = m
				}
			}
			dp[l] = num
		}
	}
	return j
}

110. 平衡二叉树

Difficulty: 简单

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树_每个节点 _的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *leetcode.TreeNode
 *     Right *leetcode.TreeNode
 * }
 */
func isBalanced(root *leetcode.TreeNode) bool {
	b, _ := deepIsBalanced(root)
	return b
}

func deepIsBalanced(root *leetcode.TreeNode) (bool, int) {
	if root == nil {
		return true, 0
	}
	b, left := deepIsBalanced(root.Left)
	if !b {
		return false, 0
	}
	b, right := deepIsBalanced(root.Right)
	if !b {
		return false, 0
	}
	return left-right <= 1 && left-right >= -1, MaxInt(left, right) + 1
}

func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

124. 二叉树中的最大路径和

Difficulty: 困难

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

  • 树中节点数目范围是 [1, 3 * 10<sup>4</sup>]
  • -1000 <= Node.val <= 1000

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *leetcode.TreeNode
 *     Right *leetcode.TreeNode
 * }
 */

const INVALID = ^(1 << 32)

func maxPathSum(root *leetcode.TreeNode) int {
	var sum int
	sum = INVALID
	deepMaxPathSum(root, &sum)
	return sum
}

func deepMaxPathSum(root *leetcode.TreeNode, sum *int) int {
	if root == nil {
		return INVALID
	}
	rootVal := root.Val
	left := deepMaxPathSum(root.Left, sum)
	right := deepMaxPathSum(root.Right, sum)

	// 找出左右及单独的自己中最大的
	a := MaxInt(left+rootVal, rootVal, right+rootVal)
	// 比较最大值
	*sum = MaxInt(*sum, a, left+rootVal+right)
	return a
}

func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

61. 旋转链表

Difficulty: 中等

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10<sup>9</sup>

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *leetcode.ListNode
 * }
 */
func rotateRight(head *leetcode.ListNode, k int) *leetcode.ListNode {
	if head == nil || k == 0 {
		return head
	}
	node := head
	length := 1
	for node.Next != nil {
		node = node.Next
		length++
	}
	k = k % length
	if k == 0 {

		return head
	}
	last := node
	node = head
	for i := 0; i < length-k-1; i++ {
		node = node.Next
	}
	last.Next = head
	head = node.Next
	node.Next = nil
	return head
}

236. 二叉树的最近公共祖先

Difficulty: 中等

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 10<sup>5</sup>] 内。
  • -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	node, _, _ := deepLowestCommonAncestor(root, p, q)
	return node
}

func deepLowestCommonAncestor(root, p, q *TreeNode) (*TreeNode, bool, bool) {
	if root == nil {
		return nil, false, false
	}
	// 左边俩都搜到了
	left, blp, blq := deepLowestCommonAncestor(root.Left, p, q)
	if blp && blq {
		return left, blp, blq
	}

	// 右边俩都搜到了
	right, brp, brq := deepLowestCommonAncestor(root.Right, p, q)
	if brp && brq {
		return right, brp, brq
	}

	rp, rq := root.Val == p.Val, root.Val == q.Val

	// 左右及根都没有
	if !rp && !rq && !brp && !brq && !blp && !blq {
		return nil, false, false
	}

	// 左边或者右边搜索到其中一个
	if (rp && (blq || brq)) || (rq && (blp || brp)) || (blq && brp) || (blp && brq) {
		return root, true, true
	}

	return root, rp || blp || brp, rq || blq || brq
}

102. 二叉树的层序遍历

Difficulty: 中等

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	var list []*TreeNode
	list = append(list, root)
	res = make([][]int, 0, 0)
	length := len(list)
	for length > 0 {
		b := make([]int, length)
		for i := 0; i < length; i++ {
			b[i] = list[i].Val
			if list[i].Left != nil {
				list = append(list, list[i].Left)
			}
			if list[i].Right != nil {
				list = append(list, list[i].Right)
			}
		}
		list = list[length:]
		length = len(list)
		res = append(res, b)
	}
	return res
}

107. 二叉树的层序遍历 II

Difficulty: 中等

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	var list []*TreeNode
	list = append(list, root)
	res = make([][]int, 0, 0)
	length := len(list)
	for length > 0 {
		b := make([]int, length)
		for i := 0; i < length; i++ {
			b[i] = list[i].Val
			if list[i].Left != nil {
				list = append(list, list[i].Left)
			}
			if list[i].Right != nil {
				list = append(list, list[i].Right)
			}
		}
		list = list[length:]
		length = len(list)
		res = append([][]int{b}, res...)
	}
	return res
}

103. 二叉树的锯齿形层序遍历

Difficulty: 中等

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	var list []*TreeNode
	list = append(list, root)
	res = make([][]int, 0, 0)
	length := len(list)
	mark := true
	for length > 0 {
		b := make([]int, length)
		for i := 0; i < length; i++ {
			if mark {
				b[i] = list[i].Val
			} else {
				b[i] = list[length-1-i].Val
			}
			if list[i].Left != nil {
				list = append(list, list[i].Left)
			}
			if list[i].Right != nil {
				list = append(list, list[i].Right)
			}
		}

		mark = !mark
		list = list[length:]
		length = len(list)
		res = append(res, b)
	}
	return res
}

98. 验证二叉搜索树

Difficulty: 中等

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

Solution

Language: ****

package main

func isValidBST(root *TreeNode) bool {
	bb, _, _ := deepIsValidBST(root)
	return bb == 1
}

func deepIsValidBST(root *TreeNode) (a int, max int, min int) {
	if root == nil {
		return 2, 0, 0
	}

	if root.Left == nil && root.Right == nil {
		return 1, root.Val, root.Val
	}

	bl, lMax, lMin := deepIsValidBST(root.Left)
	if bl == 0 {
		return bl, 0, 0
	}

	br, rMax, rMin := deepIsValidBST(root.Right)
	if br == 0 {
		return br, 0, 0
	}

	if bl != 2 && root.Val <= lMax {
		return 0, 0, 0
	}

	if br != 2 && root.Val >= rMin {
		return 0, 0, 0
	}

	if bl == 2 {
		return 1, MaxInt(rMax, root.Val), MinInt(rMin, root.Val)
	}

	if br == 2 {
		return 1, MaxInt(lMax, root.Val), MinInt(lMin, root.Val)
	}

	return 1, MaxInt(lMax, rMax, root.Val), MinInt(root.Val, lMin, rMin)
}

//MinInt get the min int vars
func MinInt(vars ...int) int {
	min := vars[0]

	for _, i := range vars {
		if min > i {
			min = i
		}
	}

	return min
}

//MaxInt get the max int vars
func MaxInt(vars ...int) int {
	max := vars[0]

	for _, i := range vars {
		if max < i {
			max = i
		}
	}

	return max
}

173. 二叉搜索树迭代器

Difficulty: ** BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。 boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。 int next()将指针向右移动，然后返回指针处的数字。 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。 **

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
  • int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

  • 树中节点的数目在范围 [1, 105] 内
  • 0 <= Node.val <= 106
  • 最多调用 105 次 hasNext 和 next 操作

进阶：

  • 你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
	root *TreeNode
	list []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
	res := BSTIterator{root: root}
	res.DeepLeft(root)
	return res
}

func (this *BSTIterator) DeepLeft(root *TreeNode) {
	for root != nil {
		this.list = append(this.list, root)
		root = root.Left
	}
}

func (this *BSTIterator) Next() int {
	t := this.list[len(this.list)-1]
	this.list = this.list[0 : len(this.list)-1]
	if t.Right != nil || !this.HasNext() {
		this.DeepLeft(t.Right)
	}
	return t.Val
}

func (this *BSTIterator) HasNext() bool {
	return len(this.list) > 0
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

701. 二叉搜索树中的插入操作

Difficulty: 中等

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

  • 给定的树上的节点数介于 0 和 10^4 之间
  • 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
  • -10^8 <= val <= 10^8
  • 新值和原始二叉搜索树中的任意节点值都不同

Solution

Language: ****

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}
	if root.Val > val {
		root.Left = insertIntoBST(root.Left, val)
	}
	if root.Val < val {
		root.Right = insertIntoBST(root.Right, val)
	}
	return root
}

206. 反转链表

Difficulty: 简单

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Solution

Language: ****

package main

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

func deepReverseList(head *.ListNode) *.ListNode {
if head == nil || head.Next == nil {
return head
}

res := deepReverseList(head.Next)
head.Next = nil
node := res
for node.Next != nil {
node = node.Next
}
node.Next = head
return res
}

92. 反转链表 II

Difficulty: 中等

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || right < 2 || left == right {
		return head
	}
	var end *ListNode
	var tEnd *ListNode
	var tNode *ListNode
	var tHead *ListNode
	current := head
	for i := 1; i <= right-1; i++ {
		// 记录left前的节点
		if i == left-1 {
			end = current
		}
		if i < left-1 {
			current = current.Next
		}
		// 在left时做初始化操作
		if i == left {
			if end == nil {
				tHead = head
			} else {
				tHead = end.Next
			}
			tNode = tHead.Next
			tHead.Next = nil
			tEnd = tHead
		}
		// 开始搞事
		if i >= left {
			tHead, tNode.Next = tNode.Next, tHead
			tHead, tNode = tNode, tHead
		}
	}
	tEnd.Next = tNode
	if end == nil {
		return tHead
	}
	end.Next = tHead
	return head
}

21. 合并两个有序链表

Difficulty: 简单

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	var head *ListNode
	var node *ListNode
	if l1.Val <= l2.Val {
		head = l1
		l1 = l1.Next
	} else {
		head = l2
		l2 = l2.Next
	}
	node = head
	for l1 != nil && l2 != nil {
		for l1 != nil && l1.Val <= l2.Val {
			node.Next = l1
			node = node.Next
			l1 = l1.Next
		}
		for l1 != nil && l2 != nil && l1.Val > l2.Val {
			node.Next = l2
			node = node.Next
			l2 = l2.Next
		}
	}

	if l1 == nil {
		node.Next = l2
	}
	if l2 == nil {
		node.Next = l1
	}

	return head
}

86. 分隔链表

Difficulty: 中等

给你一个链表的头节点 head 和一个特定值x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Solution

Language: ****

package main

func partition(head *leetcode.ListNode, x int) *leetcode.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	left := head
	right := head.Next
	var newHead *leetcode.ListNode

	if head.Val < x {
		newHead, head = head, head.Next
	}
	bHead := newHead
	for right != nil {
		if right.Val < x {
			if bHead == nil {
				newHead = right
				bHead = newHead
			} else {
				bHead.Next = right
				bHead = bHead.Next
			}
			if right == head {
				head = right.Next
			} else {
				left.Next = right.Next
			}
		}
		left, right = left.Next, right.Next
	}
	if bHead == nil {
		return head
	}
	bHead.Next = head
	return newHead
}

148. 排序链表

Difficulty: 中等

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 10<sup>4</sup>] 内
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func merge(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val <= temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else if temp2 != nil {
		temp.Next = temp2
	}
	return dummyHead.Next
}

func sortList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	length := 0
	for node := head; node != nil; node = node.Next {
		length++
	}

	dummyHead := &ListNode{Next: head}
	for subLength := 1; subLength < length; subLength <<= 1 {
		prev, cur := dummyHead, dummyHead.Next
		for cur != nil {
			head1 := cur
			for i := 1; i < subLength && cur.Next != nil; i++ {
				cur = cur.Next
			}

			head2 := cur.Next
			cur.Next = nil
			cur = head2
			for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
				cur = cur.Next
			}

			var next *ListNode
			if cur != nil {
				next = cur.Next
				cur.Next = nil
			}

			prev.Next = merge(head1, head2)

			for prev.Next != nil {
				prev = prev.Next
			}
			cur = next
		}
	}
	return dummyHead.Next
}

190. 颠倒二进制位

Difficulty: 简单

颠倒给定的 32 位无符号整数的二进制位。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

示例 1：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

  • 输入是一个长度为 32 的二进制字符串

Solution

Language: ****

package main

func reverseBits(num uint32) uint32 {
	var sum uint32
	for i := 0; i < 32 && num > 0; i++ {
		sum += (num & 1) << (31 - i)
		num >>= 1
	}
	return sum
}

143. 重排链表

Difficulty: 中等

给定一个单链表 L：L0→L1→…→_ L_n-1→Ln ，
将其重新排列后变为： L0→Ln→_ L_1→Ln-1→L 2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return
	}
	list := make([]*ListNode, 0)
	node := head
	for node != nil {
		list = append(list, node)
		node = node.Next
	}
	var i int
	for i = 1; i <= len(list)>>1; i++ {
		end := list[len(list)-i:][0]
		list[i-1].Next, end.Next = end, list[i]
	}
	list[i-1].Next = nil
}

141. 环形链表

Difficulty: 简单

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1 ，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 10<sup>4</sup>]
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
  • pos 为 -1 或者链表中的一个 有效索引 。

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	if head.Next.Next == head {
		return true
	}
	fast := head.Next.Next
	slow := head

	for slow != nil && fast != nil && fast.Next != nil {
		if slow == fast {
			return true
		}
		slow, fast = slow.Next, fast.Next.Next
	}
	return false
}

142. 环形链表 II

Difficulty: 中等

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

**说明：**不允许修改给定的链表。

进阶：

  • 你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 10<sup>4</sup>] 内
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
  • pos 的值为 -1 或者链表中的一个有效索引

Solution

Language: ****

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	if head.Next.Next == head {
		return head
	}
	fast := head.Next
	slow := head
	first := true
	for slow != nil && fast != nil && fast.Next != nil {
		if slow == fast {
			if first {
				first = false
				slow = head
				fast = fast.Next
				if fast == slow {
					return slow
				}
			} else {
				return slow
			}
		}
		if first {
			slow, fast = slow.Next, fast.Next.Next
		} else {
			slow, fast = slow.Next, fast.Next
		}
	}
	return nil
}

74. 搜索二维矩阵

Difficulty: 中等

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup>

Solution

Language: ****

package main

func searchMatrix(matrix [][]int, target int) bool {
	length := len(matrix)
	left := 0
	right := length
	for left < right {
		// 避免数据超范围
		mid := left + ((right - left) >> 1)
		if matrix[mid][0] < target {
			left = mid + 1
		} else if matrix[mid][0] > target {
			right = mid
		} else {
			return true
		}
	}
	index := left - 1
	if index < 0 {
		return false
	}
	length = len(matrix[index])
	left = 0
	right = length
	for left < right {
		// 避免数据超范围
		mid := left + ((right - left) >> 1)
		if matrix[index][mid] < target {
			left = mid + 1
		} else if matrix[index][mid] > target {
			right = mid
		} else {
			return true
		}
	}
	return false
}

234. 回文链表

Difficulty: 简单

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

Solution

Language: ****

package main

func isPalindrome(head *ListNode) bool {
	var recursivelyCheck func(*ListNode) bool
	recursivelyCheck = func(curNode *ListNode) bool {
		if curNode != nil {
			if !recursivelyCheck(curNode.Next) {
				return false
			}
			if curNode.Val != head.Val {
				return false
			}
			head = head.Next
		}
		return true
	}
	return recursivelyCheck(head)
}

138. 复制带随机指针的链表

Difficulty: 中等

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。

Solution

Language: ****

package main

func copyRandomList(head *Node) *Node {
	if head == nil {
		return head
	}
	node := head
	for node != nil {
		node.Next, node = &Node{Next: node.Next, Val: node.Val, Random: node.Random}, node.Next
	}
	node = head.Next
	for node != nil {
		if node.Random != nil {
			node.Random = node.Random.Next
		}
		if node.Next == nil {
			break
		}
		node = node.Next.Next
	}
	node = head.Next
	b := head.Next
	for head != nil && node.Next != nil {
		head, head.Next = head.Next.Next, head.Next.Next
		node, node.Next = node.Next.Next, node.Next.Next
	}
	head.Next = nil
	return b
}

136. 只出现一次的数字

Difficulty: 简单

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

Solution

Language: ****

package main

func singleNumber(nums []int) int {
	for i := 1; i < len(nums); i++ {
		nums[0] ^= nums[i]
	}
	return nums[0]
}

137. 只出现一次的数字 II

Difficulty: 中等

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

Solution

Language: ****

package main

func singleNumber(nums []int) int {
	a, b := 0, 0
	for _, num := range nums {
		b = (^a) & (b ^ num)
		a = (^b) & (a ^ num)
	}
	return b
}

260. 只出现一次的数字 III

Difficulty: 中等

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

**进阶：**你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

  • 2 <= nums.length <= 3 * 10<sup>4</sup>
  • -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
  • 除两个只出现一次的整数外，nums 中的其他数字都出现两次

Solution

Language: ****

package main

func singleNumber(nums []int) []int {
	diff := 0
	for i := 0; i < len(nums); i++ {
		diff ^= nums[i]
	}
	result := []int{diff, diff}
	// 去掉末尾的1后异或diff就得到最后一个1的位置
	diff = (diff & (diff - 1)) ^ diff
	for i := 0; i < len(nums); i++ {
		if diff&nums[i] == 0 {
			result[0] ^= nums[i]
		} else {
			result[1] ^= nums[i]
		}
	}
	return result
}

90. 子集 II

Difficulty: ** 示例 1： 输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2： 输入：nums = [0] 输出：[[],[0]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 **

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Solution

Language: ****

package main

var res [][]int

func subsetsWithDup(nums []int) [][]int {
	res = make([][]int, 0)
	sort.Ints(nums)
	dfs([]int{}, nums, 0)
	return res
}

func dfs(temp, nums []int, start int) {
	tmp := make([]int, len(temp))
	copy(tmp, temp)
	res = append(res, tmp)
	for i := start; i < len(nums); i++ {
		if i > start && nums[i] == nums[i-1] { // skip
			continue
		}
		temp = append(temp, nums[i])
		dfs(temp, nums, i+1)
		temp = temp[:len(temp)-1]
	}
}

191. 位1的个数

Difficulty: 简单

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为）。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

  • 输入必须是长度为 32 的 二进制串 。

进阶：

  • 如果多次调用这个函数，你将如何优化你的算法？

Solution

Language: ****

package main

func hammingWeight(num uint32) int {
	sum := 0
	for i := 0; i < 32; i++ {
		if num&1 == 1 {
			sum++
		}
		num = num >> 1
	}
	return sum
}

338. 比特位计数

Difficulty: 中等

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 **i **，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

  • 给出时间复杂度为**O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗？
  • 要求算法的空间复杂度为O(n)。
  • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

Solution

Language: ****

package main

func countBits(num int) []int {
	res := make([]int, 0)
	thisOne := 1
	nextOne := 2
	for i := 0; i <= num; i++ {
		if i == 0 {
			res = append(res, 0)
		} else if i == nextOne {
			res = append(res, 1)
			nextOne = nextOne << 1
			thisOne = thisOne << 1
		} else {
			res = append(res, res[i-thisOne]+1)
		}
	}
	return res
}

201. 数字范围按位与

Difficulty: 中等

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0

提示：

  • 0 <= left <= right <= 2<sup>31</sup> - 1

Solution

Language: ****

package main

func rangeBitwiseAnd(left int, right int) int {
	if left == right {
		return left & right
	}

	if right >= left<<2 {
		return 0
	}
	end := 0

	for i := 0; i < 32; i++ {
		if left <= end && right > end {
			return 0
		}
		if end >= right {
			e := end >> 1
			t := end ^ e
			return t | (rangeBitwiseAnd(left&e, right&e))
		}
		end = (end << 1) + 1
	}
	return 0
}

146. LRU 缓存机制

Difficulty: 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

运用你所掌握的数据结构，设计和实现一个 。

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 10<sup>4</sup>
  • 最多调用 3 * 10<sup>4</sup> 次 get 和 put

Solution

Language: ****

package main

import "container/list"

type LRUCache struct {
	limit  int
	list   *list.List
	eMap   map[int]*list.Element
	values map[int]int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{limit: capacity, list: list.New(), eMap: make(map[int]*list.Element), values: make(map[int]int)}
}

func (this *LRUCache) Get(key int) int {
	if e, ok := this.eMap[key]; ok {
		this.list.Remove(e)
		front := this.list.PushFront(key)
		this.eMap[key] = front
		return this.values[key]
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	length := this.list.Len()
	if e, ok := this.eMap[key]; ok {
		this.list.Remove(e)
	} else if length >= this.limit {
		back := this.list.Back()
		this.list.Remove(back)
		delete(this.eMap, back.Value.(int))
		delete(this.values, back.Value.(int))
	}
	front := this.list.PushFront(key)
	this.eMap[key] = front
	this.values[key] = value
}

package main

type LRUCache struct {
	head, tail *Node
	keys       map[int]*Node
	capacity   int
}

type Node struct {
	key, val   int
	prev, next *Node
}

func Constructor(capacity int) LRUCache {
	return LRUCache{keys: make(map[int]*Node), capacity: capacity}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.keys[key]; ok {
		this.Remove(node)
		this.Add(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.keys[key]; ok {
		node.val = value
		this.Remove(node)
		this.Add(node)
		return
	} else {
		node = &Node{key: key, val: value}
		this.keys[key] = node
		this.Add(node)
	}
	if len(this.keys) > this.capacity {
		delete(this.keys, this.tail.key)
		this.Remove(this.tail)
	}
}

func (this *LRUCache) Add(node *Node) {
	node.prev = nil
	node.next = this.head
	if this.head != nil {
		this.head.prev = node
	}
	this.head = node
	if this.tail == nil {
		this.tail = node
		this.tail.next = nil
	}
}

func (this *LRUCache) Remove(node *Node) {
	if node == this.head {
		this.head = node.next
		if node.next != nil {
			node.next.prev = nil
		}
		node.next = nil
		return
	}
	if node == this.tail {
		this.tail = node.prev
		node.prev.next = nil
		node.prev = nil
		return
	}
	node.prev.next = node.next
	node.next.prev = node.prev
}

460. LFU 缓存

Difficulty: 困难

请你为 缓存算法设计并实现数据结构。

实现 LFUCache 类：

  • LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
  • int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
  • void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1);      // 返回 1
                      // cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                      // cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2);      // 返回 -1（未找到）
lFUCache.get(3);      // 返回 3
                      // cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                      // cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1);      // 返回 -1（未找到）
lFUCache.get(3);      // 返回 3
                      // cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4);      // 返回 4
                      // cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

  • 0 <= capacity, key, value <= 10<sup>4</sup>
  • 最多调用 10<sup>5</sup> 次 get 和 put 方法

**进阶：**你可以为这两种操作设计时间复杂度为 O(1) 的实现吗？

Solution

Language: ****

28. 实现 strStr()

Description

Difficulty: 简单

Related Topics: 双指针, 字符串, 字符串匹配

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strStr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

Solution

Language: Go

func strStr(haystack string, needle string) int {

}