摘要:本文主要向大家介绍了机器学习入门之简单聊聊对计算机的学习感受,通过具体的内容向大家展现,希望对大家学习机器学习入门有所帮助。
本文主要向大家介绍了机器学习入门之简单聊聊对计算机的学习感受,通过具体的内容向大家展现,希望对大家学习机器学习入门有所帮助。
在解决一道利用二分算法就很简单,不知道二分算法就无从下手的问题过程中,可以深刻体会到算法的重要性。
题目
现在,让我们放空自己,来看一道题目:
给一棵二叉树,找出从根节点出发到叶节点的路径中,和最大的一条。返回该和。
如下,返回4
1
/ \
2 3
题目中的例子过于简单,举个复杂些的例子:
1
/ \
6 7
/ \ / \
3 12 1 2
解题思路
如果高中的你,并不知道“分治算法”,你该怎么解这个题目?只能说很难。
常规思路是每往下一层,就判断哪个分支更大(1->7分支),但这只是贪图眼前,无法保证当前选择的分支的子树也是值更大(1->7的分支均小于1->6的分支)。这如何是好,只能计算所有分支和,最后进行比较,这显然不行。
但如果你知道分治算法(前提),并且看到本题也想到了分治算法(根本),那问题就很简单(细枝末节)。
根据分治算法思想,将问题先“分”后“治”。
分:将树分成左右子树(二叉树是纯天然的分治结构),分别计算左子树和右子树的最大路径和。
治:比较左子树和右子树的和的大小,取大值再加上自己的值。
整个过程递归一下,代码就出来了:
//C++
int maxPathSum(TreeNode *root) {
if(root == NULL)
return 0;
int left = maxPathSum(root->left);
int right = maxPathSum(root->right);
return max(left, right) + root->val;
}
本题对于熟悉分治算法的人来说是入门题目,可是不了解分治算法的话,却很难快速解决。
个人笔记
本来写到上面就算结束了,但还是想记下自己的更多想法,外人当个人牢骚看看即可。
1. 分治算法在“分”的过程中并没有做实际的工作,也没有给出任何有用的解。完全是利用递归在到达最底层时才给出解,然后依靠递归的回归步骤慢慢给出解。(含有一定的抽象意味)
2. 在“治”的过程中也是“有着对第一步·分·的绝对信任”,直接对待求的解进行计算。
3. 整个步骤和“求阶乘”的递归基本是一样的,只是多了“分”的过程。
4. 如果不是二叉树结构的题目,用分治可能就没有这么直观,直接用root->left、root -> right 就能表示左右分支。不过在数组里应该可以用> index、< index来表示。
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标人工智能机器学习频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号