No. 1旅行终点站

★解题思路

题目给定了若干条有向边, 最终没有出度的点就是终点站.

既然题目保证有解, 那么我们就直接查找那个没有做过出发站的站点即可.

代码展示

class Solution { 
   public String destCity(List<List<String>> paths) { 
       Set<String> set = new HashSet<>(); 
       for (var path : paths) { 
           set.add(path.get(0));  // 将做过出发站的站点加入集合 
       } 
       for (var path : paths) { 
           if (!set.contains(path.get(1))) { 
               return path.get(1);  // 没有做过出发站, 直接返回 
           } 
       } 
       return "";  // 题目保证有解, 不会执行到这一步 (但是不加这一句会 CE) 
   } 
}

No.2 是否所有 1 都至少相隔 k 个元素

★解题思路

记录上一次 1 出现的位置, 遍历一次即可.

代码展示

class Solution { 
   public boolean kLengthApart(int[] nums, int k) { 
       int last = - k - 1;  // 初始值设置为 - k - 1, 以防 nums[0] 是 1 的时候返回 false 
       for (int i = 0; i < nums.length; i++) { 
           if (nums[i] == 1) { 
               if (i - last <= k) { 
                   return false; 
               } 
               last = i; 
           } 
       } 
       return true; 
   } 
}

No.3 绝对差不超过限制的最长连续子数组

★解题思路

该题目需要用双指针 + 单调队列. 双指针用于维护当前的最大合法区间, 单调队列用于区间移动的时候能够快速找到下一个最大值和最小值.

代码展示

class Solution { 
   public int longestSubarray(int[] nums, int limit) { 
       if (limit < 0) { 
           return 0; 
       } 
       int res = 0; 
       // maxQueue 是当前区间 [l, r) 中的元素的单调下降队列, 因此队首就是最大值 
       // minQueue 是当前区间 [l, r) 中的元素的单调上升队列, 因此队首就是最小值 
       // 单调队列的队首是最大/小值, 第二个则是次大/小值, 第三个则是第三大/小值... 
       LinkedList<Integer> maxQueue = new LinkedList<>(); 
       LinkedList<Integer> minQueue = new LinkedList<>(); 
       for (int l = 0, r = 0; l < nums.length; l++) { 
           // 对于每一个左端点 l, 找到最大的 r 
           while (r < nums.length) { 
               int newMax = maxQueue.size() > 0 ? Math.max(nums[maxQueue.getFirst()], nums[r]) : nums[r]; 
               int newMin = minQueue.size() > 0 ? Math.min(nums[minQueue.getFirst()], nums[r]) : nums[r]; 
               // 若新加一个元素会导致绝对差超过限度, 则终止 
               if (maxQueue.size() > 0 && minQueue.size() > 0 && newMax - newMin > limit) { 
                   break; 
               } 
               // 新加元素前要维护单调队列的单调性 
               while (maxQueue.size() > 0 && nums[maxQueue.getLast()] < nums[r]) { 
                   maxQueue.removeLast(); 
               } 
               while (minQueue.size() > 0 && nums[minQueue.getLast()] > nums[r]) { 
                   minQueue.removeLast(); 
               } 
               maxQueue.addLast(r); 
               minQueue.addLast(r); 
               r++; 
           } 
           res = Math.max(res, r - l); 
           // 检查是否需要删除队首 
           if (maxQueue.size() > 0 && maxQueue.getFirst() == l) { 
               maxQueue.removeFirst(); 
           } 
           if (minQueue.size() > 0 && minQueue.getFirst() == l) { 
               minQueue.removeFirst(); 
           } 
       } 
       return res; 
   } 
}

No.4 有序矩阵中的第 k 个最小数组和

★解题思路

由于数据范围不大, 所以使用优先队列即可通过.

使用优先队列来保存取数情况 (每一行取第几个), 每一种取数情况的下一步就是把某一行的位置向后移动一个, 即有 n 个后继, 而优先队列的优先级就是取数情况所取出来的元素和.

最开始入队的是最小的取数情况, 即每一行都取第一个数. 每出队一个都将它的 n 个后继加入优先队列. 而第 k 个出队的就是答案.

这个过程还需要用 Set 来判断一种取数情况是否已经入队过.

代码展示

// 取数情况 (即一个数组, 记录每一行取数的下标) 
class Arr { 
   public static int len = 0; 
   public int[] arr; 
   public Arr() { 
       arr = new int[len]; 
   } 
   public Arr(Arr a) { 
       arr = Arrays.copyOf(a.arr, len); 
   } 

   @Override 
   public boolean equals(Object o) { 
       if (this == o) return true; 
       if (o == null || getClass() != o.getClass()) return false; 
       Arr arr1 = (Arr) o; 
       return Arrays.equals(arr, arr1.arr); 
   } 

   @Override 
   public int hashCode() { 
       return Arrays.hashCode(arr); 
   } 

   public int getSum(int[][] mat) { 
       int res = 0; 
       for (int i = 0; i < mat.length; i++) { 
           res += mat[i][arr[i]]; 
       } 
       return res; 
   } 
} 

class Solution { 
   public int kthSmallest(int[][] mat, int k) { 
       int n = mat.length, m = mat[0].length; 
       Arr.len = n; 
       Set<Arr> set = new HashSet<>(); 
       PriorityQueue<Arr> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.getSum(mat))); 
       Arr start = new Arr(); 
       heap.add(start); 
       set.add(start); 
       for (int i = 1; i < k; i++) { 
           Arr cur = heap.poll(); 
           for (int j = 0; j < n; j++) { 
               if (cur.arr[j] + 1 == m) continue; 
               Arr nxt = new Arr(cur); 
               nxt.arr[j]++; 
               if (!set.contains(nxt)) { 
                   heap.add(nxt); 
                   set.add(nxt); 
               } 
           } 
       } 
       return heap.peek().getSum(mat); 
   } 
}