前端有难度的算法题

将对象数组转为树状对象

// 输入

const industry_list = [
  {
  "parent_ind" : "女装",
  "name" : "连衣裙"
  },
  {
  "name": "女装"
  },
  {
  "parent_ind" : "女装",
  "name" : "半身裙"
  },
  {
  "name": "数码"
  },
  {
  "parent_ind" : "数码",
  "name": "电脑配件"
  },
  {
  "parent_ind" : "电脑配件",
  "name": "内存"
  },
  {
    "parent_ind" : "内存",
    "name": "你懂得"
  },
];

// 期待输出

{
  "女装": {
    "连衣裙": {}
    "半身裙": {}
   },
  "数码": {
    "电脑配件": {
      "内存": {}
    },
  },
}

// 代码实现

function convert_format(data) {
    if (!Array.isArray(data)) {
      return '请输入对象数组';
    }
    const flagObj = {};
    const resData = {};
    const parents = [], children = [];
    let parent = null, child = null;
    let parentKey = null, childKey = null;
    // 先把原数组拆分成两个数组，其中一个数组只有一级节点
    for(let item of data) {
      if (item.parent_ind) {
        children.push(item);
      } else {
        parents.push(item);
      }
    }
    // 当两个数组都为空时结束循环
    while(parents.length || children.length) {
      if(parents.length) {
        // 先一次处理一级节点
        parent = parents.shift();
        parentKey = parent.name;
        resData[parentKey] = {};
        // 保留其指向的引用地址
        flagObj[parentKey] = resData[parentKey];
      } else {
        child = children.shift();
        childKey = child.name;
        if(child.parent_ind in flagObj) {
          // 如果当前节点的父节点如果已经存在，则把该节点插入进入
          flagObj[child.parent_ind][childKey] = {};
          // 保留其指向的引用地址
          flagObj[childKey] = flagObj[child.parent_ind][childKey];
        } else {
          // 否则先放回数组
          children.push(child)
        }
      }
    }

    return resData;
}

console.log('结果', convert_format(industry_list));

树状对象按照层级转为二维数组

// 输入

const obj = {
  a: {
    b: {
      c: {
        d: null
      },
      f: {
        e: null
      }
    }
  },
  g: {
    h: {
      i: null
    }
  },
  j: '222'
}

// 期待输出

[["a", "g", "j"], ["b", "h"], ["c", "f", "i"], ["d", "e"]]

// 代码实现

function isComObj(obj) {
  return obj !== null && typeof obj === 'object' && !(obj instanceof Array);
}

function flatObjKey(obj) {
  const resArr = [];
  let itemArr=[], curArr=[], nextArr=[];
  for (key in obj) {
    itemArr.push(key);
    if (isComObj(obj[key])) {
      curArr.push(obj[key]);
    }
  }
  resArr.push(itemArr);
  itemArr = [];
  let item = null;
  while (curArr.length > 0) {
    item = curArr.shift();
    for (key in item) {
      itemArr.push(key);
      if (isComObj(item[key])) {
        nextArr.push(item[key]);
      }
    }
    if (curArr.length === 0) {
      resArr.push(itemArr);
      itemArr = [];
      curArr = nextArr;
      nextArr = [];
    }
  }
  return resArr;
}

console.log('ddd', flatObjKey(obj));

求连续 1 的个数

const data = [
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 1, 0],
[1, 0, 0, 1, 0]
];

function mergeArr(arr, i, j, m, n) {
if (i < 0 || i>= m || j <0 || j >= n || arr[i][j] !== 1) {
return;
}
arr[i][j] = -1;
mergeArr(arr, i-1, j, m, n);
mergeArr(arr, i+1, j, m, n);
mergeArr(arr, i, j-1, m, n);
mergeArr(arr, i, j+1, m, n);
}

const getCounts = (arr) => {
// return 0;
const m = arr.length, n = arr[0].length;
let count = 0;

for (let i= 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (arr[i][j] === 1) {
            count++;
            mergeArr(arr, i, j, m, n);
        }
    }
}

return count;

}

console.log(getCounts(data))