|
5 | 5 |
|
6 | 6 | publicclass_764 { |
7 | 7 | publicstaticclassSolution1 { |
8 | | -/** |
9 | | - * Brute force |
10 | | - * <p> |
11 | | - * Time: O(N^3) |
12 | | - * Space: O(mines.length) |
13 | | - */ |
14 | | -publicintorderOfLargestPlusSign(intN,int[][]mines) { |
15 | | -Set<Integer>banned =newHashSet<>(); |
16 | | -for (int[]mine :mines) { |
17 | | -banned.add(mine[0] *N +mine[1]); |
18 | | - } |
19 | | -intresult =0; |
20 | | -for (introw =0;row <N;row++) { |
21 | | -for (intcol =0;col <N;col++) { |
22 | | -intk =0; |
23 | | -while (k <=row &&row <N -k &&k <=col &&col <N -k |
24 | | - && !banned.contains((row -k) *N +col) |
25 | | - && !banned.contains((row +k) *N +col) |
26 | | - && !banned.contains(row *N +col -k) |
27 | | - && !banned.contains(row *N +col +k)) { |
28 | | -k++; |
29 | | - } |
30 | | -result =Math.max(result,k); |
31 | | - } |
32 | | - } |
33 | | -returnresult; |
34 | | - } |
35 | | - } |
36 | | - |
37 | | -publicstaticclassSolution2 { |
38 | 8 | /** |
39 | 9 | * Dp |
40 | 10 | * <p> |
@@ -82,4 +52,81 @@ public int orderOfLargestPlusSign(int N, int[][] mines) { |
82 | 52 | returnresult; |
83 | 53 | } |
84 | 54 | } |
| 55 | + |
| 56 | +publicstaticclassSolution2 { |
| 57 | +/** |
| 58 | + * credit: https://leetcode.com/problems/largest-plus-sign/discuss/113314/JavaC%2B%2BPython-O(N2)-solution-using-only-one-grid-matrix |
| 59 | + */ |
| 60 | +publicintorderOfLargestPlusSign(intn,int[][]mines) { |
| 61 | +int[][]grid =newint[n][n]; |
| 62 | +for (inti =0;i <n;i++) { |
| 63 | +for (intj =0;j <n;j++) { |
| 64 | +grid[i][j] =n; |
| 65 | + } |
| 66 | + } |
| 67 | +for (inti =0;i <mines.length;i++) { |
| 68 | +grid[mines[i][0]][mines[i][1]] =0; |
| 69 | + } |
| 70 | +for (inti =0;i <n;i++) { |
| 71 | +for (intj =0,k =n -1,l =0,r =0,u =0,d =0;j <n;j++,k--) { |
| 72 | +grid[i][j] =Math.min(grid[i][j],l = (grid[i][j] ==0 ?0 :l +1));//left direction |
| 73 | +grid[i][k] =Math.min(grid[i][k],r = (grid[i][k] ==0 ?0 :r +1));//right direction |
| 74 | +grid[j][i] =Math.min(grid[j][i],u = (grid[j][i] ==0 ?0 :u +1));//upwards |
| 75 | +grid[k][i] =Math.min(grid[k][i],d = (grid[k][i] ==0 ?0 :d +1));//downwards |
| 76 | + } |
| 77 | + } |
| 78 | +intresult =0; |
| 79 | +for (inti =0;i <n;i++) { |
| 80 | +for (intj =0;j <n;j++) { |
| 81 | +result =Math.max(result,grid[i][j]); |
| 82 | + } |
| 83 | + } |
| 84 | +returnresult; |
| 85 | + } |
| 86 | + |
| 87 | +/** |
| 88 | + * break the above into FOUR separate loops to go over four directions for easier understanding |
| 89 | + */ |
| 90 | +publicintorderOfLargestPlusSign_initialVersion(intn,int[][]mines) { |
| 91 | +int[][]grid =newint[n][n]; |
| 92 | +for (inti =0;i <n;i++) { |
| 93 | +for (intj =0;j <n;j++) { |
| 94 | +grid[i][j] =n; |
| 95 | + } |
| 96 | + } |
| 97 | +for (inti =0;i <mines.length;i++) { |
| 98 | +grid[mines[i][0]][mines[i][1]] =0; |
| 99 | + } |
| 100 | +for (inti =0;i <n;i++) { |
| 101 | +for (intj =0,l =0;j <n;j++) { |
| 102 | +grid[i][j] =Math.min(grid[i][j],l = (grid[i][j] ==0 ?0 :l +1)); |
| 103 | + } |
| 104 | + } |
| 105 | + |
| 106 | +for (inti =0;i <n;i++) { |
| 107 | +for (intj =0,k =n -1,r =0;j <n;j++,k--) { |
| 108 | +grid[i][k] =Math.min(grid[i][k],r = (grid[i][k] ==0 ?0 :r +1)); |
| 109 | + } |
| 110 | + } |
| 111 | + |
| 112 | +for (inti =0;i <n;i++) { |
| 113 | +for (intj =0,k =n -1,u =0;j <n;j++,k--) { |
| 114 | +grid[j][i] =Math.min(grid[j][i],u = (grid[j][i] ==0 ?0 :u +1)); |
| 115 | + } |
| 116 | + } |
| 117 | + |
| 118 | +for (inti =0;i <n;i++) { |
| 119 | +for (intj =0,k =n -1,d =0;j <n;j++,k--) { |
| 120 | +grid[k][i] =Math.min(grid[k][i],d = (grid[k][i] ==0 ?0 :d +1)); |
| 121 | + } |
| 122 | + } |
| 123 | +intresult =0; |
| 124 | +for (inti =0;i <n;i++) { |
| 125 | +for (intj =0;j <n;j++) { |
| 126 | +result =Math.max(result,grid[i][j]); |
| 127 | + } |
| 128 | + } |
| 129 | +returnresult; |
| 130 | + } |
| 131 | + } |
85 | 132 | } |