LeetCode Contest 406

欢迎大家加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 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
2. 沿着垂直线 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;
    }
}