javascript - 如何计算所有嵌套对象的相同值的计数？

Question

嗨，我可以问一些困难的算法问题吗？

109.169.248.247
109.169.248.247
109.169.248.248
109.170.248.248
46.72.177.3
46.72.177.4

根据上面的输入，我想打印以下内容，我使用了多种方法，但我不擅长算法，所以很难实现，有人有解决方案吗？

109 4
    169 3
        248 3
            247 2
            248 1
    170 1
        248 1
            248 1
46 2
    72 2
        177 2
            3 1
            4 1

通过使用这段代码，我可以计算出整个ip的数量，但我无法计算每个ip段的数量。你能帮我解决这个问题吗？

function assign(obj, keyPath, value) {
    lastKeyIndex = keyPath.length-1;
    firstCreated = false;
    for (var i = 0; i < lastKeyIndex; ++ i) {
        key = keyPath[i];
        if (!(key in obj)) {
            obj[key] = {};
            firstCreated = true;
        }
        obj = obj[key];
    }
    if(firstCreated) {
        obj[keyPath[lastKeyIndex]] = parseInt(value);
    }
    else {
        obj[keyPath[lastKeyIndex]] = parseInt(obj[keyPath[lastKeyIndex]]) + 1;
    }
 }

Answer 1

实现@dpwrussel 的评论:从 ips 创建 Trie，然后打印树。

const ips = `
109.169.248.247
109.169.248.247
109.169.248.248
109.170.248.248
46.72.177.3
46.72.177.4
`

const IPTrie = function (ips) {
  this.root = new Map()
  for (const ip of ips.trim().split('\n')) {
    this.add(ip)
  }
  return this
}

IPTrie.prototype.add = function (ip) {
  const parts = ip.split('.')
  let cursor = this.root,
    index = -1
  while (++index < parts.length) {
    const part = parts[index]
    if (cursor.has(part)) {
      const [count, node] = cursor.get(part)
      cursor.set(part, [count + 1, node])
      cursor = node
    } else {
      let node = new Map()
      cursor.set(part, [1, node])
      cursor = node
    }
  }
}

IPTrie.prototype.print = function (cursor, indent = 0) {
  cursor = cursor || this.root
  for (const [part, entry] of cursor) {
    const [count, node] = entry
    console.log(`${' '.repeat(indent)}${part} ${count}`)
    this.print(node, indent + 4)
  }
}

new IPTrie(ips).print()