当前位置: 首页 > news >正文

数学题目系列(一)|丑数|各位和|埃氏筛|欧拉筛

一.丑数

链接:丑数
在这里插入图片描述
分析:

  • 丑数只有2,3,5这三个质因数,num = 2a + 3b + 5c
  • 也就是一个丑数是由若干个2,3,5组成,那么丑数除以这若干个数字最后一定变为1

代码

class Solution {public boolean isUgly(int n) {if (n <= 0) return false;int[] factors = { 2, 3, 5 };for (int factor : factors)while (n % factor == 0)n /= factor;return n == 1;}
}

二.丑数II

链接:丑数II
在这里插入图片描述
分析

  • 最容易想到的思路是暴力解法,因为在上一题中已经知道判断一个丑数的方法,但是时间复杂度太高,不能通过所有样例

暴力解法(无法通过所有样例)

class Solution {private boolean isUgly(int n) {int[] factors = {2,3,5};for(int factor : factors)while(n % factor == 0)n /= factor;return n == 1;}public int nthUglyNumber(int n) {int ret = 0, cnt = 0;for(int i = 1;;i++) {if(isUgly(i)) cnt++;if(cnt == n) return i;}}
}
  • 要取出第n大的丑数,可以使用优先级队列来存储丑数,丑数非常容易获得,就是由前一个丑数分别乘2,3,5所得
  • 首先创建最小堆,堆顶元素为最小的丑数
  • 初始化最小堆,堆顶元素为最小的丑数1
  • 取出堆顶元素x,第几次取出就是第几大的丑数
  • x是丑数,那么2x,3x,5x也都是丑数,将这三个数存储到优先级队列之中
  • 在这个过程中可能会出现重复元素,可以使用哈希表来去重
  • 这样,当第n次取出堆顶元素x时,x就是第n大的丑数

代码

class Solution {public int nthUglyNumber(int n) {int[] factors = {2, 3, 5};Set<Long> set = new HashSet<>();PriorityQueue<Long> q = new PriorityQueue<>();set.add(1L);q.add(1L);for(int i = 1; i < n; i++) {long top = q.poll();for(int factor : factors){long next = top * factor;if(set.add(next))q.add(next); }}return (int)q.poll().longValue();}
}

注意:

  1. 注意Long和long是不同的,Long是包装类,long是基本类型
  2. Java中,基本类型之间可以直接进行强制类型转换(int x = (int)long)
  3. 基本类型和其对应的包装类型在底层是通过方法进行转换的,但是在JDK5之后,编译器会自动帮助我们完成这个过程,也就是拆箱和装箱
  4. 包装类不能直接转换为另一个包装类或原始数据类型,必须先进行拆箱或装箱
  5. Long 不能直接转换为 int,因为它们是不同的类型,必须先将 Long 拆箱为 long,然后再转换为 int。
  6. Long转化为long是通过longvalue方法实现

三.各位相加

链接:各位相加
在这里插入图片描述
分析

  • 模拟思路:不断获得每一位,然后计算各位和,直到最后的结果是个位数

代码

class Solution {// 求各位和private int bitSum(int n) {int ret = 0;while (n > 0) {ret += n % 10;n /= 10;}return ret;}public int addDigits(int num) {int ret = num;while(ret / 10 != 0) {ret = bitSum(ret);}return ret;}
}

数学方法
看推导:
在这里插入图片描述

  • 核心在于:num和其各位和 MOD9同余
  • 进而推导出num和最后的结果MOD9同余

代码

class Solution {public int addDigits(int num) {if(num == 0) return 0;if(num % 9 == 0) return 9;return num % 9;}
}

四.计数质数

暴力解法(超时)

class Solution {private boolean isPrime(int n) {for(int i = 2; i <= Math.sqrt(n); i++){if(n % i == 0)return false;}return true;}public int countPrimes(int n) {int cnt = 0;for(int i = 2; i < n; i++)if(isPrime(i))cnt++;return cnt;}
}

埃氏筛

  • 核心:如果x是质数,则2x,3x,4x,5x…一定不是质数
  • 利用这个原理就能灵活处理很多问题

代码

class Solution {public int countPrimes(int n) {int[] is_prime = new int[n];// 标记第i个数是否是质数Arrays.fill(is_prime,1);// 默认全是质数int ret = 0;// 记录结果for(int i = 2; i < n; i++) {if(is_prime[i] == 1) {ret += 1;if((long)i*i < n)for(int k = i * i; k < n; k += i)is_prime[k] = 0;}}return ret;}
}

线性筛

  • 埃氏筛其实还存在冗余的地方,比如12这个数字,被2,4,6都删除过一次,这就是冗余操作,使用线性筛可以解决这个问题
  • 线性筛的核心在于:对于一个数x,x乘以小于x的所有质数的结果一定是合数,将这些结果标记为非质数即可,但是发现这样的删除过程仍然存在冗余操作,问题及解决方案如下

在这里插入图片描述
代码:

class Solution {public int countPrimes(int n) {List<Integer> list = new ArrayList<>();// 存储之前出现的所有质数int[] is_prime = new int[n];Arrays.fill(is_prime,1);int ret = 0;for(int i = 2; i < n; i++) {if(is_prime[i] == 1){list.add(i);ret++;}for(int k : list){if(k*i >= n) break;is_prime[k*i] = 0;if(i % k == 0) break;// k是i的最小质因数}}return ret;}
}

三种算法的时间复杂度对比(数据量大)

  • 线性筛 > 埃氏筛 > 暴力解法

对比实验:求2-n之间所有的质数
代码:

package org.example;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;// 打印2-n之间的所有质数
public class Demo2 {// 埃氏筛public static void Eratosthenes(int n) {List<Integer> list = new ArrayList<>();int[] is_prime = new int[n + 1];Arrays.fill(is_prime, 1);for(int i = 2; i <= n; i++) {if(is_prime[i] == 1){list.add(i);if((long)i*i <= n)for(int k = i*i; k <= n; k += i)is_prime[k] = 0;}}}// 暴力解法public static void isPrime(int n){List<Integer> list = new ArrayList<>();for(int i = 2; i<= n; i++){if(is_prime(i))list.add(i);}}private static boolean is_prime(int n){for(int i = 2; i <= Math.sqrt(n); i++)if(n % i == 0)return false;return true;}// 线性筛public static void Euler_prime(int n){List<Integer> list = new ArrayList<>();int[] is_prime = new int[n + 1];Arrays.fill(is_prime, 1);for(int i = 2; i <= n; i++) {if(is_prime[i] == 1)list.add(i);for(int k : list){if(k*i > n) break;is_prime[k*i] = 0;if(i % k == 0) break;// k是i的最小质因数}}}public static void main(String[] args) {int n = 200000000;long start1 = System.currentTimeMillis();Eratosthenes(n);long end1 = System.currentTimeMillis();System.out.println("埃氏筛时间:" + (end1 - start1));long start2 = System.currentTimeMillis();isPrime(n);long end2 = System.currentTimeMillis();System.out.println("暴力时间:" + (end2 - start2));long start3 = System.currentTimeMillis();Euler_prime(n);long end3 = System.currentTimeMillis();System.out.println("线性筛时间:" + (end3 - start3));}
}

打印结果:
在这里插入图片描述

  • 只有当数据量特别大时,才符合上述时间复杂度的排序,对于计算机来说,取模%是一个非常耗时的操作

相关文章:

数学题目系列(一)|丑数|各位和|埃氏筛|欧拉筛

一.丑数 链接&#xff1a;丑数 分析&#xff1a; 丑数只有2&#xff0c;3&#xff0c;5这三个质因数&#xff0c;num 2a 3b 5c也就是一个丑数是由若干个2&#xff0c;3&#xff0c;5组成&#xff0c;那么丑数除以这若干个数字最后一定变为1 代码 class Solution {publi…...

k8s学习--Secret详细解释与应用

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 Secret什么是Secret?Secret四种类型及其特点Secret应用案例&#xff08;1&#xff09;将明文密码进行base64编码&#xff08;2&#xff09;编写创建secret的YAML文…...

功能问题:如何防止接口重复请求?

大家好&#xff0c;我是大澈&#xff01; 本文约 1400 字&#xff0c;整篇阅读约需 3 分钟。 防止接口重复请求在软件开发中非常重要&#xff0c;重复请求必然会导致服务器资源的浪费。 因为每次请求都需要服务器进行处理&#xff0c;如果请求是重复的&#xff0c;那么服务…...

系统架构设计师【第5章】: 软件工程基础知识 (核心总结)

文章目录 5.1 软件工程5.1.1 软件工程定义5.1.2 软件过程模型5.1.3 敏捷模型5.1.4 统一过程模型&#xff08;RUP&#xff09;5.1.5 软件能力成熟度模型 5.2 需求工程5.2.1 需求获取5.2.2 需求变更5.2.3 需求追踪 5.3 系统分析与设计5.3.1 结构化方法5.3.2 面向对象…...

嵌入式Linux系统编程 — 2.2 标准I/O库:检查或复位状态

目录 1 检查或复位状态简介 2 feof()函数 2.1 feof()函数简介 2.2 示例程序 3 ferror()函数 4 clearerr()函数 4.1 clearerr()函数简介 4.2 示例程序 1 检查或复位状态简介 调用 fread() 函数读取数据时&#xff0c;如果返回值小于参数 nmemb 所指定的值&#xff0c;这…...

pESC-HIS是什么,怎么看?-实验操作系列-2

01 典型的pESC-HIS质粒遗传图谱 02 介绍 质粒类型&#xff1a;酿酒酵母蛋白表达载体 表达水平&#xff1a;高拷贝 诱导方法&#xff1a;半乳糖 启动子&#xff1a;GAL1和GAL10 克隆方法&#xff1a;多克隆位点&#xff0c;限制性内切酶 载体大小&#xff1a;6706bp 5 测…...

树形表/树形数据接口的开发

数据表格式 需要返回的json格式 点击查看json数据 [{"childrenTreeNodes" : [{"childrenTreeNodes" : null,"id" : "1-1-1","isLeaf" : null,"isShow" : null,"label" : "HTML/CSS","na…...

二叉树的镜像--c++【做题记录】

【问题描述】 给定扩展二叉树的前序序列&#xff0c;构建二叉树。 求这课二叉树的镜像&#xff0c;并输出其前序遍历序列。 【输入形式】 输入扩展二叉树的前序序列。 【输出形式】 输出镜像二叉树的前序遍历序列。 【样例输入】 ab##cd##e## 【样例输出】 镜像后二叉树的前序遍…...

redis安裝启动

1、下载redis解压 https://github.com/tporadowski/redis/releases 2、打开cmd&#xff0c;切换到解压的文件夹 3、redis-server.exe redis.windows.conf 启动redis redis可通过命令行输入config set requirepass password和直接修改redis.config文件中修改 requirepass 来设…...

为什么Java中的main方法必须是public static void的?

当我们创建main方法时&#xff0c;首先都是public、都是static&#xff0c;返回值都是void&#xff0c;方法名都是main&#xff0c;入参都是一个字符串数组。 在以上的方法声明中&#xff0c;唯一可以改变的部分就是方法的参数名&#xff0c;我们可以吧args改成任意我们想要使…...

shell的编程方式

文章目录 变量俩种方式第一种方式第二种方式 取消变量数组创建数组获取数组元素的方式 read输出的方式限制输入的方式 流程控制方式for循环输出的方式第一种方式第二种方式while循环输出的方式select选择输出的方式 判断方式判断的四种方式第一种方式第二种方式第三种方式 算术…...

前端面试项目细节重难点(已工作|做分享)想(八)

面试官&#xff1a;请你讲讲你在该项目中遇到的印象深刻的问题是什么&#xff1f; 答&#xff1a;我的回答&#xff1a;该项目的实现过程中我确实遇到了问题&#xff1a;【我会给大家整理回答思路和角度&#xff0c;那那么遇到这样的问题也可借鉴这种思路进行阐述】 第一层面…...

Loguru,一个 Python 日志神器

大家好!我是爱摸鱼的小鸿,关注我,收看每期的编程干货。 一个简单的库,也许能够开启我们的智慧之门, 一个普通的方法,也许能在危急时刻挽救我们于水深火热, 一个新颖的思维方式,也许能激发我们无尽的创造力, 一个独特的技巧,也许能成为我们的隐形盾牌…… 神奇的 Pyth…...

C++ 反转单词

在C中&#xff0c;反转一个字符串中的单词&#xff08;单词之间通过空格分隔&#xff0c;但单词内部保持原有顺序&#xff09;可以通过以下步骤实现&#xff1a; 找到字符串中的所有单词&#xff0c;这可以通过查找空格来实现。将单词存储在一个容器中&#xff08;例如 std::v…...

Apache Doris 基础 -- 数据表设计(表索引)

1、索引概述 索引用于帮助快速过滤或搜索数据。目前&#xff0c;Doris支持两种类型的索引:内置智能索引和用户创建的二级索引。 内置智能索引 排序键和前缀索引:Apache Doris基于排序键以有序的方式存储数据。它为每1024行数据创建一个前缀索引。索引中的键是当前1024行组的…...

资源描述框架的用途及实际应用解析

什么是RDF&#xff1f; RDF代表 资源描述框架 RDF是用于描述网络资源的框架 RDF旨在被计算机阅读和理解 RDF并非设计用于供人阅读 RDF以 XML 编写 示例 描述购物商品的属性&#xff0c;如价格和可用性描述网络活动的时间表描述网页的信息&#xff08;内容&#xff0c;作者&a…...

工业级物联网边缘网关解决方案-天拓四方

随着工业4.0时代的到来&#xff0c;越来越多的企业开始寻求智能化升级&#xff0c;以提高生产效率、降低运营成本并增强市场竞争力。然而&#xff0c;在实际的转型升级过程中&#xff0c;许多企业面临着数据孤岛、设备兼容性差、网络安全风险高等问题&#xff0c;这些问题严重制…...

认识微服务,认识Spring Cloud

1. 介绍 本博客探讨的内容如下所示 什么是微服务&#xff1f;什么是springcloud&#xff1f;微服务和springcloud有什么关系&#xff1f; 首先&#xff0c;没有在接触springcloud之前&#xff0c;我写的项目都是单体结构&#xff0c; 但随着网站的用户量越来越大&#xff0c;…...

电脑设置密码怎么设置?让你的电脑更安全!

在如今信息化的社会中&#xff0c;保护个人电脑的安全至关重要。设置密码是最基本的电脑安全措施之一&#xff0c;它可以有效防止未经授权的访问和保护个人隐私&#xff0c;可是电脑设置密码怎么设置&#xff1f;本文将介绍三种设置电脑密码的方法&#xff0c;帮助您加强电脑的…...

搜维尔科技:SenseGlove Nova2使用主动接触反馈来模拟手掌的感觉,结合力反馈和振动触觉反馈,使其成为市场上第一款具有手掌反馈的无线触觉手套

SenseGlove Nova2使用主动接触反馈来模拟手掌的感觉&#xff0c;结合力反馈和振动触觉反馈&#xff0c;使其成为市场上第一款具有手掌反馈的无线触觉手套。 搜维尔科技&#xff1a;SenseGlove Nova2使用主动接触反馈来模拟手掌的感觉&#xff0c;结合力反馈和振动触觉反馈&…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...