7月22号python 每日一题

LCR 121. 寻找目标值 - 二维数组

难度：中等

m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：

• 每行中，每棵植物的右侧相邻植物不矮于该植物；
• 每列中，每棵植物的下侧相邻植物不矮于该植物。

请判断 plants 中是否存在目标高度值 target。

示例 1：

输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8

输出：true
 

示例 2：

输入：plants = [[1,3,5],[2,5,7]], target = 4

输出：false

补全代码：

class Solution:
    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:
    

答案：

思路：

首先进行非空判断，即排除matrix＝[]和matrix＝[[]]
然后找标志数，找左下角数字作为标志数，它为第一列最大数字，是本行最小数字
如果target 大于该数则向上查找，否则往右查找。

代码 ：

class Solution:
    def findTargetIn2DPlants(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix)==0 or (len(matrix[0])==0 and len(matrix)==1):
            return False
        else:
            i, j = 0, len(matrix) - 1
            while j>=0 and i<len(matrix[0]):
                if target < matrix[j][i]:
                    j-=1
                elif matrix[j][i] < target:
                    i += 1 
                else:
                    return True
        return False

1. 初始化和边界检查：首先，检查矩阵是否为空或是否只包含空列表。如果是，则返回False。
2. 初始化索引：将i初始化为0（指向矩阵的第一列），将j初始化为len(matrix) - 1（指向矩阵的最后一行）。
3. 遍历矩阵

最简单的代码：（执行最快的）

class Solution:
    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:
        for row in plants:
            if target in row:
                return True
        
        return False

这个也不错哦：

class Solution:
    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:
        
        for i in plants:
            if not i: return False
            if i[0] <= target and i[-1] >= target:
                for j in i:
                    if j == target: return True
        return False