//暴力解法 //时间复杂度:O(N²) //空间复杂度:O(1) functwoSum1(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} } } } returnnil }
//查找表法 //用map记录已经遍历过的数值和下标 //空间换时间 //时间复杂度:O(N) //空间复杂度:O(N) functwoSum2(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 } returnnil }
//优化空间复杂度后的动态规划 //滚动数组思想 //时间复杂度:O(n) //空间复杂度:O(1) funcclimbStairs3(n int)int { p, q, r := 0, 0, 1 for i := 0; i < n; i++ { p = q q = r r = p + q } return r }
funcmain() { 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) 的级别。 funcinorderTraversal1(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 }