No.1 The K Weakest Rpws in a Matrix

解题思路

统计出每一行的 1 的数量, 然后排序, 选出来前 k 小的即可.

由于每一行 1 总是出现在 0 之前, 所以可以使用二分法在 o(logn)的时间复杂度内统计出一行的 1 的数量. 总时间复杂度 o(nlogn)

至于排序, 关键字是 (数量, 行号) 二元组. 或者我们也可以不排序, 而是维护一个大小为 k 的大根堆.

代码展示

class Solution { 
   public int[] kWeakestRows(int[][] mat, int k) { 
       List<List<Integer>> list = new ArrayList<>(); 
       for (int i = 0; i < mat.length; i++) { 
           list.add(Arrays.asList(count(mat[i]), i)); 
       } 
       list.sort((t1, t2) -> t1.get(0).equals(t2.get(0)) ?  
                 t1.get(1) - t2.get(1) : t1.get(0) - t2.get(0)); 
       int[] res = new int[k]; 
       for (int i = 0; i < k; i++) { 
           res[i] = list.get(i).get(1); 
       } 
       return res; 
   } 

   private int count(int[] row) { 
       int l = 0, r = row.length; 
       while (l + 1 < r) { 
           int mid = (l + r) / 2; 
           if (row[mid] == 1) { 
               l = mid; 
           } else { 
               r = mid; 
           } 
       } 
       return row[l] == 1 ? r : l; 
   } 
}

上岸算法小班 /免费试听

超过24小时的实时线上沉浸式白板训练

快速掌握最新最高频面试题及核心算法套路

10人小班化教学，师生比达到1：2.5

快快扫描二维码参与免费试听~

No.2 Reduce Array Size to The Half

解题思路

贪心地想, 删除出现次数更多的值即可. 所以我们需要统计出每一个值出现的次数. 然后对这些次数排序, 从大到小取, 直到加和达到了原数组长度的一半即可.

统计每一个值出现的次数有两种方案:

使用 Map 进行计数

排序之后计数

前者耗费额外的空间 (即 Map 所占的空间), 但是速度更快, 并且不会影响原数组. 下面的代码是使用 Map 的实现. 由于排序的存在, 总时间复杂度 o(nlogn)

代码展示

class Solution { 
   public int minSetSize(int[] arr) { 
       // 统计每个值出现的次数 
       Map<Integer, Integer> map = new HashMap<>(); 
       for (int num : arr) { 
           map.put(num, map.getOrDefault(num, 0) + 1); 
       } 
       // 排序 
       List<Integer> list = new ArrayList<>(); 
       for (Map.Entry<Integer, Integer> entry : map.entrySet()) { 
           list.add(entry.getValue()); 
       } 
       list.sort(Collections.reverseOrder()); 
       // 依次取, 直到总和不小于长度的一半 
       int res = 0, left = (arr.length + 1) / 2;  // left 表示还需要删去的数量 
       for (int cnt : list) { 
           res++; 
           left -= cnt; 
           if (left <= 0) { 
               break; 
           } 
       } 
       return res; 
   } 
}

No.3 Maximum Product of Splitted Binary Tree

解题思路

若两个数的和为定值, 那么这两个数最接近的时候, 它们的乘积最大.

所以首先统计出整棵树的节点和 sum, 然后再检查每一棵子树的节点和, 找到最接近 sum / 2 的即可.

只需要对整棵树进行两次遍历, 时间复杂度o(n)

代码展示

class Solution { 
   private int sum, half; 

   private int findClosest(TreeNode node) { 
       // 查找与 sum / 2 最接近的子树节点和, 将结果保存在 half 中 
       if (node == null) { 
           return 0; 
       } 
       int nowSum = node.val + findClosest(node.left) + findClosest(node.right); 
       // 比较以当前节点为根的子树的节点和是否更接近 sum / 2 
       if (Math.abs(nowSum - sum / 2) < Math.abs(half - sum / 2)) { 
           half = nowSum; 
       } 
       return nowSum; 
   } 

   private int calcTreeSum(TreeNode node) { 
       if (node == null) { 
           return 0; 
       } 
       return node.val + calcTreeSum(node.left) + calcTreeSum(node.right); 
   } 

   public int maxProduct(TreeNode root) { 
       sum = calcTreeSum(root); 
       half = 0; 
       findClosest(root); 
       return (int)((long)(sum - half) * (long)half % 1000000007L); 
   } 
}

No.4 Jump Game V 解题思路

动态规划问题:

定义状态: dp[i] 表示从 i 开始跳, 最多可以到达多少个点

状态转移方程: dp[i] = max{ dp[j] + 1 } 其中 j 需要满足题意所描述条件, 能够从 i 跳跃到 j

初始状态: dp[i] = 1 因为至少可以到达自己

最终答案: max{ dp[i] }

由于这个题目转移顺序不容易确定, 所以使用记忆化搜索更合适. 时间复杂度 o(nd)状态数量 x 状态转移时间

代码展示

class Solution { 
   public int maxJumps(int[] arr, int d) { 
       // dp, 需要使用记忆化搜索 
       int[] dp = new int[arr.length]; 
       int res = 0; 
       for (int i = 0; i < arr.length; i++) { 
           // startFrom(i, ...) 返回从 i 开始跳最多能够到达多少个点 
           res = Math.max(res, startFrom(i, arr, d, dp)); 
       } 
       return res; 
   } 

   private int startFrom(int start, int[] arr, int d, int[] dp) { 
       if (dp[start] > 0) {  // 初值为 0 表示还没有计算过 
           return dp[start]; 
       } 
       dp[start] = 1;        // 至少能访问到自己 
       // 尝试往左跳 
       for (int i = 1; i <= d; i++) { 
           if (start < i || arr[start - i] >= arr[start]) { 
               break; 
           } 
           dp[start] = Math.max(dp[start], startFrom(start - i, arr, d, dp) + 1); 
       } 
       // 尝试往右跳 
       for (int i = 1; i <= d; i++) { 
           if (start + i >= arr.length || arr[start + i] >= arr[start]) { 
               break; 
           } 
           dp[start] = Math.max(dp[start], startFrom(start + i, arr, d, dp) + 1); 
       } 
       return dp[start]; 
   } 
}

想要了解最新的周赛题解信息，可以入群与大佬们一起交流~