专栏首页江涛的博客leetcode - 可以形成最大正方形的矩形数目

leetcode - 可以形成最大正方形的矩形数目

题意

给你一个数组 rectangles ,其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li、宽度为 wi

如果存在 k同时满足 k <= lik <= wi,就可以将第 i个矩形切成边长为 k的正方形。例如,矩形 [4,6]可以切成边长最大为 4的正方形。

maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

返回可以切出边长为 maxLen 的正方形的矩形 数目 。

示例

示例 1:

输入:rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出:3
解释:能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ,可以由 3 个矩形切分得到。

示例 2:

输入:rectangles = [[2,3],[3,7],[4,3],[3,7]]
输出:3

提示

  • 1 <= rectangles.length <= 1000
  • rectangles[i].length == 2
  • 1 <= li, wi <= 109
  • li != wi

出处

链接:https://leetcode-cn.com/problems/number-of-rectangles-that-can-form-the-largest-square

思路

这题翻译一下就是,计算二维数组中每一项的最小的值,然后求出现最小值中的最大值的次数。我们可以用一个对象去记录最小值出现的次数,然后求其最大值的次数。

代码

/**
 * @param {number[][]} rectangles
 * @return {number}
 */
const countGoodRectangles = function (rectangles) {
  const obj = {};
  rectangles.forEach((item) => {
    const res = item[0] > item[1] ? item[1] : item[0];
    if (obj[res]) {
      obj[res]++;
    } else {
      obj[res] = 1;
    }
    return res;
  });
  const max = Math.max.apply(this, Object.keys(obj));
  return obj[max];
};

export default countGoodRectangles;

测试

import countGoodRectangles from '../../code/leetcode/5653';

describe('test function countGoodRectangles: ', () => {
  test('test case rectangles = [[5,8],[3,9],[5,12],[16,5]]', () => {
    const res = countGoodRectangles([
      [5, 8],
      [3, 9],
      [5, 12],
      [16, 5],
    ]);
    expect(res).toBe(3);
  });
  test('test case rectangles = [[2,3],[3,7],[4,3],[3,7]]', () => {
    const res = countGoodRectangles([
      [2, 3],
      [3, 7],
      [4, 3],
      [3, 7],
    ]);
    expect(res).toBe(3);
  });
});

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1725. 可以形成最大正方形的矩形数目

    给你一个数组 rectangles ,其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。

    Michael阿明
  • LeetCode 1139. 最大的以 1 为边界的正方形(DP)

    给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。

    Michael阿明
  • LeetCode 996. 正方形数组的数目(回溯+剪枝)

    给定一个非负整数数组 A,如果该数组每对相邻元素之和是一个完全平方数,则称这一数组为正方形数组。

    Michael阿明
  • LeetCode 1363. 形成三的最大倍数(贪心,难)

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    Michael阿明
  • LeetCode 85 | 如何从矩阵当中找到数字围成的最大矩形的面积?

    今天是LeetCode专题53篇文章,我们一起来看看LeetCode中的85题,Maximal Rectangle(最大面积矩形)。

    TechFlow-承志
  • 【LeetCode第 177 场周赛】5172. 形成三的最大倍数

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    韩旭051
  • LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium

    题目: Given a 2D binary matrix filled with 0's and 1's, find the largest square co...

    猿大白
  • 每日算法系列【LeetCode 1363】形成三的最大倍数

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    godweiyang
  • 【LeetCode每日一题】363. 矩形区域不超过 K 的最大数值和

    题目:给你一个 m x n 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

    公众号guangcity
  • LeetCode 1292. 元素和小于等于阈值的正方形的最大边长(DP)

    请你返回元素总和小于或等于阈值的正方形区域的最大边长; 如果没有这样的正方形区域,则返回 0 。

    Michael阿明
  • LeetCode 363. 矩形区域不超过 K 的最大数值和(DP+set二分查找)

    给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。

    Michael阿明
  • LeetCode 836. 矩形重叠

    矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。

    Michael阿明
  • LeetCode 0085. 最大矩形[动态规划详解]

    给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

    Yano_nankai
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • LeetCode 221. 最大正方形(DP)

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    Michael阿明
  • LeetCode1-100题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到100道题了。今天把发布的1-100篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • LeetCode 0084. 柱状图中最大的矩形

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

    Yano_nankai
  • (进阶版)有了四步解题法模板,再也不害怕动态规划!

    这次来针对具体的一类动态规划问题,矩阵类动态规划问题,来看看针对这一类问题的思路和注意点。

    五分钟学算法
  • 【leetcode刷题】T215-矩形重叠

    https://leetcode-cn.com/problems/rectangle-overlap

    木又AI帮

扫码关注云+社区

领取腾讯云代金券