本文主要是介绍Leetcode 3044. Most Frequent Prime,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- Leetcode 3044. Most Frequent Prime
- 1. 解题思路
- 2. 代码实现
- 题目链接:3044. Most Frequent Prime
1. 解题思路
这一题的话思路上倒是没啥,直接遍历一下每一个点作为起点时8个方向上所能找到的全部质数然后count一下他们出现的总次数即可。
2. 代码实现
给出python代码实现如下:
def get_primes(n):status = [0 for _ in range(n+1)]primes = set()for i in range(2, n+1):if status[i] != 0:continueprimes.add(i)for j in range(i, n+1, i):status[j] = 1return primesPRIMES = get_primes(10**7)class Solution:def mostFrequentPrime(self, mat: List[List[int]]) -> int:n, m = len(mat), len(mat[0])def get_number(point, direction):x, y = points, ans = 0, []while 0 <= x < n and 0 <= y < m:s = s * 10 + mat[x][y]if s >= 10:ans.append(s) x += direction[0]y += direction[1]return anscnt = defaultdict(int)for i in range(n):for j in range(m):for direction in [(0, 1), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, 0), (-1, -1)]:nums = get_number((i, j), direction)for num in nums:if num in PRIMES:cnt[num] += 1res = sorted(cnt.items(), key=lambda x: (x[1], x[0]), reverse=True)return res[0][0] if res else -1
提交代码评测得到:耗时1286ms,占用内存163.4MB。
这篇关于Leetcode 3044. Most Frequent Prime的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!