深圳做网站设计公司,wordpress自动适应手机,网络培训内容,门头效果图制作【LetMeFly】2614.对角线上的质数#xff1a;遍历(质数判断)
力扣题目链接#xff1a;https://leetcode.cn/problems/prime-in-diagonal/
给你一个下标从 0 开始的二维整数数组 nums 。
返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数…【LetMeFly】2614.对角线上的质数遍历(质数判断)
力扣题目链接https://leetcode.cn/problems/prime-in-diagonal/
给你一个下标从 0 开始的二维整数数组 nums 。
返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数返回 0 。
注意
如果某个整数大于 1 且不存在除 1 和自身之外的正整数因子则认为该整数是一个质数。如果存在整数 i 使得 nums[i][i] val 或者 nums[i][nums.length - i - 1] val 则认为整数 val 位于 nums 的一条对角线上。 在上图中一条对角线是 [1,5,9] 而另一条对角线是 [3,5,7] 。 示例 1
输入nums [[1,2,3],[5,6,7],[9,10,11]]
输出11
解释数字 1、3、6、9 和 11 是所有 位于至少一条对角线上 的数字。由于 11 是最大的质数故返回 11 。示例 2
输入nums [[1,2,3],[5,17,7],[9,11,10]]
输出17
解释数字 1、3、9、10 和 17 是所有满足位于至少一条对角线上的数字。由于 17 是最大的质数故返回 17 。提示
1 nums.length 300nums.length numsi.length1 nums[i][j] 4*106
解题方法质数判断
如何判断一个数是否为质数 首先如果这个数小于2那么一定不是质数 用 i i i从2到 s q r t ( n ) sqrt(n) sqrt(n)枚举若 i i i能整除 n n n则 n n n不是质数 否则 n n n是质数 如何遍历对角线题目中说了 nums.length numsi.length 也就是说矩阵是正方形。 所以我们可以用 i i i从 0 0 0枚举到 n − 1 n - 1 n−1那么 n u m s [ i ] [ i ] nums[i][i] nums[i][i]和 n u m s [ i ] [ l e n ( n u m s ) − i − 1 ] nums[i][len(nums) - i - 1] nums[i][len(nums)−i−1]即为对角线和副对角线上的元素。 时间复杂度 O ( l e n ( n u m s ) max ( n u m s [ i ] [ j ] ) ) O(len(nums)\sqrt{\max(nums[i][j]))} O(len(nums)max(nums[i][j])) 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
/** Author: LetMeFly* Date: 2025-03-18 23:40:09* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-18 23:43:36*/
class Solution {
private:bool isPrime(int n) {if (n 2) {return false;}int k sqrt(n);for (int i 2; i k; i) {if (n % i 0) {return false;}}return true;}
public:int diagonalPrime(vectorvectorint nums) {int ans 0;for (int i 0; i nums.size(); i) {if (isPrime(nums[i][i])) {ans max(ans, nums[i][i]);}if (isPrime(nums[i][nums.size() - i - 1])) {ans max(ans, nums[i][nums.size() - i - 1]);}}return ans;}
};Python Author: LetMeFly
Date: 2025-03-18 23:46:52
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-18 23:48:14from typing import List
from math import sqrtclass Solution:def isPrime(self, n: int) - bool:if n 2:return Falsefor i in range(2, int(sqrt(n)) 1):if n % i 0:return Falsereturn Truedef diagonalPrime(self, nums: List[List[int]]) - int:ans 0for i in range(len(nums)):if self.isPrime(nums[i][i]):ans max(ans, nums[i][i])if self.isPrime(nums[i][len(nums) - i - 1]):ans max(ans, nums[i][len(nums) - i - 1])return ansJava
/** Author: LetMeFly* Date: 2025-03-18 23:50:23* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-18 23:55:24*/
class Solution {private boolean isPrime(int n) {if (n 2) {return false;}int k (int)Math.sqrt(n);for (int i 2; i k; i) {if (n % i 0) {return false;}}return true;}public int diagonalPrime(int[][] nums) {int ans 0;for (int i 0; i nums.length; i) {if (isPrime(nums[i][i])) {ans Math.max(ans, nums[i][i]);}if (isPrime(nums[i][nums.length - i - 1])) {ans Math.max(ans, nums[i][nums.length - i - 1]);}}return ans;}
}Go
/** Author: LetMeFly* Date: 2025-03-18 23:55:55* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-18 23:58:46*/
package mainfunc isPrime2614(n int) (ans bool) {if n 2 {return}for i : 2; i * i n; i {if n % i 0 {return}}return true
}func diagonalPrime(nums [][]int) (ans int) {for i : range nums {if isPrime2614(nums[i][i]) {ans max(ans, nums[i][i])}if isPrime2614(nums[i][len(nums) - i - 1]) {ans max(ans, nums[i][len(nums) - i - 1])}}return
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ 千篇源码题解已开源
