javascript - 二维数组的处理，有点类似接龙

问题描述

问 题

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"]

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

解决方案

花了点时间写个递归，用到了一个剪枝逻辑，如果一个字母只出现过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');
}

这篇关于javascript - 二维数组的处理，有点类似接龙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！