今天早上做Twitch的在线笔试，还是经验不够丰富，这道题其实可以把问题拆分开来。这样就会让思路清晰很多。这道题有三个input， int min_cheermote_amount, String[] valid_cheermotes, String messages。 min_cheermote_amount 就是一个最小值，只要一个messages里面有个string 根valid_cheermotes里面的一个string一样，并且尾端数字大于等于这个min_cheermote_amount 就可以计入输出。输出值就是从大到小排好序的cheermote string[]。没有match的就输出“NO_CHEERS”
下面是例子和testcase
输入：1, cheer, roo100 big1000
输出：NO_CHEERS
1, [cheer], "this is just a normal message and also cheer100 cheer100"
cheer200
1, [cheer], "this is just a normal message,look at me"
NO_CHEERS
1, [cheer,party,rainbow], "cheer1 cheer2, cheer4, party100 cheer1"
party100,cheer8
1, [cheer,party], "cheer1 cheer2, cheer4,party100 cheer1"
party100,cheer8
1, [cheer], "cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer1, cheer4"
cheer4
1, [cheer], "cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000 cheer10000, cheer4"
cheer100004
1, [cheer], "cheer1 cheer10001, cheer4"
cheer4
1, [cheer], "cheer1 cheer10000, cheer4"
cheer10005
3, [cheer], "cheer1 cheer2,cheer4"
cheer4
1, [party], "cheer1"
NO_CHEERS
1, [cheer], "cheer1 cheer2,cheer4"
cheer7
其实我思路是没问题的，但是中间写代码的时候就因为一层层for loop的嵌套导致自己思路不清晰，然后把自己绕进去了。因为你把整个messages通过逗号分成一个String array的时候就应该新建一个hashmap counter，但是你却放进了第二个for loop里面（应该在第二个for loop外面的）这样实际上你break之后还是把一些invalid的情况算进了结果里面，所以有很多testcase过不了。
其实最好的解决办法就是问题的拆分，你一开始实际上就是拆分开来做的，只不过你只是检查了是否valid，实际上返回一个map就可以了，map如果是空就不计入结果里面。这样就不用写三层嵌套了。把第二个和第三个for loop分别拆分成两个函数就可以了。
下面是做完之后自己debug之后的代码：
public static String[] solution(int min_cheermote_amount, String[] valid_cheermotes, String messages) {
// Please write your code here.
Map<String, Integer> totalCount = new HashMap<>();
String[] split = messages.split(",");
for (int i = 0; i < split.length; i++) {
String[] curStrings = split[i].split("\\s+");
// int[] count = new int[valid_cheermotes.length];
Map<String, Integer> currentCount = new HashMap<>();
for (int j = 0; j < curStrings.length; j++) {
String curStr = curStrings[j];
// increase the current message cheers count, return empty tree if there is a invalid cheermote amount
for (int k = 0; k < valid_cheermotes.length; k++) {
String cheerStr = valid_cheermotes[k];
if (curStr.length() <= cheerStr.length()) {
continue;
}
String str = curStr.substring(0, cheerStr.length());
// System.out.println(str);
// System.out.println(curStr.substring(cheerStr.length(), curStr.length()));
int cheermote = -1;
try {
cheermote = Integer.parseInt(curStr.substring(cheerStr.length(), curStr.length()));
} catch (NumberFormatException e) {
}
// System.out.println(cheermote);
if (str.equals(cheerStr) && cheermote >= min_cheermote_amount && cheermote <= 100000) {
currentCount.put(str, currentCount.getOrDefault(str, 0) + cheermote);
// check if it is greater than 100,000
if (cheermote < min_cheermote_amount || currentCount.get(str) > 100000) {
currentCount = null;
break;
}
}
}
if (currentCount == null) {
break;
}
}
// update total count
if (currentCount != null) {
for (Map.Entry<String, Integer> pair: currentCount.entrySet()) {
totalCount.put(pair.getKey(), totalCount.getOrDefault(pair.getKey(), 0) + pair.getValue());
System.out.println(totalCount.get(pair.getKey()));
}
}
}
// maxHeap to keep the most number of bits used
Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
pq.addAll(totalCount.entrySet());
List<String> res = new ArrayList<>();
while (!pq.isEmpty()) {
Map.Entry<String, Integer> pair = pq.poll();
res.add(pair.getKey() + pair.getValue());
}
String[] result = new String[res.size()];
if (res.size() == 0) {
return new String[] {"NO_CHEERS"};
} else {
for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i);
}
return result;
}
}
下面是拆分之后的代码，可以明显看到拆分之后的思路更加清晰并且易懂：
public static String[] solution(int min_cheermote_amount, String[] valid_cheermotes, String messages) {
// Please write your code here.
Map<String, Integer> totalCount = new HashMap<>();
String[] split = messages.split(",");
for (int i = 0; i < split.length; i++) {
String[] curStrings = split[i].split("\\s+");
// int[] count = new int[valid_cheermotes.length];
Map<String, Integer> currentCount = new HashMap<>();
currentCount = currentMessageCount(min_cheermote_amount, valid_cheermotes, curStrings, new HashMap<String, Integer>());
// update total count
if (currentCount != null) {
for (Map.Entry<String, Integer> pair: currentCount.entrySet()) {
totalCount.put(pair.getKey(), totalCount.getOrDefault(pair.getKey(), 0) + pair.getValue());
System.out.println(totalCount.get(pair.getKey()));
}
}
}
// maxHeap to keep the most number of bits used
Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
pq.addAll(totalCount.entrySet());
List<String> res = new ArrayList<>();
while (!pq.isEmpty()) {
Map.Entry<String, Integer> pair = pq.poll();
res.add(pair.getKey() + pair.getValue());
}
String[] result = new String[res.size()];
if (res.size() == 0) {
return new String[] {"NO_CHEERS"};
} else {
for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i);
}
return result;
}
}
private static Map<String, Integer> currentMessageCount(int min_cheermote_amount, String[] valid_cheermotes, String[] curStrings, Map<String, Integer> currentCount) {
for (int j = 0; j < curStrings.length; j++) {
String curStr = curStrings[j];
// increase the current message cheers count, return empty tree if there is a invalid cheermote amount
for (int k = 0; k < valid_cheermotes.length; k++) {
String cheerStr = valid_cheermotes[k];
if (curStr.length() <= cheerStr.length()) {
continue;
}
String str = curStr.substring(0, cheerStr.length());
// System.out.println(str);
// System.out.println(curStr.substring(cheerStr.length(), curStr.length()));
int cheermote = -1;
try {
cheermote = Integer.parseInt(curStr.substring(cheerStr.length(), curStr.length()));
} catch (NumberFormatException e) {
}
// System.out.println(cheermote);
if (str.equals(cheerStr) && cheermote >= min_cheermote_amount && cheermote <= 100000) {
currentCount.put(str, currentCount.getOrDefault(str, 0) + cheermote);
// check if it is greater than 100,000
if (cheermote < min_cheermote_amount || currentCount.get(str) > 100000) {
currentCount = null;
break;
}
}
}
if (currentCount == null) {
break;
}
}
return currentCount;
}
网友评论