Leetcode

[LeetCode750]角の長方形の数



Number Corner Rectangles



0と1しかないグリッドが与えられた場合、角の長方形の数を見つけます。

値が1である必要があるのはコーナーのみであることに注意してください。また、使用される4つの1はすべて別個でなければなりません。



例

例1：

Input: [ [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].

例2：



Input: [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

例3：

Input: [[1,1,1,1]] Output: 0 Explanation: Rectangles must have four distinct corners.

通知

  1. グリッドの行と列の数は、それぞれ[1、200] [1,200]の範囲になります。
  2. 各grid[i][j] 0または1のいずれかになります。
  3. グリッド内の1の数は最大6000になります。

分析

これはleetCodeの暗号化に関する質問ですが、同じトピックがlintCodeにあり、送信できることがわかりました。



この質問は、グリッド内で4つの頂点すべてが1である長方形の数を見つけることです。実際、2つの線の間で互いに等しい縦座標の数を比較することであり、最初の線と2番目の線に3つの線がある場合、（3 * 2）/ 2 = 3つの長方形を形成できます。グリッド全体をトラバースすると、複雑さはO（n * n * m）になります。

コード

class Solution { public: /** * @param grid: the grid * @return: the number of corner rectangles */ int countCornerRectangles(vector &grid) { // Write your code here int rows = grid.size() if (rows == 0) return 0 int cols = grid[0].size() int sum = 0 for (int i = 0 i

運用効率

あなたの提出物は72.84％の提出物を上回っています！