欢迎大家加QQ群：623375442，可以方便群里面交流。
100352. Lexicographically Smallest String After a Swap
给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。
如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。
测试样例：
输入：s = "45320"
输出："43520"
解释：
s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。
解答：只能交换一次有相同奇偶性的数字，目标又是字典序最小。那么就是从头到尾遍历。寻找第一对相邻数字，且前数大于后数。
class Solution {
public String getSmallestString(String s) {
int[] arr = new int[s.length()];
for (int i = 0; i < arr.length; ++i) {
arr[i] = s.charAt(i) - '0';
}
for (int i = 1; i < arr.length; ++i) {
if (arr[i] % 2 == arr[i - 1] % 2 && arr[i] < arr[i - 1]) {
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
break;
}
}
StringBuilder res = new StringBuilder();
for (int n : arr) {
res.append(n);
}
return res.toString();
}
}100368. Delete Nodes From Linked List Present in Array
给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。
测试样例：
输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：移除数值为 1, 2 和 3 的节点。
解答：把nums变成一个HashSet，然后遍历链表，把所有出现在HashSet中的数字去掉就行了。
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
Set<Integer> set = new HashSet<>();
for (int n : nums) {
set.add(n);
}
ListNode res = new ListNode(0), cur = res;
while (head != null) {
if (!set.contains(head.val)) {
cur.next = head;
cur = cur.next;
}
head = head.next;
}
cur.next = null;
return res.next;
}
}100367. Minimum Cost for Cutting Cake II
有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。
给你整数 m ，n 和两个数组：
- horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
- verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：
- 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
- 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销，并且不会改变。
请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
测试样例：
输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出：13
解释：
- 沿着垂直线 0 切开蛋糕，开销为 5 。
- 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
- 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
- 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
- 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
解答：第三题和第四题是一样的，我就放第四题的答案了。这题是一道脑筋急转弯。重点是：如果进行一次垂直切，那么所有水平切分次数+1，反之就是垂直切次数+1。如果要总开销最小，那么就需要确保开销高的切分尽早完成（越晚次数就越多）。
class Solution {
public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
long horizontalCutCount = 1, verticalCutCount = 1;
long res = 0;
Integer[] horizontalSort = sortByIndex(horizontalCut), verticalSort = sortByIndex(verticalCut);
int l1 = 0, l2 = 0;
while (l1 < horizontalSort.length && l2 < verticalSort.length) {
if (horizontalCut[horizontalSort[l1]] > verticalCut[verticalSort[l2]]) {
res += horizontalCutCount * horizontalCut[horizontalSort[l1++]];
verticalCutCount++;
} else {
res += verticalCutCount * verticalCut[verticalSort[l2++]];
horizontalCutCount++;
}
}
while (l1 < horizontalSort.length) {
res += horizontalCutCount * horizontalCut[horizontalSort[l1++]];
}
while (l2 < verticalSort.length) {
res += verticalCutCount * verticalCut[verticalSort[l2++]];
}
return res;
}
private Integer[] sortByIndex(int[] arr) {
Integer[] sort = new Integer[arr.length];
for (int i = 0; i < arr.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (Integer.compare(arr[b], arr[a])));
return sort;
}
}