题解 | #放苹果#

/**

• 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
• @param matrix string字符串一维数组
• @param versionA int整型
• @param versionB int整型
• @return int整型 / /* 本来粗略读题应该就是转换为两个链表的第一个公共节点问题，但是偷懒没有去实现链表了， 直接求得路径A，路径B，两个数组求交集的最后一位就是第一个公共节点。 同样通过创建hashmap的方式简化树结构，来进行递归 递归过程就一条，循环遍历每条数组

0 => 3

跳到3：[0, 3] => 忽略前面路径中已有的0 => 1

跳到1：[0, 3, 1] => 忽略已有的3 => 8 ....

...

{
  '0': [ 3 ],
  '1': [ 3, 8, 9 ],
  '2': [ 9 ],
  '3': [ 0, 1, 6 ],
  '4': [ 9 ],
  '5': [ 7 ],
  '6': [ 3 ],
  '7': [ 5, 9 ],
  '8': [ 1 ],
  '9': [ 1, 2, 4, 7 ]
}

实际上如果自己做树结构，不管二叉树还是普通树，应该都是从小到大有个顺序排列吧。 可是这题顺序是随机的，不然通过得到的map去判断公共节点就太简单了 */

function Git( matrix ,  versionA ,  versionB ) {
//     class Node {
//         constructor(element) {
//             this.element = element
//             this.next = null
//         }
//     }
//     class List {
//         constructor() {
//             this.head = new Node('head')
//         }
//         inser(element, item) {
//             let current = this.find(item)
//             if(!current) return null
//             let newNode = new Node(item)
//             newNode = current.next
//             current.next = newNode
//         }
//         find(item) {
//             let temp = this.head
//             while (temp && temp.element!=item) {
//                 temp = temp.next
//             }
//             return temp
//         }
//     }
   if (versionA == 0 || versionB == 0) return 0 //特殊处理0,0的情况
//     if (versionA ==  versionB) return versionA
   let table = matrix.reduce((p, c, idx) => {
       for (let i = 0; i < c.length; i++) {
           if(c[i] == 1) p[idx]? p[idx].push(i) : p[idx] = [i]
       }
       return p
   }, {})
   let resA = [], resB = []
   function dfs(temp = [0], idx = 0){
//         if(!table[idx]) return
       if(idx == versionA) resA = [...temp]
       if(idx == versionB) resB = [...temp]
        table[idx].forEach(val => {
           if(!temp.includes(val)){
              return dfs(temp.concat(val), val)
           }
        })
   }
   dfs()
   let same = resA.filter(e => resB.includes(e))
   let res = same[same.length-1]
   // write code here
   return res
}
module.exports = {
   Git : Git
};