240423 leetcode exercises

240423 leetcode exercises

@jarringslee

33. 搜索旋转排序数组

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1], target = 0
输出：-1

​ 这到底在问什么？

​ 这道题本质上是在考 如何在一个被「折叠」过的有序数组里，用 O(log n) 时间准确地定位一个元素。具体来说
​ 给你一个原本严格升序、互不相同的数组 nums，它被在某个位置 k “旋转”——把前半段搬到后面，变成：

[nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]

​ 然后给定一个 target，让你在这个“折叠”后的数组里，仍然用对数时间找到 target 的位置（下标），如果不存在就返回 -1。

​ 我们需要不超时、通过比较大小快速定位数组元素，该用怎样的查找方法？答案已经呼之欲出了，就是二分查找。

​ 我们首先回顾一下二分查找的大致思路：

取左右边界 --> 根据左右边界取中间值mid --> 将mid和给定值比较 --> 更新边界，再取mid进行比较

​ 本题在此基础上对数组进行了有序旋转，旋转后我们需要先判断哪一半（左侧或右侧）是有序的，或者先找到“折叠点”（最小值），再在对应子区间中二分。

🔁先找旋转点 再分段二分

1. 找最小值下标（旋转点）

我们可以对 nums 做一次二分，找到“从末尾看，第一个比末尾大的元素位置”——也就是旋转前的最后一个元素位置，再加 1 就是最小值下标。

• 循环不变量
  • nums[left] ≥ nums[n-1]（left 在第一段或 等于n-1）
  • nums[right] < nums[n-1]（right 在最小值及其右侧）

2. 在对应区间做二分查找

再写一个常规的 lowerBound 函数，在开区间里寻找第一个 ≥ target 的位置，最后判断是否等于 target。

// 在开区间 (-1, n-1) 中找最小值的位置
int findMin(int* nums, int numsSize) {int left = -1, right = numsSize - 1;while (left + 1 < right) {int mid = left + (right - left) / 2;// 若 nums[mid] < nums[n-1]，说明 mid 在右半段（最小值左侧）if (nums[mid] < nums[numsSize - 1]) {right = mid;} else {left = mid;}}return right; // 最小值下标
}// 在 nums[left+1..right-1]（开区间）里找 target
int lowerBound(int* nums, int left, int right, int target) {while (left + 1 < right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid;} else {left = mid;}}return (nums[right] == target) ? right : -1;
}int search(int* nums, int numsSize, int target) {int rot = findMin(nums, numsSize);// 如果 target 比末尾元素大，则落在第一段 [0..rot-1]if (target > nums[numsSize - 1]) {return lowerBound(nums, -1, rot, target);}// 否则落在第二段 [rot..n-1]return lowerBound(nums, rot - 1, numsSize, target);
}

时间复杂度

• findMin 做一次二分 → O(log n)
• lowerBound 最坏再做一次二分 → O(log n)
• 总体 O(log n)

空间复杂度 O(1)

🔁利用布尔变量进行一次二分

一次遍历式二分，在每次判断 mid 所在的那段是否有序，并结合 target 落在哪一段来决定向左收窄还是向右收窄。

• 每次二分都先看 nums[left] ≤ nums[mid]：若成立，说明左边是连续递增的；否则右边是连续递增的。
• 再判断 target 是否落在有序那段范围内，决定下一步收缩哪一半。

1. 初始化

​ 我们需要维护区间 [left, right]，在它之内如果有解，我们始终不把它丢掉。循环条件是 left <= right，保证当区间为空时退出。

2. 进入循环体

​ 用二分查找的思路迭代，不断更新mid值并和目标值进行检查。如果 nums[left] <= nums[mid]，说明 左半段 是升序；否则右半段 就是升序，最后根据 target 落点，收缩哪一半：

​ 若左半段有序，即 nums[left] ≤ target < nums[mid]，说明 target 在这段，就把 right = mid - 1；否则去右半段，left = mid + 1。反之，右半段有序，上述操作相反。

int search(int* nums, int numsSize, int target) {int left = 0, right = numsSize - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid;// 判断左半段 [left..mid] 是否有序if (nums[left] <= nums[mid]) {// target 在这有序段内则缩右边界，否则去右段if (nums[left] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}}// 否则右半段 [mid..right] 必有序else {if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;
}

时间复杂度 O(log n)，每次都能砍掉一半区间
空间复杂度 O(1)

LCR 009. 乘积小于 K 的子数组

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1：

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2：

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

​ 这道题到比较好理解。

​ 在紧张刺激的考核中，我首先想到的是利用双指针遍历。但是为了确保万无一失，我先试用了暴力解法：

​ 其实在两次便利的基础上我还优化了一下：

​ 我让内层循环从末尾开始倒着遍历。如果发现这段元素的成绩小于目标值，那么说明从现在开始到内层循环结束所有的可能都符合条件，直接让计数器增加相应的次数并跳出循环。

int fornum(int* num, int a, int b, int k){int n = 1;while (a <= b){n *= num[a++];if(n >= k) return -1;}return 1;
}//写一个判断目标区间内所有元素之积是否小于目标值的小函数int numSubarrayProductLessThanK(int* nums, int numsSize, int k){if (k == 0) return 0;int cjx = 0;for (int i = 0; i <= numsSize - 1; i++){if (nums[i] < k) cjx++;}for (int i = 0; i < numsSize - 1; i++ ){int j = numsSize - 1;while(j >= i){if (fornum(nums, i, j, k) == 1){cjx += (j - i);break;}j--;}}return cjx;
} 

不出意料地还是超时了。

这还想让我怎样。

思考了若干秒。

怎么这么难。

于是我开始探索更高效的做法。

🔁前缀对数 + 二分查找

这个利用对数值二分法竟然是官方第一题解。现在对程序员数学要求都这么高吗。

• 直接比较 子数组乘积 容易爆栈/溢出，也无法快速定位；

• 利用对数性质，将乘积转为加法,预先计算 对数前缀和;

• 对于每个右端点 r（对应代码中的 j+1），希望找到最小的 l

  这正好是一个 后缀区间里第一个大于某个值的下标 问题，可用二分解决。

int numSubarrayProductLessThanK(int* nums, int numsSize, int k){if (k <= 1) return 0;                              // k<=1 时，任何正数乘积都 ≥1，不可能 < k// 1) 构造对数前缀和double *logPrefix = malloc(sizeof(double) * (numsSize + 1));logPrefix[0] = 0;for (int i = 0; i < numsSize; i++) {logPrefix[i + 1] = logPrefix[i] + log(nums[i]);}double target = log(k);int count = 0;// 2) 对每个右端点 j，二分在 logPrefix[0..j] 中找第一个 > (logPrefix[j+1] - log k)for (int j = 0; j < numsSize; j++) {double need = logPrefix[j + 1] - target + 1e-12; int l = 0, r = j + 1, idx = j + 1;while (l <= r) {int mid = (l + r) / 2;if (logPrefix[mid] > need) {idx = mid;r = mid - 1;} else {l = mid + 1;}}// [idx..j] 开始的每个子数组都满足乘积<kcount += (j + 1 - idx);}free(logPrefix);return count;
}

复杂度分析

• 时间：
  • 构造前缀和 O(n)；
  • 对每个 j 做一次二分 O(log n)，共 O(n log n)。
• 空间：O(n)（存放 logPrefix）。

数学好的话看了一遍答案大概就能理清这个取对数的思路了，但是相信大家在实战中也很难打出来，那么这时候有人就要问了，主播主播取对数的高数方法还是太吃操作了，有没有简单又强势的不吃数学基础低复杂度方法？

有的兄弟有的。

🔁双指针（滑动窗口）

• 用一个可变区间 [i..j]，维护区间内的乘积 prod；

• 当 prod < k 时，所有以 j 为右端点且左端点位于 i…j 的子数组都符合条件，数量为 j - i + 1；

• 如果 prod ≥ k，则不断 右移左指针 i，并在 prod 上除去 nums[i]，直至 prod < k 或 i > j。

  其实就是暴力解法的变种，增加了一些限制条件，可以省去很多不必要的步骤，提高效率。

int numSubarrayProductLessThanK(int* nums, int numsSize, int k){if (k <= 1) return 0;  // 同样，k<=1 时无解int count = 0;long prod = 1;int i = 0;for (int j = 0; j < numsSize; j++) {prod *= nums[j];// 当乘积不满足时，收缩左指针while (i <= j && prod >= k) {prod /= nums[i];i++;}// 现在 [i..j] 内任意左端点都能满足 prod<kcount += (j - i + 1);}return count;
}

复杂度分析

• 时间：
  • 每个 j 只进一次窗、每个 i 最多出一次窗，整体 O(n)。
• 空间：O(1)。

要么把所有数字都取对数，变成前缀和然后对每个右端点二分，复杂度大概是 n·log n；要么更直接就是滑动窗口，维护一个乘积，只要它大于等于 k 就把左指针右移、除掉旧元素，保证窗口内乘积始终小于 k，这样每个数字只进出窗口一次，O(n) 秒解。