最大加號標(biāo)志
題目
在一個 n x n 的矩陣?grid?中，除了在數(shù)組?mines?中給出的元素為?0，其他每個元素都為?1。mines[i] = [xi, yi]表示?grid[xi][yi] == 0
返回 ?grid 中包含?1?的最大的 軸對齊 加號標(biāo)志的階數(shù) 。如果未找到加號標(biāo)志，則返回 0 。
一個?k?階由?1?組成的 “軸對稱”加號標(biāo)志 具有中心網(wǎng)格?grid[r][c] == 1?，以及4個從中心向上、向下、向左、向右延伸，長度為?k-1，由?1?組成的臂。注意，只有加號標(biāo)志的所有網(wǎng)格要求為 1 ，別的網(wǎng)格可能為 0 也可能為 1 。
示例 1：
輸入: n = 5, mines = [[4, 2]]
輸出: 2
解釋: 在上面的網(wǎng)格中，最大加號標(biāo)志的階只能是2。一個標(biāo)志已在圖中標(biāo)出。
示例 2：
輸入: n = 1, mines = [[0, 0]]
輸出: 0
解釋: 沒有加號標(biāo)志，返回 0 。
提示：
1 <= n <= 500
1 <= mines.length <= 5000
0 <= xi, yi?< n
每一對?(xi, yi)?都 不重復(fù)
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/largest-plus-sign
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
暴力破解
超時
解題思路
遍歷所有點(diǎn)，取所有點(diǎn)的長度，取最大長度
public static int orderOfLargestPlusSign0(int n, int[][] mines) {
? ? ? ?HashSet<Point> mineSet= new HashSet<>();
? ? ? ?for (int i = 0; i < mines.length; i++) {
? ? ? ? ? ?Point point =new Point();
? ? ? ? ? ?point.x=mines[i][0];
? ? ? ? ? ?point.y=mines[i][1];
? ? ? ? ? ?mineSet.add(point);
? ? ? ?}
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?Point center= new Point();
? ? ? ? ? ? ? ?center.x=i;
? ? ? ? ? ? ? ?center.y=j;
? ? ? ? ? ? ? ?if(mineSet.contains(center))
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?System.out.print(0+"\t");
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?System.out.print(1+"\t");
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?System.out.println();
? ? ? ?}
? ? ? ?int maxLen=0;
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?Point center= new Point();
? ? ? ? ? ? ? ?center.x=i;
? ? ? ? ? ? ? ?center.y=j;
? ? ? ? ? ? ? ?if(mineSet.contains(center))
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?List<Point> allPoint = getAllPoint(n, center,mineSet);
? ? ? ? ? ? ? ?int len = allPoint.size()/4+1;
? ? ? ? ? ? ? ?maxLen=Math.max(len,maxLen);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return maxLen;
? ?}
? ?public static List<Point> getAllPoint(int n,Point center,HashSet<Point> mineSet)
? ?{
? ? ? ?List<Point> rs = new ArrayList<>();
? ? ? ?rs.add(center);
? ? ? ?int up ?= center.x-1;
? ? ? ?int right = center.y+1;
? ? ? ?int down = center.x+1;
? ? ? ?int left =center.y-1;
? ? ? while (up>=0 && right<n&& down<n && left>=0) {
? ? ? ? ? Point upPoint= new Point();
? ? ? ? ? upPoint.x=up;
? ? ? ? ? upPoint.y=center.y;
? ? ? ? ? Point rightPoint= new Point();
? ? ? ? ? rightPoint.x=center.x;
? ? ? ? ? rightPoint.y=right;
? ? ? ? ? Point downPoint= new Point();
? ? ? ? ? downPoint.x=down;
? ? ? ? ? downPoint.y=center.y;
? ? ? ? ? Point leftPoint= new Point();
? ? ? ? ? leftPoint.x=center.x;
? ? ? ? ? leftPoint.y=left;
? ? ? ? ? if(mineSet.contains(upPoint) ||
? ? ? ? ? ? ? ? ? mineSet.contains(rightPoint) ||
? ? ? ? ? mineSet.contains(downPoint) ||
? ? ? ? ? mineSet.contains(leftPoint))
? ? ? ? ? {
? ? ? ? ? ? ? break;
? ? ? ? ? }
? ? ? ? ? rs.add(upPoint);
? ? ? ? ? rs.add(rightPoint);
? ? ? ? ? rs.add(downPoint);
? ? ? ? ? rs.add(leftPoint);
? ? ? ? ? up--;
? ? ? ? ? right++;
? ? ? ? ? down++;
? ? ? ? ? left--;
? ? ? }
? ? ? ?return rs;
? ?}
? ?public static class Point
? ?{
? ? ? ?public Integer x;
? ? ? ?public Integer y;
? ? ? ?@Override
? ? ? ?public boolean equals(Object obj) {
? ? ? ? ? ?return (this.x==((Point) obj).x) && (this.y==((Point) obj).y);
? ? ? ?}
? ? ? ?@Override
? ? ? ?public int hashCode() {
? ? ? ? ? ?return x.hashCode()+y.hashCode();
? ? ? ?}
? ?}
優(yōu)化枚舉
可以通過
解題思路
設(shè)置一個map，將排除點(diǎn)標(biāo)記為1，然后枚舉所有點(diǎn)的長度，取最大長度，將上一個方法的哈希和實(shí)體轉(zhuǎn)為簡單的數(shù)組了?？梢酝ㄟ^了
public static int orderOfLargestPlusSign(int n, int[][] mines) {
? ? ? ?//初始化map值為0的矩陣
? ? ? ?int[][] map= new int[n][n];
? ? ? ?//
? ? ? ?for (int i = 0; i < mines.length; i++) {
? ? ? ? ? ?map[mines[i][0]][mines[i][1]]=1;
? ? ? ?}
? ? ? ?int maxLen=0;
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?if(map[i][j]==1)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?int len = getLen(n,i,j,map);
? ? ? ? ? ? ? ?maxLen=Math.max(len,maxLen);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return maxLen;
? ?}
? ?public static int getLen(int n,int x,int y,int[][] map)
? ?{
? ? ? ?int up ?= x-1;
? ? ? ?int right = y+1;
? ? ? ?int down = x+1;
? ? ? ?int left =y-1;
? ? ? ?int len=1;
? ? ? ?while (up>=0 && right<n&& down<n && left>=0) {
? ? ? ? ? ?if (map[up][y] == 1 ||
? ? ? ? ? ? ? ? ? ?map[x][right] == 1 ||
? ? ? ? ? ? ? ? ? ?map[down][y] == 1 ||
? ? ? ? ? ? ? ? ? ?map[x][left] == 1) {
? ? ? ? ? ? ? ?break;
? ? ? ? ? ?}
? ? ? ? ? ?up--;
? ? ? ? ? ?right++;
? ? ? ? ? ?down++;
? ? ? ? ? ?left--;
? ? ? ? ? ?len++;
? ? ? ?}
? ? ? ?return len;
? ?}
動態(tài)規(guī)劃
解題思路
每個點(diǎn)所能形成的大加好標(biāo)志?？梢岳斫鉃樗膫€方向連續(xù)的1的個數(shù)。并且是四個方法連續(xù)1個數(shù)的最小值。所以可以設(shè)置dp[][]，為每個點(diǎn)為最大連續(xù)個數(shù)，然后取四個方向的最小值。以下代碼還可以優(yōu)化簡寫，但簡寫了之后，不太好理解，為了保證可讀性，所以就沒有在簡寫了。
public static int orderOfLargestPlusSign3(int n, int[][] mines) {
? ? ? ?int[][] dp = new int[n][n];
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?dp[i][j]=n;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?for (int i = 0; i < mines.length; i++) {
? ? ? ? ? ?dp[mines[i][0]][mines[i][1]]=0;
? ? ? ?}
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?int left=0;
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?left = dp[i][j]>0?left+1:0;
? ? ? ? ? ? ? ?dp[i][j]=Math.min(dp[i][j],left);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?int right=0;
? ? ? ? ? ?for (int j = n-1; j>=0; j--) {
? ? ? ? ? ? ? ?right = dp[i][j]>0?right+1:0;
? ? ? ? ? ? ? ?dp[i][j]=Math.min(dp[i][j],right);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?int up = 0;//循環(huán)up，x軸
? ? ? ? ? ?for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ?up = dp[j][i] > 0 ? up + 1 : 0;
? ? ? ? ? ? ? ?dp[j][i] = Math.min(dp[j][i], up);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?for (int i = 0; i < n; i++) {
? ? ? ? ? ?int down = 0;
? ? ? ? ? ?for (int j = n - 1; j >= 0; j--) {
? ? ? ? ? ? ? ?down = dp[j][i] > 0 ? down + 1 : 0;
? ? ? ? ? ? ? ?dp[j][i] = Math.min(dp[j][i], down);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?int rs = 0;
? ? ? ?for (int[] e : dp) {
? ? ? ? ? ?rs = Math.max(rs, Arrays.stream(e).max().getAsInt());
? ? ? ?}
? ? ? ?return rs;
? ?}
鏈接：https://www.dianjilingqu.com/607166.html
