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

实现原理与步骤

1.8个方便遍历集合组成的数据

2.素数判断,由于数据较为稀疏,当个判断效率更高。

3.根据结果规则返回结果。

实现代码

class Solution {public int mostFrequentPrime(int[][] mat) {int row = mat.length;int col = mat[0].length;HashMap<Integer, Integer> map = new HashMap();int[][] direct = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 }, { 1, 1 }, { 1, -1 }, { -1, -1 }, { -1, 1 } };for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {for (int[] d : direct) {//v由于随着该方向延伸动态变化,需要在新的方向搜索时初始化int v = mat[i][j];int x = i + d[0];int y = j + d[1];while (x >= 0 && x < row && y >= 0 && y < col) {v = v * 10 + mat[x][y];if (isPrime(v)) {map.merge(v, 1, Integer::sum);}x += d[0];y += d[1];}}}}int res=-1;int maxCnt=-1;for(Map.Entry<Integer,Integer> entry:map.entrySet()){int v=entry.getKey();int c=entry.getValue();if(c>maxCnt){res=v;maxCnt=c;}else if(c==maxCnt){res=Math.max(res,v);}}return res;}public boolean isPrime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {return false;}}return true;}
}

1.QA:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/391793.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

通俗易懂!495页看漫画学Python入门教程(全彩版)Git首发破万Star

前言 在编程的世界里&#xff0c;Python无疑是一颗璀璨的明星。从最初作为打发圣诞节闲暇时间的项目&#xff0c;到如今成为最受欢迎的程序设计语言之一&#xff0c;Python以其简洁、易学、强大的特点吸引了无数编程爱好者。然而&#xff0c;对于初学者来说&#xff0c;编程的…

【redis 第八篇章】链表结构

一、数组和链表 1、数组 数组会在内存中开辟一块连续的空间存储数据&#xff0c;这种存储方式有利也有弊端。当获取数据的时候&#xff0c;直接通过下标值就可以获取到对应的元素&#xff0c;时间复杂度为 O(1)。但是如果新增或者删除数据会移动大量的数据&#xff0c;时间复…

范伟:大叔这句是咱俩合唱的,赵本山:我唱不上去!——小品《门神》(下)的台词与解说

范伟&#xff1a;大叔这句是咱俩合唱的&#xff0c;赵本山&#xff1a;我唱不上去&#xff01; ——小品《门神》&#xff08;下&#xff09;的台词与解说 &#xff08;接上&#xff09; 范伟&#xff1a;大叔快快快走 赵本山&#xff1a;干啥 范伟&#xff1a;上咱家过年…

苹果手机锁屏怎么设置?3个技巧,教你快速设置

在科技与创意交织的时代&#xff0c;苹果手机以其简约而不失优雅的设计&#xff0c;成为了我们日常生活中不可或缺的一部分。而作为手机的【第一印象】&#xff0c;锁屏界面更是彰显用户个性的关键所在。那么&#xff0c;苹果手机锁屏怎么设置呢&#xff1f;接下来&#xff0c;…

AI生成PPT?三款工具让总结更轻松

哎呀&#xff0c;职场新人们&#xff0c;你们是不是也跟我一样&#xff0c;刚开始做PPT的时候&#xff0c;感觉像是走进了一个大迷宫&#xff0c;脑袋里装满了想法&#xff0c;但就是不知道怎么把它们变成一页页漂亮的幻灯片&#xff1f;别急&#xff0c;今天咱们就来聊聊三个超…

【C++】C++特性揭秘:引用与内联函数 | auto关键字与for循环 | 指针空值

C语法相关知识点可以通过点击以下链接进行学习一起加油&#xff01;命名空间缺省参数与函数重载 本章将分享C增加的几种常见特性&#xff0c;主要内容为引用与内联函数 | auto关键字与for循环 | 指针空值&#xff0c;这些知识看似很多&#xff0c;实际也不少。本章篇幅长&#…

C# Unity 面向对象补全计划 七大原则 之 里氏替换

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列作为七大原则和设计模式的进阶知识&#xff0c;看不懂没关系 请看专栏&#xff1a;http://t.csdnimg.cn/mIitr&#xff0c;尤其是关于继承的两篇文章&#xff…

形参和实参的运用

形式参数&#xff1a;定义函数时括号中的变量。只有被调用时才被初始化&#xff0c;函数调用完成后自动销毁&#xff0c;只在函数中有效。 实际参数&#xff1a;真实传递给函数的参数&#xff0c;可以是常量、变量、表达式、函数等。无论实参是何种类型&#xff0c;在调用函数…

DBMS 与 RDBMS

DBMS 与 RDBMS 了解数据库什么是数据库管理系统&#xff1f;Types of DBMS 数据库管理系统的类型T数据库管理系统的好处 关系型数据库管理系统的优点 【纪录片】中国数据库前世今生 在数字化潮流席卷全球的今天&#xff0c;数据库作为IT技术领域的“活化石”&#xff0c;已成为…

JAVA(IO流)7.31

ok了家人们今天还是学习IO流&#xff0c; 一.打印流【了解】 1.1 打印流的概述 我们平时使用的System语句就是调用了print()方法和println()方法。 这两个方法都来自于 java.io.PrintStream 类。 作用&#xff1a; 该类能够方便地打印各种数据类型的值&#xff0c;写入数据后…

【Web】TFCCTF 2024 部分题解

目录 GREETINGS SURFING SAFE_CONTENT FLASK DESTROYER GREETINGS 打express的SSTI GitHub - TheWation/NodeJsSSTI: Express app with Pug templates demonstrating SSTI vulnerability and secure implementation for educational purposes. payload: /result?user…

使用腾讯云域名解析实现网站重定向

前言 最近&#xff0c;在CSDN平台上我写了一系列博客&#xff0c;希望能与同学分享一些技术心得。然而&#xff0c;每当需要向他人推荐我的博客时&#xff0c;那串复杂且缺乏规律的CSDN博客首页域名总让我感到不便。这让我开始思考&#xff0c;如果能将这一域名替换为一个既个…

设计模式的概念

设计模式主要分为三类&#xff1a;创建类的设计模式、结构型设计模式、行为型设计模式。 创建类的设计模式&#xff1a;简单工厂&#xff0c;工厂模式&#xff0c;抽象工厂&#xff0c;建造者&#xff0c;单例&#xff0c;原型 结构型设计模式&#xff1a;代理模式、享元模式 行…

博物馆展厅AI交互数字人,解锁创新的文化交互体验

在智能化时代&#xff0c;博物馆展厅融入AI交互数字人&#xff0c;可以为游客给予实时交互的旅游服务&#xff0c;AI交互数字人可以承担智能引导、讲解、接待、客服与导游等多重角色&#xff0c;为游客塑造崭新的旅游体验。 AI交互数字人相比传统的录屏解说相比&#xff0c;AI…

【无所从来,亦无所去】纪念去世的奶奶和外公「纪念网页」

大家好&#xff0c;我是DX3906 &#x1f308; 欢迎莅临我的个人主页 &#x1f448;这里是我静心耕耘大前端领域、真诚分享知识与智慧的小天地&#xff01;&#x1f387; 纪念 2024年 奶奶 85岁、 外公83岁。他们俩分别在今年的2月份和7月份离开了。 时光倒流&#xff0c;奶…

SVPWM5段式7段式差异分析和关键代码基于TI F28035

SVPWM5段式7段式差异分析和关键代码基于TI F28035 5段式有一相占空比始终为0或者1 扇区判断的扇区号和实际扇区不是一一对应,直接使用,而是映射关系 扇区判断变量 7段式和5段式在基本矢量作用顺序上的差异 SVPWM算法详解(已标注重点) 来自这篇文章,但经过实际测试,发现是…

使用Halcon变换与校正图像

使用Halcon变换与校正图像 文章目录 使用Halcon变换与校正图像1. 二维图像的平移、旋转和缩放1.图像的平移2.图像的旋转3.图像的缩放2. 图像的仿射变换3. 投影变换4 实例&#xff1a;透视形变图像校正 由于相机拍摄的时候可能存在角度偏差&#xff0c;因此实际获得的画面可能会…

Chainlit快速实现AI对话应用的界面定制化教程

前言 本文主要讲解如何自定义chainlit实现的网页界面的中的一些可以自定修改的样式的实现教程。比如修改自己的logo网站图标或者主题等 翻译 chainlit 默认网页界面显示的是英文&#xff0c;如果我们想显示为其他语言可以进行以下操作。 翻译文件位于项目根目录下的.chainli…

正点原子imx6ull-mini-Linux驱动之Linux I2C 驱动实验(21)

I2C 是很常用的一个串行通信接口&#xff0c;用于连接各种外设、传感器等器件&#xff0c;在裸机篇已经对 I.MX6U 的 I2C 接口做了详细的讲解。本章我们来学习一下如何在 Linux 下开发 I2C 接口器件 驱动&#xff0c;重点是学习 Linux 下的 I2C 驱动框架&#xff0c;按照指定的…

python中类class的魔法方法

开始介绍之前&#xff0c;我们先看下之前文章我们介绍过的内置类merryview的一些方法&#xff0c;如下图所示&#xff1a; 有很多双下划线开始和结束的method&#xff0c;这么多method是做啥子用的呢&#xff1f; 其实这些方法就是我们常说的魔法方法&#xff0c;也是python中的…