100131. Make Three Strings Equal
给你三个字符串 s1、s2 和 s3。 你可以根据需要对这三个字符串执行以下操作 任意次数 。
在每次操作中，你可以选择其中一个长度至少为 2 的字符串 并删除其 最右位置上 的字符。
如果存在某种方法能够使这三个字符串相等，请返回使它们相等所需的 最小 操作次数；否则，返回 -1。
测试样例：
输入：s1 = "abc"，s2 = "abb"，s3 = "ab"
输出：2
解释：
对 s1 和 s2 进行一次操作后，可以得到三个相等的字符串。
可以证明，不可能用少于两次操作使它们相等。
解答：最长前缀相同的字符串。如果最长前缀为0，需要返回-1.
class Solution {
public int findMinimumOperations(String s1, String s2, String s3) {
String t = common(s1, s2);
t = common(t, s3);
return t.length() == 0 ? -1 : (s1.length() - t.length() + s2.length() - t.length() + s3.length() - t.length());
}
private String common(String s1, String s2) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Math.min(s1.length(), s2.length()); ++i) {
if (s1.charAt(i) == s2.charAt(i)) {
sb.append(s1.charAt(i));
} else {
break;
}
}
return sb.toString();
}
}100122. Separate Black and White Balls
桌子上有 n 个球，每个球的颜色不是黑色，就是白色。
给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。
在每一步中，你可以选择两个相邻的球并交换它们。
返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。
测试样例：
输入：s = "101"
输出：1
解释：
我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。
解答：将所有白球移到左边，记录最左的位置，然后移动白球累和。注意返回的是long，不要用int爆范围了。
class Solution {
public long minimumSteps(String s) {
int white = 0;
long res = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '0') {
res += (i - white);
++white;
}
}
return res;
}
}100119. Maximum Xor Product
给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2n。
由于答案可能会很大，返回它对 10^9 + 7 取余 后的结果。
注意，XOR 是按位异或操作。
测试样例：
输入：a = 12, b = 5, n = 4
输出：98
解释：
当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) (b XOR x) = 98 。
98 是所有满足 0 <= x < 2n 中 (a XOR x) (b XOR x) 的最大值。
解答：这周最恶心的一道题目了。如果a和b在小于n的位数，某一位相同，那么可以通过异或操作同时变成1.问题在于如果不相同怎么办。如果反转(a - c) (b + c) = a b + c * (a - b + c)。那么第一位不同的位数，可以确定之后是否反转。
class Solution {
private static final int mod = 1_000_000_007;
public int maximumXorProduct(long a, long b, int n) {
boolean isA = true, isFirst = true;
for (int i = 49; i >= 0; --i) {
if (i >= n) {
if (isMark(a, i) + isMark(b, i) == 1) {
if (isFirst && isMark(b, i) == 1) {
isA = false;
}
isFirst = false;
}
} else {
if (isMark(a, i) + isMark(b, i) == 0) {
a += (1L << i);
b += (1L << i);
} else if (isMark(a, i) + isMark(b, i) == 1) {
if (isFirst) {
if (isMark(a, i) == 0) {
a += (1L << i);
b -= (1L << i);
}
} else {
if (isA && isMark(a, i) == 1) {
a -= (1L << i);
b += (1L << i);
} else if (!isA && isMark(a, i) == 0) {
a += (1L << i);
b -= (1L << i);
}
}
isFirst = false;
}
}
}
return (int)((a % mod) * (b % mod) % mod);
}
private int isMark(long num, int offset) {
int tmp = (int) ((num >> offset) & 1);
return tmp;
}
}100110. Find Building Where Alice and Bob Can Meet
给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。
请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。
测试样例
输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：
第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
解答：其实感觉这题比第三题简单多了。这道题目利用单调栈和排序就能搞定了。我们将queries按照Math.max(queries[i][0], queries[i][1])降序摆列。然后开始遍历queries，我们利用单调栈维护右侧数组降序排列，每次利用折半搜索就能寻找到最左的位置。
class Solution {
private class Stack {
List<Integer> stack;
int pos;
public Stack() {
stack = new ArrayList<>();
pos = -1;
}
public int peek() {
return stack.get(pos);
}
public void pop() {
--pos;
}
public void push(int x) {
++pos;
if (pos == stack.size()) {
stack.add(x);
} else {
stack.set(pos, x);
}
}
public boolean isEmpty() {
return pos < 0;
}
}
public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
for (int i = 0; i < queries.length; ++i) {
int min = Math.min(queries[i][0], queries[i][1]);
int max = Math.max(queries[i][0], queries[i][1]);
queries[i][0] = min;
queries[i][1] = max;
}
Integer[] sort = new Integer[queries.length];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (queries[b][1] - queries[a][1]));
int pos = heights.length - 1, memPos = -1;
Stack stack = new Stack();
int[] res = new int[queries.length];
for (int i : sort) {
while (pos >= queries[i][1]) {
int h = heights[pos];
while (!stack.isEmpty() && heights[stack.peek()] <= h) {
stack.pop();
}
stack.push(pos);
--pos;
}
if (heights[queries[i][0]] < heights[queries[i][1]] || queries[i][0] == queries[i][1]) {
res[i] = queries[i][1];
} else {
int st = 0, ed = stack.pos;
while (st < ed) {
int mid = (st + ed + 1) / 2;
if (heights[stack.stack.get(mid)] > heights[queries[i][0]]) {
st = mid;
} else {
ed = mid - 1;
}
}
if (heights[stack.stack.get(st)] > heights[queries[i][0]]) {
res[i] = stack.stack.get(st);
} else {
res[i] = -1;
}
}
}
return res;
}
}