网站收录排名,红盾网官网入口,辽宁建设工程信息网站,页面具有动态效果网站建设前言
经过前期的基础训练以及部分实战练习#xff0c;粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述 给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格#xff0c;你可以按以下方式生成数字#xff1a; 最多有 8 条路径可以选择#xff1…前言
经过前期的基础训练以及部分实战练习粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述 给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格你可以按以下方式生成数字 最多有 8 条路径可以选择东东南南西南西西北北东北。选择其中一条路径沿着这个方向移动并且将路径上的数字添加到正在形成的数字后面。注意每一步都会生成数字例如如果路径上的数字是 1, 9, 1那么在这个方向上会生成三个数字1, 19, 191 。 返回在遍历矩阵所创建的所有数字中出现频率最高的、大于 10的 质数 如果不存在这样的质数则返回 -1 。如果存在多个出现频率最高的质数那么返回其中最大的那个。 注意移动过程中不允许改变方向。 示例 1
输入mat [[1,1],[9,9],[1,1]]
输出19
解释
从单元格 (0,0) 出发有 3 个可能的方向这些方向上可以生成的大于 10 的数字有
东方向: [11], 东南方向: [19], 南方向: [19,191] 。
从单元格 (0,1) 出发所有可能方向上生成的大于 10 的数字有[19,191,19,11] 。
从单元格 (1,0) 出发所有可能方向上生成的大于 10 的数字有[99,91,91,91,91] 。
从单元格 (1,1) 出发所有可能方向上生成的大于 10 的数字有[91,91,99,91,91] 。
从单元格 (2,0) 出发所有可能方向上生成的大于 10 的数字有[11,19,191,19] 。
从单元格 (2,1) 出发所有可能方向上生成的大于 10 的数字有[11,19,19,191] 。
在所有生成的数字中出现频率最高的质数是 19 。 示例 2 输入mat [[7]]
输出-1
解释唯一可以生成的数字是 7 。它是一个质数但不大于 10 所以返回 -1 。 示例 3 输入mat [[9,7,8],[4,6,5],[2,8,6]]
输出97
解释
从单元格 (0,0) 出发所有可能方向上生成的大于 10 的数字有: [97,978,96,966,94,942] 。
从单元格 (0,1) 出发所有可能方向上生成的大于 10 的数字有: [78,75,76,768,74,79] 。
从单元格 (0,2) 出发所有可能方向上生成的大于 10 的数字有: [85,856,86,862,87,879] 。
从单元格 (1,0) 出发所有可能方向上生成的大于 10 的数字有: [46,465,48,42,49,47] 。
从单元格 (1,1) 出发所有可能方向上生成的大于 10 的数字有: [65,66,68,62,64,69,67,68] 。
从单元格 (1,2) 出发所有可能方向上生成的大于 10 的数字有: [56,58,56,564,57,58] 。
从单元格 (2,0) 出发所有可能方向上生成的大于 10 的数字有: [28,286,24,249,26,268] 。
从单元格 (2,1) 出发所有可能方向上生成的大于 10 的数字有: [86,82,84,86,867,85] 。
从单元格 (2,2) 出发所有可能方向上生成的大于 10 的数字有: [68,682,66,669,65,658] 。
在所有生成的数字中出现频率最高的质数是 97 。提示 m mat.lengthn mat[i].length1 m, n 61 mat[i][j] 9 实现原理与步骤
1.8个方便遍历集合组成的数据
2.素数判断由于数据较为稀疏当个判断效率更高。
3.根据结果规则返回结果。
实现代码
class Solution {public int mostFrequentPrime(int[][] mat) {int row mat.length;int col mat[0].length;HashMapInteger, Integer map new HashMap();int[][] direct { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 }, { 1, 1 }, { 1, -1 }, { -1, -1 }, { -1, 1 } };for (int i 0; i row; i) {for (int j 0; j col; j) {for (int[] d : direct) {//v由于随着该方向延伸动态变化需要在新的方向搜索时初始化int v mat[i][j];int x i d[0];int y j d[1];while (x 0 x row y 0 y col) {v v * 10 mat[x][y];if (isPrime(v)) {map.merge(v, 1, Integer::sum);}x d[0];y d[1];}}}}int res-1;int maxCnt-1;for(Map.EntryInteger,Integer entry:map.entrySet()){int ventry.getKey();int centry.getValue();if(cmaxCnt){resv;maxCntc;}else if(cmaxCnt){resMath.max(res,v);}}return res;}public boolean isPrime(int x) {for (int i 2; i * i x; i) {if (x % i 0) {return false;}}return true;}
} 1.QA:
