Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
396 views
in Technique[技术] by (71.8m points)

javascript - 在1和0的矩阵中找到最大尺寸平方的Javascript算法[关闭](Javascript Algorithm to find maximum size square in matrix of 1's and 0's [closed])

You are the owner of a coworking space like WeWork and your office building is rectangular.(您是WeWork等共享办公空间的所有者,而您的办公大楼是矩形的。)

You team just created many wall partitions to create mini offices for startups.(您的团队刚刚创建了许多墙分区,为初创企业创建了迷你办公室。) Your office campus is represented by a 2D array of 1s (floor spaces) and 0s (walls).(您的办公室园区由1s(地面空间)和0s(墙壁)的2D数组表示。) Each point on this array is a one foot by one foot square.(此数组上的每个点都是一英尺乘一英尺的正方形。) Before renting to tenants, you want to reserve an office for yourself.(在租给租户之前,您想为自己保留一个办公室。) You wish to fit the largest possible rectangular table in your office, and you will select the office that fits this table.(您希望适合办公室中最大的矩形桌子,然后选择适合该桌子的办公室。) The table sides will always be parallel to the boundaries of the office building.(桌子的侧面将始终平行于办公大楼的边界。) What is the area of the biggest table that can fit in your office?(可容纳您办公室的最大桌子的面积是多少?) Functions biggestTable() has one parameter:(函数maximumTable()具有一个参数:) grid: a 2D grid/array of 1s and 0s(网格:1和0的2D网格/阵列) Input Format For some of our templates, we have handled parsing for you.(输入格式对于我们的某些模板,我们已为您处理了解析。) If we do not provide you a parsing function, you will need to parse the input directly.(如果我们不为您提供解析功能,则需要直接解析输入。) In this problem, our input format is as follows:(在这个问题中,我们的输入格式如下:) The first line is the number of rows in the 2D array The second line is the number of columns in the 2D array The rest of the input contains the data to be processed Here is an example of the raw input:(第一行是2D数组中的行数,第二行是2D数组中的列数。输入的其余部分包含要处理的数据,这是原始输入的示例:) 4 5 11110 11010 11000 00000 Expected Output Return the area of the biggest right-angled parallelogram made of 1s in the grid.(预期输出返回网格中由1s组成的最大直角平行四边形的面积。) Assume the grid is surrounded by 0s (walls).(假定网格被0(墙)包围。) Constraints Assume that the bounds of the array are the following: The total amount of elements in the array: width x height <= 10^6(约束假定数组的边界如下:数组中元素的总数:宽x高<= 10 ^ 6) Example(例) Example biggestTable() Input grid: [[1, 0, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]] Example Output 9 /** * @param {character[][]} grid * @return {number} */ var biggestTable = function(grid) { // your code here return 0; }; let height = parseInt(readline()); let width = parseInt(readline()); let grid = []; for (var i = 0; i < height; i++) { grid[i] = (readline() || "").split(""); } can some one pls help with the solution.(可以帮助解决方案吗?)   ask by Johnniexson translate from so

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The problem can be approached in a logical way where you loop through the building and check for potential space where tables can be placed, then just return the biggest table found:(可以以逻辑方式解决该问题,其中您可以遍历整个建筑物并检查可以放置表的潜在空间 ,然后仅返回找到的最大表 :)

function biggestTable(grid) { const tableExist = (x, y, w, h) => { let exist = 1; for(let i = 0; i < w ; i++) { for(let j = 0; j < h ; j++) { exist &= grid[j + y] !== undefined && grid[j + y][i + x] === 1; } } return exist; }; const biggestTableAt = (x, y) => { let max = 0; for(let w = 1; w <= grid[0].length; w++) { for(let h = 1; h <= grid.length; h++) { const table_size = w * h; if (tableExist(x, y, w, h) && table_size>max) { max = table_size; } } } return max; }; let max = 0; for(let x = 0; x < grid[0].length; x++) { for(let y= 0; y < grid.length; y++) { const table_size = biggestTableAt(x, y); if (table_size > max) { max = table_size; } } } return max; } const simple_grid = [ [1, 0, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0] ]; console.log(biggestTable(simple_grid)); //returns 9 const big_grid = [ [1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1], ]; console.log(biggestTable(big_grid)); // returns 18 The accepted response returns 9 for both grids, as it assumes that tables are square instead of rectangular as requested in the question.(接受的响应对于两个网格均返回9,因为它假定表格是正方形而不是问题中要求的矩形 。)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...