LeetCode热题HOT100

一、简单

1.两数之和(1)

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

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

package main

import "fmt"

//暴力解法
//时间复杂度：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)
}

2.有效的括号(20)

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

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

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

package main

import "fmt"

//时间复杂度：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)
}

3.合并两个有序链表(21)

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

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

package main

import "fmt"

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)
}

4.最大子序和(53)

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

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

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

package main

import (
	"fmt"
)

//动态规划
//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)
}

5.爬楼梯(70)

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

package main

import "fmt"

//暴力递归，动态规划
//转移方程：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)
}

6.二叉树的中序遍历(94)

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,null,2]
输出：[1,2]

package main

import "fmt"

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)

}