日常刷题0x10之未出新手村

//都能想到的方法，最笨的实现
//遍历
var searchRange = function (nums, target) {
    let result = []
    for (let i = 0; i < nums.length; i++) {
        const ele = nums[i];
        if (ele == target) {
            if (result.length == 0) {
                result.push(i)
                result.push(i)
            } else {
                result.pop()
                result.push(i)
            }
        }
    }
    if (result.length == 0) {
        result = new Array(2).fill(-1)
    }
    return result
};

//二分查找
var searchRange = function (nums, target) {
    let left = 0, right = nums.length - 1
    //魔鬼出没的地方1
    //需不需要==
    let rightIdx = nums.length
    while (left <= right) {
        //魔鬼小细节可能溢出
        let mid = Math.floor(left + (right - left) / 2)
        //魔鬼小细节等还是不加等
        if (nums[mid] > target) {
            //魔鬼小细节+1 -1需不需要
            right = mid - 1
        } else {
            rightIdx = mid
            left = mid + 1
        }
    }
    left = 0, right = nums.length - 1
    let leftIdx = 0
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] >= target) {
            leftIdx = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    //判断坐标leftIdx和rightIdx是否合法（不一定有结果的）
    if (nums[leftIdx] == target && nums[rightIdx] == target) {
        return [leftIdx, rightIdx]
    } else {
        return [-1, -1]
    }
};

//学习别人的递归思路，让我对递归有了更好的认识
var flatten = function (root) {
    if (root == null) {
        return
    }
    //递归处理的是相同子问题，是相同不是相似
    //处理完当前节点的逻辑，下面的节点树还是一个树
    //问题是一个问题，那就继续调用flatten处理下一个
    //相同的问题（规模变小）
    if (root.left == null) {
        flatten(root.right)
    } else {
        //观察先序遍历的走向
        //访问到一个节点的时候，先处理的是左节点
        //那么就把左放到当前节点的右边，原来的右
        //子树放哪？不能丢了
        //原来的右子树一定在左边的子树遍历完再遍历
        //那么我就把原来的右树放到左树的最后遍历
        //的那个元素后面不就可以了吗
        let left = root.left
        let right = root.right
        root.right = left
        root.left = null

        let preRight = left
        while (preRight.right != null) {
            preRight = preRight.right
        }
        preRight.right = right
        //继续递归
        flatten(root.right)
    }
};

//动态规划
//             +
//     @@@@@@@@+
//     @@@@@@@@+
//     @@@@@@@@+
// ------------=
var maximalSquare = function (matrix) {
    let dptable = new Array(matrix.length)
    for (let i = 0; i < matrix.length; i++) {
        let arr = new Array(matrix[0].length).fill(0)
        dptable[i] = arr
    }
    let maxLen = 0
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            //matrix[i][j] == 0 长宽再长都行不成符合题意正方形
            if (matrix[i][j] == 1) {
                //初始情况
                //横竖一行的情况
                if (i == 0 || j == 0) {
                    dptable[i][j] = 1
                } else {
                    dptable[i][j] = Math.min(dptable[i - 1][j], dptable[i][j - 1], dptable[i - 1][j - 1]) + 1
                }
            }
            maxLen = Math.max(maxLen, dptable[i][j])
        }
    }
    return maxLen * maxLen
};