温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何重建python二叉树、求出礼物的最大价值以及计算1+2+…+n

发布时间:2021-12-13 16:53:48 来源:亿速云 阅读:117 作者:柒染 栏目:大数据

如何重建python二叉树、求出礼物的最大价值以及计算1+2+…+n,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3

   / \

  9  20

    /  \

   15   7

限制:

0 <= 节点个数 <= 5000

解题思路:

1,本题考察二叉树的基础:前序遍历、中序遍历

前序遍历特点:根节点在第一个位置

2,找到根元素后,可以根据中序遍历的性质,把二叉树分为两个部分,因为值各不相同,所以,中序数组中和根元素相同位置左侧是左子树

3,前序遍历和中序遍历的相同点,都是先遍历左子树和根节点

4,假设左子树长度为i,那么前序遍历中,1到i一定属于左子树

5,递归解决

代码实现

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func buildTree(preorder []int, inorder []int) *TreeNode {   if len(preorder)==0{       return nil   }
  i:=0   for i<len(inorder)&& inorder[i]!=preorder[0]{       i++   }   l:=buildTree(preorder[1:i+1],inorder[:i])   r:=buildTree(preorder[i+1:],inorder[i+1:])   return &TreeNode{       Left:l,       Val:preorder[0],       Right:r,   }}
礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入: 

[

  [1,3,1],

  [1,5,1],

  [4,2,1]

]

输出: 12

解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示:

0 < grid.length <= 200

0 < grid[0].length <= 200

解题思路:

1,这是一个典型的动态规划题目

2,状态转移方程 dp[i,j]=max(dp[i-1,j],dp[i,j-1])+grid[i-1,j-1]

3,为了方便计算,dp的大小比grid 两个维度都加1

代码实现:

func maxValue(grid [][]int) int {   dp:=make([][]int,len(grid)+1)   for i:=0;i<len(dp);i++{       dp[i]=make([]int,len(grid[0])+1)   }   for i:=1;i<=len(grid);i++{       for j:=1;j<=len(grid[0]);j++{          dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]       }   }   return dp[len(grid)][len(grid[0])]   }
func max(a,b int)int{    if a>b{        return a    }    return b}
求1+2+…+n

求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

示例 1:

输入: n = 3

输出: 6

示例 2:

输入: n = 9

输出: 45

限制:

1 <= n <= 10000

解题思路:

1,这个题目没有啥难度,就是比较贱

2,求和方式有三个:迭代、求和公式、递归

3,限制了前俩,就是第三个

代码实现

func sumNums(n int) int {    if n==1{        return n    }    return sumNums(n-1)+n}

关于如何重建python二叉树、求出礼物的最大价值以及计算1+2+…+n问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI