lcpBi113

8039. 使数组成为递增数组的最少右移次数

方法一：模拟

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nums.get(i);
        }
        boolean flag = true;
        for (int i = 1; i < n; ++i) {
            if (nums.get(i) < nums.get(i - 1))
                flag = false;
        }
        if (flag)
            return 0;


        int[] temp = arr.clone();
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < n; ++j) {
                arr[(j + 1) % n] = temp[j];
            }
            flag = true;
           for (int j = 1; j < n; ++j) {
               if (arr[j] < arr[j - 1]) {
                   flag = false;
                   break;
               }
           }
           if (flag)
               return i;
           temp = arr;
           arr = new int[n];
        }
        return -1;
    }
}

方法二：O(n)

2856. 删除数对后的最小数组长度

方法一：TreeMap二分

同lcp334 t3

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = n / 2 + (n % 2); i < n; ++i)
            map.put(nums.get(i), map.getOrDefault(nums.get(i), 0) + 1);
        int res = n;
        for (int i = 0; i < n / 2; ++i) {
            int x = nums.get(i);
            Integer ceil = map.higherKey(x);
            if (ceil == null)
                break;
            else {
                res -= 2;
                map.put(ceil, map.get(ceil) - 1);
                if (map.get(ceil) == 0)
                    map.remove(ceil);
            }
        }
        return res;
    }
}

6988. 统计距离为 k 的点对

方法一：前缀和 + HashMap

两数之和

class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        long res = 0;
        Map<Long, Integer> map = new HashMap<>();
        for (List<Integer> arr : coordinates) {
            int x = arr.get(0), y = arr.get(1);
            for (int i = 0; i <= 100; ++i) {
                long t1 = x ^ i, t2 = y ^ (k - i);
                res += map.getOrDefault((t1 << 32) | t2, 0);
            }
            long key = ((long) x << 32) | y;
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        System.out.println();
        return (int) res;
    } 

}