这次双周赛有意外，第二第三题按照提示返回int[]会报错，要返回List
第一题
给你一个字符串 S，返回只含 单一字母 的子串个数。
示例 1：
输入： “aaaba”
输出： 8
解释：
只含单一字母的子串分别是 “aaa”， “aa”， “a”， “b”。
“aaa” 出现 1 次。
“aa” 出现 2 次。
“a” 出现 4 次。
“b” 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。
public int countLetters(String S) {
if (S.length() == 0) {
return 0;
}
char[] cs = S.toCharArray();
char cc = cs[0];
int k = 1;
int ans = 0;
for (int i = 1; i < cs.length; i++) {
char c = cs[i];
if (c == cc) {
k++;
} else {
cc = c;
ans += getAns(k);
k = 1;
}
}
ans += getAns(k);
return ans;
}
private int getAns(int k) {
return k*(k+1)/2;
}
第二题
给你一个「短语」列表 phrases，请你帮忙按规则生成拼接后的「新短语」列表。
「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。
「前后拼接」（Before and After puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，第一个短语的最后一个单词 和 第二个短语的第一个单词 必须相同。
返回每两个「短语」 phrases[i] 和 phrases[j]（i != j）进行「前后拼接」得到的「新短语」。
注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。
请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 不重复的 。
示例 1：
输入：phrases = [“writing code”,“code rocks”]
输出：[“writing code rocks”]
示例 2：
输入：phrases = [“mission statement”,
“a quick bite to eat”,
“a chip off the old block”,
“chocolate bar”,
“mission impossible”,
“a man on a mission”,
“block party”,
“eat my words”,
“bar of soap”]
输出：[“a chip off the old block party”,
“a man on a mission impossible”,
“a man on a mission statement”,
“a quick bite to eat my words”,
“chocolate bar of soap”]
public List<String> beforeAndAfterPuzzles(String[] phrases) {
Map<String, List<Integer>> topMap = new HashMap<>();
Map<String, List<Integer>> endMap = new HashMap<>();
Set<String> ans = new HashSet<String>();
String[][] res = new String[phrases.length][];
for (int i = 0; i < phrases.length; i++) {
String s = phrases[i];
String[] ss = s.split(" ");
res[i] = ss;
List<Integer> topList = topMap.get(ss[0]);
if (topList == null) {
topList = new ArrayList<Integer>();
topMap.put(ss[0], topList);
}
topList.add(i);
List<Integer> endList = endMap.get(ss[ss.length - 1]);
if (endList == null) {
endList = new ArrayList<Integer>();
endMap.put(ss[ss.length - 1], endList);
}
endList.add(i);
}
for (String topKey : topMap.keySet()) {
List<Integer> endList = endMap.get(topKey);
if (endList == null) {
continue;
}
List<Integer> topList = topMap.get(topKey);
for (Integer top : topList) {
for (Integer end : endList) {
if (top == end) {
continue;
}
ans.add(getRes(res[end], res[top]));
}
}
}
List<String> ree = new ArrayList<String>(ans);
ree.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o1.compareTo(o2);
}
});
return ree;
}
private String getRes(String[] res, String[] res2) {
String ans = "";
for (int i = 0; i < res.length - 1; i++) {
ans += " " + res[i];
}
for (int i = 0; i < res2.length; i++) {
ans += " " + res2[i];
}
return ans.substring(1);
}
第三题
给你一个数组 colors，里面有 1、2、 3 三种颜色。
我们需要在 colors 上进行一些查询操作 queries，其中每个待查项都由两个整数 i 和 c 组成。
现在请你帮忙设计一个算法，查找从索引 i 到具有目标颜色 c 的元素之间的最短距离。
如果不存在解决方案，请返回 -1。
示例 1：
输入：colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
输出：[3,0,3]
解释：
距离索引 1 最近的颜色 3 位于索引 4（距离为 3）。
距离索引 2 最近的颜色 2 就是它自己（距离为 0）。
距离索引 6 最近的颜色 1 位于索引 3（距离为 3）。
这道题其实就是左右各找一次，找到短的那个
public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
List<Integer> ans = new ArrayList<Integer>();
int coLen = colors.length;
int[][] left = new int[3][coLen];
int[][] right = new int[3][coLen];
int[] len = new int[3];
len[0] = 100000;
len[1] = 100000;
len[2] = 100000;
for (int i = 0; i < coLen; i++) {
len[colors[i]%3] = 0;
len[(colors[i] + 1) % 3]++;
len[(colors[i] + 2) % 3]++;
left[0][i] = len[0];
left[1][i] = len[1];
left[2][i] = len[2];
}
len[0] = 100000;
len[1] = 100000;
len[2] = 100000;
for (int i = coLen - 1; i >= 0; i--) {
len[colors[i]%3] = 0;
len[(colors[i] + 1) % 3]++;
len[(colors[i] + 2) % 3]++;
right[0][i] = Math.min(len[0], left[0][i]);
right[1][i] = Math.min(len[1], left[1][i]);
right[2][i] = Math.min(len[2], left[2][i]);
}
for (int i = 0; i < queries.length; i++) {
int key = queries[i][0];
int v = queries[i][1]%3;
ans.add(right[v][key] >= 100000 ? -1 : right[v][key]);
}
return ans;
}
第四题
现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。
而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。
请你设计一个算法，计算矩阵中最多可以有多少个 1。
示例 1：
输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 33 的矩阵中，每一个 22 的子阵中的 1 的数目不超过 1 个。
最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
[1,0,1]
[0,0,0]
[1,0,1]
示例 2：
输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
输出：6
解释：
[1,0,1]
[1,0,1]
[1,0,1]
提示：
1 <= width, height <= 100
1 <= sideLength <= width, height
0 <= maxOnes <= sideLength * sideLength
这道题你要理解1填的位置的优先顺序，然后就知道怎么做了
每个sideLength * sideLength的格子，1的方位应该一致
public int maximumNumberOfOnes(int width, int height, int sideLength,
int maxOnes) {
int wYu = width % sideLength;
int hYu = height % sideLength;
int wN = width / sideLength;
int hN = height / sideLength;
int ans = wN * hN * maxOnes;
if (maxOnes <= wYu * hYu) {
ans += maxOnes * (wN + hN + 1);
return ans;
}
ans += wYu * hYu;
if (wN >= hN) {
if (maxOnes <= hYu * sideLength) {
return ans + wYu * hYu * hN + maxOnes * wN;
} else if (((maxOnes - hYu * sideLength) + wYu * hYu) <= sideLength
* wYu) {
return ans + hYu * sideLength * wN
+ ((maxOnes - hYu * sideLength) + wYu * hYu) * hN;
} else {
return width * height - wN * hN
* (sideLength * sideLength - maxOnes);
}
} else {
if (maxOnes <= wYu * sideLength) {
return ans + wYu * hYu * wN + maxOnes * hN;
} else if (((maxOnes - wYu * sideLength) + hYu * wYu) <= sideLength
* hYu) {
return ans + wYu * sideLength * hN
+ ((maxOnes - wYu * sideLength) + hYu * wYu) * wN;
} else {
return width * height - hN * wN
* (sideLength * sideLength - maxOnes);
}
}
}
