| Level 1 | Level 2 | Level 3 | |
|---|---|---|---|
| Div 1 | Level 2 | Level 3 | |
| Div 2 | Level 3 |
Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
Source Code:
Division One - Level One:
Solution
Generally, this problem asks to connect character in the palindrome place. For instance, string "abcde", then, 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'c'. By default, any English character will group with itself. For another example, string "abcbde", 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'b', while 'b' and 'd' are in the same group, then 'b', 'c', 'd' are in the same group, so we have two groups, [a,e] and [b,c,d].So, for this problem, we will count the number of changes from non-maximum characters to the maximum count character for each group.
So, for the first step, grouping each English character is implemented by three different methods.
getmin2 uses Flood Fill (DFS). O(N), N is the length of String S.
getmin3 uses Floyd–Warshall algorithm. O(26^3)
getmin uses Union-Find data structure with Path Compression. Time Complexity: < O(N)
So, for N <= 50, it looks like the getmin function is the fastest one.
Source Code:
public class GooseTattarrattatDiv1 {
private int[] count;
private boolean[] notVisited;
public int getmin2(String S) {
count = new int[26];
int min = S.length();
int N = S.length();
notVisited = new boolean[26];
for (int i = 0; i < N; i++) {
int a = S.charAt(i) - 'a';
count[a]++;
notVisited[a] = true;
}
for (int i = 0; i < N; i++) {
min -= dfs(S.charAt(i), S);
}
return min;
}
/**
* Find the maximum number of characters connect to c in s; It's like a
* chain. We need to find the node in the chain with maximum cost; The
* algorithm here is like Flood Fill;
* */
private int dfs(char c, String s) {
if (notVisited[c - 'a'] == false)
return 0;
int max = count[c - 'a'];
notVisited[c - 'a'] = false;
for (int i = 0; i < s.length(); i++) {
if (c == s.charAt(i))
max = Math.max(max, dfs(s.charAt(s.length() - 1 - i), s));
}
return max;
}
/**
* Floyd–Warshall algorithm
* Finding all the connectivity for all the characters from 'a' to 'z'.
* Then, find the maximum and total characters for each group (subgraph),
* make all the rest of characters change to the character holds the
* maximum, Thus, it costs (total - maximum);
* */
public int getmin3(String s) {
int N = s.length();
int[] counter = new int[26];
boolean[][] connected = new boolean[26][26];
for (int i = 0; i < N; i++) {
counter[s.charAt(i) - 'a']++;
}
for (int i = 0; i < N - i; i++) {
int a = s.charAt(i) - 'a';
int b = s.charAt(N - i - 1) - 'a';
connected[a][b] = true;
connected[b][a] = true;
}
for (int i = 0; i < 26; i++)
connected[i][i] = true;
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
connected[i][j] |= connected[i][k] && connected[k][j];
}
}
}
int ret = 0;
for (int i = 0; i < N; i++) {
if (counter[s.charAt(i) - 'a'] <= 0)
continue;
int total = 0;
int max = 0;
for (int j = 0; j < 26; j++) {
if (connected[s.charAt(i) - 'a'][j]) {
total += counter[j];
max = Math.max(max, counter[j]);
counter[j] = 0;
}
}
ret += total - max;
}
return ret;
}
/**
* This problem actually asks to group 'a' - 'z'. Here I use the Union-Find
* data structure to speed this process up;
* */
public int getmin(String S) {
int[] count = new int[26];
for (int i = 0; i < S.length(); i++) {
count[S.charAt(i) - 'a']++;
}
int min = 0;
Union_Find set = new Union_Find(26);
for (int i = 0; i < S.length() - 1 - i; i++) {
set.union(S.charAt(i) - 'a', S.charAt(S.length() - 1 - i) - 'a');
}
for (int i = 0; i < 26; i++) {
int total = 0;
int max = 0;
for (int j = 0; j < 26; j++) {
if (set.find(j) == set.find(i)) {
total += count[j];
max = Math.max(max, count[j]);
count[j] = 0;
}
}
min += total - max;
}
return min;
}
class Union_Find {
public int[] parents;
public Union_Find(int N) {
parents = new int[N];
for (int i = 0; i < N; i++) {
parents[i] = i;
}
}
public int find(int x) {
if (x == parents[x])
return x;
return parents[x] = find(parents[x]);
}
public void union(int x, int y) {
int xx = find(x);
int yy = find(y);
if (xx != yy) {
this.parents[xx] = yy;
}
}
}
}
Sivision Two - Level Three:
Solution
Source Code:
Division Two - Level Two:
Solution
This is a Dynamic Programming problem, people could easily find out the dp state formula for this problem. For every gear, people could choose use it or remove it. So we could either use the current gear or not use current one, which depends on the previous state.For this problem, I tried to find the number of most gears we could use to work, which equals to the problem finds the fewest removal of gears to make it work.
But this problem has one thing requires your attention, which asks you to make this gear string in circular, that means the first and very last one is connected. This brings the challenge, while bringing the convenience for us. We could start at any point in this circular, so we ideally choose the 0th one to start, but we have to remember for every state that if any current state result depends on using the 0th gear or not. Then at last, we need to check if we use the 0th gear for my last state result, when first and last gear direction is the same. If the result depends on it, then we should not use the last gear, otherwise just use it, since it will bring you one more gear to use.
Source Code:
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
public class GearsDiv2 {
public int getmin(String dir) {
int[][] dp = new int[dir.length()][2];
boolean[][] hasFirst = new boolean[dir.length()][2];
dp[0][0] = 0;
dp[0][1] = 1;
hasFirst[0][0] = false;
hasFirst[0][1] = true;
for (int i = 1; i < dir.length(); i++) {
if (dp[i - 1][0] == dp[i - 1][1]) {
hasFirst[i][0] = hasFirst[i - 1][0] && hasFirst[i - 1][1];
dp[i][0] = dp[i - 1][1];
} else if (dp[i - 1][0] > dp[i - 1][1]) {
hasFirst[i][0] = hasFirst[i - 1][0];
dp[i][0] = dp[i - 1][0];
} else {
hasFirst[i][0] = hasFirst[i - 1][1];
dp[i][0] = dp[i - 1][1];
}
// dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
if (dir.charAt(i) != dir.charAt(i - 1)) {
dp[i][1] = 1 + dp[i][0];
hasFirst[i][1] = hasFirst[i][0];
} else {
dp[i][1] = dp[i - 1][0] + 1;
hasFirst[i][1] = hasFirst[i - 1][0];
}
}
// return dir.length() - Math.max(dp[dir.length()-1][0],
// dp[dir.length()-1][1]);
if (dir.charAt(dir.length() - 1) != dir.charAt(0)) {
return dir.length()
- Math.max(dp[dir.length() - 1][0], dp[dir.length() - 1][1]);
} else {
if (hasFirst[dir.length() - 1][1]) {
return dir.length() - dp[dir.length() - 1][0];
} else {
return dir.length() - dp[dir.length() - 1][1];
}
}
}
// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
The second solution comes from TC tutorial. The two key ideas of this recursion solution are:
1, Don't be trapped by this circular requirement, for the first and last gears, we only have four possibilities, we keep them both, keep first, keep last and remove them both. Since we are using a recursion to solve this problem, the 4th possibility will come through one of 2nd and 3rd case, since remove one, we could possibly remove the other later. This way, we could get rid of circular trap and treat the new string as a linear problem.
2, In the linear problem, when two adjacent gears are the same, we have to remove one of them, here we absolutely remove the second one. Further detail reason, check out the link.
public class GearsDiv2 {
public int getmin(String dir) {
int N = dir.length();
int ret = N - 1;
if (dir.charAt(0) != dir.charAt(N - 1))
ret = Math.min(ret, getminLinear(dir));
ret = Math.min(ret, 1 + getminLinear(dir.substring(1)));
ret = Math.min(ret, 1 + getminLinear(dir.substring(0, N - 1)));
return ret;
}
private int getminLinear(String dir) {
if (dir.length() < 2)
return 0;
// change the second one to '_'
if (dir.charAt(0) == dir.charAt(1)) {
return 1 + getminLinear(dir.substring(2));
}
return getminLinear(dir.substring(1));
}
}
Division Two - Level One:
Solution
Source Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.*; import java.util.regex.*; import java.text.*; import java.math.*; import java.awt.geom.*; public class GooseTattarrattatDiv2 { public int getmin(String s) { int[] count = new int[26]; int max = 0; int index = -1; for(int i=0; i<s.length(); i++){ count[s.charAt(i)-'a']++; if(max < count[s.charAt(i)-'a']) { max = count[s.charAt(i)-'a']; index = s.charAt(i)-'a'; } } int ret = 0; for(int i=0; i<26; i++){ if(count[i] > 0 && i != index){ ret += count[i]; } } return ret; } } //Powered by [KawigiEdit] 2.0! |
