leetcode数论(3044. 出现频率最高的质数)
前言
经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述
给你一个大小为
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;HashMap<Integer, 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.Entry<Integer,Integer> entry:map.entrySet()){int v=entry.getKey();int c=entry.getValue();if(c>maxCnt){res=v;maxCnt=c;}else if(c==maxCnt){res=Math.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;}
}