写点什么

ARTS-week 4

用户头像
steve_lee
关注
发布于: 2021 年 03 月 28 日
ARTS-week 4

Algorithm

题目链接

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

题目分析

前序遍历第一个节点就是 root 节点,通过找到 root 节点在中序遍历数组的位置,可以分开左右子树,递归操作,返回条件是:当一个子树是单一节点(即叶节点)。注意,左右子树可能为空。通过起始点到 root 节点的距离判断左右子树的大小,前序遍历数组里面,根据左右子树大小,很容易判断哪个节点是左右子树根节点,然后就可以完成整棵树的构建。

代码实现

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:       TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {        int start = 0;        int end = preorder.size()-1;        return buildTreewithRoot(preorder, inorder, start, end, 0);     }        int own_find(vector<int>& V, int target, int start_idx, int end_idx){        for(auto i = start_idx; i <= end_idx; i++){            if(V[i] == target){                return i;            }        }        return start_idx;    }    TreeNode* buildTreewithRoot(vector<int>& preorder, vector<int>& inorder, int start, int end, int root_idx){        if(start > end){            return nullptr;        }        if(start == end){            return new TreeNode(preorder[root_idx]);        }        int root_idx_inorder = own_find(inorder, preorder[root_idx], start, end);        TreeNode* root = new TreeNode(preorder[root_idx]);        // find left root and right root position by find the size of left/right tree        int left_size = root_idx_inorder - start;        int right_size = end - root_idx_inorder;        TreeNode* left = nullptr;        TreeNode* right = nullptr;        if(left_size>0){            left = buildTreewithRoot(preorder, inorder, start, root_idx_inorder - 1, root_idx+1);        }        if(right_size > 0){            right = buildTreewithRoot(preorder, inorder, root_idx_inorder + 1, end, root_idx+left_size+1);        }        root->left = left;        root->right = right;        return root;    }};
复制代码


Review

Fullstack part0 | Fundamentals of Web apps (fullstackopen.com)

这是赫尔辛基大学的全栈课程,提供芬兰语,英语,中文的教程。本人是使用英文版。因为本人专业是机器学习相关,上次进行 web 开发已经是五六年前做的课程项目,技术更新的很快,而且当时也没有做到很好。目前的工作场景要求作者将 web 这块重新捡起来,因此学习这门课就很有必要了。接下来每周的 review 应该都是围绕全栈开发展开了,争取每周能够 review 一周的可能。

我分享的是第一部分,是特别适合初学者的内容。介绍 web app 的基础知识,以及操作指南。

  • web 开发者第一守则: Developer Console 开着的,F12, ctrl + shift + i 打开

  • 介绍了 developer console 常用的功能,比如 Network, Elements 等;

  • 介绍了传统 Web 开发的做法,发送请求到服务器,服务器返回页面,重新渲染页面。以及现在的 Ajax 技术(Asynchronous JavaScript and XML),这个名词目前已经很少听到了,因为已经成了事实上的标准,大家都会用。对年轻一代而言,Ajax 已经是没有听过的名词了。这门技术,真的做到了大音希声,大象无形

  • Ajax 用 JavaScript 获取数据即可,不用重新渲染页面;

  • 目前很流行的 JS 框架,React, Vue, AngularJS 1 曾经是事实上的标准,但是 AngularJS 2.0 因为后端不支持 Anjular 1.0, 导致后面不是特别受欢迎

这门课是全栈技术课,用的是 Node.js 和 React ,如果有兴趣的读者,可以一起研究下。

Tips

推荐一个好用的,勾画流程图的工具网站Graph of interaction - WebSequenceDiagrams


Share

本周分享的观点是:

快速,廉价,失控,这个可能是造出智能生物体的一个有效方式。用蜂群产生的类行为人群体智慧,而不是造出一个万能的类人脑机器,实现路径可能更为快速。这个观点是 MIT 机器人教授罗德尼·布鲁克斯,在论文“快速、廉价、失控:一场太阳系的机器人入侵”提出的,他认为制造一个无用的天才,不如制造一群有用的白痴。作为实用主义的我,也有类似的看法。

机器人领域自然有相关的研究,实际上在感知和认知领域也有类似的问题。

举一个感知领域最常见应用:神经网络里面,会有 dropout 机制,当真正推理的时候,将 dropout 关闭,此时,是多个模型的混合结果,而非某一个模型,预期的性能是有上升的,对于纠正偏见有很好的效果。

AI 落地难,超强模型总是会遇到各种诡异问题,不能够理解场景,能否采用蜂群机制,简单模型的组装,获得一个类人智慧的模型,这是一个很值得研究的问题。说不定能够获得一个认知领域的突破。


发布于: 2021 年 03 月 28 日阅读数: 13
用户头像

steve_lee

关注

还未添加个人签名 2018.03.09 加入

还未添加个人简介

评论

发布
暂无评论
ARTS-week 4