shelterofly

目标

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

进阶：

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路

将 有序数组 划分为两个子数组，交换子数组的顺序得到旋转数组 nums，判断旋转数组中是否存在 target。

根据题意可知，原来的有序数组被划分成两部分，第一部分的所有元素均大于 等于 第二部分的所有元素。

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。如果当前元素恰好与切点的元素值相同，那么我们无法判断该搜索哪一部分。

例如，如果当前元素值大于 target，但是恰好与第一个元素相同：

• 如果当前元素就是位于第一部分，那么我们应该将 left 右移，以便到达第二部分搜索。
• 如果当前元素已经位于第二部分，那么我们应该将 right 左移，以便找到更小的target。

最简单的处理方法是缩小右边界，因为这种情况只会出现在切点刚好在连续相同元素中间，这时最左侧的元素一定与最右侧的元素相同，我们可以提前将 right 移到第一个与 left 不同的位置。这样当前元素属于哪一部分就确定了，不会影响判断。

代码

/**
 * @date 2025-02-01 14:33
 */
public class Search81 {

    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (right > 0 && nums[left] == nums[right]) {
            right--;
        }
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums[mid], nums[0], target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        if (left >= 0 && left < n) {
            return nums[left] == target;
        }
        return false;
    }

    public boolean check(int midValue, int firstValue, int target) {
        if (target < firstValue) {
            if (midValue >= firstValue) {
                return true;
            } else {
                return midValue < target;
            }
        } else {
            if (midValue >= firstValue) {
                return midValue < target;
            } else {
                return false;
            }
        }
    }

}

性能

目标

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

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

说明:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

思路

数组 nums 的元素表示可以向后跳跃的最大长度，求从 0 跳到 n - 1 所需的最小跳跃次数。

定义 dp[i] 表示到达下标 i 所需的最小跳跃次数，状态转移方程为 dp[i + k] = min(dp[i] + 1)，其中 k ∈ [1, nums[i]]。

代码

/**
 * @date 2024-03-07 17:14
 */
public class CanJumpII45 {

    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 0x3f3f3f);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + nums[i]; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

}

性能

目标

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

说明:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

思路

有一个数组 candidates，用 candidates 中的元素值组成目标值 target，返回每种组合的元素列表。数组中的每个元素在每种组合中只能使用一次。

考虑是否选择某个元素，可能的组合有 2^n 种。但是题目有条件限制，要求组合元素值之和等于target，那么如果组合的和大于 target 可以提前返回。因此可以将 candidates 从小到大排序，回溯。关键是如何去除重复组合，对于相同的元素，只关心取的个数，因此如果不选某个元素，后续相同的元素也都不能选。

代码

/**
 * @date 2025-01-26 15:24
 */
public class CombinationSum40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, 0, target, candidates, path, res);
        return res;
    }

    public void dfs(int index, int sum, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            List<Integer> tmp = new ArrayList<>(path);
            res.add(tmp);
            return;
        }
        if (index == candidates.length || sum > target) {
            return;
        }
        int cur = candidates[index];
        path.add(cur);
        dfs(index + 1, sum + cur, target, candidates, path, res);
        path.remove(path.size() - 1);
        index++;
        // 如果不选当前的值，也同样不选后续所有相同的值
        // 对于相同的值，只考虑选了几个，如果这里不跳过，就会出现重复
        // 比如有4个相同的值，选 选 不选 不选，如果允许后续再次选择，就会出现
        // 选 不选 不选 选、
        // 选 不选 选 不选
        // 不选 选 选 不选、
        // 不选 选 不选 选、
        // 不选 不选 选 选、
        while (index < candidates.length && cur == candidates[index]) {
            index++;
        }
        dfs(index, sum, target, candidates, path, res);
    }
}

性能

目标

给你一个 下标从 1 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

• 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i + 1] 的水果。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：
用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。
免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。
免费获得第 4 个水果。
免费获得第 5 个水果。
用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。
免费获得第 7 个水果。
免费获得第 8 个水果。
请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

说明：

1 <= prices.length <= 1000
1 <= prices[i] <= 10^5

思路

有 n 个水果，其价格由 prices 表示，当我们以 prices[i] 枚金币购买了第 i + 1 个苹果时，我们可以免费获得下标 [i + 1, i + i + 1] 的 所有 个苹果（当然也可以购买以获得后面的奖励），求获得全部苹果所需的最少硬币。

最直接的想法是记忆化搜索。

代码

/**
 * @date 2025-01-24 9:07
 */
public class MinimumCoins2944 {

    public int minimumCoins(int[] prices) {
        int[] mem = new int[2 * prices.length + 3];
        Arrays.fill(mem, Integer.MAX_VALUE);
        return dfs(0, prices, mem, 0);
    }

    public int dfs(int index, int[] prices, int[] mem, int cost) {
        int n = prices.length;
        if (index >= n) {
            return cost;
        }
        int res = cost + prices[index];
        int next = index * 2 + 2;
        if (mem[next] == Integer.MAX_VALUE) {
            mem[next] = dfs(next, prices, mem, 0);
        }
        int remainder = mem[next];
        if (remainder == 0) {
            return res;
        }
        for (int i = index + 1; i < n && i <= index * 2 + 1; i++) {
            if (mem[i] == Integer.MAX_VALUE) {
                mem[i] = dfs(i, prices, mem, 0);
            }
            remainder = Math.min(mem[i], remainder);
        }
        return res + remainder;
    }

}

性能