Leetcode/CountNegativeInMatrix.py at master · vizeit/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def countNegatives(grid):
    c = 0
    for r in grid:
        c += _subcountnegatives(r)
    return c

def _subcountnegatives(r):
    c=0
    if len(r) == 1:
        return 1 if r[0] < 0 else 0
    elif len(r) and r[0] < 0:
        return len(r)
    elif len(r) and r[-1] < 0:
        c += _subcountnegatives(r[:len(r)//2])
        c += _subcountnegatives(r[len(r)//2:])
    return c


if __name__ == "__main__":
    print(countNegatives([[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]))
    print(countNegatives([[3,2],[1,0]]))
    print(countNegatives([[1,-1],[-1,-1]]))
    print(countNegatives([[-1]]))
    print(countNegatives([[10,9,8,8,8,7,6,6,5,5,4,-13,-14,-15],[10,9,7,7,7,7,5,4,3,2,1,-13,-15,-15],[10,9,7,6,6,5,4,4,2,2,0,-14,-16,-16],[9,9,7,5,4,4,4,4,1,1,-1,-15,-16,-16],[9,8,7,4,3,2,1,1,-15,-15,-16,-17,-18,-18],[9,7,7,3,2,2,-20,-20,-20,-20,-20,-20,-20,-20],[8,7,6,3,2,1,-20,-20,-20,-20,-20,-20,-20,-20],[8,6,6,-16,-16,-16,-20,-20,-20,-20,-20,-20,-20,-20],[-19,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20],[-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20,-20]]))