一、简单

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)

}