3379.转换数组

目标

给你一个整数数组 nums,它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result :

对于每个下标 i(其中 0 <= i < nums.length),独立执行以下操作:

  • 如果 nums[i] > 0:从下标 i 开始,向 右 移动 nums[i] 步,在循环数组中落脚的下标对应的值赋给 result[i]。
  • 如果 nums[i] < 0:从下标 i 开始,向 左 移动 abs(nums[i]) 步,在循环数组中落脚的下标对应的值赋给 result[i]。
  • 如果 nums[i] == 0:将 nums[i] 的值赋给 result[i]。

返回新数组 result。

注意:由于 nums 是循环数组,向右移动超过最后一个元素时将回到开头,向左移动超过第一个元素时将回到末尾。

示例 1:

输入: nums = [3,-2,1,1]
输出: [1,1,1,3]
解释:
对于 nums[0] 等于 3,向右移动 3 步到 nums[3],因此 result[0] 为 1。
对于 nums[1] 等于 -2,向左移动 2 步到 nums[3],因此 result[1] 为 1。
对于 nums[2] 等于 1,向右移动 1 步到 nums[3],因此 result[2] 为 1。
对于 nums[3] 等于 1,向右移动 1 步到 nums[0],因此 result[3] 为 3。

示例 2:

输入: nums = [-1,4,-1]
输出: [-1,-1,4]
解释:
对于 nums[0] 等于 -1,向左移动 1 步到 nums[2],因此 result[0] 为 -1。
对于 nums[1] 等于 4,向右移动 4 步到 nums[2],因此 result[1] 为 -1。
对于 nums[2] 等于 -1,向左移动 1 步到 nums[1],因此 result[2] 为 4。

说明:

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

思路

将循环数组 nums 根据规则转换成一个新数组,新数组下标 i 的值是 nums[offset],当 nums[i] > 0 时,offseti 右边 nums[i] 个位置上的值,当 nums[i] < 0 时,取 i 左边 nums[i] 个位置上的值,如果为 0,取 nums[i]

代码


/**
 * @date 2026-02-05 8:43
 */
public class ConstructTransformedArray3379 {

    public int[] constructTransformedArray_v1(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nums[((i + nums[i]) % n + n) % n];
        }
        return res;
    }

}

性能

3637.三段式数组I

目标

给你一个长度为 n 的整数数组 nums。

如果存在索引 0 < p < q < n − 1,使得数组满足以下条件,则称其为 三段式数组(trionic):

  • nums[0...p] 严格 递增,
  • nums[p...q] 严格 递减,
  • nums[q...n − 1] 严格 递增。

如果 nums 是三段式数组,返回 true;否则,返回 false。

示例 1:

输入: nums = [1,3,5,4,2,6]
输出: true
解释:
选择 p = 2, q = 4:
nums[0...2] = [1, 3, 5] 严格递增 (1 < 3 < 5)。
nums[2...4] = [5, 4, 2] 严格递减 (5 > 4 > 2)。
nums[4...5] = [2, 6] 严格递增 (2 < 6)。

示例 2:

输入: nums = [2,1,3]
输出: false
解释:
无法选出能使数组满足三段式要求的 p 和 q 。

说明:

  • 3 <= n <= 100
  • -1000 <= nums[i] <= 1000

思路

判断数组是否是三段式数组,所谓三段式数组指第一段严格递增,第二段严格递减,第三段严格递增。

根据题意模拟,判断数组拐弯的次数是否等于 2,注意第一段应该是严格递增的。

代码


/**
 * @date 2026-02-03 9:11
 */
public class IsTrionic3637 {

    public boolean isTrionic(int[] nums) {
        if (nums[0] >= nums[1]) {
            return false;
        }
        int n = nums.length;
        int cnt = 0;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return false;
            } else if (nums[i - 1] > nums[i] != nums[i] > nums[i + 1]) {
                cnt++;
            }
        }
        return cnt == 2;
    }

}

性能

3010.将数组分成最小总代价的子数组I

目标

给你一个长度为 n 的整数数组 nums 。

一个数组的 代价 是它的 第一个 元素。比方说,[1,2,3] 的代价是 1 ,[3,4,1] 的代价是 3 。

你需要将 nums 分成 3 个 连续且没有交集 的子数组。

请你返回这些子数组的 最小 代价 总和 。

示例 1:

输入:nums = [1,2,3,12]
输出:6
解释:最佳分割成 3 个子数组的方案是:[1] ,[2] 和 [3,12] ,总代价为 1 + 2 + 3 = 6 。
其他得到 3 个子数组的方案是:
- [1] ,[2,3] 和 [12] ,总代价是 1 + 2 + 12 = 15 。
- [1,2] ,[3] 和 [12] ,总代价是 1 + 3 + 12 = 16 。

示例 2:

输入:nums = [5,4,3]
输出:12
解释:最佳分割成 3 个子数组的方案是:[5] ,[4] 和 [3] ,总代价为 5 + 4 + 3 = 12 。
12 是所有分割方案里的最小总代价。

示例 3:

输入:nums = [10,3,1,1]
输出:12
解释:最佳分割成 3 个子数组的方案是:[10,3] ,[1] 和 [1] ,总代价为 10 + 1 + 1 = 12 。
12 是所有分割方案里的最小总代价。

说明:

  • 3 <= n <= 50
  • 1 <= nums[i] <= 50

思路

定义数组的代价是其第一个元素值,有一个数组 nums,将其分割成 3 个连续且不相交子数组,求子数组的最小总代价。

第一个数组的代价是固定的,问题变成从 1 ~ n -1 选两个最小的元素值。可以排序后取前三个元素的和,或者使用双指针记录最小与次小元素。

代码


/**
 * @date 2026-02-02 9:49
 */
public class MinimumCost3010 {

    public int minimumCost(int[] nums) {
        int n = nums.length;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (nums[i] < min1) {
                min2 = min1;
                min1 = nums[i];
            } else if (nums[i] < min2) {
                min2 = nums[i];
            }
        }
        return nums[0] + min1 + min2;
    }
}

性能

744.寻找比目标字母大的最小字母

目标

给你一个字符数组 letters,该数组按非递减顺序排序,以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符,则返回 letters 的第一个字符。

示例 1:

输入: letters = ['c', 'f', 'j'],target = 'a'
输出: 'c'
解释:letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释:letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释:letters 中没有一个字符在字典上大于 'z',所以我们返回 letters[0]。

说明:

  • 2 <= letters.length <= 10^4
  • letters[i] 是一个小写字母
  • letters 按非递减顺序排序
  • letters 最少包含两个不同的字母
  • target 是一个小写字母

思路

有一个升序排列的字符数组 letters,返回大于 target 的最小字符,如不存在返回第一个字符。

使用二分,查找第一个大于 target 的字符。

代码


/**
 * @date 2026-02-02 9:42
 */
public class NextGreatestLetter744 {

    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int r = n - 1;
        int l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l < n ? letters[l] : letters[0];
    }

}

性能

1200.最小绝对差

目标

给你个整数数组 arr,其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对,并且按升序的顺序返回。

每对元素对 [a,b] 如下:

  • a , b 均为数组 arr 中的元素
  • a < b
  • b - a 等于 arr 中任意两个元素的最小绝对差

示例 1:

输入:arr = [4,2,1,3]
输出:[[1,2],[2,3],[3,4]]

示例 2:

输入:arr = [1,3,6,10,15]
输出:[[1,3]]

示例 3:

输入:arr = [3,8,-10,23,19,-4,-14,27]
输出:[[-14,-10],[19,23],[23,27]]

说明:

  • 2 <= arr.length <= 10^5
  • -10^6 <= arr[i] <= 10^6

思路

找到数组 arr 中元素值距离最小的元素对,按照升序返回。升序指 元素对 内部升序,结果集中元素对第一个元素升序。

将数组排序,最小距离在相邻元素中产生。

代码


/**
 * @date 2026-01-26 8:44
 */
public class MinimumAbsDifference1200 {

    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> res = new ArrayList<>();
        int n = arr.length;
        int diff = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            diff = Math.min(diff, arr[i + 1] - arr[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            if (arr[i + 1] - arr[i] == diff) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(arr[i]);
                tmp.add(arr[i + 1]);
                res.add(tmp);
            }
        }
        return res;
    }
}

性能

1984.学生分数的最小差值

目标

给你一个 下标从 0 开始 的整数数组 nums ,其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数,使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

示例 1:

输入:nums = [90], k = 1
输出:0
解释:选出 1 名学生的分数,仅有 1 种方法:
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2:

输入:nums = [9,4,1,7], k = 2
输出:2
解释:选出 2 名学生的分数,有 6 种方法:
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

说明:

  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 10^5

思路

nums 中选择 k 个元素,求这 k 个元素中最大值与最小值的差的最小值。

要使差值最小,应该尽量缩小所选元素之间的距离。排序,使用定长滑动窗口,窗口内最大值与最小值的差即为 nums[r] - nums[l]

代码


/**
 * @date 2026-01-26 9:59
 */
public class MinimumDifference1984 {

    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        Arrays.sort(nums);
        int l = 0;
        int n = nums.length;
        for (int r = k - 1; r < n; r++) {
            res = Math.min(res, nums[r] - nums[l++]);
        }
        return res;
    }
}

性能

3507.移除最小数对使数组有序I

目标

给你一个数组 nums,你可以执行以下操作任意次数:

  • 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对,选择最左边的一个。
  • 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素(如果存在的话),则称该数组为非递减。

示例 1:

输入: nums = [5,2,3,1]
输出: 2
解释:
元素对 (3,1) 的和最小,为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2:

输入: nums = [1,2,2]
输出: 0
解释:
数组 nums 已经是非递减的。

说明:

  • 1 <= nums.length <= 50
  • -1000 <= nums[i] <= 1000

思路

有一个数组 nums,每一次操作可以将数组中和最小的相邻元素用它们的和替换掉,求使得数组非递减所需要的最少操作次数。

暴力解法是每次遍历找到和最小的数对 并替换,直到数组非递减。可以使用 next 数组模拟链表来删除元素。

代码


/**
 * @date 2026-01-22 9:02
 */
public class MinimumPairRemoval3507 {

    public int minimumPairRemoval_v1(int[] nums) {
        int res = 0;
        boolean decrease;
        int n = nums.length;
        int[] next = new int[n];
        Arrays.setAll(next, i -> i + 1);
        do {
            decrease = false;
            int index = 0, sum = Integer.MAX_VALUE;
            for (int i = 0; next[i] < n; i = next[i]) {
                if (nums[next[i]] < nums[i]) {
                    decrease = true;
                }
                int s = nums[i] + nums[next[i]];
                if (s < sum) {
                    sum = s;
                    index = i;
                }
            }
            if (decrease) {
                nums[index] = sum;
                next[index] = next[next[index]];
                res++;
            }
        } while (decrease);
        return res;
    }

}

性能

3314.构造最小位运算数组I

目标

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ,对于每个下标 i ,以下 条件 均成立:

  • ans[i] OR (ans[i] + 1) == nums[i]

除此以外,你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合 条件 的 ans[i] ,那么 ans[i] = -1 。

质数 指的是一个大于 1 的自然数,且它只有 1 和自己两个因数。

示例 1:

输入:nums = [2,3,5,7]
输出:[-1,1,4,3]
解释:
对于 i = 0 ,不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ,所以 ans[0] = -1 。
对于 i = 1 ,满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ,因为 1 OR (1 + 1) = 3 。
对于 i = 2 ,满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ,因为 4 OR (4 + 1) = 5 。
对于 i = 3 ,满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ,因为 3 OR (3 + 1) = 7 。

示例 2:

输入:nums = [11,13,31]
输出:[9,12,15]
解释:
对于 i = 0 ,满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ,因为 9 OR (9 + 1) = 11 。
对于 i = 1 ,满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ,因为 12 OR (12 + 1) = 13 。
对于 i = 2 ,满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ,因为 15 OR (15 + 1) = 31 。

说明:

  • 1 <= nums.length <= 100
  • 2 <= nums[i] <= 1000
  • nums[i] 是一个质数。

思路

有一个长度为 n 的质数列表 nums,针对质数 nums.get(i),找到最小的值 res[i] 满足 (res[i] | res[i] + 1) == nums.get(i)。

针对每一个质数,直接枚举所有可能的值,判断是否满足条件。

代码


/**
 * @date 2026-01-20 0:15
 */
public class MinBitwiseArray3314 {

    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            int num = nums.get(i);
            for (int j = 0; j < num; j++) {
                if ((j | (j + 1)) == num){
                    res[i] = j;
                    break;
                }
            }
        }
        return res;
    }
}

性能

1266.访问所有点的最小时间

目标

平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间(以秒为单位)。

你需要按照下面的规则在平面上移动:

  • 每一秒内,你可以:
    • 沿水平方向移动一个单位长度,或者
    • 沿竖直方向移动一个单位长度,或者
    • 跨过对角线移动 sqrt(2) 个单位长度(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。
  • 必须按照数组中出现的顺序来访问这些点。
  • 在访问某个点时,可以经过该点后面出现的点,但经过的那些点不算作有效访问。

示例 1:

输入:points = [[1,1],[3,4],[-1,0]]
输出:7
解释:一条最佳的访问路径是: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2:

输入:points = [[3,2],[-2,2]]
输出:5

说明:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000

思路

二维平面上有一些点 points,按顺序访问这些点,每一秒可以沿 x 轴、 y 轴 或者 格子的对角线移动,求访问所有点的最小时间。

优先走斜线,直到与下一个坐标点的 横坐标 或者 纵坐标 相等,然后再走直线。两点之间最短时间为 Math.max(dx, dy),即切比雪夫距离。

代码


/**
 * @date 2026-01-12 8:50
 */
public class MinTimeToVisitAllPoints1266 {

    public int minTimeToVisitAllPoints(int[][] points) {
        int res = 0;
        for (int i = 1; i < points.length; i++) {
            int dx = Math.abs(points[i][0] - points[i - 1][0]);
            int dy = Math.abs(points[i][1] - points[i - 1][1]);
            res += Math.max(dx, dy);
        }
        return res;
    }
}

性能

961.在长度2N的数组中找出重复N次的元素

目标

给你一个整数数组 nums ,该数组具有以下属性:

  • nums.length == 2 * n.
  • nums 包含 n + 1 个 不同的 元素
  • nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1:

输入:nums = [1,2,3,3]
输出:3

示例 2:

输入:nums = [2,1,2,5,3,2]
输出:2

示例 3:

输入:nums = [5,1,5,2,5,3,5,4]
输出:5

说明:

  • 2 <= n <= 5000
  • nums.length == 2 * n
  • 0 <= nums[i] <= 10^4
  • nums 由 n + 1 个 不同的 元素组成,且其中一个元素恰好重复 n 次

思路

长度为 2 * n 数组 numsn + 1 个不同元素,其中恰好有一个元素重复 n 次,返回该重复元素。

除了该重复元素,其余元素各不相同。

暴力做法是使用哈希表记录元素的出现次数,如果出现次数大于 1,直接返回,空间复杂度为 O(n)

对于本题,从下标 1 开始与第一个元素比较,如果相等直接返回。否则问题变成从 2n - 1 个元素中找重复 n 次的元素,重复元素占绝对多数,可以使用摩尔投票算法。

还可以根据重复元素的最小间隔来分析:

  • 假设重复元素至少隔着一个其它元素,有 n - 1 个空隙,至少有 2 * n - 1 个元素,可能。
  • 假设重复元素至少隔着两个其它元素,有 n - 1 个空隙,至少有 n + 2 * (n - 1) = 3 * n - 2 个元素,当 n = 2 时,有可能,当 n > 2 时,必定存在一个重复元素的间隔小于 2,否则元素个数不够

也就是说,可以检查当前元素与其前 123 个元素是否相等来找出该重复元素。空间复杂度为 O(1)

以上算法的时间复杂度均为 O(n),还有一种期望 O(1) 的算法,使用随机数,随机选取两个元素。它们两个相等的概率是 n/2n × (n - 1)/(2n - 1) = 1/2 * (1 - 1/n)/(2 - 1/n),当 n = 2 时,p = 1/6,当 n -> ∞p -> 1/4。期望循环次数 <= 6。

代码


/**
 * @date 2026-01-04 14:45
 */
public class RepeatedNTimes961 {

    public int repeatedNTimes_v1(int[] nums) {
        int n = nums.length;
        int candidate = 0;
        int vote = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (vote == 0) {
                candidate = nums[i];
                vote = 1;
            } else if (candidate != nums[i]) {
                vote--;
            } else {
                return candidate;
            }
        }
        return candidate;
    }

    public int repeatedNTimes(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] || (i >= 2 && nums[i] == nums[i - 2]) || (i >= 3 && nums[i] == nums[i - 3])) {
                return nums[i];
            }
        }
        return 0;
    }

}

性能