|
38 | 38 | The range of width and height of the input 2D array is [1,200]. |
39 | 39 | */ |
40 | 40 | publicclass_533 { |
41 | | -/**Credit: https://discuss.leetcode.com/topic/81686/verbose-java-o-m-n-solution-hashmap/5 |
42 | | - * |
43 | | - * This program is very well designed to do things: |
44 | | - * 1. it scans the entire matrix once, but does two things in this scan: |
45 | | - * first it records an array of cols that keeps count of how many 'B' are there in each column; |
46 | | - * second, at the end of traversing each column, it puts this entire row as the key into a HashMap |
47 | | - * when there N number of 'B's in this row. |
48 | | - * |
49 | | - * 2. then we could go through the HashMap keyset: |
50 | | - * if one row has N number of 'B's, we go through this row's each column to see if any element in this row is 'B' and also that element's column has N 'B's*/ |
51 | | -publicintfindBlackPixel(char[][]picture,intN) { |
52 | | -if (picture ==null ||picture.length ==0 ||picture[0].length ==0) { |
53 | | -return0; |
54 | | - } |
55 | | -intm =picture.length; |
56 | | -intn =picture[0].length; |
57 | | -int[]cols =newint[n]; |
58 | | -Map<String,Integer>map =newHashMap<>(); |
59 | | -StringBuilderstringBuilder =newStringBuilder(); |
60 | | -for (inti =0;i <m;i++) { |
61 | | -intcount =0; |
62 | | -for (intj =0;j <n;j++) { |
63 | | -if (picture[i][j] =='B') { |
64 | | -count++; |
65 | | -cols[j]++; |
66 | | - } |
67 | | -stringBuilder.append(picture[i][j]); |
| 41 | +publicstaticclassSolution1 { |
| 42 | +/** |
| 43 | + * Credit: https://discuss.leetcode.com/topic/81686/verbose-java-o-m-n-solution-hashmap/5 |
| 44 | + * This program is very well designed to do things: |
| 45 | + * 1. it scans the entire matrix once, but does two things in this scan: |
| 46 | + * first it records an array of cols that keeps count of how many 'B' are there in each column; |
| 47 | + * second, at the end of traversing each column, it puts this entire row as the key into a HashMap |
| 48 | + * when there N number of 'B's in this row. |
| 49 | + * 2. then we could go through the HashMap keyset: |
| 50 | + * if one row has N number of 'B's, we go through this row's each column to see if any element in this row is 'B' and also that element's column has N 'B's |
| 51 | + */ |
| 52 | +publicintfindBlackPixel(char[][]picture,intN) { |
| 53 | +if (picture ==null ||picture.length ==0 ||picture[0].length ==0) { |
| 54 | +return0; |
68 | 55 | } |
69 | | -if (count ==N) { |
70 | | -/**we use this entire row string as key for the map*/ |
71 | | -map.put(stringBuilder.toString(),map.getOrDefault(stringBuilder.toString(),0) +1); |
| 56 | +intm =picture.length; |
| 57 | +intn =picture[0].length; |
| 58 | +int[]cols =newint[n]; |
| 59 | +Map<String,Integer>map =newHashMap<>(); |
| 60 | +StringBuilderstringBuilder =newStringBuilder(); |
| 61 | +for (inti =0;i <m;i++) { |
| 62 | +intcount =0; |
| 63 | +for (intj =0;j <n;j++) { |
| 64 | +if (picture[i][j] =='B') { |
| 65 | +count++; |
| 66 | +cols[j]++; |
| 67 | + } |
| 68 | +stringBuilder.append(picture[i][j]); |
| 69 | + } |
| 70 | +if (count ==N) { |
| 71 | +/**we use this entire row string as key for the map*/ |
| 72 | +map.put(stringBuilder.toString(),map.getOrDefault(stringBuilder.toString(),0) +1); |
| 73 | + } |
| 74 | +stringBuilder.setLength(0); |
72 | 75 | } |
73 | | -stringBuilder.setLength(0); |
74 | | - } |
75 | 76 |
|
76 | | -intanswer =0; |
77 | | -for (Stringkey :map.keySet()) { |
78 | | -if (map.get(key) !=N) { |
79 | | -continue; |
80 | | - } |
81 | | -for (inti =0;i <n;i++) { |
82 | | -if (key.charAt(i) =='B' &&cols[i] ==N) { |
83 | | -answer +=N; |
| 77 | +intanswer =0; |
| 78 | +for (Stringkey :map.keySet()) { |
| 79 | +if (map.get(key) !=N) { |
| 80 | +continue; |
| 81 | + } |
| 82 | +for (inti =0;i <n;i++) { |
| 83 | +if (key.charAt(i) =='B' &&cols[i] ==N) { |
| 84 | +answer +=N; |
| 85 | + } |
84 | 86 | } |
85 | 87 | } |
| 88 | +returnanswer; |
86 | 89 | } |
87 | | -returnanswer; |
88 | 90 | } |
89 | 91 |
|
90 | 92 | } |