javascript - 二维数组的处理,有点类似接龙
仅有的幸福
仅有的幸福 2017-05-19 10:38:44
0
3
582
var arr = [["A", "B"], ["C", "D"], ["E", "F"], ["G", "H"], ["C", "A"],["C","Q"] ["F", "D"], ["E", "G"],["H", "A"]];
var point = "A";//根据arr二维数组进行接龙,point这个是接龙的起点和终点
//要求输出:output_arr=[["A", "C"],["C", "D"],["D", "F"],["F", "E"],["E", "G"],["G", "H"],["H", "A"]]
//如上,起点和终点都为"A"
//用不到的元素舍弃了:["A", "B"]中"A"以后的"B"再接不下去,所以没用,同理["C","Q"]中的"Q"也接不下去,也不用了
//注意顺序:["C", "A"],因为从"A"开始,所以这个元素变为["A","C"]

我不是从事这方面工作的,自己写程序玩,遇到上述问题,困扰我好几天了,请大咖帮忙

仅有的幸福
仅有的幸福

全部回复(3)
我想大声告诉你

提供一个单一解的思路。

首先要找到所以首元素是A的数组,把它取出来,命名为候选数组

然后从候选数组中选取其中一个,再定义一个当前数组和一个结果数组,储存当前的头和尾和结果,例如[A,B]和[[A,B], [B,C]],当然,当前数组可以不要,这里是方便说明。

然后循环arr,知道首字母是A的数组,例如[B,C]。这首结果数组就可以折叠为[A,C]。然后当然要把[B,C]存到结果数组里,并将[B,C]这项从arr删去。

然后如果组后把当前数组折叠为长度0,则说明找到一条龙了,则可以输出结果。

但是如果找不到,则说明[B,C]这一项是无解的,则将结果数组和当前数组回退到上一阶段,并且[B,C]不再加进arr中,因为它不可能是答案的其中一项。然后一直循环这一个过程。

形象点描述就是我们发现[A,B,B,C,C,D]找不到结果,回退到[A,B,B,C],然后又找不到,则继续回退到[A,B]。诸如此类。

直到最后找出答案。

多解的话,就是完全一种解法。太麻烦。

淡淡烟草味

这是要玩穷举啊.....
我能想到的思路是选两头, 往中间穷举.
记录每一对可能性(要注意锁定, 不能重复选中), 可能性的末尾能接得上, 就ok.
由于结果的长度不定, 顺序也不定, 这又更复杂了许多...

滿天的星座

花了点时间写个递归,用到了一个剪枝逻辑,如果一个字母只出现过1次,那么将对应的字母对从原始数据中剔掉。

let map = {};   // 计算字母出现次数使用
let result = [];

// 计算字母出现次数
arr.forEach(item => {
    map[item[0]] ? map[item[0]]++ : (map[item[0]] = 1);
    map[item[1]] ? map[item[1]]++ : (map[item[1]] = 1);
});

// 淘汰包含出现小于1字母的数组, 避免无用递归
arr = arr.filter(item => {
    return (map[item[0]] > 1 && map[item[1]] > 1);
});

let dfs = (_point, _arr) => {
    for(let i = _arr.length; i--; ) {
        let item = _arr[i];
        if(item[0] === _point || item[1] === _point) {

            if(result.length === 0 && item[1] === _point) {
                [item[0], item[1]] = [item[1], item[0]];
            }

            let tempArr = Object.assign(_arr);  // 复制一个数组副本,方便回溯
            tempArr.splice(i, 1);   // 从临时数组中删去当前组,进一步递归

            if(item[1] === point || dfs(item[1], tempArr)) {
                // 如果找到答案,一层层往上返回
                // 不带下划线的point是全局的目标point
                result.unshift(item);
                return true;
            }
        }
    }
    return false;
};

if(dfs(point, arr)){
    console.log(result);
} else {
    console.log('no result');
}
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板