前言
最后我想再拜讬你一件事就好，但愿你能忘了我。
整体评价
涉及的知识点比较多，t2是撮合交易的核心逻辑模拟，t3是二分经典题，t4是 0-1Trie的使用。
真心不错，推荐这场周赛。
1. 最大升序子数组和
核心是贪心, 实现方式是滑窗, 时间复杂度为
Java
class Solution {
public int maxAscendingSum(int[] nums) {
int ans = 0;
int i = 0;
while (i < nums.length) {
int acc = 0;
int prev = nums[i];
int j = i + 1;
acc += nums[i];
while (j < nums.length && prev < nums[j]) {
acc += nums[j];
prev = nums[j];
j++;
}
ans = Math.max(ans, acc);
i = j;
}
return ans;
}
}2. 积压订单中的订单总数
有一定代码量的模拟题，诠释了交易系统的撮合逻辑。
具体的做法，就是分别维护buy和sell的两个优先队列，注意大小堆，当然multiset也可以。
Java
class Solution {
// 核心撮合交易
public int getNumberOfBacklogOrders(int[][] orders) {
PriorityQueue<int[]> buy = new PriorityQueue<>(Comparator.comparing(x -> -x[0]));
PriorityQueue<int[]> sell = new PriorityQueue<>(Comparator.comparing(x -> x[0]));
long total = 0;
for (int[] order: orders) {
if (order[2] == 0) {
// buy
while (!sell.isEmpty() && sell.peek()[0] <= order[0]) {
int[] cur = sell.poll();
total -= cur[1];
if (cur[1] > order[1]) {
sell.offer(new int[] {cur[0], cur[1] - order[1]});
total += (cur[1] - order[1]);
order[1] = 0;
break;
} else if (cur[1] == order[1]) {
order[1] = 0;
break;
} else {
order[1] -= cur[1];
}
}
if (order[1] > 0) {
buy.offer(new int[] {order[0], order[1]});
total += order[1];
}
} else {
// sell
while (!buy.isEmpty() && buy.peek()[0] >= order[0]) {
int[] cur = buy.poll();
total -= cur[1];
if (cur[1] > order[1]) {
buy.offer(new int[] {cur[0], cur[1] - order[1]});
total += (cur[1] - order[1]);
order[1] = 0;
break;
} else if (cur[1] == order[1]) {
order[1] = 0;
break;
} else {
order[1] -= cur[1];
}
}
if (order[1] > 0) {
sell.offer(new int[] {order[0], order[1]});
total += order[1];
}
}
}
return (int)(total % 10_0000_0007l);
}
}3. 有界数组中指定下标处的最大值
本质是枚举，不过这题特殊性，使其具备单调性，因此使用二分。
核心：二分+贪心
Java
class Solution {
// 求区间最小
long smallest(int n, int m) {
if (n <= m) return 1l * (m - n + 1 + m) * n / 2;
return (n - m) * 1l + 1l * (m + 1) * m / 2;
}
// 二分+贪心
boolean check(int maxn, int n, int index, int maxSum) {
long ls = smallest(index, maxn - 1);
long rs = smallest(n - index - 1, maxn - 1);
return ls + maxn + rs <= maxSum;
}
public int maxValue(int n, int index, int maxSum) {
int ans = 1;
int l = 1, r = maxSum;
while (l <= r) {
int m = l + (r - l) / 2;
if (check(m, n, index, maxSum)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}这题需要注意边界，感觉是道不错的题，甚至可以作为面试题。
4. 统计异或值在范围内的数对有多少
因为是异或，所以必然是 0-1trie
那区间范围查询，怎么搞呢？能否像线段树那样，实现的时间复杂度。
更准确地说，0-1Trie像二叉计数树。
Java
class Solution {
static class Trie {
// 2 ^ 15 = 32768 > 20000
static final int HIGH = 15;
Trie[] child = new Trie[2];
int cnt;
public static void add(Trie root, int val) {
Trie cur = root;
cur.cnt++;
for (int i = HIGH - 1; i >= 0; i--) {
int p = (val >> i) & 0x01;
if (cur.child[p] == null) {
cur.child[p] = new Trie();
}
cur = cur.child[p];
cur.cnt++;
}
}
// *)
public static int query(Trie root, int low, int high, int val) {
return query2(root, low, high, 0, val, HIGH);
}
// 扩展查询接口
public static int query2(Trie root, int low, int high, int curVal, int val, int depth) {
// 节点出口
if (depth == 0) {
if (curVal >= low && curVal <= high) return root.cnt;
return 0;
}
// 剪枝(很重要)
int range = (1 << depth) - 1;
if (low <= curVal && curVal + range <= high) {
return root.cnt;
} else if (curVal > high) {
return 0;
} else if (curVal + range < low) {
return 0;
}
int ans = 0;
int p = (val >> (depth - 1)) & 0x01;
int lVal = curVal + ((0^p) << (depth - 1));
int rVal = curVal + ((1^p) << (depth - 1));
// 左节点
if (root.child[0] != null) {
ans += query2(root.child[0], low, high, lVal, val, depth - 1);
}
// 右节点
if (root.child[1] != null) {
ans += query2(root.child[1], low, high, rVal, val, depth - 1);
}
return ans;
}
}
// 感觉像0-1 trie的做法
public int countPairs(int[] nums, int low, int high) {
Trie root = new Trie();
for (int v: nums) {
Trie.add(root, v);
}
int ans = 0;
for (int v: nums) {
ans += Trie.query(root, low, high, v);
}
// 注意这边需要除以2，因为(0, 1) 和 (1, 0) 只统计一次
return ans / 2;
}
}评论 (2)
