No.1最大升序子数组和
解题思路
注意该题目的子数组是连续的。因此枚举起始位置即可。
代码展示
class Solution {
? ? public int maxAscendingSum(int[] nums) {
? ? ? ? int res = nums[0];
? ? ? ? for (int start = 0; start < nums.length; start++) {
? ? ? ? ? ? int sum = nums[start];
? ? ? ? ? ? for (int i = start + 1; i < nums.length; i++) {
? ? ? ? ? ? ? ? if (nums[i] > nums[i - 1]) {
? ? ? ? ? ? ? ? ? ? sum += nums[i];
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? res = Math.max(res, sum);
? ? ? ? }
? ? ? ? return res;
? ? }
}
No.2 积压订单中的订单总数
解题思路
使用?PriorityQueue?或者?TreeMap?维护两类挤压订单即可。
代码展示
class Solution {
? ? public int getNumberOfBacklogOrders(int[][] orders) {
? ? ? ? TreeMap<Integer, Integer> toSell = new TreeMap<Integer, Integer>();
? ? ? ? TreeMap<Integer, Integer> toBuy = new TreeMap<Integer, Integer>();
? ? ? ? for (var order : orders) {
? ? ? ? ? ? if (order[2] == 0) {
? ? ? ? ? ? ? ? // buy
? ? ? ? ? ? ? ? while (order[1] > 0) {
? ? ? ? ? ? ? ? ? ? var entry = toSell.firstEntry();
? ? ? ? ? ? ? ? ? ? if (entry == null || entry.getKey() > order[0]) {
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? int cnt = Math.min(entry.getValue(), order[1]);
? ? ? ? ? ? ? ? ? ? order[1] -= cnt;
? ? ? ? ? ? ? ? ? ? if (cnt == entry.getValue()) {
? ? ? ? ? ? ? ? ? ? ? ? toSell.remove(entry.getKey());
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? toSell.put(entry.getKey(), entry.getValue() - cnt);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? // break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (order[1] > 0) {
? ? ? ? ? ? ? ? ? ? toBuy.put(order[0], order[1] + toBuy.getOrDefault(order[0], 0));
? ? ? ? ? ? ? ? }
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? // sell
? ? ? ? ? ? ? ? while (order[1] > 0) {
? ? ? ? ? ? ? ? ? ? var entry = toBuy.lastEntry();
? ? ? ? ? ? ? ? ? ? if (entry == null || entry.getKey() < order[0]) {
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? int cnt = Math.min(entry.getValue(), order[1]);
? ? ? ? ? ? ? ? ? ? order[1] -= cnt;
? ? ? ? ? ? ? ? ? ? if (cnt == entry.getValue()) {
? ? ? ? ? ? ? ? ? ? ? ? toBuy.remove(entry.getKey());
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? toBuy.put(entry.getKey(), entry.getValue() - cnt);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? // break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (order[1] > 0) {
? ? ? ? ? ? ? ? ? ? toSell.put(order[0], order[1] + toSell.getOrDefault(order[0], 0));
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int res = 0;
? ? ? ? for (var entry : toSell.entrySet()) {
? ? ? ? ? ? res = (res + entry.getValue()) % 1000000007;
? ? ? ? }
? ? ? ? for (var entry : toBuy.entrySet()) {
? ? ? ? ? ? res = (res + entry.getValue()) % 1000000007;
? ? ? ? }
? ? ? ? return res;
? ? }
}
No.3 有界数组中指定下标处的最大值
解题思路
二分答案。当指定下标处的值确定后，贪心地令其他元素尽可能小即可，所以就是等差数列求和。
代码展示
class Solution {
? ? public int maxValue(int n, int index, int maxSum) {
? ? ? ? long l = 0, r = maxSum;
? ? ? ? while (l + 1 < r) {
? ? ? ? ? ? long mid = (l + r) / 2;
? ? ? ? ? ? if (check(mid, index, maxSum, n)) {
? ? ? ? ? ? ? ? l = mid;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? r = mid;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return (int) (check(r, index, maxSum, n) r : l);
? ? }
? ? long sum(long start, long count) {
? ? ? ? if (count <= 0) {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? if (start < count) {
? ? ? ? ? ? return (start + 1) * start / 2 + (count - start);
? ? ? ? }
? ? ? ? return (start + start - count + 1) * count / 2;
? ? }
? ? boolean check(long value, long index, long maxSum, long n) {
? ? ? ? long left = index;
? ? ? ? long right = n - index - 1;
? ? ? ? return sum(value - 1, left) + sum(value - 1, right) + value <= maxSum;
? ? }
}
No.4 统计异或值在范围内的数对有多少
解题思路
求?[low, high]?区间内的等同于求?[low, inf)?再减去?(high, inf)。
因此问题转换成求异或值大于给定数值的数对数量。使用字典树即可。
代码展示
class Solution {
? ? public int countPairs(int[] nums, int low, int high) {
? ? ? ? return (int) (solve(nums, low - 1) - solve(nums, high));
? ? }
? ? static class TrieTree {
? ? ? ? TrieTree[] next = new TrieTree[2];
? ? ? ? int count = 1;
? ? }
? ? long solve(int[] nums, int m) {
? ? ? ? TrieTree trieTree = buildTrieTree(nums);
? ? ? ? long result = 0;
? ? ? ? for (int i = 0; i < nums.length; i++) {
? ? ? ? ? ? result += queryTrieTree(trieTree, nums[i], m, 31);
? ? ? ? }
? ? ? ? return result / 2;
? ? }
? ? long queryTrieTree(TrieTree trieTree, int a, int m, int index) {
? ? ? ? if (trieTree == null)
? ? ? ? ? ? return 0;
? ? ? ? TrieTree current = trieTree;
? ? ? ? for (int i = index; i >= 0; i--) {
? ? ? ? ? ? int aDigit = (a >> i) & 1;
? ? ? ? ? ? int mDigit = (m >> i) & 1;
? ? ? ? ? ? if (aDigit == 1 && mDigit == 1) {
? ? ? ? ? ? ? ? if (current.next[0] == null)
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? current = current.next[0];
? ? ? ? ? ? } else if (aDigit == 0 && mDigit == 1) {
? ? ? ? ? ? ? ? if (current.next[1] == null)
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? current = current.next[1];
? ? ? ? ? ? } else if (aDigit == 1 && mDigit == 0) {
? ? ? ? ? ? ? ? long p = queryTrieTree(current.next[1], a, m, i - 1);
? ? ? ? ? ? ? ? long q = current.next[0] == null 0 : current.next[0].count;
? ? ? ? ? ? ? ? return p + q;
? ? ? ? ? ? } else if (aDigit == 0 && mDigit == 0) {
? ? ? ? ? ? ? ? long p = queryTrieTree(current.next[0], a, m, i - 1);
? ? ? ? ? ? ? ? long q = current.next[1] == null 0 : current.next[1].count;
? ? ? ? ? ? ? ? return p + q;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return 0;
? ? }
? ? TrieTree buildTrieTree(int[] a) {
? ? ? ? TrieTree trieTree = new TrieTree();
? ? ? ? for (int i = 0; i < a.length; i++) {
? ? ? ? ? ? TrieTree current = trieTree;
? ? ? ? ? ? for (int j = 31; j >= 0; j--) {
? ? ? ? ? ? ? ? int digit = (a[i] >> j) & 1;
? ? ? ? ? ? ? ? if (current.next[digit] == null) {
? ? ? ? ? ? ? ? ? ? current.next[digit] = new TrieTree();
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? current.next[digit].count++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? current = current.next[digit];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return trieTree;
? ? }
}