上岸算法，我们直击上岸

关注我们，第一时间获得大厂面试真题讲解

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; 
   } 
}