“This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Today’s topic is simplicity. It’s easy to get the right answer through simple simulation thinking, but think about how to optimize the process and simplify the code.

A daily topic

1725. The number of rectangles that can form the largest square is easy

  • Give you a rectangles, rectangles[I] = [li, wi] means that the length of the ith rectangle is Li and the width is wi.

  • If k satisfies both k <= Li and k <= wi, the ith rectangle can be cut into a square with sides of length K. For example, a rectangle [4,6] can be cut into a square with sides of up to 4.

  • Let maxLen be the side length of the largest square that can be sliced from the rectangular array Rectangles.

  • Ask you to count how many rectangles can cut out a square with sides of maxLen and return the number of rectangles.

Example 1:

Input: rectangles = [[5.8], [3.9], [5.12], [16.5]] output:3Explanation: The largest square sides that can be cut out of each rectangle are [5.3.5.5]. The largest square has two sides of length5By,3I have a rectangle cut and I get.Copy the code

Example 2:

Input: rectangles = [[2.3], [3.7], [4.3], [3.7]] output:3
Copy the code

Tip:

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

Answer key

Violent solution

As the problem requires, we can loop through the rectangles array twice, first finding the largest square that can be cut, and the second finding how many rectangles can make that square.

We define a maxLen initial 0, at the time of first traversal, to determine each cycle length and the width of which is the smallest, because the rectangle into a square, with little of the edge, the small one is the rectangular can cut out the biggest square, then as long as there is the biggest square side length is more than maxLen, will replace maxLen.

And the second time I go through it, I’m just going to say how many rectangles are there and the shortest one is equal to maxLen, and then it can cut out the square, and I’m going to return the number of rectangles that I got.

/ * * *@param {number[][]} rectangles
 * @return {number}* /
var countGoodRectangles = function (rectangles) {
  let n = rectangles.length;
  let maxLen = 0;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    let maxWidth = Math.min(rectangles[i][0], rectangles[i][1]);
    if(maxLen < maxWidth) { maxLen = maxWidth; }}for (let i = 0; i < n; i++) {
    let maxWidth = Math.min(rectangles[i][0], rectangles[i][1]);
    if(maxLen == maxWidth) { ans++; }}return ans;
};
Copy the code

Optimization time complexity is O(n)

In the above method, we loop through the array twice, but we can loop only once.

In a loop, each time is divided into two cases:

  1. The one with the smallest length or width of the loop is equal to maxLen, so ans plus 1
  2. If the length or width of the loop is greater than maxLen, then the previous criterion is not the largest, so reset the answer ANS to 1 and update maxLen
/ * * *@param {number[][]} rectangles
 * @return {number}* /
var countGoodRectangles = function (rectangles) {
  let ans = 0,
    maxLen = 0;
  for (const rectangle of rectangles) {
    const l = rectangle[0],
      w = rectangle[1];
    const maxWidth = Math.min(l, w);
    if (maxWidth === maxLen) {
      ++ans;
    } else if (maxWidth > maxLen) {
      ans = 1; maxLen = maxWidth; }}return ans;
};
Copy the code