算法

[msforest]

算法

1. 广度优先算法 2. 深度优先算法 3. 洗牌算法

1. 广度优先算法思想

依次遍历顺序为： A -> B -> C -> D -> E -> F

2. 深度优先算法思想

依次遍历顺序为：A -> B -> D -> E -> C -> F -> G

数据源

[{
    "name": "it",
    "children": [{
        "name": "fsmr3",
        "children": [{
            "name": "provision",
            "children": [{
                "name": "scm",
                "result": "fail"
              }]
          }, {
            "name": "sct",
            "result": "pass"
          }, {
            "name": "qt",
            "result": "pass"
          } ]
      } ]
  }, {
    "name": "ut",
    "children": [{
        "name": "fsmr3",
        "children": [{
            "name": "provision1",
            "result": "pass"
          }, {
            "name": "sct1",
            "result": "pass"
          }, {
            "name": "qt1",
            "result": "pass"
          } ]
      } ]
  }]

问题

• 输入一个name值， 输出children的值(name可以是任意级的值)

let names = [], child = [], nameSplit = [], temp = [];

/**
 * @name: getChildrenByName
 */
const treeName = function(nodes, phase) {
    if (!nodes || !nodes.length) return;
    for (let i = 0, len = nodes.length; i < len; i++) {
        const item = nodes[i];
       if(item.name === phase){
              names = item.children ? item.children : [item];
       }
        const childs = item.children;
        if (childs && childs.length > 0) {
             treeName(childs, phase);
        }
    }
};

/**
 * @name: getItemByChildren
 */
const treeChildren = function(nodes) {
    if (!nodes || !nodes.length) return;
    for (let i = 0, len = nodes.length; i < len; i++) {
        const item = nodes[i];
       if(!item.children){
              child.push(item)
       }
        const childs = item.children;
        if (childs && childs.length > 0) {
             treeChildren(childs);
        }
    }
};

treeName(arr, 'scm')
treeChildren(names)

console.log('names====',names);
console.log('child =====',child);

根据一个name值， 可以获取其children值， 这时候就有个问题， 如果一级不同， 二级有相同的name， 按照这个问题引发出另一种写法

const treeNameSplit = function(nodes, phase) {
    if (!nodes || !nodes.length) return;
    nameSplit = phase.split(';');

    for (let i = 0, len = nodes.length; i < len; i++) {
      const item = nodes[i];
       if(item.name === nameSplit[0]){
              nameSplit.shift();
              temp = item.children ? item.children : [item];
       }

        const childs = item.children;

        if (childs && childs.length > 0) {
             treeNameSplit(childs, phase);
        }
    }
};

treeNameSplit(arr, 'ut;fsmr3')
console.log('temp=====',temp[0]);

以上递归遍历是递归深度优先遍历算法。

非递归广度优先实现

let result = null;
const iterator1 = function(treeNodes, phase) {
    if (!treeNodes || !treeNodes.length) return;

    let stack = [...treeNodes];
    let item;

    while (stack.length) {
        item = stack.shift();

        console.log(item.name);
        if(item.name === phase){
              result = item;
              break;
        }

        //如果该节点有子节点，继续添加进入栈底  -- warning
        if (item.children && item.children.length) {
            stack = [...stack, item.children];
        }
    }
};

iterator1(arr, 'it');
console.log('arr', result)

非递归深度优先实现

const iterator2 = function(treeNodes, phase) {
    if (!treeNodes || !treeNodes.length) return;

    const stack = [...treeNodes];
    let item;

    while (stack.length) {
        item = stack.shift();

        console.log(item.name);
        if (item.name === phase) {
            result = item;
            break;
        }

        //如果该节点有子节点，继续添加进入栈顶  -- warning
        if (item.children && item.children.length) {
            stack = item.children.concat(stack);
        }
    }
};

iterator2(arr, 'it');
console.log('arr', result);

[msforest]

洗牌算法(Fisher–Yates Shuffle 也叫高纳德置乱算法)

洗牌，就是把牌打乱以确保每张牌都是随机、公平的发出来。 如何在未洗牌的情况下，对刚买来的牌进行随机发放给玩家呢？ 或许我们会为每一个玩家进行随机抽牌，这样才能保证每个玩家拿到的每张牌都是随机的，而且没有做过手脚的。嗯，这是一个想法，我们可以对我们的想法用code实践😄

桌面上一堆纸牌🃏，随机抽出一张，把它放到一边，创建另一堆纸牌，每一张都随机拿，最后，原来的一堆纸牌没有，新堆起来的纸牌就是随机乱序的。

function shuffle(array) {
    var copy = [], n = array.length, i;

    while (n) {
        i = Math.floor(Math.random() * array.length); // 随机抽牌

        if (i in array) {
            copy.push(array[i]); // 放到新的纸牌盒里
            delete array[i];
            n--;
        }
    }

    return copy;
}

很明显，这种实现方法效率不高。每当删除一个元素，都需要移动数组里面的元素，而且还占用额外空间。然后我们可以想想，上面的方法虽然是乱序的，但是好像和冒牌排序一样，每次都冒出一张牌，然后我们又可以想到排序中快速排序是比较好的算法，何不利用快速排序的特点，在不占用额外空间的情况下，对元素进行数据交换，由于洗牌是随机的、乱序的。选取一个随机元素作为基数，然后从右往左交换，每一次的基数都是随机抽出的，保证右边的元素都是乱序。

function shuffle(array) {
  var m = array.length, t, i;

  while (m) {
    i = Math.floor(Math.random() * m--);

    // 元素交换
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

这种实现方式，空间复杂度o(3)，其实都是常数，时间复杂度是o(m)

参考： Fisher–Yates Shuffle shuffle