Go back

算法题记录

Published:  at  06:02 PM

文章目录

递归算法

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

var methods = (n) => {
    if (n == 0) return 0;
    if (n == 1) return 1;
    const dp = {};
    dp[2] = 2;
    for (var i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额

// 动态规划方程：dp[n] = num + Max(dp[n-1])
// 由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值

var rob = function(nums) {
    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0];
    if(nums.length === 2) return Math.max(nums[0],nums[1]);
    let dp = [nums[0],Math.max(nums[0],nums[1])];
    for(let i = 2;i < nums.length;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
    }
    return Math.max(dp[nums.length-1],dp[nums.length-2]);
};

最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积

// 错误思路: 先从2x2矩阵开始验证, 基于此继续验证更大的3x3矩阵, 以此类推
// 正确思路: 仍然使用二维数组保存自己的状态, 如果当前位置的左边/上边/左上的点都为1, 则把当前点保存为2; 如果当前位置的左边/上边/左上的点都为2, 则把当前点保存为3; 以此类推

var maxSquare = (ary) => {
    if (ary.length == 0) return 0

    let maxLen = 0
    let rowLen = ary[0].length, colLen = ary.length;

    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (Number(ary[i][j]) === 1) {
                ary[i][j] = Number(ary[i][j]);
                if (i !== 0 && j !== 0) {
                    ary[i][j] = Math.min(ary[i - 1][j - 1], ary[i - 1][j], ary[i][j - 1]) + 1
                }
                maxLen = Math.max(maxLen, ary[i][j])
            }
        }
    }

    return maxLen ** 2
}


console.log(maxSquare(
    [
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
    ]
));

单向链表节点两两互换，递归算法

如果当前节点已经是末尾，就返回自己

function helper(node) {
    if (!node) return null
    const tempNext = node.next;
    const tempNextNext = tempNext.next;
    if (tempNext) {
        node.next = helper(tempNextNext);
        tempNext.next = node;
    }
    return tempNext || node
}

var d = { v: 'd' }
var c = { v: 'c', next: d }
var b = { v: 'b', next: c }
var a = { v: 'a', next: b }
helper(a)
console.log(a);
console.log(b);
console.log(c);
console.log(d);

扁平数组输出树状结构

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]
// [
//     {
//         "id": 1,
//         "name": "部门1",
//         "pid": 0,
//         "children": [
//             {
//                 "id": 2,
//                 "name": "部门2",
//                 "pid": 1,
//                 "children": []
//             },
//             {
//                 "id": 3,
//                 "name": "部门3",
//                 "pid": 1,
//                 "children": [
//                     // 结果 ,,,
//                 ]
//             }
//         ]
//     }
// ]

// 递归
function createTree(ary) {
    const resAry = new Set();
    const findBy = (target, list) => list.find(item => {
        if (item.id === target.pid) {
            // 当前对象匹配了id
            item.children = item.children || [];
            return item.children.push(target)
        } else if (!!item.children) {
            // 当前对象不匹配，继续遍历他的子节点
            return findBy(target, item.children)
        } else {
            return false
        }
    })
    ary.forEach(item => {
        if (item.pid == 0) {
            resAry.add(item);
        } else {
            var res = findBy(item, ary);
            if (res && res.pid == 0) {
                resAry.add(res);
            }
        }
    })
    return Array.from(resAry)
}

console.log(JSON.stringify(Array.from(createTree(arr))))


// 不用递归
function aryToTreeWithMap(ary) {
    const result = [];
    const maps = {};

    ary.forEach(item => {
        item.children = maps[item.id]?.children || [];
        maps[item.id] = {
            ...maps[item.id],
            ...item
        };
        if (item.pid === 0) {
            result.push(item);
        }
        if (maps[item.pid]) {
            maps[item.pid].children.push(item);
        } else {
            maps[item.pid] = {
                children: [item]
            };
        }
    })  

    return result;
}

console.log(JSON.stringify(Array.from(aryToTreeWithMap(arr))))

输入数组中三个数的和，满足与目标值最接近

// 输入：nums = [-1,2,1,-4], target = 1
// 输出：2
// 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

function targets(nums, target) {
    let len = nums.length;
    if (len === 3) {
        return nums
    }
    nums = nums.sort((a, b) => a - b);
    let min = Infinity
    let res

    for (var i = 0; i < len - 3; i++) {
        let basic = nums[i];
        let left = i + 1;
        let right = len - 1;
        while (left < right) {
            res = basic + nums[left] + nums[right];
            let diff = Math.abs(res - target);
            if (diff < min) {
                diff = min
                res = sum
            }
            if (res < target) {
                left++
            } else if (res > target) {
                right--
            } else {
                return sum
            }
        }
    }
    return res
}

单词查询

// board = [
//   ['A','B','C','E'],
//   ['S','F','C','S'],
//   ['A','D','E','E']
// ]

// 给定 word = "ABCCED", 返回 true
// 给定 word = "SEE", 返回 true
// 给定 word = "ABCB", 返回 false


function wordExist(board, word) {
    var source = word.split('');
    if (source.length == 0) return false;

    var record = '';
    const char = source[0];
    // 第一步找到所有的线头，也就是所有可能
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (char === board[i][j]) {
                record = '*' + i + '' + j;
                if (source.length === 1) return true
                if (juan(i, j, 1, record)) {
                    return true
                }
            }
        }
    }

    return false

    // 这里就卷起来了
    function juan(i, j, targetIndex, record) {
        const getVal = (row, col) => {
            var posi = row + '' + col;
            var r = record;
            var val = r.includes(posi) ? null : board[row] && board[row][col];
            console.log(row, col, val);
            if (val && val === source[targetIndex]) {
                // 查找层数与字符长度相等，即通过
                if (targetIndex === source.length - 1) {
                    return true
                }
                // 当前位置已被使用
                r += '*' + posi;
                return juan(Number(row), Number(col), targetIndex + 1, r);
            }
            return false
        }
        // 查找自己上下左右的所有可能，当然，已经使用过的位置不能重复使用
        return getVal(i, j - 1) || getVal(i, j + 1) || getVal(i - 1, j) || getVal(i + 1, j);
    }
}

节点遍历的两种方法

var node = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 4,
        },
        right: {
            value: 5,
            left: {
                value: 8,
            },
            right: {
                value: 9,
            },
        },
    },
    right: {
        value: 3,
        left: {
            value: 6,
            left: {
                value: 10,
                left: {
                    value: 14,
                },
                right: {
                    value: 15,
                },
            },
            right: {
                value: 11,
            },
        },
        right: {
            value: 7,
            left: {
                value: 12,
            },
            right: {
                value: 13,
                left: {
                    value: 16,
                },
                right: {
                    value: 17,
                },
            },
        },
    },
}

// 深度优先遍历
function deepFirst(node, result) {
    result = result ? result + '->' + node.value : node.value;
    if (node.left !== undefined) {
        deepFirst(node.left, result)
    }
    if (node.right !== undefined) {
        deepFirst(node.right, result)
    }
    if (node.left === undefined && node.right === undefined) {
        console.log(result);
    }
}

deepFirst(node, '');
// 1->2->4
// 1->2->5->8
// 1->2->5->9
// 1->3->6->10->14
// 1->3->6->10->15
// 1->3->6->11
// 1->3->7->12
// 1->3->7->13->16
// 1->3->7->13->17

// 广度优先遍历
function wildlyFirst(node) {
    var res = []
    function wildlyMaxFirst(node, result, index) {
        result[index] = result[index] || [];
        result[index].push(node.value);
        if (node.left !== undefined) {
            wildlyMaxFirst(node.left, result, index + 1)
        }

        if (node.right !== undefined) {
            wildlyMaxFirst(node.right, result, index + 1)
        }
    }
    wildlyMaxFirst(node, res, 0)
    console.log(res);
}

wildlyFirst(node)
// [
//   [ 1 ],
//   [ 2, 3 ],
//   [ 4, 5, 6, 7 ],
//   [ 8, 9, 10, 11, 12, 13 ],
//   [ 14, 15, 16, 17 ]
// ]

合并有序数组

Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous Post
数据结构
Next Post
Nodejs模块机制