讨论/题目交流/🏆 第 175 场力扣周赛/
🏆 第 175 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 检查整数及其两倍数是否存在
4 分 - 制造字母异位词的最小步骤数
5 分 - 推文计数
7 分 - 参加考试的最大学生数

展开讨论

第四题回溯法(通过)

/**
 * 
 * @param {number} cur 座位坐标
 * @param {number} len 座位总长度
 * @param {object} obj 记录(x,y)是否放置学生
 * @param {object} result 记录最大值max
 * @param {Array} seats 
 * @param {number} m 宽
 * @param {number} n 长
 * @param {number} count 记录当前放置学生数量
 */
function backtrack(cur,len,obj,result,seats,m,n,count){
    if(cur===len) {
        result.max=Math.max(count,result.max)
        return
    }
    let x=Math.floor(cur/n)
    let y=cur%n
    if((len-cur)/2+count<result.max) return //剪枝,[cur,len-1] 最多不超过(len-cur)/2个点
    
    if(seats[x][y]==='#'){
        backtrack(cur+1,len,obj,result,seats,m,n,count)
    }else{
        //左,左上,右上 因为cur是递增,所以不用考虑右
        let arr=[[x,y-1],[x-1,y-1],[x-1,y+1]]
        let flag=false
        for(const [p,k] of arr){
            let key=p+'#'+k
            if(obj[key]){
                flag=true
            }
        }
        //如果左,左上,右上均没有学生,则可以选择放学生
        if(!flag){
            const key=x+'#'+y
            obj[key]=true
            backtrack(cur+1,len,obj,result,seats,m,n,count+1)
            obj[key]=false
        }
      
        backtrack(cur+1,len,obj,result,seats,m,n,count)
    }
}
/**
 * @param {character[][]} seats
 * @return {number}
 */
var maxStudents = function(seats) {
    let max=-Infinity
    let result={max}
    let m=seats.length
    let n=seats[0].length

    backtrack(0,m*n,{},result,seats,m,n,0)
    return result.max
};
展开全部 42 讨论