关于面试:LeetCode-第-45-场双周赛题解

点击这里能够查看更多算法面试相干内容~

给你一个整数数组 nums。数组中惟一元素是那些只呈现 恰好一次 的元素。

请你返回 nums 中惟一元素的和。

示例 1：

输出：nums = [1,2,3,2]
输入：4
解释：惟一元素为 [1,3]，和为 4。

示例 2：

输出：nums = [1,1,1,1,1]
输入：0
解释：没有惟一元素，和为 0。

示例 3：

输出：nums = [1,2,3,4,5]
输入：15
解释：惟一元素为 [1,2,3,4,5]，和为 15。

提醒：

1 <= nums.length <= 100
1 <= nums[i] <= 100

一道模拟题，间接应用 哈希表 或者数组来存元素呈现次数即可。

对于一些给定了元素数据范畴的题目，倡议应用数据来进行统计，这样对于 Java 语言来说，代码会短些。

对于没有给定元素数据范畴，或者数据范畴很大的，则应用哈希表。

代码：

class Solution {public int sumOfUnique(int[] nums) {int[] cnt = new int[110];
        for (int i : nums) cnt[i]++;
        int ans = 0;
        for (int i = 0; i < 110; i++) {if (cnt[i] == 1) ans += i;
        }
        return ans;
    }
}

工夫复杂度：$O(n)$
空间复杂度：$O(n)$

给你一个整数数组 nums。

一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的和的绝对值为 abs(numsl + numsl+1 + ... + numsr-1 + numsr)。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该最大值。

abs(x) 定义如下：

如果 x 是负整数，那么 abs(x) = -x。
如果 x 是非负整数，那么 abs(x) = x。

示例 1：

输出：nums = [1,-3,2,3,-4]
输入：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5。

示例 2：

输出：nums = [2,-5,1,-4,3,-2]
输入：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8。

提醒：

1 <= nums.length <= 10 ^ 5
-10 ^ 4 <= nums[i] <= 10 ^ 4

题目要咱们求间断一段的子数组的和，很天然就能想到前缀和。

当咱们有了前缀和数组 sum 之后，需要求任意一段子数组 [i,j] 的和能够间接通过 sum[j] - sum[i - 1] 得出。

要使得 abs(sum[j] - sum[i - 1]) 最大，其实有这么几种状况：

找到前缀和数组中的最大值减去最小值，失去一个最大负数（前提是最大值呈现在最小值的前面，并且最小值是个正数，否则应该间接取最大值作为答案）
找到前缀和的最小值减去最大值，失去一个最小正数（前提是最小值呈现在最大值的前面，而且最大值是一个负数，否则间接取最小值作为答案）。

也就是说最终答案只与前缀和数组中的最大值和最小值相干，而且最大值可能会呈现在最小值后面或者前面。

因而咱们能够边循环边做更新答案：

class Solution {public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        
        int max = 0, min = 0, ans = 0;
        for (int i = 1; i <= n; i++) {ans = Math.max(ans, Math.abs(sum[i] - min));
            ans = Math.max(ans, Math.abs(sum[i] - max));
            max = Math.max(max, sum[i]);
            min = Math.min(min, sum[i]);
        }
        return ans;
    }
}

工夫复杂度：$O(n)$
空间复杂度：$O(n)$

给你一个只蕴含字符 'a'，'b' 和 'c' 的字符串 s，

你能够执行上面这个操作（5 个步骤）任意次：

抉择字符串 s 一个非空的前缀，这个前缀的所有字符都雷同
抉择字符串 s 一个非空的后缀，这个后缀的所有字符都雷同
前缀和后缀在字符串中任意地位都不能有交加
前缀和后缀蕴含的所有字符都要雷同
同时删除前缀和后缀

请你返回对字符串 s 执行下面操作任意次当前（可能 0 次），能失去的最短长度

示例 1：

输出：s = "ca"
输入：2
解释：你没法删除任何一个字符，所以字符串长度依然放弃不变。

示例 2：

输出：s = "cabaabac"
输入：0
解释：最优操作序列为：- 抉择前缀 "c" 和后缀 "c" 并删除它们，失去 s = "abaaba"。- 抉择前缀 "a" 和后缀 "a" 并删除它们，失去 s = "baab"。- 抉择前缀 "b" 和后缀 "b" 并删除它们，失去 s = "aa"。- 抉择前缀 "a" 和后缀 "a" 并删除它们，失去 s = ""。

示例 3：

输出：s = "aabccabba"
输入：3
解释：最优操作序列为：- 抉择前缀 "aa" 和后缀 "a" 并删除它们，失去 s = "bccabb"。- 抉择前缀 "b" 和后缀 "bb" 并删除它们，失去 s = "cca"。

提醒：

1 <= s.length <= 105
s 只蕴含字符 'a'，'b' 和 'c'

因为只有「前缀」和「后缀」必须是雷同的字母能力删除。

因而咱们每次都将「前缀」和「后缀」所有的雷同字符的间断一段删除。

否则删除过程就可能会因为下一个字符不同而进行，最终失去的就不是最短的答案

代码：

class Solution {public int minimumLength(String s) {int n = s.length();
        char[] cs = s.toCharArray();
        int ans = n;
        for (int i = 0, j = n - 1; i < j; i++, j--) {if (cs[i] != cs[j]) break;
            while (i + 1 < j && cs[i + 1] == cs[i]) i++;
            while (j - 1 > i && cs[j - 1] == cs[j]) j--;
            ans = Math.max(0, j - i - 1);
        }
        return ans;
    }
}

工夫复杂度：$O(n)$
空间复杂度：$O(1)$

给你一个 events 数组。

其中 events[i] = [startDay[i], endDay[i], value[i]。

示意第 i 个会议在 startDay[i] 天开始，第 endDay[i] 天完结，如果你加入这个会议，你能失去价值 value[i]。

同时给你一个整数 k 示意你能加入的最多会议数目。

你同一时间只能加入一个会议。
如果你抉择加入某个会议，那么你必须残缺地加入完这个会议。

会议完结日期是蕴含在会议内的，也就是说你不能同时加入一个开始日期与另一个完结日期雷同的两个会议。

请你返回能失去的会议价值 最大和。

示例 1：

输出：events = [[1,2,4],[3,4,3],[2,3,1]], 
     k = 2
输入：7
解释：抉择绿色的流动会议 0 和 1，失去总价值和为 4 + 3 = 7。

示例 2：

输出：events = [[1,2,4],[3,4,3],[2,3,10]], 
     k = 2
输入：10
解释：加入会议 2，失去价值和为 10。你没法再加入别的会议了，因为跟会议 2 有重叠。你不须要加入满 k 个会议。

示例 3：

输出：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], 
     k = 3
输入：9
解释：只管会议互不重叠，你只能加入 3 个会议，所以抉择价值最大的 3 个会议。

提醒：

1 <= k <= events.length
1 <= k * events.length <= 10 ^ 6
1 <= startDayi <= endDayi <= 10 ^ 9
1 <= valuei <= 10 ^ 6

定义 f[i][j] 为思考前 i 个工夫，抉择不超过 j 的最大价值

对于每件工夫，都有抉择与不选两种抉择，不选有 f[i][j] = f[i - 1][j]。

抉择的话，则要找到第 i 件事件之前，与第 i 件事件不抵触的事件，记为 last，则有 f[i][j] = f[last][j - 1]。

两者取一个 max，则是 f[i][j] 的值。

剖析到这里，因为咱们要找 last，咱们须要先对 events 的完结工夫排序，而后找从右往左找，找到第一个满足 完结工夫小于以后事件的开始工夫 的事件，就是 last

而找 last 的过程，能够间接循环找，也能够通过二分来找，都能过。

不通过「二分」来找 last 的 DP 解法：

class Solution {public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        // f[i][j] 代表思考前 i 个事件，抉择不超过 j 的最大价值
        int[][] f = new int[n + 1][k + 1]; 
        for (int i = 1; i <= n; i++) {int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // 找到第 i 件事件之前，与第 i 件事件不抵触的事件
            // 对于以后事件而言，抵触与否，与 j 无关
            int last = 0;
            for (int p = i - 1; p >= 1; p--) {int[] prev = es[p - 1];
                if (prev[1] < s) {
                    last = p;
                    break;
                }
            }
            
            for (int j = 1; j <= k; j++) {f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}

工夫复杂度：排序复杂度为 $O(n\log{n})$，循环 n 个事件，每次循环须要往回找一个事件，复杂度为 $O(n)$，并更新 k 个状态，复杂度为 $O(k)$，因而转移的复杂度为 $O(n * (n + k))$；总的复杂度为 $O(n * (n + k + \log{n}))$
空间复杂度：$O(n * k)$

通过「二分」来找 last 的 DP 解法：

class Solution {public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        // f[i][j] 代表思考前 i 个事件，抉择不超过 j 的最大价值
        int[][] f = new int[n + 1][k + 1]; 
        for (int i = 1; i <= n; i++) {int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // 通过「二分」，找到第 i 件事件之前，与第 i 件事件不抵触的事件
            // 对于以后事件而言，抵触与否，与 j 无关
            int l = 1, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                int[] prev = es[mid - 1];
                if (prev[1] < s) {l = mid;} else {r = mid - 1;}
            }
            int last = (r > 0 && es[r - 1][1] < s) ? r : 0;
            
            for (int j = 1; j <= k; j++) {f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}

工夫复杂度：排序复杂度为 $O(n\log{n})$，循环 n 个事件，每次循环须要往回找一个事件，复杂度为 $O(\log{n})$，并更新 k 个状态，复杂度为 $O(k)$，因而转移的复杂度为 $O(n * (\log{n} + k))$；总的复杂度为 $O(n * (k + \log{n}))$
空间复杂度：$O(n * k)$

这是 2021/02/06 的 LeetCode 第 45 场双周赛的较量题解。

整体偏简略，没有冷门的内容，都是考查一些比拟常见的模型。

对于比赛生来说就是手速场，LeetCode 的排名是不分语言的，所以 C++ 还是有较大的劣势。

最近两天也是比拟累，原本明天打算不更新的了。

看了一下双周赛的题目，还挺简略，也属于口试面试的常见题目，就做了一下，写了题解发上来。

看状况今天会把明天周赛的题解发上来。大家晚安 ~

关于面试:LeetCode-第-45-场双周赛题解

t1：5657. 惟一元素的和（简略）

奢侈解法

t2：5658. 任意子数组和的绝对值的最大值（中等）

前缀和解法

t3：5659. 删除字符串两端雷同字符后的最短长度（中等）

双指针 + 贪婪解法

t4：5660. 最多能够加入的会议数目 II（艰难）

基本思路

动静布局解法

二分 + 动静布局解法

最初

Just My Socks（注册教程内含优惠码）

关于面试:LeetCode-第-45-场双周赛题解

t1：5657. 惟一元素的和（简略）

奢侈解法

t2：5658. 任意子数组和的绝对值的最大值（中等）

前缀和解法

t3：5659. 删除字符串两端雷同字符后的最短长度（中等）

双指针 + 贪婪解法

t4：5660. 最多能够加入的会议数目 II（艰难）

基本思路

动静布局解法

二分 + 动静布局解法

最初

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）