Math

Catalogue
  1. 1. 750. Number Of Corner Rectangles
  2. 2. 836. Rectangle Overlap
  • Prime Number
    1. 1. is Prime
    2. 2. 204. Count Primes

    • 750. Number Of Corner Rectangles

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution(object):
        def countCornerRectangles(self, grid):
            m, n = len(grid), len(grid[0])
            res = 0
            corner = []
            for i in range(m):
                layer = {j for j in range(n) if grid[i][j] == 1}
                for prev in corner:
                    cnt = len(layer & prev)
                    res += cnt * (cnt - 1) // 2
                corner.append(layer)
            return res

    836. Rectangle Overlap

    1
    2
    3
    4
    5
    class Solution(object):
        def isRectangleOverlap(self, rec1, rec2):
            x1, y1, x2, y2 = rec1
            x3, y3, x4, y4 = rec2
            return x2 > x3 and x1 < x4 and y2 > y3 and y1 < y4

    Prime Number

    A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

    is Prime

    1
    2
    3
    4
    5
    6
    7
    def isPrime(m):
        i = 2
        while(i*i <= m):
            if m % i == 0:
                return False
            i += 1
        return True

    204. Count Primes

    • Time : O(n)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      class Solution:
          def countPrimes(self, n):
              if n <= 2:
                  return 0

              primes = [True] * n
              primes[0] = primes[1] = False
              for i in range(2, int(n**0.5)+1):
                  if not primes[i]:
                      continue
                  k = 2
                  while i * k < n:
                      primes[i * k] = False
                      k += 1
              return sum(primes)
    Share