天津网站建设流程,引蜘蛛网站,动漫网站设计模板,交通运输部:全力保障交通网络畅通作者推荐
动态规划的时间复杂度优化
本文涉及知识点
素数 矩阵 方向
LeetCode 3044 出现频率最高的素数
给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格#xff0c;你可以按以下方式生成数字#xff1a; 最多有 8 条路径可以选择#xff1a;东你可以按以下方式生成数字 最多有 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*10mat[nr][nc]。 三所有num 如果是大于10的质数则mNumCount[num]。 四找出频率最大的素数如果有多个返回值最大的。 时间复杂度O(nmmax(n,m)8)。 初始化的时候枚举所有[2,16]的质数。
代码
核心代码
class Solution {
public:int mostFrequentPrime(vectorvectorint mat) {static const auto v CreatePrime(1000000);static unordered_setint 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_mapint, 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];}}}}}vectorpairint, 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;}
};templateclass 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() { vectorvector 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
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
