lcp342

计算列车到站时间

方法一：

class Solution {
    public int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime + delayedTime) % 24;
    }
}

倍数求和

方法二：数学

class Solution {
    public int sumOfMultiples(int n) {
        this.n = n;
        return s(3) + s(5) + s(7) - s(15) - s(21) - s(35) + s(105);
    }

    private int s(int m) {
        return (1 + n / m) *  (n / m) / 2 * m;
    }
    int n;
}

方法一：暴力

class Solution {
    public int sumOfMultiples(int n) {
        int res = 0;
        for (int i = 3; i <= n; ++i) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
                res += i;
        }
        return res;
    }

}

滑动子数组的美丽值

方法一：双TreeMap

题解

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        TreeMap<Integer, Integer> greater = new TreeMap<>(), smaller = new TreeMap<>();
        for (int i = 0; i < n; ++i) {
            smaller.put(nums[i], smaller.getOrDefault(nums[i], 0) + 1);
            if (i >= x) { // smaller 弹出最大元素
                int curMax = smaller.lastKey();
                greater.put(curMax, greater.getOrDefault(curMax, 0) + 1);
                if (smaller.get(curMax) == 1)
                    smaller.remove(curMax);
                else
                    smaller.put(curMax, smaller.get(curMax) - 1);
            }
            if (i >= k) { // 移除nums[i-k]
                int target = nums[i - k];
                if (greater.containsKey(target)) {
                    if (greater.get(target) == 1)
                        greater.remove(target);
                    else
                        greater.put(target, greater.get(target) - 1);
                }
                else {
                    if (smaller.get(target) == 1)
                        smaller.remove(target);
                    else
                        smaller.put(target, smaller.get(target) - 1);
                    int temp = greater.firstKey();
                    smaller.put(temp, smaller.getOrDefault(temp, 0) + 1);
                    if (greater.get(temp) == 1)
                        greater.remove(temp);
                    else
                        greater.put(temp, greater.get(temp) - 1);
                }
            }
            if (i >= k - 1)
                res[i - k + 1] = Math.min(0, smaller.lastKey());
        }
        return res;
    }
}

2654. 使数组所有元素变成 1 的最少操作次数

方法一：

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length, gcdAll = 0, count1 = 0;
        for (int x : nums) {
            gcdAll = gcd(gcdAll, x);
            if (x == 1)
                ++count1;
        }
        if (gcdAll > 1)
            return -1;
        if (count1 > 0)
            return n - count1;
        int minSize = n;
        for (int i = 0; i < n; ++i) {
            int g = 0;
            for (int j = i; j < n; ++j) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    minSize = Math.min(minSize, j - i + 1);
                    break;
                }
            }
        }
        return minSize + n - 2;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }
}