刷题笔记

[Lirx-Xin]

刷题笔记

34. 在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 进阶： 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    const leftindex = getindex(nums,target,true) // 找到第一个大于等于target的元素位置；
    const rightindex = getindex(nums,target,false)-1; // 找到第一个大于target的元素位置，再减一，则为最后一个等于target的位置；
    if(nums[leftindex] !== target ||  nums[rightindex] !== target){ // leftindex，和rightindex位置不等于target，则表示元素不存在；
        return [-1,-1]
    }
    return [leftindex,rightindex]
};

function getindex(nums,target,low) {
    let l = 0,r = nums.length - 1,result = nums.length;
    while(l <= r){
        const mid = Math.floor((l + r)/2);
        if(nums[mid] > target || (low && nums[mid] >= target)){
            r = mid-1; // 找到满足条件的mid时，下一个right为该位置之前的元素；
            result = mid; // 将该满足条件的位置设置为结果，这个位置左侧如果还有满足条件的数，则会在后面循环中被刷新；
        }else{
            l = mid+1; // mid小于target则从mid右侧位置作为left；
        }
    }
    return result;
}

---

162. 寻找峰值 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-peak-element 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    // 升序则表示右侧一定存在峰值，降序则表示左侧一定存在峰值；
    let l = 0,r = nums.length;
    while(l < r){
        const m = (l + r) >> 1
        nums[m] < nums[m+1] ? l = m+1 : r = m 
    }
    return l; // 经过上面的循环，l与r最终会相等；
};

---

剑指 Offer 04. 二维数组中的查找 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
// 根据该数组每行每列都从小到大排序的特点，从二维数组右上角开始向左/下遍历，每一个遍历到的数据的右侧与上侧都一定不符合条件。
var findNumberIn2DArray = function(matrix, target) {
if (matrix.length == 0) return false
let row = 0 // 第一行开始
let col = matrix[0].length - 1 // 第一列开始
while (row < matrix.length && col >= 0) { // 行列索引超出范围
if (matrix[row][col] === target) {
return true
} else if(matrix[row][col] > target) {
col--
} else {
row++ 
}
}
return false
};

---

剑指 Offer 32 - I. 从上到下打印二叉树 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 使用队列进行二叉树的广度优先遍历BFS, 对队列进行循环出队入队，每次出队将值输出到结果数组，每次入队将当前节点的子节点从左到右依次入队，那么每一层都将依次入队，依次出队
var levelOrder = function(root) {
    if (root == null || root.val == null) return []
    const result = []
    const qu = [root]
    while(qu[0]) {
        const x = qu.shift()
        result.push(x.val)
        if (x.left) qu.push(x.left)
        if (x.right) qu.push(x.right)
    }
    return result;
};