搜尋

首頁  >  問答  >  主體

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

我不是從事這方面工作的,自己寫程式玩,遇到上述問題,困擾我好幾天了,請大咖幫忙

仅有的幸福仅有的幸福2807 天前614

全部回覆(3)我來回復

  • 我想大声告诉你

    我想大声告诉你2017-05-19 10:40:44

    提供一個單一解的思路。

    首先要找到所以首元素是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]。諸如此類。

    直到最後找出答案。

    多解的話,就是完全一種解法。太麻煩。

    回覆
    0
  • 淡淡烟草味

    淡淡烟草味2017-05-19 10:40:44

    這是要玩窮舉啊.....
    我能想到的思路是選兩頭, 往中間窮舉.
    記錄每一對可能性(要注意鎖定, 不能重複選中), 可能性的末尾能接得上, 就ok.
    由於結果的長度不定, 順序也不定, 這又更複雜了許多...

    回覆
    0
  • 滿天的星座

    滿天的星座2017-05-19 10:40:44

    花了點時間寫個遞歸,用到了一個剪枝邏輯,如果一個字母只出現過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');
    }

    回覆
    0
  • 取消回覆