美文网首页
算法简记- 全排

算法简记- 全排

作者: 白小纯kl | 来源:发表于2021-09-30 17:18 被阅读0次

    1、// 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 回溯

    var permute = function(nums) {
        let res = [];
        let track = [];
        backTrack(nums, track, res);
        return  res;
    };
    let backTrack = (nums, track, res) => {
        if (track.length === nums.length) {
            res.push([].concat(track));
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (track.includes(nums[i])){
                continue;
            }
            track.push(nums[i]);
            backTrack(nums, track, res);
            track.pop();
        }
    }
    

    2、// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    // 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

    // 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    var solveNQueens = function(n) {
        let res = [];
        let queueRes = Array.from(new Array(n), () => {return new Array(n).fill('.')});
        backTrack(res, 0, queueRes);
        return res;
    };
    let backTrack = (res, row, queueRes) => {
        let n = queueRes.length;
        if (row === n) {
            let arr = queueRes.map(item => {
                return item.join('');
            })
            res.push(arr);
            return;
        }
    
        for (let clo = 0; clo < n; clo++) {
            if (isValide(queueRes, row, clo)) {
                continue;
            }
            queueRes[row][clo] = 'Q';
            backTrack(res, row + 1, queueRes);
            queueRes[row][clo] = '.';
    
        }
    }
    let isValide = (queueRes, row, clo) => {
        let n = queueRes.length;
        for (let i = 0; i < n; i++) { // 列检查
            if (queueRes[i][clo] === 'Q') {
                return true;
            }
        }
        for (let i = row - 1, j = clo + 1; i >= 0 && j < n; i--, j++ ) { // 右上
            if (queueRes[i][j] === 'Q') {
                return true;
            }
        }
        for (let i = row - 1, j = clo - 1; i >= 0 && j >= 0; i--, j--) {
            if (queueRes[i][j] === 'Q') {
                return true;
            }
        }
        return false;
    }
    
    solveNQueens(4);
    

    3、// . 串联所有单词的子串

     var findSubstring = function(s, words) {
        let res = [];
        let len = words[0].length;
        let wordNum = words.length;
        let totalLen = len * wordNum;
    
        for (let i = 0; i <= s.length - totalLen; i++) {
            let arr = [...words];
            let allStr = s.substring(i);
            dfs(arr, i, allStr);
        }
        function dfs(arr, start, allStr) {
            if (!arr.length) {
                res.push(start);
            }
            let str = allStr.substring(0, len);
            let index = arr.findIndex(item => item === str);
            if (index > -1) {
                arr.splice(index, 1);
                dfs(arr, start, allStr.substring(len));
            }
        }
        console.log(res)
        return res;
    };
    
    let b = "barfoothefoobarman", words = ["foo","bar"];
    // let b ="wordgoodgoodgoodbestword",words = ["word","good","best","good"];
    findSubstring(b,words);
    

    相关文章

      网友评论

          本文标题:算法简记- 全排

          本文链接:https://www.haomeiwen.com/subject/fibrnltx.html