前言
心中充满了痛苦与心酸，悲伤与寂寞。
但是，那样的感情，我现在也渴望毫无保留地去珍惜。
因为一旦这些感情都全部消失的时候，我想我就会彻底的不复存在了。
整体评价
手速赛, t4挺有意思的。
1. 与对应负数同时存在的最大正整数
排序+双指针
Java
go
class Solution {
public int findMaxK(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] == -nums[j]) {
return Math.abs(nums[j]);
} else if (Math.abs(nums[i]) > Math.abs(nums[j])) {
i++;
} else {
j--;
}
}
return -1;
}
}2. 反转之后不同整数的数目
模拟，不解释
Java
go
class Solution {
int reverse(int v) {
int res = 0;
while (v > 0) {
int d = v % 10;
res = res * 10 + d;
v /= 10;
}
return res;
}
public int countDistinctIntegers(int[] nums) {
Set<Integer> tree = new TreeSet<>();
for (int v: nums) {
tree.add(v);
tree.add(reverse(v));
}
return tree.size();
}
}3. 反转之后的数字和
直接暴力解了，没细想。
所谓正难则反，就是先预处理在1e5范围内有效的数。
毕竟1e5，这才多大，属于打表做法。
Java
go
class Solution {
static boolean ok = false;
static boolean[] used;
static int reverse(int v) {
int res = 0;
while (v > 0) {
int d = v % 10;
res = res * 10 + d;
v /= 10;
}
return res;
}
static void init() {
if (ok) return;
used = new boolean[100001];
for (int i = 0; i <= 100000; i++) {
int ts = i + reverse(i);
if (ts <= 100000) {
used[ts] = true;
}
}
ok = true;
}
// *)
public boolean sumOfNumberAndReverse(int num) {
init();
return used[num];
}
}4. 统计定界子数组的数目
方法一： 滑动窗口解
一般区间计数问题，等价于滑窗解法，通俗一点，就是固定左/右边界，寻求满足的数量，最后枚举遍历整个区间的左/右端点即可。
给个滑窗版本（但不需要分割区间）
引入dp数组用于保存有效的最长边界
滑动引入三个变量，
- minCnt(等于minK的数量)
- maxCnt(等于maxK的数量)
- notCnt(不在[minK, maxK]范围内的数量)
在这个前提下，不切割子区间，也可以利用滑窗来计算区间数量.
Java
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long ans = 0;
// 区间计数==滑动窗口
int n = nums.length;
int minCnt = 0, maxCnt = 0, notCnt = 0;
// *) 预处理
int[] dp = new int[n];
dp[n - 1] = (nums[n - 1] >= minK && nums[n - 1] <= maxK ? n - 1 : -1);
for (int i = n - 2; i >= 0; i--) {
if (nums[i] >= minK && nums[i] <= maxK) {
dp[i] = Math.max(dp[i + 1], i);
} else {
dp[i] = -1;
}
}
int j = 0;
for (int i = 0; i < n; i++) {
int v = nums[i];
if (v == minK) {
minCnt++;
}
if (v == maxK) {
maxCnt++;
}
if (v < minK || v > maxK) {
notCnt++;
}
while (j <= i && notCnt > 0) {
if (nums[j] == minK) minCnt--;
if (nums[j] == maxK) maxCnt--;
if (nums[j] < minK || nums[j] > maxK) notCnt--;
j++;
}
// *) 进行判定
while (j <= i && minCnt > 0 && maxCnt > 0 && notCnt == 0) {
ans += (dp[i] - i + 1);
if (nums[j] == minK) minCnt--;
if (nums[j] == maxK) maxCnt--;
if (nums[j] < minK || nums[j] > maxK) notCnt--;
j++;
}
}
return ans;
}
}方法二： 容斥解？
这题的核心思想是
合法的区间数=全部区间数-不合法的区间
那何为不合法的区间数呢？
就是minK和maxK两数的中间子区间不合法，以及minK/maxK作为中心点，像两边扩散的区间组合.
Java
class Solution {
long solve(int[] nums, int s, int e, int minK, int maxK) {
int m = (e - s + 1);
long ans = 1l * (m + 1) * m / 2;
// 取反
int prev = s - 1;
int i = s;
while (i <= e) {
int minPos = -1, maxPos = -1;
int j = i;
while (j <= e) {
int v = nums[j];
if (v == minK) minPos = j;
if (v == maxK) maxPos = j;
if (minPos == -1 || maxPos == -1) {
j++;
} else {
break;
}
}
int d = j - i - 1;
ans = ans - 1l * (d + 1) * d / 2;
if (minK != maxK) {
ans = ans - 1l * (i - prev) * (d + 1);
}
if (j != e + 1) {
prev = (nums[j] == minK) ? maxPos : minPos;
}
i = j;
if (minK == maxK) {
i++;
}
}
return ans;
}
public long countSubarrays(int[] nums, int minK, int maxK) {
long ans = 0;
int i = 0;
while (i < nums.length) {
int v = nums[i];
if (v < minK || v > maxK) {
i++;
continue;
} else {
boolean f1 = false, f2 = false;
int j = i;
while (j < nums.length) {
if (nums[j] < minK || nums[j] > maxK) {
break;
}
if (nums[j] == minK) f1 = true;
if (nums[j] == maxK) f2 = true;
j++;
}
if (f1 && f2) {
ans += solve(nums, i, j - 1, minK, maxK);
}
i = j;
}
}
return ans;
}
}评论 (11)
