当前位置：首页 > news >正文

网站建设网页制微信分享网站开发

news 2025/11/8 13:22:03

网站建设网页制,微信分享网站开发,有的网站没设关键词,想学做网站应该学作者推荐动态规划的时间复杂度优化本文涉及知识点素数矩阵方向 LeetCode 3044 出现频率最高的素数给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字： 最多有 8 条路径可以选择：东&am…

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

素数矩阵方向

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.length
n == mat[i].length
1 <= m, n <= 6
1 <= mat[i][j] <= 9

分析

四层循环：第一层枚举起始行，第二层循环枚举起始列，第三层循环枚举方向。第三层循环：
一，num = mat[r][c]。
二，移动d格后是否越界，如果越界退出第四层循环，否则num = num*10+mat[nr][nc]。
三，所有num 如果是大于10的质数，则mNumCount[num]++。
四，找出频率最大的素数，如果有多个，返回值最大的。
时间复杂度：O(nmmax(n,m)8)。
初始化的时候：枚举所有[2,1⁶]的质数。

代码

核心代码

class Solution {
public:int mostFrequentPrime(vector<vector<int>>& mat) {static const auto& v = CreatePrime(1000'000);static unordered_set<int> setPrime;if (setPrime.empty()){for (auto& n : v){if (n > 10){setPrime.emplace(n);}}}int move[8][2] = { {0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1} };unordered_map<int, int> mNumCount;for (int r = 0; r < mat.size(); r++){for (int c = 0; c < mat[0].size(); c++){for (int d = 0; d < sizeof(move) / sizeof(move[0]); d++){int num = mat[r][c];for (int k = 1;; k++){const int nr = r + move[d][0] * k;const int nc = c + move[d][1] * k;if ((nr < 0) || (nr >= mat.size())){break;}if ((nc < 0) || (nc >= mat[0].size())){break;}num = num * 10 + mat[nr][nc];if (setPrime.count(num)){mNumCount[num]++;}}}}}vector<pair<int, int>> vCntNum;for (const auto& [num, cnt] : mNumCount){vCntNum.emplace_back(cnt, num);}sort(vCntNum.begin(), vCntNum.end());return vCntNum.size() ? vCntNum.rbegin()->second : -1;}
};

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}

}

int main()
{
vector<vector> mat;
{
Solution sln;
mat = { {1,1},{9,9},{1,1} };
auto res = sln.mostFrequentPrime(mat);
Assert(19, res);
}
{
Solution sln;
mat = { {7} };
auto res = sln.mostFrequentPrime(mat);
Assert(-1, res);
}
{
Solution sln;
mat = { {9,7,8} ,{4,6,5},{2,8,6} };
auto res = sln.mostFrequentPrime(mat);
Assert(97, res);
}

}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛