Leetcode - Maximum Product Subarray
Leetcode - Integer to English Words

leetcode - Number Of Corner Rectangles

violet posted @ May 22, 2020 03:57:46 AM in 算法 with tags Algorithm Golang array , 211 阅读

https://leetcode.com/problems/number-of-corner-rectangles/

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

 

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

 

func countCornerRectangles(grid [][]int) int {
    result := 0
    for i := 0; i < len(grid)-1; i++ {
        for j := i + 1; j < len(grid); j++ {
            count := 0
            for k := 0; k < len(grid[0]); k++ {
                if grid[i][k] == 1 && grid[j][k] == 1 {
                    count++
                }
            }
            if count > 0 {
                result += count * (count-1) /2
            }
        }
    }
    return result
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter