Skip to content

Commit 58e02db

Browse files
awangdevawangdev
committed
hk color grid
1 parent 146e81e commit 58e02db

File tree

4 files changed

+721
-551
lines changed

4 files changed

+721
-551
lines changed

‎Java/ColorGrid.java

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
M
2+
3+
用HashMap， 理解题目规律，因为重复的计算可以被覆盖，所以是个优化题。
4+
5+
消灭重合点:
6+
如果process当下col, 其实要减去过去所有加过的row的交接点。。。
7+
再分析，就是每次碰到row 取一个单点, sumRow += xxx。
8+
然后process当下col时候， sum += colValue * N - sumRow. 就等于把交叉所有row（曾经Process过的row）的点减去了。很方便。
9+
10+
最后read in 是O(P), process也是O(P).
11+
12+
13+
```
14+
15+
/*
16+
HackerRank.
17+
You are given an N×NN×N grid. Each cell has the color white (color 0) in the beginning.
18+
19+
Each row and column has a certain color associated with it. Filling a row or column with a new color VV means changing all the cells of that row or column to VV (thus overriding the previous colors of the cells).
20+
21+
Now, given a sequence of PP such operations, calculate the sum of the colors in the final grid.
22+
23+
For simplicity, the colors will be positive integers whose values will be most 109109.
24+
25+
Input Format
26+
The first line of input contains two integers NN and PP separated by a space.
27+
The next PP lines each contain a filling operation. There are two types of filling operations.
28+
29+
ROW I V which means "fill row II with color VV".
30+
COL I V which means "fill column II with color VV".
31+
Output Format
32+
Output one line containing exactly one integer which is the sum of the colors in the final grid.
33+
34+
Constraints
35+
1≤N≤60001≤N≤6000
36+
1≤P≤4000001≤P≤400000
37+
1≤I≤N1≤I≤N
38+
1≤V≤1091≤V≤109
39+
40+
Sample Input
41+
42+
5 4
43+
COL 1 6
44+
COL 4 11
45+
ROW 3 9
46+
COL 1 24
47+
Sample Output
48+
49+
200
50+
Explanation
51+
There are four operations. After the second operation, the grid looks like
52+
53+
6 0 0 11 0
54+
6 0 0 11 0
55+
6 0 0 11 0
56+
6 0 0 11 0
57+
6 0 0 11 0
58+
After the third operation (ROW 3 9), the third row was colored with 9, overriding any previous color in the cells.
59+
60+
6 0 0 11 0
61+
6 0 0 11 0
62+
9 9 9 9 9
63+
6 0 0 11 0
64+
6 0 0 11 0
65+
After the fourth operation (COL 1 24), the grid becomes:
66+
67+
24 0 0 11 0
68+
24 0 0 11 0
69+
24 9 9 9 9
70+
24 0 0 11 0
71+
24 0 0 11 0
72+
The sum of the colors in this grid is 200.
73+
74+
*/
75+
76+
import java.io.*;
77+
import java.util.*;
78+
import java.text.*;
79+
import java.math.*;
80+
import java.util.regex.*;
81+
/*
82+
Thoughts:
83+
This is for practice. I didn't run much tests on the code.
84+
Store info into class Cell {int x; boolean isRow; long value}
85+
Save to arraylist. Later need to call list.remove(object)
86+
Use hash map to store the appearance <String, Cell>
87+
process the final data:
88+
keep track of curr single row cell sum = rowSum; also colSum
89+
during process: add up n*colorValue.
90+
if row, minus rowSum
91+
if col, minus colSum
92+
*/
93+
public class Solution {
94+
class Cell {
95+
int x;
96+
boolean isRow;
97+
long value;
98+
public Cell(String s) {
99+
String[] ss = s.split(" ");
100+
this.isRow = ss[0].charAt(0) == 'R';
101+
this.x = Integer.parseInt(ss[1]);
102+
this.value = Long.parseLong(ss[2]);
103+
}
104+
}
105+
public static void main(String[] args) {
106+
Solution sol = new Solution();
107+
108+
Scanner in = new Scanner(System.in);
109+
String[] ss = in.nextLine().split(" ");
110+
int N = Integer.parseInt(ss[0]);
111+
int P = Integer.parseInt(ss[1]);
112+
113+
//Storage
114+
HashMap<String, Cell> map = new HashMap<String, Cell>();
115+
ArrayList<Cell> list = new ArrayList<Cell>();
116+
117+
while (P != 0) {//O(P)
118+
//create Cell
119+
String s = in.nextLine();
120+
Cell cell = sol.new Cell(s);
121+
//add into list
122+
list.add(cell);
123+
//Check if cell exist in map.
124+
//if exist in map, replace it with current cell, and remove old cell from list
125+
String key = s.substring(0, s.lastIndexOf(" "));
126+
if (!map.containsKey(key)) {
127+
map.put(key, cell);
128+
} else {
129+
Cell oldCell = map.get(key);
130+
map.put(key, cell);
131+
list.remove(oldCell);
132+
}
133+
P--;
134+
}
135+
136+
//Process final results
137+
int sumCol = 0;
138+
int sumRow = 0;
139+
long sum = 0;
140+
for (int i = 0; i < list.size(); i++) {//O(P)
141+
Cell cell = list.get(i);
142+
sum += cell.value * N;
143+
if (cell.isRow) {
144+
sum -= sumCol;
145+
sumRow += cell.value;
146+
} else {
147+
sum -= sumRow;
148+
sumCol += cell.value;
149+
}
150+
}
151+
152+
System.out.println(sum);
153+
}
154+
}
155+
```

0 commit comments

Comments
 (0)