lcp354

第一题 特殊元素平方和

class Solution {
    public int sumOfSquares(int[] nums) {
        int n = nums.length, res = 0;
        for (int i = 0; i < n; ++i) {
            if (n % (i + 1) == 0)
                res += (nums[i] * nums[i]);
        }
        return res;
    }
}

第二题 数组的最大美丽值

方法一：二分查找

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
            // 求小于nums[i] + 2k的最大值
            int j = bisearch(nums, nums[i] + 2 * k);
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

    private int bisearch(int[] nums, int num) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] <= num)
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return right;
    } 
    
}

滑动窗口

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int res = 0;
        Arrays.sort(nums);
        for (int left = 0, right = 0; right < nums.length; ++right) {
            if (nums[right] - nums[left] > 2 * k) 
                left += 1;
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

差分

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int[] diff = new int[100003];
        for (int x : nums) {
            int left = Math.max(0, x - k);
            int right = Math.min(100001, x + k);
            ++diff[left];
            --diff[right + 1];
        }
        int res = 0;
        for (int i = 1; i < diff.length; ++i) {
            diff[i] += diff[i - 1];
            res = Math.max(res, diff[i]);
        }
        return res;
    }
}

第三题

class Solution {
    public int minimumIndex(List<Integer> nums) {
        n = nums.size();
        this.nums = nums.stream().mapToInt(i->i).toArray();
        Map<Integer, Integer> count = new HashMap<>();
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < n; ++i) {
            count.put(this.nums[i], count.getOrDefault(this.nums[i], 0) + 1);
            treeMap.put(count.get(this.nums[i]), this.nums[i]);
        }
        primary = treeMap.lastEntry().getValue();
        int[] cnt = new int[n];
        cnt[0] = this.nums[0] == primary ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            cnt[i] = cnt[i - 1];
            if (this.nums[i] == primary)
                cnt[i]++;
        }
        for (int i = 0; i < n - 1; ++i) {
            if (cnt[i] * 2 > i + 1 && (cnt[n - 1] - cnt[i]) * 2 > n - i - 1) {
                return i;
            }
        }
        return -1;
    }



    int n, MAX = Integer.MAX_VALUE, primary;
    int[] nums;
}

第四题

双指针

固定右端点，从右往左判断是否含有禁止的字符串

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        int res = 0, n = word.length();
        Set<String> set = new HashSet<>(forbidden);
        for (int left = 0,right = 0; right < n; ++right) {
            for (int i = right; i >= left && i > right - 10; --i) {
                if (set.contains(word.substring(i, right + 1))) {
                    left = i + 1;
                    break;
                }
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}