luckycc

模运算

X % Q == (X + Q) % Q
(X + Y) % Q == (X % Q + Y % Q) % Q

在前缀和中，通常会用到同模
pre[i] % Q = h
pre[j] % Q = h
那么 pre[i]-pre[j] % Q = h， 反之亦然

1015. 可被 K 整除的最小整数

题目：

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最小正整数 n 的长度。返回 n 的长度。如果不存在这样的 n ，就返回-1。

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

思路：

要掌握一个模数的定理：

(n*p+q) % k = ((p%k)*n + q) % k

根据这个模数定理，因为数字全由1构成，因此可以推导出

new = old * 10 + 1
因此，new % k = ( old * 10 +1 ) % k = ((old%k) *10 +1) %k
old % k 正是上一次的模运算结果
设 old % k = x
new = (x*10+1)%k

因此，我们可以从1开始，不断 %k, 因为一个数 %k 的结果的数据范围在[1,k-1] 之间，因此，最多做k-1次运算就能够知道一个数的是否能被k整除，因为如果一个数无法被k整除，那么k次运算中 x的取值必有一次会重复，如果有重复的话，那么这个数无论添加多少个1，都不会被k除了，直接return -1。

使用 HashSet来记录是否出现重复的数字

数学

1330. 翻转子数组得到最大的数组值

题目：

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作一次。请你找到可行的最大数组值。

输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。

思路：

翻转前与翻转后的数组值的差值越大，最终找到的数组值就越大。那么如果想要使最终的数组值最大，就要使这个差值最大。对子数组进行翻转，只会影响到4个数字，假设翻转前数组为 [...a,b,...c,d...]翻转后为 [...a,c,...b,d...]，那么这时候，新旧数组值的差值为：diff=|c-a|+|d-b|-|a-b|-|c-d|

我们只需要使得这个diff最大，即可。那么问题就转化为了使diff最大

我们需要对这个diff进行分类讨论，讨论 a,c与b,d之间的大小。

①当a>c b>d时，原式=(a-c)+(b-d)-|a-b|-|c-d|=(a+b)-|a-b|-(c+d)-|c-d|
②当a<c b>d时，原式=(c-a)+(b-d)-|a-b|-|c-d|=(c-d)-|c-d|+(b-a)-|b-a|<0，舍去
③当a>c b<d时，原式=(a-c)+(d-b)-|a-b|-|c-d|=(a-b)-|a-b|+(d-c)-|d-c|<0，舍去
④当a>c b<d时，原式=(c-a)+(d-b)-|a-b|-|c-d|=(c+d)-|c-d|-(a+b)-|a-b|

综上，我们只需要讨论①④两种情况

这两种情况都转变为了形如:（x+y) + |x-y|和 (x+y)-|x-y| 这种形式。

对于两个数差的绝对值，我们可以使用最大值与最小值拆掉它的绝对值号，下面的公式是解题的关键

(x+y)+|x-y| = max(x,y)+min(x,y)+max(x,y)-min(x,y) = 2max(x,y)
(x+y)-|x-y| = max(x,y)+min(x,y)-max(x,y)+min(x,y) = 2min(x,y)

因此，上面的①④可以转化为：

①2min(a,b)-2max(c,d)
④2min(c,d)-2max(a,b)

我们再看上面两个式子，a和b，c和d其实都是相邻的两个数。我们要使得①④两个式子最大，就需要使 min(x,y)最大，使 max(x,y)最小。注：这里 x和 y指的是数组中相邻的两个数。最后，需要判断一下边界情况，也就是 a = nums[0] 和 b=nums[n-1]的情况

完整代码：

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int mx = Integer.MIN_VALUE; //min(x,y)的最大值
        int mn = Integer.MAX_VALUE; //max(x,y)的最小值
        int sum = 0; //旧的数组值
        int d = Integer.MIN_VALUE;
        for(int i=1 ; i<n ; i++){
            int a = nums[i-1];
            int b = nums[i];
            int diff = Math.abs(a-b); //相邻两个数的差值
            mx = Math.max(mx,Math.min(a,b));
            mn = Math.min(mn,Math.max(a,b));
            sum+=diff;
            d = Math.max(d,Math.max(
              Math.abs(nums[0]-b)-diff ,//a = nums[0]的情况
              Math.abs(nums[n-1]-a)-diff //b = nums[n-1]的情况
            )); // 这里这个d计算的是边界情况

        }
        return sum+Math.max(d,2*(mx-mn)); // 旧的数组值 + 这个最大的差值 = 新的数组值
    }
}

数据结构

创建一个优先级队列的array

PriorityQueue<Integer>[] pq = new PriorityQueue[m];
pq[i] = new PriorityQueue<Integer>((a, b)->a-b);

位运算

js的异或： a^b，同位相同返回0，不同返回1
a>>1 右移一位，代表除以2
末位是1代表是奇数

其他小技巧

模运算

1015. 可被 K 整除的最小整数

数学

1330. 翻转子数组得到最大的数组值

数据结构

创建一个优先级队列的array

位运算