网站整体地图怎么做,做网站是否用数据库,网站建设课的感想,wordpress填写题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 1#xff1a; 输入#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,…题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 1 输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5
输出true示例 2 输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 20
输出false提示
m matrix.lengthn matrix[i].length1 n, m 300-10^9 matrix[i][j] 10^9每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-10^9 target 10^9 解答
源代码
class Solution {public boolean searchMatrix(int[][] matrix, int target) {return dfs(matrix, 0, matrix[0].length - 1, target);}public boolean dfs(int[][] matrix, int i, int j, int target) {if (i matrix.length || j 0) {return false;}if (matrix[i][j] target) {return true;} else if (matrix[i][j] target) {return dfs(matrix, i, j - 1, target);} else {return dfs(matrix, i 1, j, target);}}
}
总结
想用递归但重点在于递归的起点在哪里。一开始我把递归的起点定在了左上角这样做出来的算法其实比暴力破解还糟糕把起点定在右上角才是正确的选择此时当前元素的左边都比它小下边都比它大。
