ARTS(14)

什么是 ARTS？

1. 算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习
2. 阅读(Review)： 阅读并点评至少一篇英文技术文章，提高英文水平
3. 技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点
4. 分享(Share)：分析一篇有观点和思考的技术文章，建立影响力，输出价值观

时间周期

2022 年9月19日至9月25日

一：算法：

实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];

前置知识
思路：

function convert (list) {
  let res = []
  let map = list.reduce((res, value) => (res[value.id] = value, res), {})
  for (let item of list) {
    if (item.parentId === 0) {
      res.push(item)
      continue
    }
    if (item.parentId in map) {
      let parent = map[item.parentId]
      parent.children = parent.children || []
      parent.children.push(item)
    }
  }
  return res
}

// 基于DFS来写
function convert (source, parentId = 0) {
  let trees = []
  for (let item of source) {
    if (item.parentId === parentId) {
      let children = convert(source, item['id'])
      if (children.length) {
        item.children = children
      }
      trees.push(item)
    }
  }
  return trees
}


function convert (list) {
  let result = list.filter((item) => {
    let children = list.filter((child) => {
      return item.id === child.parentId
    })
    item.children = children
    return item.parentId === 0
  })
  return result
}

二：阅读

中文书：
《在工作中，看到中国》
推荐理由：

1. 既然工作不可避免，且各行如隔山，那么不如看看其他山的风景如何，既是满足好奇心，也是聊以自慰

英文：
https://kk.org/thetechnium/1000-true-fans/

三：技巧

第1期 | 聊聊有效学习这件事-极客时间

四：分享

李飞飞：云原生数据库是大势所趋

分享理由：

1. 基础是诸多技术的起点，多了解基础技术的发展，有助于理解由此而产生的上层的变化
2. 无论招式变化多态，内功是一直要有的，日拱一卒，不期速进，多关注基础，打牢基础

笔记：

1. 数据库、芯片、操作系统并列为全球信息技术的三大件基础
2. 技术领域的创新可分为两种，渐进性创新和破坏性创新
3. 云计算彻底改变了传统软件系统构建的基本逻辑，它对冯·诺依曼架构里的计算核心模块做了两件事。
   1. 第一是资源池化：对计算资源从独享式到共享式的利用，就像人类用水的过程，会发生一模一样的变化。
   2. 第二是解耦，以前计算和存储是紧耦合在一起的，现在是计算、存储、网络三层结构
4. 阿里云更关注两类行业动态：一类是头部云计算厂商，比如微软云、AWS等；第二类是头部的独立数据库公司，比如说Snowflake、Databricks等