目前只做Difficulty=Medium的题，之前做的就不写了，就从镇楼这个开始
https://www.hackerrank.com/challenges/organizing-containers-of-balls/problem

比较简单的一题，题目大意是有n种球和n个盒子，然后给你一个n*n的矩阵，矩阵里面是这n种球在n个盒子中的排布状况。
如：
3，3，4
2，2，3
1，1，1
表示：
在一号盒有3个一号球，3个二号球，4个三号球
在二号盒有2个一号球，2个二号球，3个三号球
在三号盒有1个一号球，1个二号球，1个三号球
问的问题是：在每次【交换】一个球的情况下，能不能最后出现这样一个场景：每个盒子里都有且仅有一种球。
…………………………………………………………………………………………
看上去贼复杂，其实稍微一想就贼简单了，由于球只能【交换】，所以最后每个盒子里的球【数量不会变化】
如果要达成最后的场景，那么初始状态的【每个盒子的球数】和【每种球的数量】必须是一一对应的关系。
充分性的证明从略。
按照这个思路做，代码就很简单了，把矩阵的横排加起来得到n个数，再把矩阵竖排加起来得到n个数，看看这些数是否一一对应即可。
……………………………………………………………………
代码如下：
static String organizingContainers(int[][] container) {
int n = container.length;
ArrayList<Integer> rowList = new ArrayList<>();
for (int[] is : container) {
int x = sum(is);
rowList.add(x);
}
while (--n >= 0) {
int sum = 0;
for (int[] is : container) {
sum += is[n];
}
boolean hasSum = rowList.remove((Integer) sum);
if (!hasSum) {
return "Impossible";
}
}
return "Possible";
}
private static int sum(int[] is) {
int count = 0;
for (int i : is) {
count += i;
}
return count;
}

https://www.hackerrank.com/challenges/encryption/problem
贼简单一题 贴代码走人：
static String encryption(String s) {
int len = s.length();
if (len <= 1) {
return s;
}
int row = (int) Math.sqrt(len - 1) + 1;
String retVal = "";
for (int i = 0; i < row ; i++) {
int x = i;
while (x < len) {
retVal = retVal + s.charAt(x);
x += row;
}
retVal = retVal + " ";
}
return retVal;
}

矩阵匹配
https://www.hackerrank.com/challenges/the-grid-search/problem

矩阵匹配这道题看上去比较简单，但情况比较多
题目大意是：
有一个大矩阵，如：
1234
4333
1234
3333
还有一个小矩阵
12
33
问大矩阵里面是否包含小矩阵
这里面基础思路是：
逐行匹配，先在大矩阵每一行里面找小矩阵第一行，找到之后去下一行找小矩阵第二行，如果起始位置相同，就继续找下一行，直到小矩阵找完，就匹配到了。
这里面最大的问题是，同一行可能会出现多个匹配到的起始位置。
如大矩阵是
1333
1122
小矩阵是
33
22
在第一行找到33之后，去第二行找到22，但是发现起始位置不同。这个时候应该需要回到第一次发现33的地方，发现这一行还有个33，然后继续匹配就成功了。
还有一种场景类似，
如大矩阵是
1133
1222
小矩阵是
33
22
也是需要把当前行匹配完的。
实际上，当第一行的位置确定之后，后面就不再需要匹配了，直接去看对应位置的字符是否正确即可。
……………………………………
static String gridSearch(String[] G, String[] P) {
String first = P[0];
int Pindex = 0;
int gIndex = 0;
int startIndex = 0;
int recordRow = -1;
int recordIndex = -1;
while (gIndex < G.length) {
String string = G[gIndex];
int index = string.indexOf(first, startIndex);
System.out.println("gIndex = " + gIndex);
System.out.println("startIndex = " + startIndex);
System.out.println("index = " + index);
System.out.println("recordRow = " + recordRow);
System.out.println("Pindex = " + Pindex);
if (index > -1 && (recordRow == -1 || string.substring(recordIndex - 1, recordIndex - 1 + first.length()).equals(first))) {
//find, try to match next line
if (Pindex >= P.length - 1) {
return "YES";
}
if (recordRow == -1) {
//no record , record row and index to back
recordIndex = index + 1;
recordRow = gIndex;
}
gIndex ++;
startIndex = 0;
Pindex ++;
first = P[Pindex];
} else {
//not match, reset P and try to match next in first same line
if (recordRow > -1) {
startIndex = recordIndex;
gIndex = recordRow;
recordIndex = -1;
recordRow = -1;
} else {
startIndex = 0;
gIndex ++;
}
first = P[0];
Pindex = 0;
}
}
return "NO";
}

https://www.hackerrank.com/challenges/bomber-man/problem

除了扣6，无以言表

接7楼的题
这题大意：起始摆一拨炸弹，偶数秒填满，奇数秒引爆上上次放置的炸弹，炸弹不会连锁引爆。然后问N秒之后炸弹的排布情况。
这题有几个规律：
1.如果N=1 那么就是初始状态
2.如果N为偶数，那么是全满状态
3.N=3和N=5可以递推出来
4.N=4n+3的时候，和N=3相同，N=4n+1的时候，和N=5相同。
这样这题就很简单了。
……………………………………………………………………………………………………
static String[] bomberMan(int n, String[] grid) {
String[] retVal = grid;
if (n % 2 == 0) {
retVal = fill(retVal);
return retVal;
}
int x = n / 2;
if (x == 0) {
return retVal;
}
x = (x % 2 == 0) ? 2 : 1;
while (x > 0) {
grid = getOppset(grid);
x --;
}
return grid;
}
private static String[] fill(String[] retVal) {
String[] ret = new String[retVal.length];
for (int i = 0; i < retVal.length; i++) {
ret[i] = retVal[i].replaceAll(".", "O");
}
return ret;
}
private static String[] getOppset(String[] origin) {
String[] ret = new String[origin.length];
for (int i = 0; i < origin.length; i++) {
String string = origin[i];
String newString = "";
for (int j = 0; j < string.length(); j++) {
if (string.charAt(j) == 'O'
|| (j + 1 < string.length() && string.charAt(j + 1) == 'O')
|| (j - 1 >= 0 && string.charAt(j - 1) == 'O')
|| (i + 1 < origin.length && origin[i + 1].charAt(j) == 'O')
|| (i - 1 >= 0 && origin[i - 1].charAt(j) == 'O')
) {
newString += '.';
} else {
newString += 'O';
}
}
ret[i] = newString;
}
return ret;
}

https://www.hackerrank.com/challenges/two-pluses/problem

一次过
大概思路是，遍历所有十字，确定这个十字之后，把这个十字占领的格子染红，然后在剩下的格子里面找个最大的十字，然后算乘积。 这样遍历一遍之后找到最大的乘积即可
……………………………………………………………………………………………………
static int twoPluses(String[] grid) {
int maxPlus = 0;
int temp = 0;
for (int i = 0; i < grid.length; i++) {
String string = grid[i];
for (int j = 0; j < string.length(); j++) {
char x = string.charAt(j);
if (x == 'G') {
temp = 1;
int index = 1;
String[] tempStrings = makeBad(grid, i, j);
int other = findMax(tempStrings);
if (temp * other > maxPlus) {
maxPlus = temp * other;
}
while ((j + index < string.length() && string.charAt(j + index) == 'G')
&& (j - index >= 0 && string.charAt(j - index) == 'G')
&& (i + index < grid.length && grid[i + index].charAt(j) == 'G')
&& (i - index >= 0 && grid[i - index].charAt(j) == 'G')
) {
temp += 4;
tempStrings = makeBad(tempStrings, i + index, j);
tempStrings = makeBad(tempStrings, i - index, j);
tempStrings = makeBad(tempStrings, i , j + index);
tempStrings = makeBad(tempStrings, i , j - index);
other = findMax(tempStrings);
if (temp * other > maxPlus) {
maxPlus = temp * other;
}
index ++;
}
temp = 0;
} else {
continue;
}
}
}
return maxPlus;
}
private static String[] makeBad(String[] grid, int x, int y) {
String[] ret = new String[grid.length];
for (int i = 0; i < grid.length ; i ++) {
String string = grid[i];
String s = "";
for (int j = 0; j < string.length(); j ++) {
char f = string.charAt(j);
if (i == x && j == y) {
s = s + 'B';
} else {
s = s + string.charAt(j);
}
}
ret[i] = s;
}
return ret;
}
static int findMax(String[] grid) {
int maxPlus = 0;
int temp = 0;
for (int i = 0; i < grid.length ; i ++) {
String string = grid[i];
for (int j = 0; j < string.length(); j ++) {
char x = string.charAt(j);
if (x == 'G') {
temp = 1;
int index = 1;
while ((j + index < string.length() && string.charAt(j + index) == 'G')
&& (j - index >= 0 && string.charAt(j - index) == 'G')
&& (i + index < grid.length && grid[i + index].charAt(j) == 'G')
&& (i - index >= 0 && grid[i - index].charAt(j) == 'G')
) {
temp += 4;
index ++;
}
if (maxPlus < temp) {
maxPlus = temp;
}
temp = 0;
} else {
continue;
}
}
}
return maxPlus;
}

https://www.hackerrank.com/challenges/lilys-homework/problem

题目不算难，大意：
给一个数组，如{3，2，1，4}，要换成完全顺序的数组，最少需要【交换】几次。
比如上面那个数组，交换1和3之后，就会换成{1,2,3,4}，就可以成立。所以最小次数=1
这题是一个很常见的数字排序题，百度了一下就有结论：https://blog.csdn.net/yg_hou/article/details/85177414
如果使用普遍的交换方法，时间不够，所以需要使用循环节的方法。不同的是，需要自己处理降序的二分法查找，copy代码出来稍微改改就可以。
…………………………………………………………………………………………………………
static int lilysHomework(int[] arr) {
int[] target1 = sort(arr);
int lily1 = checkswap(target1, arr);
int[] target2 = new int[arr.length];
for (int i = 0; i < target1.length; i++) {
target2[i] = target1[target1.length - 1 - i];
}
int lily2 = checkswap2(target2, arr);
return Math.min(lily1, lily2);
}
static int checkswap(int[] target, int[] origin) {
int count = 0;
int[] copy = copy(origin);
boolean[] flag = new boolean[origin.length];
for (int i = 0; i < flag.length; i++) {
flag[i] = false;
}
for (int i = 0; i < copy.length; i ++) {
if (!flag[i]) {
int j = i;
while (!flag[j]) {
flag[j] = true;
j = Arrays.binarySearch(target, copy[j]);
}
count ++;
}
}
return copy.length - count;
}
static int checkswap2(int[] target, int[] origin) {
int count = 0;
int[] copy = copy(origin);
boolean[] flag = new boolean[origin.length];
for (int i = 0; i < flag.length; i++) {
flag[i] = false;
}
for (int i = 0; i < copy.length; i ++) {
if (!flag[i]) {
int j = i;
while (!flag[j]) {
flag[j] = true;
j = binarySearch0(target, 0, target.length, copy[j]);
}
count ++;
}
}
return copy.length - count;
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal > key)
low = mid + 1;
else if (midVal < key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
static int[] sort(int[] arr) {
int[] copy = copy(arr);
Arrays.sort(copy);
return copy;
}
static int[] sort2(int[] arr) {
int[] copy = copy(arr);
Arrays.sort(copy);
int[] ret = new int[arr.length];
for (int i = 0; i < ret.length; i++) {
ret[i] = copy[ret.length - 1 - i];
}
return ret;
}
static int[] copy(int[] arr) {
int[] x = Arrays.copyOf(arr, arr.length);
return x;
}

题目被吃了？
https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem

本题大意：
给一个数组和一个数字 如{1,2,3,4,4,7}和4。
首先算出前四个数字（{1,2,3,4}）的中位数的两倍，如果第五个数字(4)大于他，则计数+1。然后再比较下四个数字({2,3,4,4})和下一个数（7）。以此类推，最后给出计数的数量即可。
* 中位数逻辑，如果数组元素数量为奇数，则为排序后最中间的数，如果是偶数，则是最中间两个数的均值。
如{3，1，2，1}的中位数是1.5，{2,3,4,3,2}的中位数是3
……………………………………………………
这题正常计算比较简单，但是正常的计算方法都会超时。
最正常的算法：
先求出中位数，然后一直比较即可。但是我们看数据大小：

最差的情况，n = 10^5 d=10^5，计算中位数算法的复杂度为O(n)~O(nlogn)之间，就算用最好的O(n)方法，时间也达到了n*d = 10^10，会直接超时（一般的算法超过10^8 即一亿 就会超时）
但是看了一下数据的特点，所有的数值都在0~200之间，在n很大的时候，大部分的数值都是重复的。
所以用map储存各个元素数量的方法就出现了，即记录每个元素出现过多少次，这样计算中位数就很方便了。
如我们需要找{2,2,2,1,3,2,2}的中位数，我们只需要记下来这里面有1个1，5个2，1个3，这样就可以不用排序很容易的算出中位数了。
另外用这种方式储存时，当计算下一个中位数的时候，由于大部分元素没有变，只是移除了开头一个元素，加入了后面一个元素。所以计数也非常简单。（如{1,2,3,4,4,7}和4，第一个需要算中位数的数组是{1,2,3,4}，第二个是{2，3，4，4},只需要移除一个1加进来一个4即可，很方便计数）
这么一拨操作之后，时间复杂度就够用了。
……………………………………………………………………………………………………
static int activityNotifications(int[] expenditure, int d) {
int len = expenditure.length;
if (len == d) {
return 0;
}
int count = 0;
for (int i = d; i < len ; i ++) {
if (i == d) {
initMap(Arrays.copyOfRange(expenditure, 0, i));
} else {
move(expenditure[i - d - 1], expenditure[i - 1]);
}
int mid = get2Mid(d);
if (expenditure[i] >= mid) {
count ++;
}
}
return count;
}
private static void initMap(int[] copyOfRange) {
for (int i : copyOfRange) {
if (temps.containsKey(i)) {
temps.put(i, temps.get(i) + 1);
} else {
temps.put(i, 1);
}
}
}
static HashMap<Integer, Integer> temps = new HashMap<>();
private static void move(int moveout, int movein) {
if (temps.containsKey(movein)) {
temps.put(movein, temps.get(movein) + 1);
} else {
temps.put(movein, 1);
}
temps.put(moveout, temps.get(moveout) - 1);
}
static int get2Mid(int total) {
if (total % 2 == 1) {
int target = total / 2 + 1;
int count = 0;
for (int i = 0; i < 201; i++) {
if (temps.containsKey(i)) {
count += temps.get(i);
if (count >=target) {
return i * 2;
}
}
}
} else {
int target1 = total / 2;
int target2 = total / 2 + 1;
int final1 = -1;
int final2 = -1;
int count = 0;
for (int i = 0; i < 201; i++) {
if (temps.containsKey(i)) {
count += temps.get(i);
if (count >= target1 && final1 < 0) {
final1 = i;
}
if (count >= target2) {
final2 = i;
return final1 + final2;
}
}
}
}
return -1;
}