【当前排名42710】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/evaluate-reverse-polish-notation/submissions/588296105/?envType=study-plan-v2&envId=top-interview-150
偷懒利用eval秒了

var evalRPN = function (tokens) {
    const stack = []
    for (let index = 0; index < tokens.length; index++) {
        const item = tokens[index];
        if (item == '*' || item == '/' || item == "+" || item == '-') {
            const item1=stack.pop();
            const item2=stack.pop()
            stack.push(parseInt(eval(`${item2} ${item} ${item1}`)))
        } else {
            stack.push(parseInt(item))
        }
    }
    return parseInt(stack.pop())
};

李恒道

王一之 发表于 2024-12-20 16:31
有排名了吗？

快300题了还是没排名
不过已经快兴致缺缺了...
越往后做提升越少，高分题做不动，低分题起手秒
中等的纯属猜解法

李恒道

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/588299340/?envType=study-plan-v2&envId=top-interview-150
一次过

var buildTree = function (inorder, postorder) {
    const generateTree = (il, ir, pl, pr) => {
        if (il == ir) {
            return {
                val: inorder[il],
                left: null,
                right: null,
            }
        }
        const val = postorder[pr];
        const node = {
            val,
            left: null,
            right: null,
        }
        let iPos = -1;
        for (let index = il; index <= ir; index++) {
            if (inorder[index] === val) {
                iPos = index;
            }
        }
        const leftLen = iPos - il;
        const rightLen = ir - iPos;
        if (leftLen !== 0) {
            node.left = generateTree(il, iPos - 1, pl, pl + leftLen - 1)
        }
        if (rightLen !== 0) {
            node.right = generateTree(iPos + 1, ir, pl + leftLen, pr - 1)
        }
        return node
    }
    return generateTree(0, postorder.length - 1, 0, postorder.length - 1)
};

李恒道

https://leetcode.cn/problems/n-queens-ii/submissions/588300918/?envType=study-plan-v2&envId=top-interview-150
一次过
懒得位运算了

var totalNQueens = function (n) {
    const board = []
    for (let index = 0; index < n; index++) {
        board.push(new Array(n).fill('.'))
    }
    const checkValid = (x, y) => {
        //上方
        for (let index = 0; index < x; index++) {
            const pos = board[index][y];
            if (pos === 'Q') {
                return false
            }
        }
        //右斜方
        for (let index = x - 1; index >= 0; index--) {
            const posY = y + (x - index)
            if (posY >= board.length) {
                break;
            }
            const pos = board[index][posY];
            if (pos === 'Q') {
                return false
            }
        }
        //左斜方
        for (let index = x - 1; index >= 0; index--) {
            const posY = y - (x - index)
            if (posY < 0) {
                break;
            }
            const pos = board[index][posY];
            if (pos === 'Q') {
                return false
            }
        }
        return true;
    }
    let result=0
    const dfs = (index) => {
        if(index==board.length){
            result++
            return
        }
        const layout = board[index]//第n行
        for (let y = 0; y < layout.length; y++) {//第y列
            if (checkValid(index, y)) {
                board[index][y]='Q'
                dfs(index+1)
                board[index][y]='.'
            }
        }
    }
    dfs(0)
    return result

};

李恒道

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/submissions/588319466/?envType=study-plan-v2&envId=top-interview-150
简单题
秒了

var zigzagLevelOrder = function (root) {
    if (root == null) {
        return []
    }
    const ans = []
    let stack = [root];
    let first = true
    while (stack.length !== 0) {
        let newStack = [];
        let result = []
        while (stack.length !== 0) {
            const item = stack.shift();
            first === true ? result.push(item.val) : result.unshift(item.val);
            if (item.left !== null) {
                newStack.push(item.left)
            }
            if (item.right !== null) {
                newStack.push(item.right)
            }
        }
        stack = newStack
        first = !first
        ans.push(result)
    }
    return ans
};

李恒道

https://leetcode.cn/problems/course-schedule-ii/submissions/588464982/?envType=study-plan-v2&envId=top-interview-150
标准bfs，一次过

var findOrder = function (numCourses, prerequisites) {
    const outEdges = new Array(numCourses).fill(0).map(() => []);
    const inEdges = new Array(numCourses).fill(0);
    for (let index = 0; index < prerequisites.length; index++) {
        const prerequisite = prerequisites[index];
        outEdges[prerequisite[1]].push(prerequisite[0])
        inEdges[prerequisite[0]]++;
    }
    const stack = [];
    const ans = []
    for (let index = 0; index < inEdges.length; index++) {
        const item = inEdges[index];
        if (item == 0) {
            stack.push(index);
        }
    }
    while (stack.length !== 0) {
        const item = stack.pop();
        ans.push(item);
        const childrens = outEdges[item];
        for (let index = 0; index < childrens.length; index++) {
            const children = childrens[index];
            inEdges[children]--;
            if(inEdges[children]==0){
                stack.push(children);
            }
        }
    }
    if(ans.length!==numCourses){
        return []
    }
    return ans
};

李恒道

https://leetcode.cn/problems/sort-the-students-by-their-kth-score/
今天的每日一题没前几天的难

var sortTheStudents = function(score, k) {
  return  score.sort((a,b)=>b[k]-a[k])
};

李恒道

https://leetcode.cn/problems/construct-quad-tree/submissions/588471321/?envType=study-plan-v2&envId=top-interview-150
位置算错了扣个半个小时
我日

var construct = function (grid) {
    const gridTotal = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(0))
    for (let index = 0; index < grid[0].length; index++) {
        let total = 0
        for (let indey = 0; indey < grid.length; indey++) {
            const num = grid[indey][index];
            total += num
            gridTotal[indey][index] = (gridTotal[indey][index - 1] ?? 0) + total
        }
    }
    const getArea = (x, y, len) => {
        const all = gridTotal[x][y];
        const sub1 = y - len < 0 ? 0 : gridTotal[x][y - len];
        const sub2 = x - len < 0 ? 0 : gridTotal[x - len][y];
        const add = x - len < 0 || y - len < 0 ? 0 : gridTotal[x - len][y - len];
        return all - sub1 - sub2 + add
    }
    const isAllOneOrZero = (x, y, len) => {
        const area = getArea(x, y, len);
        if (area == 0 || area == (len * len)) {
            return { isLeaf: true, val: area == 0 ? false : true }
        }
        return { isLeaf: false, val: false }
    }
    const generateTree = (x, y, len) => {
        const node = isAllOneOrZero(x, y, len);
        if (node.isLeaf) {
            node.topLeft = node.topRight = node.bottomLeft = node.bottomRight = null;
        } else {
            const halfLen = parseInt(len / 2)
            node.topLeft = generateTree(x - (halfLen), y - halfLen, halfLen)
            node.topRight = generateTree(x- (halfLen),y, halfLen)
            node.bottomLeft = generateTree(x, y - halfLen, halfLen)
            node.bottomRight = generateTree(x, y, halfLen)
        }
        return node
    }
    return generateTree(grid[0].length - 1, grid.length - 1, grid.length)
};

李恒道

https://leetcode.cn/problems/richest-customer-wealth/submissions/588536600/?envType=study-plan-v2&envId=programming-skills
水题秒一个玩

func maximumWealth(accounts [][]int) int {
    var ans int
    for i := 0; i < len(accounts); i++ {
        var total int = 0
        for index := 0; index < len(accounts[i]); index++ {
            total += accounts[i][index]
        }
        ans = int(math.Max(float64(ans), float64(total)))
    }
    return ans
}

李恒道

https://leetcode.cn/problems/matrix-diagonal-sum/submissions/588536659/?envType=study-plan-v2&envId=programming-skills

func diagonalSum(mat [][]int) int {
    var ans int
    for i := 0; i < len(mat); i++ {
        ans += mat[i][i]
        if i!=len(mat)-i-1 {
            ans += mat[i][len(mat)-i-1]
        }
    }
    return ans
}