LeetCode热题Top100 | 简单

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

//暴力解法
//时间复杂度：O(N²)
//空间复杂度：O(1)
func twoSum1(nums []int, target int) []int {
    for i, v := range nums{
        for j := i + 1; j < len(nums); j++ {
            sum := v + nums[j]
            if sum == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

//查找表法
//用map记录已经遍历过的数值和下标
//空间换时间
//时间复杂度：O(N)
//空间复杂度：O(N)
func twoSum2(nums []int, target int) []int {
    //mapTemp := map[int]int{}
    mapTemp := make(map[int]int, len(nums)) //初始化一定内存，内存消耗更少
    for i, v := range nums {
        if j, ok := mapTemp[target-v]; ok {
            return []int{j, i}
        }
        mapTemp[v] = i
    }
    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9

    result1 := twoSum1(nums, target)
    fmt.Println(result1)

    result2 := twoSum2(nums, target)
    fmt.Println(result2)
}

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()[]{}"
输出：true

示例 2：
输入：s = "{[]}"
输出：true

示例 3：
输入：s = "([)]"
输出：false

//时间复杂度：O(N)
//空间复杂度：O(N+E)，E表示括号的个数
//栈的思想
func isValid(s string) bool {
    if len(s)%2 == 1 {
        return false
    }
    mapTemp := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    var stack []byte
    for i := 0; i < len(s); i++ {
        if v, ok := mapTemp[s[i]]; ok {
            if len(stack) == 0 || stack[len(stack)-1] != v {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

func main() {
    s := "()[]{}"
    b := isValid(s)
    fmt.Println(b)
}

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

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

type ListNode struct {
    Val  int
    Next *ListNode
}

//递归法
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }

    if l2 == nil {
        return l1
    }

    var result *ListNode
    if l1.Val <= l2.Val {
        result = l1
        result.Next = mergeTwoLists1(l1.Next, l2)
    } else {
        result = l2
        result.Next = mergeTwoLists1(l1, l2.Next)
    }

    return result
}

//迭代法
//会比用递归占用更少的空间
func mergeTwoLists2(l1 *ListNode, l2 *ListNode) *ListNode {
    nodeTemp := &ListNode{}
    current := nodeTemp

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }

    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }
    return nodeTemp.Next
}

func main() {
    var h1 = new(ListNode)
    h1.Val = 1
    var h2 = new(ListNode)
    h2.Val = 2
    var h3 = new(ListNode)
    h3.Val = 4
    h1.Next = h2
    h2.Next = h3
    h3.Next = nil

    var h11 = new(ListNode)
    h11.Val = 1
    var h22 = new(ListNode)
    h22.Val = 3
    var h33 = new(ListNode)
    h33.Val = 4
    h11.Next = h22
    h22.Next = h33
    h33.Next = nil

    //result1 := mergeTwoLists1(h1, h11)
    //fmt.Println(result1)

    result2 := mergeTwoLists2(h1, h11)
    fmt.Println(result2)
}

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

示例 2：
输入：nums = [1]
输出：1

//动态规划
//f(i)表示以第i个数结尾的最大连续和
//f(i)=max{f(i−1)+nums[i],nums[i]}
//时间复杂度：O(n)，其中 n 为 nums 数组的长度，我们只需要遍历一遍数组即可求得答案
//空间复杂度：O(1)，我们只需要常数空间存放若干变量
func maxSubArray(nums []int) int {
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        /*
        凡是会让总数变小的值，即<0的值，一律丢弃，
        这里也可以写成：
        if nums[i-1] > 0 {
            nums[i] += nums[i-1]
        }
        */
        if nums[i-1]+nums[i] > nums[i] {
            nums[i] += nums[i-1]
        }
        if max < nums[i] {
            max = nums[i]
        }
    }
    return max
}

func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    result := maxSubArray(nums)
    fmt.Println(result)
}

假设你正在爬楼梯。需要 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 阶

//暴力递归，动态规划
//转移方程：f(x) = f(x-1)+f(x-2)
//时间复杂度：O(2ⁿ)
//空间复杂度：O(n)
func climbStairs1(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    return climbStairs1(n-1) + climbStairs1(n-2)
}

//记忆化递归，动态规划
//把已经用过的楼梯数保存起来直接返回，减少递归次数
//时间复杂度：O(n)
//空间复杂度：O(n)
func climbStairs2(n int) int {
    memo := make([]int, n+1, n+1)
    return climbStairsMemo(n, memo)
}
func climbStairsMemo(n int, memo []int) int {
    if memo[n] > 0 {
        return memo[n]
    }
    if n == 1 {
        memo[n] = 1
    } else if n == 2 {
        memo[n] = 2
    } else {
        memo[n] = climbStairsMemo(n-1, memo) + climbStairsMemo(n-2, memo)
    }
    return memo[n]
}

//优化空间复杂度后的动态规划
//滚动数组思想
//时间复杂度：O(n)
//空间复杂度：O(1)
func climbStairs3(n int) int {
    p, q, r := 0, 0, 1
    for i := 0; i < n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}

func main() {
    n := 10
    result1 := climbStairs1(n)
    fmt.Println(result1)

    result2 := climbStairs2(n)
    fmt.Println(result2)

    result3 := climbStairs3(n)
    fmt.Println(result3)
}

假设你正在爬楼梯。需要 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 阶

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

//递归法
//时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度：O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal1(root *TreeNode) (res []int) {
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node != nil {
            inorder(node.Left)
            res = append(res, node.Val)
            inorder(node.Right)
        }
        return
    }
    inorder(root)
    return
}

//迭代法
//时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度：O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal2(root *TreeNode) (res []int) {
    var stack []*TreeNode
    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
}

func main() {
    var root = new(TreeNode)
    var root1 = new(TreeNode)
    var root2 = new(TreeNode)

    root.Val = 1
    root.Left = nil
    root.Right = root1

    root1.Val = 2
    root1.Right = nil
    root1.Left = root2

    root2.Val = 3
    root2.Left = nil
    root2.Right = nil

    a := inorderTraversal1(root)
    fmt.Println(a)

    b := inorderTraversal2(root)
    fmt.Println(b)

}

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
    3   3

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

//递归法
//时间复杂度：O(n)
//空间复杂度：O(n)
/*可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
pp 指针和 qq 指针一开始都指向这棵树的根，随后 pp 右移时，qq 左移，pp 左移时，qq 右移。
每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称*/
func isSymmetric1(root *TreeNode) bool {
   return check(root, root)
}

func check(p, q *TreeNode) bool {
   if p == nil && q == nil {
      return true
   }
   if p == nil || q == nil {
      return false
   }

   return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}

//迭代法
//时间复杂度：O(n)
//空间复杂度：O(n)
//用队列模拟递归的实现
func isSymmetric2(root *TreeNode) bool {
   u, v := root, root
   var queue []*TreeNode
   queue = append(queue, u)
   queue = append(queue, v)
   for len(queue) > 0 {
      u, v = queue[0], queue[1]
      queue = queue[2:]
      if u == nil && v == nil {
         continue
      }
      if u == nil || v == nil {
         return false
      }
      if u.Val != v.Val {
         return false
      }
      queue = append(queue, u.Left)
      queue = append(queue, v.Right)

      queue = append(queue, u.Right)
      queue = append(queue, v.Left)
   }
   return true
}

func main() {
   var n1 = new(TreeNode)
   var n2 = new(TreeNode)
   var n3 = new(TreeNode)
   var n4 = new(TreeNode)
   var n5 = new(TreeNode)
   var n6 = new(TreeNode)
   var n7 = new(TreeNode)
   n1.Val = 1
   n2.Val = 2
   n3.Val = 2
   n4.Val = 3
   n5.Val = 4
   n6.Val = 4
   n7.Val = 3

   n1.Left = n2
   n1.Right = n3

   n2.Left = n4
   n2.Right = n5

   n3.Left = n6
   n3.Right = n7

   result1 := isSymmetric1(n1)
   fmt.Println(result1)

   result2 := isSymmetric2(n1)
   fmt.Println(result2)
}

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度3

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

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

//深度优先搜索
//时间复杂度：O(n)
//空间复杂度：O(height)
func maxDepth(root *TreeNode) int {
   if root == nil {
      return 0
   }
   return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

//广度优先搜索
//时间复杂度：O(n)
//空间复杂度：最坏情况O(n)
func maxDepth1(root *TreeNode) int {
   if root == nil {
      return 0
   }
   var queue []*TreeNode
   queue = append(queue, root)
   ans := 0
   for len(queue) > 0 {
      sz := len(queue)
      for sz > 0 {
         node := queue[0]
         queue = queue[1:]
         if node.Left != nil {
            queue = append(queue, node.Left)
         }
         if node.Right != nil {
            queue = append(queue, node.Right)
         }
         sz--
      }
      ans++
   }
   return ans
}

func main() {
   var root = new(TreeNode)
   var root1 = new(TreeNode)
   var root2 = new(TreeNode)
   var root3 = new(TreeNode)
   var root4 = new(TreeNode)

   root.Val = 3
   root.Left = root1
   root.Right = root2

   root1.Val = 9
   root2.Val = 20

   root2.Left = root3
   root2.Right = root4

   root3.Val = 15
   root4.Val = 7

   fmt.Println(maxDepth(root))
   fmt.Println(maxDepth1(root))
}

给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

//时间复杂度：O(n)
//空间复杂度：O(1)
func maxProfit(prices []int) int {
   maxNum := 0
   tempMaxNum := 0
   min := prices[0]

   for i := 1; i < len(prices); i++ {
      if prices[i] < min {
         min = prices[i]
      }
      tempMaxNum = prices[i] - min
      if tempMaxNum > maxNum {
         maxNum = tempMaxNum
      }
   }
   return maxNum
}

func main() {
   prices := []int{7, 1, 5, 3, 6, 4}
   fmt.Println(maxProfit(prices))

   pricess := []int{7, 6, 4, 3, 1, 0}
   fmt.Println(maxProfit(pricess))

   fmt.Println(math.MaxInt64)
   fmt.Println(math.MinInt64)
}

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

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

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

//时间复杂度：O(n)
//空间复杂度：O(n)
func singleNumber(nums []int) int {
   repeate := make(map[int]bool)
   for i := 0; i < len(nums); i++ {
      _, exist := repeate[nums[i]]
      if exist {
         repeate[nums[i]] = true
      } else {
         repeate[nums[i]] = false
      }
   }
   for i := 0; i < len(nums); i++ {
      if repeate[nums[i]] == false {
         return nums[i]
      }
   }
   return 0
}

//时间复杂度：O(n)
//空间复杂度：O(n)
func singleNumber1(nums []int) int {
   repeate := make(map[int]bool)
   final := 0
   for i := 0; i < len(nums); i++ {
      if _, exist := repeate[nums[i]]; !exist {
         repeate[nums[i]] = true
         final += nums[i]
      } else {
         final -= nums[i]
      }
   }
   return final
}

//异或
//时间复杂度：O(n)
//空间复杂度：O(1)
func singleNumber2(nums []int) int {
   s := 0
   for i:=0; i<len(nums); i++ {
      s = s ^ nums[i]
   }
   return s
}

func main() {
   a := []int{4, 1, 2, 1, 2}
   fmt.Println(singleNumber(a))

   fmt.Println(singleNumber1(a))

   fmt.Println(singleNumber2(a))

}

给一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

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

type ListNode struct {
	Val  int
	Next *ListNode
}

//方法一：哈希表法
//每到达一个节点，若该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中
//时间复杂度：O(n)
//空间复杂度：O(n)
func hasCycle1(head *ListNode) bool {
	tempMap :=  map[*ListNode]struct{}{}
	for head != nil {
		if _, ok := tempMap[head]; ok {
			return true
		}
		tempMap[head] = struct{}{}
		head = head.Next
	}
	return false
}

//方法二：快慢指针法
//一个慢指针每次移动一步，一个快指针一次移动两步，当快指针追上慢指针后说明存在环
//时间复杂度：O(n)
//空间复杂度：O(1)
func hasCycle2(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow, fast := head, head.Next
	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node1.Val = 3
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 0
	node3.Next = node4
	node4.Val = -4
	node4.Next = node2

	cycle1 := hasCycle1(node1)
	fmt.Println(cycle1)

	cycle2 := hasCycle2(node1)
	fmt.Println(cycle2)

}

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop()—— 删除栈顶的元素。
top()—— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

思路：
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，
只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，
就可以直接返回存储的最小值 m

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

type MinStack struct {
	stack    []int
	minStack []int
}

func Constructor() MinStack {
	return MinStack{
		stack:    []int{},
		minStack: []int{math.MaxInt64},
	}
}

func (this *MinStack) Push(x int) {
	this.stack = append(this.stack, x)
	top := this.minStack[len(this.minStack)-1]
	this.minStack = append(this.minStack, min(x, top))
}

func (this *MinStack) Pop() {
	this.stack = this.stack[:len(this.stack)-1]
	this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
	return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
	return this.minStack[len(this.minStack)-1]
}

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

func main() {

}

给两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点，
如果两个链表不存在相交节点，返回 null。
题目保证整个链式结构中不存在环，且函数返回结果后，链表必须保持其原始结构

设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案

type ListNode struct {
	Val  int
	Next *ListNode
}

//哈希集合法
//思路：遍历链表headA，并将链表headA中的每个节点加入哈希集合中，
//然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。
//时间复杂度：O(m+n)
//空间复杂度：O(n)
func getIntersectionNode1(headA, headB *ListNode) *ListNode {
	tempMap := map[*ListNode]bool{}
	for tmp := headA; tmp != nil; tmp = tmp.Next {
		tempMap[tmp] = true
	}
	for tmp := headB; tmp != nil; tmp = tmp.Next {
		if tempMap[tmp] {
			return tmp
		}
	}
	return nil
}

//双指针法
//时间复杂度：O(m+n)
//空间复杂度：O(1)
func getIntersectionNode2(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}

	pa, pb := headA, headB
	for pa != pb {
		if pa == nil {
			pa = headB
		} else {
			pa = pa.Next
		}

		if pb == nil {
			pb = headA
		} else {
			pb = pb.Next
		}
	}
	return pa
}

func main() {

}

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
可以假设数组是非空的，并且给定的数组总是存在多数元素。

设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

示例1：
输入：[3,2,3]
输出：3

示例2：
输入：[2,2,1,1,1,2,2]
输出：2

//哈希表法
//元素作为key，个数作为value，根据value最大的那个选择key对应的元素即是结果
//时间复杂度：O(n)
//空间复杂度：O(n)
func majorityElement1(nums []int) int {
	tempMap := map[int]int{}
	max := math.MinInt
	final := 0
	for _, v := range nums {
		if _, ok := tempMap[v]; ok {
			tempMap[v]++
		} else {
			tempMap[v] = 1
		}
	}

	for k, v := range tempMap {
		if v > max {
			max = v
			final = k
		}
	}
	return final
}

//排序法
//如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，
//那么下标为 ⌊ n/2 ⌋ 的元素（下标从 0 开始）一定是众数
//时间复杂度：O(nlogn)，将数组排序的时间复杂度为 O(nlogn)
//空间复杂度：O(logn)
func majorityElement2(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

//随机化法
//因为超过 ⌊n/2⌋ 的数组下标被众数占据了，这样随机挑选一个下标对应的元素并验证，有很大的概率能找到众数
//时间复杂度：理论上最坏情况下的时间复杂度为 O(∞)，期望的时间复杂度为 O(n)
//空间复杂度：O(1)
func majorityElement3(nums []int) int {
	for {
		randIndex := rand.Intn(len(nums))
		candidate := nums[randIndex]
		count := 0
		for i := 0; i < len(nums); i++ {
			if nums[i] == candidate {
				count++
				if count > len(nums)/2 {
					return nums[i]
				}
			}
		}
	}
}

//投票算法
//维护一个候选众数 candidate 和它出现的次数 count
//遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，先将 x 的值赋予 candidate，随后判断 x：
//如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
//如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
//在遍历完成后，candidate 即为整个数组的众数
//时间复杂度：O(n)
//空间复杂度：O(1)
func majorityElement4(nums []int) int {
	count := 0
	candidate := 0
	for i := 0; i < len(nums); i++ {
		if count == 0 {
			candidate = nums[i]
		}
		if candidate == nums[i] {
			count++
		} else {
			count--
		}
	}
	return candidate
}

func main() {
	s := []int{2, 2, 1, 1, 1, 2, 2}
	fmt.Println(majorityElement1(s))
	fmt.Println(majorityElement2(s))
	fmt.Println(majorityElement3(s))
	fmt.Println(majorityElement4(s))
}

给一个单链表的头节点 head ，请你反转链表，并返回反转后的链表

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

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

type ListNode struct {
	Val  int
	Next *ListNode
}

//迭代法
//时间复杂度：O(n)
//空间复杂度：O(1)
func reverseList1(head *ListNode) *ListNode {
	var nPrev *ListNode
	nNow := head
	for nNow != nil {
		tempNode := nNow.Next
		nNow.Next = nPrev
		nPrev = nNow
		nNow = tempNode
	}
	return nPrev
}

//递归法
//时间复杂度：O(n)
//空间复杂度：O(n)
//递归过程
/*
  reverseList: head=1
    reverseList: head=2
	    reverseList: head=3
		    reverseList:head=4
			    reverseList:head=5
					终止返回
				cur = 5
				4.next.next->4，即5->4
			cur=5
			3.next.next->3，即4->3
		cur = 5
		2.next.next->2，即3->2
	cur = 5
	1.next.next->1，即2->1

	最后返回cur
*/
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList2(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node5 := new(ListNode)
	node1.Val = 1
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 3
	node3.Next = node4
	node4.Val = 4
	node4.Next = node5
	node5.Val = 5
	//a := reverseList1(node1)
	//for a != nil {
	//	fmt.Println(a.Val)
	//	a = a.Next
	//}

	b := reverseList1(node1)
	for b != nil {
		fmt.Println(b.Val)
		b = b.Next
	}
}

给一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

例如：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

输入：root = []
输出：[]

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

//迭代法
//时间复杂度：O(n)
//空间复杂度：O(n)
func invertTree1(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	var queue []*TreeNode
	queue = append(queue, root)
	for len(queue) > 0 {
		tempA := queue[0]
		queue = queue[1:]
		tempData := tempA.Left
		tempA.Left = tempA.Right
		tempA.Right = tempData
		if tempA.Left != nil {
			queue = append(queue, tempA.Left)
		}
		if tempA.Right != nil {
			queue = append(queue, tempA.Right)
		}
	}
	return root
}

//递归法
//时间复杂度：O(n)
//空间复杂度：O(log(n))，最坏情况下O(n)
func invertTree2(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	left := invertTree2(root.Left)
	right := invertTree2(root.Right)
	root.Left = right
	root.Right = left
	return root
}

func main() {

}

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true，否则，返回 false
能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题

示例1：
输入：head = [1,2,2,1]
输出：true

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

type ListNode struct {
	Val  int
	Next *ListNode
}

//快慢指针法
//时间复杂度：O(n)
//空间复杂度：O(1)
/*
整个流程可以分为以下五个步骤：

找到前半部分链表的尾节点
反转后半部分链表
判断是否回文
恢复链表
返回结果
*/
func isPalindrome1(head *ListNode) bool {
	var reverseList func(head *ListNode) *ListNode
	reverseList = func(head *ListNode) *ListNode {
		var prev, cur *ListNode = nil, head
		for cur != nil {
			nextTmp := cur.Next
			cur.Next = prev
			prev = cur
			cur = nextTmp
		}
		return prev
	}

	var endOfFirstHalf func(head *ListNode) *ListNode
	endOfFirstHalf = func(head *ListNode) *ListNode {
		fast := head
		slow := head
		for fast.Next != nil && fast.Next.Next != nil {
			fast = fast.Next.Next
			slow = slow.Next
		}
		return slow
	}

	if head == nil {
		return true
	}

	firstHalfEnd := endOfFirstHalf(head)
	secondHalfStart := reverseList(firstHalfEnd.Next)

	p1 := head
	p2 := secondHalfStart
	result := true
	for result && p2 != nil {
		if p1.Val != p2.Val {
			result = false
		}
		p1 = p1.Next
		p2 = p2.Next
	}

	firstHalfEnd.Next = reverseList(secondHalfStart)
	return result
}

//将值复制到数组中后用双指针法
//时间复杂度：O(n)
//空间复杂度：O(n)
func isPalindrome2(head *ListNode) bool {
	var vals []int
	for ; head != nil; head = head.Next {
		vals = append(vals, head.Val)
	}
	n := len(vals)
	for i, v := range vals[:n/2] {
		if v != vals[n-1-i] {
			return false
		}
	}
	return true
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node1.Val = 1
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 2
	node3.Next = node4
	node4.Val = 1
	fmt.Println(isPalindrome1(node1))
	fmt.Println(isPalindrome2(node1))
}

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

//双指针，自己的写法
//时间复杂度：O(n)
//空间复杂度：O(1)
func moveZeroes1(nums []int) {
	length := len(nums)
	if length == 0 || length == 1 {
		return
	}
	prev, cur := 0, 1
	for cur < length && prev != cur {
		for nums[prev] != 0 && prev < cur {
			prev++
		}
		if nums[prev] == 0 && nums[cur] == 0 {
			cur++
		}
		if cur < length && nums[prev] == 0 && nums[cur] != 0 {
			tempData := nums[prev]
			nums[prev] = nums[cur]
			nums[cur] = tempData
			prev++
			cur++
		} else {
			cur++
		}
	}
}

//双指针，官方写法
//时间复杂度：O(n)
//空间复杂度：O(1)
func moveZeroes2(nums []int) {
	left, right, n := 0, 0, len(nums)
	for right < n {
		if nums[right] != 0 {
			nums[left], nums[right] = nums[right], nums[left]
			left++
		}
		right++
	}
}

func main() {
	nums := []int{0, 1, 0, 3, 12}
	moveZeroes1(nums)
	fmt.Println(nums)
}

给你一个整数 n ，对于0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，
返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

//Brian Kernighan 算法
//时间复杂度：O(nlog(n))
//空间复杂度：O(1)
func countBits1(n int) []int {
	var onesCount func(x int) int
	onesCount = func(x int) (ones int) {
		for ; x > 0; x &= x - 1 {
			ones++
		}
		return
	}

	bits := make([]int, n+1)
	for i := range bits {
		bits[i] = onesCount(i)
	}
	return bits
}

//动态规划——最高有效位
//时间复杂度：O(n)
//空间复杂度：O(1)
func countBits2(n int) []int {
	bits := make([]int, n+1)
	highBit := 0
	for i := 1; i <= n; i++ {
		if i&(i-1) == 0 {
			highBit = i
		}
		bits[i] = bits[i-highBit] + 1
	}
	return bits
}

//动态规划——最低有效位
//时间复杂度：O(n)
//空间复杂度：O(1)
func countBits3(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bits[i] = bits[i>>1] + i&1
	}
	return bits
}

//动态规划——最低设置位
//时间复杂度：O(n)
//空间复杂度：O(1)
func countBits4(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bits[i] = bits[i&(i-1)] + 1
	}
	return bits
}

func main() {
	n := 10
	fmt.Println(countBits1(n))
	fmt.Println(countBits2(n))
	fmt.Println(countBits3(n))
	fmt.Println(countBits4(n))
}

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗?

示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

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

//原地修改法
//时间复杂度：O(n)
//空间复杂度：O(1)
/*
遍历nums，每遇到一个数 x，就让nums[x−1] 增加 n。
由于nums中所有数均在[1,n]中，增加以后，这些数必然大于 n。
最后遍历nums，若nums[i]未大于 n，
就说明没有遇到过数i+1，这样就找到了缺失的数字
*/
func findDisappearedNumbers(nums []int) []int {
	n := len(nums)
	for _, v := range nums {
		v = (v - 1) % n
		nums[v] += n
	}
	var ans []int
	for i, v := range nums {
		if v <= n {
			ans = append(ans, i+1)
		}
	}
	return ans
}

func main() {
	nums := []int{4, 3, 2, 7, 8, 2, 3, 1}
	fmt.Println(findDisappearedNumbers(nums))
}

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：
输入：x = 3, y = 1
输出：1

//内置位计数功能
//时间复杂度：O(1)
//空间复杂度：O(1)
func hammingDistance1(x int, y int) int {
	return bits.OnesCount(uint(x ^ y))
}

//移位实现位计数
//时间复杂度：O(logC)
//空间复杂度：O(1)
func hammingDistance2(x int, y int) int {
	var ans int
	for s := x ^ y; s > 0; s >>= 1 {
		ans += s & 1
	}
	return ans
}

//Brian Kernighan 算法
//时间复杂度：O(logC)
//空间复杂度：O(1)
func hammingDistance3(x int, y int) int {
	var ans int
	for s := x ^ y; s > 0; s &= s - 1 {
		ans++
	}
	return ans
}

func main() {
	x := 1
	y := 4
	fmt.Println(hammingDistance1(x, y))
	fmt.Println(hammingDistance2(x, y))
	fmt.Println(hammingDistance3(x, y))
}