分割数组
题目：给定一个数组 A，将其划分为两个连续子数组 left 和 right， 使得：
left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 的长度要尽可能小。
在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。
示例 1：
输入：[5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]
示例 2：
输入：[1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]
提示：
2 <= A.length <= 30000
0 <= A[i] <= 10^6
可以保证至少有一种方法能够按题目所描述的那样对 A 进行划分。
思路：这个题怎么说呢，感觉应该不难，一个是从左往右记录当前的最大值。另一个是从右往左记录当前最小值。如果某个节点左边最大值小于右边最小值就可以了。大概思路是这样，我去实现下试试。
第一版代码：
class Solution {
public int partitionDisjoint(int[] nums) {
int n = nums.length-1;
int[] max = new int[nums.length];
max[1] = nums[0];
int[] min = new int[nums.length];
min[n] = nums[n];
for(int i = 2;i<=n;i++) max[i] = Math.max(max[i-1], nums[i-1]);
for(int i = n-1;i>=0;i--) min[i] = Math.min(min[i+1], nums[i]);
for(int i = 1;i<=n;i++) {
if(max[i]<=min[i]) return i;
}
return -1;
}
}
果然这个题比较简单，三个循环就搞定了。。然后我觉得其实这个题可能还有很多种方式可以实现。而且我写出来了才觉得因为这个题是要从左开始遍历的，所以可能压根不用存max。我去改改试试。果然：
class Solution {
public int partitionDisjoint(int[] nums) {
int n = nums.length-1;
int[] min = new int[nums.length];
min[n] = nums[n];
for(int i = n-1;i>=0;i--) min[i] = Math.min(min[i+1], nums[i]);
int max = nums[0];
for(int i = 1;i<=n;i++) {
if(max<=min[i]) return i;
max = Math.max(max, nums[i]);
}
return -1;
}
}
不过这俩代码的性能差不多，都不咋地，我去看看性能第一的代码：
？？？？我完全理解不了为什么人家的性能第一，感觉写的也没多简单啊：
class Solution {
public int partitionDisjoint(int[] nums) {
int [] max = new int [nums.length]; //从左到i，最大的元素值
int [] min = new int[nums.length]; //从右到i，最小的元素值
int periodMax = 0;
int periodMin = Integer.MAX_VALUE;
for (int i=0;i<nums.length;i++){
if (nums[i] > periodMax){
periodMax = nums[i];
}
max[i] = periodMax;
}
for (int i = nums.length-1;i>=0;i--){
if (nums[i] < periodMin){
periodMin = nums[i];
}
min[i] = periodMin;
}
for (int i=1;i<nums.length;i++){
if (min[i] >= max[i-1]){
return i;
}
}
return 0;
}
}
可能就是人家没用Math.min和Math.max吧。。。这个暂时理解不了，不过因为题目比较简单，没什么好说的，下一题。
单词子集
题目：我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。你可以按任意顺序以列表形式返回 A 中所有的通用单词。
示例 1：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]
示例 2：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出：["apple","google","leetcode"]
示例 3：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]
示例 4：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出：["google","leetcode"]
示例 5：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出：["facebook","leetcode"]
提示：
1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] 和 B[i] 只由小写字母组成。
A[i] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A[i] == A[j]。
思路：感觉继之前死去活来的dp以后迎来了一大波简单题目。。简单来说这个题目我的想法是首先根据B去获取所有需要的元素的个数。我这里打算用26个元素的数组表示a到z。然后元素值表示个数。比如B是aa,b,ab,c,d。其实这个需要的总数是a是两个，b是一个，c是一个，d是一个。我们可以把B化成嘴贱需求。然后用二维数组去和每一个A比对。反正不知道会不会超时。我去试试了。
第一版代码：
class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
int[] d = new int[26];
for(String s : words2) {
int[] temp = new int[26];
for(char c : s.toCharArray()) temp[c-'a']++;
for(int i = 0;i<26;i++) d[i] = Math.max(d[i], temp[i]);
}
List<String> ans = new ArrayList<String>();
for(String s : words1) {
int[] temp = new int[26];
for(char c : s.toCharArray()) temp[c-'a']++;
boolean flag = true;
for(int i = 0;i<26;i++) if(d[i]>temp[i]) flag = false;
if(flag) ans.add(s);
}
return ans;
}
}
这个怎么说呢，完全按照我之前的思路做的，中间没遇到坑。一次ac。但是性能一般。暂时没啥优化的思路，我去看看性能第一的代码：
class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
int[] bFrq = new int[26];
for (String b : B) {
int[] tempFrq = new int[26];
for (char c : b.toCharArray()) {
tempFrq[c - 'a']++;
if (tempFrq[c - 'a'] > bFrq[c - 'a']) {
bFrq[c - 'a'] = tempFrq[c - 'a'];
}
}
}
List<String> rt = new ArrayList<>();
for (String a : A) {
int[] tempFrq = new int[26];
for (char c : a.toCharArray()) {
tempFrq[c - 'a']++;
}
boolean canAdd = true;
for (int i = 0; i < 26; i++) {
if (tempFrq[i] < bFrq[i]) {
canAdd = false;
break;
}
}
if (canAdd) {
rt.add(a);
}
}
return rt;
}
}
今天刷的这两道题，我是真觉得Math.max好像性能有点问题啊，百分之九十的代码都一样，主要区别就是在确定d的时候我是两次遍历。一次是记录元素数。一次是比较并替换。人家用了一次比较。。总而言之这个题算是细节处理不够好吧，下一题了。
环形子数组的最大和
题目：给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）
示例 1：
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1
提示：
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
思路：这种题还挺简单的。首尾相连而且每个元素只能出现一次。如果说这个题不能首尾相连的话，那么dp数组就是毫无疑问的做法。但是这个题目前是多了一个首尾相连的选项。所以这个题就有两种可能了：一种不需要收尾相连，那么选取数组中某段子和的最大值即可。另一种是需要收尾相连，那么本质就变成了要前面一部分+后面一部分。这样做我们再仔细考量：其实就是整个数组扣出去一部分和是负数的值。所以我们只要知道总和 还有扣出去的值就可以了。现在有了简单的思路，我去代码实现试试。
第一版本代码：
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int dpMax = nums[0];
int dpMin = nums[0];
int sum = nums[0];
int max = nums[0];
int min = 0;//min不包括第一个和最后一个元素
for(int i = 1;i<nums.length;i++){
sum += nums[i];
dpMax = nums[i]+Math.max(dpMax,0);
max = Math.max(max,dpMax);
if(i<nums.length-1){//因为这个min一定是中间的，所以不包含第一个和最后一个元素
dpMin = nums[i]+Math.min(dpMin,0);
min = Math.min(min,dpMin);
}
}
return Math.max(max,sum-min);
}
}
虽然这个题ac了，但是性能不是很好，但是我思路是没问题的。总而言之这个题的复杂点也就是多了一个收尾相连。不然就是一个单纯的dp。至于优化我个人没啥耐心了，直接去看性能第一的代码：
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int wudp=nums[0];
int youdp=0;
int wumax=nums[0];
int youmin=0;
int sum=0;
for(int i:nums){
sum+=i;
}
for(int i=1;i<nums.length;i++){
wudp=Math.max(nums[i]+wudp,nums[i]);
wumax=Math.max(wumax,wudp);
}
for(int i=1;i<nums.length-1;i++){
youdp=Math.min(nums[i]+youdp,nums[i]);
youmin=Math.min(youmin,youdp);
}
return Math.max(sum-youmin,wumax);
}
}
咋说呢，一样的思路差不多的写法，性能就天壤之别。反正也就这样了。还有一种很高大上但是我没看懂的写法就不贴出来了，直接下一题。
绝对差值和
题目：给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
|x| 定义为：
如果 x >= 0 ，值为 x ，或者
如果 x <= 0 ，值为 -x
示例 1：
输入：nums1 = [1,7,5], nums2 = [2,3,5]
输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3
示例 2：
输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0
示例 3：
输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
提示：
n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105
思路：这个题怎么说呢，我个人的感觉：审题，审题！！审题！！！！明明字不多怎么就那么难以理解，这个问题不仅仅是我，我们群里另一个小孩也审题不清所以坑了（这个题是曾经的一道周赛题）、而真正明白题目这个题思路还是很简单的。首先判断改动哪个元素，这是个遍历的过程，不过我们可以保存一个当前已经缩小了的值。如果遇到一些元素改的最好的效果也没这个值大，就不用白白计算了。而每一个元素可替换的角度有两个：大于给定2中的值和小于给定2中的值。我们可以直接选择绝对差值最小的那个。思路比较清晰，下面是实现代码：
class Solution {
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] rec = new int[n];
System.arraycopy(nums1, 0, rec, 0, n);
Arrays.sort(rec);
int max = 0;
long sum = 0;
for(int i = 0;i<n;i++){
int cha = Math.abs(nums1[i]-nums2[i]);
sum += cha;
if(cha<=max) continue;
max = Math.max(max,cha-Math.abs(getV(nums2[i],rec)-nums2[i]));
}
// System.out.println(sum);
// System.out.println(max);
return (int)((sum-max)%1000000007);
}
public int getV(int temp,int[] rec){
int l = 0;
int r = rec.length-1;
//比最大值大。
if(rec[r]<=temp) return rec[r];
//比最小值小
if(rec[l]>=temp) return rec[l];
while(l<r){
int mid = (r-l)/2+l;
if(rec[mid]<temp){
l = mid+1;
}else {
r = mid;
}
}
return rec[r]-temp>temp-rec[r-1]?rec[r-1]:rec[r];
}
}
性能也还好。超过了百分之九十四的人，在我这已经可以过了，直接下一题了。
减少和重排列数组后的最大元素
题目：给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：
arr 中 第一个 元素必须为 1 。
任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。
你可以执行以下 2 种操作任意次：
减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
重新排列 arr 中的元素，你可以以任意顺序重新排列。
请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。
示例 1：
输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。
示例 2：
输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
- 重新排列 arr 得到 [1,100,1000] 。
- 将第二个元素减小为 2 。
- 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。
示例 3：
输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。
提示：
1 <= arr.length <= 105
1 <= arr[i] <= 109
思路：感觉这个题应该是从最小开始计算。因为数据只能往小不能往大变。所以整体思路我是从最小值开始找起。往上一步一步顺。每次变化也是从最小值开始变。大概思路有了，我去实现下试试。
这个题咋说呢，比我想的简单的多，然后一次ac并且性能不错，附上代码：
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
int last = 1;//第一个元素必然是1
for(int i = 1;i<arr.length;i++){
if(arr[i] > last){
last += 1;
}
}
return last;
}
}
着实没什么好说的了。刚刚看了下性能第一的代码，没有排序，而是创建数组计数，能理解，就是比较麻烦。附上代码：
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
int length = arr.length;
int[] countArr = new int[length];
int interCount = 0; // 在计数范围内的元素个数
// 计数(其实记录 1 到 length - 1 就够了，因为值为 length 的元素也是“万能牌”)
for (int ele : arr) {
if (ele >= 1 && ele< length) {
countArr[ele - 1]++;
interCount++;
}
}
int totalNeedAdd = 0; // 在遍历当前元素时，有多少比当前小的元素需要被补充
int interMax = 0; //计数范围内部的实际最大值
//计算计数范围内部真正最大值(可优化)
for (int i = 0; i < length; i++) {
if (countArr[i] == 0) {
totalNeedAdd++;
} else {
if (countArr[i] > totalNeedAdd) {
totalNeedAdd = 0;
interMax = i + 1;
} else {
totalNeedAdd -= countArr[i];
interMax += countArr[i];
}
}
}
return interMax + (length - interCount);
}
}
这个注释写的挺全的，比较好理解。我就不多说什么了。也可能是数据范围的事，反正是性能差距不大。而且这种方式着实略复杂、总而言之这个题暂时就这样了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康！
网友评论