青岛网站排名公司,上海摄影网站建设,全国黄页平台,重庆网站seo推广给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 示例 1#xff1a; 输入…给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。示例 1输入nums [2,3,1,1,4]输出true解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2输入nums [3,2,1,0,4]输出false解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。这道题也是一道经典的贪心算法站在下标0每个位置nums[i]表示从i最多可以往右跳nums[i]步然后能不能达到最后一个位置。我们不需要真的跳而是去维护一个变量记录当前能达到的最远位置。核心思考就是我们当前位置的下标是否大于我们维护的那个变量如果下标大说明这个位置个根本到不了如果小于我们维护的这个变量就更新最远的距离具体的代码实现/** * param {number[]} nums * return {boolean} */ var canJump function(nums) { let maxReach 0 for(let i 0;i nums.length;i){ if(i maxReach)return false maxReach Math.max(maxReach,i nums[i]) } return true };我们分析一下两个示例[2,3,1,1,4]inums[i]maxReach022134214314448[3,2,1,0,4]inums[i]maxReach03312321330344❌ 到不了我们在每次遍历都在选择当前位置能到达的最大距离所以是贪心。编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。我拿到这一道题第一反应是使用二分法对每一行二分但是时间复杂度是O(m log n)突然发先右上角的元素有神奇的性质它左边都比它小它下面都比它大这意味着一次比较就能排除一整行或一整列。假设从row 0col n - 1 // 右上角开始。每一步如果matrix[row][col] target找到返回 true如果matrix[row][col] target说明这一列都比 target 大往左走col--如果matrix[row][col] target说明这一行都比 target 小往下走rowvar searchMatrix function(matrix, target) { const m matrix.length const n matrix[0].length let row 0 let col n - 1 while (row m col 0) { const val matrix[row][col] if (val target) return true if (val target) { col-- } else { row } } return false };时间复杂度每一步不是往下就是往左最多m n 步所以时间复杂度 O(m n)