记录一下碰到的算法题

不可变数组未和

假设有固定数组[1,2,3,4,....,10000]，任意给起始位置n和m，求n和m之间的和(不含n、包含m)

如果使用变通循环的话有以下问题：

• 循环成本大，如果计算频繁的话，非常影响性能

比较好的思路是加入缓存，对计算过的不再进行重复计算，这里需要注意的是，我们要缓存不是n到m之间和，而是0-n 和 0-m这样的和

因为求 n-m 之间和，我们可以拆解为 0-m 减 0-n

  const arr = [1,3,4,5,6,7,8,9]
  const catchSum = {}
  function sum(n, m) {
    const sumN = catchSum[n] ? catchSum[n] : getSumInArr(n)
    const sumM = catchSum[m] ? catchSum[m] : getSumInArr(m)
    return sumM - sumN
  }
  function getSumInArr(end) {
    let total = 0
    for(let i = end; i>=0; i--) {
      total += arr[i]
    }
    catchSum[end] = total
    return total
  }
  console.log(sum)

将扁平对象转换为树形结构

let data = {
	h3: {
        parent: 'h2',
        name: '经理(市场)'
    },
    h1: {
        parent: 'h0',
        name: '公司机构'
    },
    h7: {
        parent: 'h6',
        name: '经理(总务)'
    },
    h4: {
        parent: 'h3',
        name: '销售'
    },
    h0: {
        parent: '',
        name: 'root'
    },
    h2: {
        parent: 'h1',
        name: '总经理'
    },
    h8: {
        parent: 'h0',
        name: '财务'
    },
    h6: {
        parent: 'h4',
        name: '仓管'
    },
    h5: {
        parent: 'h4',
        name: '代表'
    }
}

转换成如下结构

let tree = {
    'parent': '',
    'name': 'root',
    'h1': {
        'parent': 'h0',
        'name': '公司机构',
        'h2': {
            'parent': 'h1',
            'name': '总经理',
            'h3': {
                'parent': 'h2',
                'name': '经理(市场)',
                'h4': {
                    'parent': 'h3',
                    'name': '销售',
                    'h6': {
                        'parent': 'h4',
                        'name': '仓管',
                        'h7': {
                            'parent': 'h6',
                            'name': '经理(总务)'
                        }
                    },
                    'h5': {
                        'parent': 'h4',
                        'name': '代表'
                    }
                }
            }
        }
    },
    'h8': { 'parent': 'h0', 'name': '财务' }
}

实现代码

function toTree(obj) {
    let result = {}
    for(let key in obj) {
      let parent = obj[key].parent
      if(parent) {
        obj[parent][key] = obj[key]
      } else {
        result = obj[key]
      }
    }
    return result
}

利用了对象存储是引用的特点

从一个无序，不相等的数组中，选取N个数，使其和为M实现算法

  function sum(curArr, total, start = 0) {
    const arr = curArr.slice(start)
    if(arr.indexOf(total) > -1) {
      return [arr.indexOf(total) + start]
    }
    if(arr.length < 2) {
      return false
    }
    const getSum = arr.reduce((el1,el2) => el1 +el2)
    if(total > getSum) {
      return false
    }
    let tmp = 0
    for(let i=0; i < arr.length; i++) {
      tmp = i
      const findResult = sum(curArr, total-arr[i], start + i+1)
      if(findResult){
        return [start+i, ...findResult]
      }
    }
    return false
  }
  const test = [1,3,4,6]
  console.log(sum(test, 14))