No.1 Count Negative Numbers in a Sorted Matrix ★解题思路

数据范围很小, 所以我们直接遍历整个矩阵, 统计负数的数量是完全可行的. 时间复杂度: o(nm)

代码展示

class Solution { 
   public int countNegatives(int[][] grid) { 
       int res = 0; 
       for (int[] line : grid) { 
           for (int num : line) { 
               res += num < 0 ? 1 : 0; 
           } 
       } 
       return res; 
   } 
}

解题思路

不过题目又说明: 每一行的元素单调不增, 那么我们就可以二分查找第一个负数(或最后一个非负数)的位置从而确定这一行内负数的个数, 时间复杂度 o(mlogn)

代码展示

class Solution { 
   public int countNegatives(int[][] grid) { 
       int res = 0; 
       for (int[] line : grid) { 
           res += line.length - firstNeg(line); 
       } 
       return res; 
   } 
   private int firstNeg(int[] line) { 
       // 二分查找 line 第一个负数的位置, 返回下标 
       // 若不存在则返回 line.length 
       int l = 0, r = line.length; 
       while (l + 1 < r) { 
           int mid = (l + r) / 2; 
           if (line[mid] >= 0) { 
               l = mid; 
           } else { 
               r = mid; 
           } 
       } 
       return line[l] < 0 ? l : r; 
   } 
}

No.2 Product of the Last K Numbers ★解题思路

使用前缀积数组可以做到o(1)的插入与查询.

不过如果添加的数字中有 0, 那么直接使用前缀积可能会有除零的风险.

所以当我们遇见 0 的时候, 就抛弃之前的前缀积数组. 对应地, 在查询的时候, 如果 k 比当前的前缀积数组要长, 说明倒数 k 个数字中一定会包含 0, 直接返回 0 即可.

代码展示

class ProductOfNumbers { 

   private List<Integer> list; 

   public ProductOfNumbers() { 
       list = new ArrayList<Integer>(){{add(1);}}; 
   } 

   public void add(int num) { 
       if (num == 0) { 
           list = new ArrayList<Integer>(){{add(1);}};             
       } else { 
           list.add(num * list.get(list.size() - 1)); 
       } 
   } 

   public int getProduct(int k) { 
       if (list.size() > k) { 
           return list.get(list.size() - 1) / list.get(list.size() - k - 1); 
       } else { 
           return 0; 
       } 
   } 
}

No.3 Maximun Number of Events That Can Be Attended ★解题思路

核心思路: 贪心法, 在每一天能参加的并且还未参加过的会议中, 选取那个结束最早的会议就可以了.

具体的实现, 首先给所有的会议按照开始时间排序, 然后定义一个堆来维护当前时间能参加的会议, 堆按照会议的结束时间排序.

我们枚举时间, 一天一天地枚举, 如果这一天有会议开始, 就把这些会议添加到堆中. 这一天要参加的会议就是堆顶的会议, 就是当前能参加的会议中结束最早的.

代码展示

class Event { 
   public int start, end; 

   public Event(int start, int end) { 
       this.start = start; 
       this.end = end; 
   } 
} 

class Solution { 
   public int maxEvents(int[][] events) { 
       Arrays.sort(events, (int[] o1, int[] o2) -> { 
           return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]; 
       }); 
       PriorityQueue<Event> heap = new PriorityQueue<>((Event a, Event b) -> { 
           return a.end == b.end ? a.start - b.start : a.end - b.end; 
       }); 
       int res = 0; 
       // now 表示当前时间点, 每次循环递增 
       // 循环结束的条件是: 即没有还没开始的会议, 也没有还没结束的会议 
       // 即 i 枚举完了, heap 也为空的时候 
       for (int i = 0, now = 0; i < events.length || !heap.isEmpty(); now++) { 
           // 把已经开始的会议添加到堆中 
           while (i < events.length && now >= events[i][0]) { 
               heap.add(new Event(events[i][0], events[i][1])); 
               i++; 
           } 
           // 从堆中把已经结束的会议移除 
           while (!heap.isEmpty() && heap.peek().end < now) { 
               heap.poll(); 
           } 
           // 若堆不为空, 则参加堆顶的会议 
           if (!heap.isEmpty()) { 
               heap.poll(); 
               res++; 
           } 
       } 
       return res; 
   } 
}

No.4 Construct Target Array Witn Multiple Sums

★解题思路

这道题目很有趣, 其实并不难. 能想到: 总和一定是单调递增的, 也就是说更大的数字一定更晚被构造出来.

正着去构造可能并不容易, 但是我们可以倒着把数组还原成全 1.

我们拿出序列中最大的元素 max, 假设当前的总和是 sum. 可以知道之前的序列元素之和就是 max, 那么可以计算出这个位置的元素被设定为 max 之前是 max - (sum - max). 那么我们就完成了一次还原.

重复这样的过程直到数组全为 1 即可. 而非法情况就是推导当前的 max 的上一个值得到的是小于 1 的数, 或者 max 没有任何变化, 即 max - (sum - max) < 1 || max == sum, 此时应该返回 false.

具体的实现我们可以使用堆, 快速得到序列中最大的值.

代码展示

class Solution { 
   public boolean isPossible(int[] target) { 
       PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); 
       int sum = 0; 
       for (int num : target) { 
           // 堆中储存的是大于 1 的元素, 表示还需要继续还原 
           if (num > 1) {   
               heap.add(num); 
           } 
           sum += num; 
       } 
       // 当堆不为空时, 表示还有元素需要还原 
       while (!heap.isEmpty()) { 
           int max = heap.poll();          // 取出最大 
           int last = max * 2 - sum;       // 计算该元素的上一个值 
           if (last < 1 || last == max) {  // 小于 1 或无变化, 非法 
               return false; 
           } 
           sum += last - max;              // 维护 sum 
           if (last != 1) {                // 非 1, 还需要继续还原, 加入堆 
               heap.add(last); 
           } 
       } 
       return true; 
   } 
}

解题思路

不过其实我们可以不必将 max 还原一次得到的 last 立即插入堆中, 因为此时 last 可能仍然比堆中任何一个元素大, 那么我们就白白进行了一次 add 和 poll 浪费时间.

所以下面是优化之后的写法, 取出 max 之后将其还原直到它不比堆顶大, 然后再把它插入堆. 下面是优化之后的代码 (12ms=>9ms 整体速度并不明显):

代码展示

class Solution { 
   public boolean isPossible(int[] target) { 
       PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); 
       int sum = 0; 
       for (int num : target) { 
           if (num > 1) { 
               heap.add(num); 
           } 
           sum += num; 
       } 
       while (!heap.isEmpty()) { 
           int max = heap.poll(); 
           while (max > 1 && (heap.isEmpty() || max >= heap.peek())) { 
               int last = max * 2 - sum; 
               if (last <= 0 || last == max) { 
                   return false; 
               } 
               sum += last - max; 
               max = last; 
           } 
           if (max != 1) { 
               heap.add(max); 
           } 
       } 
       return true; 
   }

}