作者推薦
動態規劃的時間復雜度優化
本文涉及知識點
素數 矩陣 方向
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,16]的質數。
代碼
核心代碼
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
相關下載
想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。 |
| 子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
測試環境
操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。
)
