376-摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
    子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

1
2
3
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

1
2
3
4
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

1
2
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

题解：
从数组第二个元素开始遍历，每一层循环中做的事有：

  1. 跳过平坡，即遇到相等元素直接跳过
  2. 记录上一次是上坡还是下坡
  3. 若上一次是上坡，则只记录下坡，反之则只记录上坡 相当于只记录上坡和下坡数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int wiggleMaxLength(int[] nums) {
        // if(nums.length==1)
        //     return 1;
        //记录比较的趋势，开始为0
        int trend = 0;


        int res = 1;
        for(int i = 0; i<nums.length-1; i++){
        //从每一个元素开始做起始，记录找到最长序列
            int cur = 0;
                cur = nums[i]-nums[i+1];
                if(cur<0&& trend>=0){
                    trend = -1;
                    res++;
                }else if(cur>0&&trend<=0){
                    trend = 1;
                    res++;
                }
        }
       return res;
    }
}

2517. 礼盒的最大甜蜜度
给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格 ，另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

示例 1：

1
2
3
4
5
输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例 2：

1
2
3
4
5
输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例 3：

1
2
3
输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：

  • 2 <= k <= price.length <= 105
  • 1 <= price[i] <= 109

题解：
易知当甜度值ans越小时，更容易取得更长的k,即ans与k的函数具有单调性 => 二分

  1. 二分范围：[0,price[-1]-price[0]//(K-1)]
    因为最大值，当需要取k类时，则有差值 (甜蜜度) k-1段，最大差值/段数 => 最大值
  2. check 检查 从price的第一个元素开始，遍历
    f 方法的作用是在给定差值 d 的情况下，计算 price 数组中最多能选择多少个元素。具体来说，该方法首先将变量 cnt 初始化为 1，表示至少要选择一个元素。然后遍历 price 数组中的每个元素 p，如果 p 与上一个被选择的元素的价格的差值不小于 d，说明 p 可以被选择，将 cnt 加 1，并将上一个被选择的元素的价格赋值为 p。遍历完成后，返回 cnt。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);

        int left = 0, right = (price[price.length - 1] - price[0]) / (k - 1) + 1;
        while (left + 1 < right) { 
            int mid = left + (right - left) / 2;
            if (f(price, mid) >= k) left = mid; 
            else right = mid; 
        }
        return left;
    }

    private int f(int[] price, int d) {
        int cnt = 1, pre = price[0];
        for (int p : price) {
            if (p >= pre + d) {
                cnt++;
                pre = p;
            }
        }
        return cnt;
    }
}

前缀和

1177. 构建回文串检测

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], …, s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = “aaa” 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

示例：

1
2
3
4
5
6
7
8
输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

提示：

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • s 中只有小写英文字母

包含区间的问题 => 考虑前缀和
有数组S 长度为n，则有S[0i] - S[0k] = S[k~i] (i>k);
也就是说，任意区间可以用两个前缀表示。 显然这里的字符子串也是可以用前缀和实现的。

由题，在子串内可以任意重新排列字符，故影响是否为回文串的要素就是 => 某字符其数量的奇偶。对于偶数字符不需要操作，而对于奇数字符，需要执行替换操作。
具体的，替换次数为(x-1)/2,若替换次数小于k则说明回文成立。

所以，我们定义一个二维数组ss用于处理前缀中每个字符出现的次数，ss[i][j],其中i为末尾索引，j为字符，值为字符出现次数。 

1
2
3
4
5
6
7
8
int[][] prefix = new int[s.length() + 1][26];

for (int i = 0; i < s.length(); i++) {
    for (int j = 0; j < 26; j++) {
        prefix[i + 1][j] = prefix[i][j];
    }
    prefix[i + 1][s.charAt(i) - 'a']++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {

        //构建前缀
        //i+1 代表前i个字符
        int[][] prefix = new int[s.length() + 1][26];
        for (int i = 1; i < s.length() + 1; i++) {
            prefix[i] = prefix[i - 1].clone();
            prefix[i][s.charAt(i - 1) - 'a']++;
        }

        List<Boolean> booleans = new ArrayList<>();
        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2];
            int x = 0;
            for (int j = 0; j < 26; ++j) {
                x += (prefix[r + 1][j] - prefix[l][j]) & 1;
            }
            booleans.add(x / 2 <= k);
        }
        return booleans;
    }
}

优化
由于只关心每种字母出现次数的奇偶性，所以不需要在前缀和中存储每种字母的出现次数，只需要保存每种字母出现次数的奇偶性。
为方便计算，用 0 表示出现偶数次，用 1 表示出现奇数次。
注意只有奇数减偶数，或者偶数减奇数，才能得到奇数。所以如果相减的结果不为 0（或者说相减的两个数不相等），就表示出现了奇数次。
由于异或运算满足 111 和 000 的结果是 111，而 000 和 000，以及 111 和 111 的结果都是 000，所以可以用异或替换上面的减法。
题解