VIVO算法题——数位之积
记录算法究极无敌菜菜菜鸟的垃圾思维
题目:
现给定任意正整数 n,请寻找并输出最小的正整数 m(m>9),使得 m 的各位(个位、十位、百位 … …)之乘积等于n,若不存在则输出 -1。
菜鸟思维Recording【30分钟左右】
大学四年没碰过算法,小学生思维,勿喷勿喷
最开始我想使用查找表的方式先将所有结果都记录在一个table中,然后后续根据index去查找答案。
#include<stdio.h>
#include<limits.h>#define MAX 10000
int table[MAX];
/**
* 构造查找表
*/
void createTable(){int i, temp, multi;//初始化全局变量为最大值,否则默认为0for(i = 0; i < MAX; i++){table[i] = INT_MAX;}i = 0;while(i<MAX){multi = 1;temp = i;while(temp > 0){multi = multi*(temp%10);temp = temp/10;}if(table[multi] > i){table[multi] = i;}i++;}
}/*@param input:输入字符串序列@return int:返回正确的结果
*/
int func(char* input) {createTable();// Please fill this blank//将char*转换为intint num = 0, i = 0;while(input[i] != '\0'){num = num*10+input[i] -'0';i++;}return table[num];
}int main() {char str[100];printf("请输入一个字符串\n");scanf("%s", str);printf("%d", func(str));return 0;
}
分析
- 题目并没有说明输入的字符的最大数量,在我的代码里人为定义了MAX,会造成内存溢出的问题(ERR)
- createTable的成本太高太高太高。内层while次数取决于位数,可以近似等于log(i)。所以总的时间复杂度应该是O(nlog(n))

参考题解
因为限制了最小正整数m>9,所以对于小于10的数,返回结果应该是(10+num);对于大于等于10的数,高位越小,那么得到的数字肯定越小,结果其实就是这个整数的因子的一个组合,要得到最小的组合的整数,那么低位就应该尽可能的取大值,这样才能保证高位得到的是最小的。如果没有余数就表示这个数是有结果的,有余数就表示这个数不存在。
#include <stdio.h>
int func(char* input){
//将str转换为intint i = 0, num = 0, res = 0, pos = 1;while(input[i]!='\0'){num = num*10 + input[i]-'0';i++;}if(num < 10) return (10+num);for(i = 9; i > 1; i--){while(num% i == 0){//pos表示位数res += i*pos;pos *= 10;num/=i;}}if(num> 1) return -1;else return res;
}int main() {char str[1000];printf("请输入一个字符串\n");scanf("%s", str);printf("%d", func(str));return 0;
}
分析
时间复杂度应该是O(log(n)),因为这里char转换为整型也存在可能内存溢出的情况,但是没有上面的严重。

相关文章:
VIVO算法题——数位之积
记录算法究极无敌菜菜菜鸟的垃圾思维 题目: 现给定任意正整数 n,请寻找并输出最小的正整数 m(m>9),使得 m 的各位(个位、十位、百位 … …)之乘积等于n,若不存在则输出 -1。 菜鸟…...
OPC Router快速打通设备层与influxDB数据通讯
随着时代演化,数据量呈几何倍数增加的情况下出现了时序数据库。时序数据库是基于时间进行存储的数据库,每一条数据中都有一个时间戳,这种数据库特别适合存储那些随着时间变化的数据,通过一些工具处理后,能够分析出数据…...
鸿蒙开发 四十四 ArkTs BuilderParam传递UI(二)
子组件多个BuilderParam,必须通过参数的方式传入,如果界面中有多个界面需要传递,可以定义多个尾随闭包,如图: 在自定义组件中调用: 在使用时候调用是作为参数传递给自定义的组件,参数是界面&…...
同期数分析-留存率
目录 同期数分析 加载数据 单月实现 统计每个月的订单量 求2月份的订单量和用户数量 求2月之前的历史订单量 筛选出2023年2月的新增的用户数 计算2023年2月在后面的留存情况 完整的2023年2月份同期群结果 遍历合并和分析 引入月份列表 遍历 调整成留存率的形式 回…...
Java前后端交互:构建现代Web应用
在现代Web应用开发中,前后端分离是一种常见的架构模式。后端通常负责数据处理和业务逻辑,而前端则负责用户界面和用户体验。Java作为后端开发的强大语言,提供了多种方式与前端进行交互。本文将探讨Java后端与前端交互的几种主要方式ÿ…...
vue3中用axios请求怎么添加cookie
在 Vue 3 中使用 axios 发起请求时,可以通过配置 axios 的请求选项来携带 Cookies。具体来说,确保跨域请求时,设置 withCredentials: true,以便发送和接收 Cookies。 1. Axios 配置携带 Cookie 首先确保你在 axios 请求中设置了…...
informer学习笔记
一、informer讲解 infomer 要解决的三大问题: Attention计算的更快Decoder要一次性输出所有预测堆叠encoder也要更快 1. Attention 在长序列中,并非每一个位置的Attention都重要,对于每一个Q来说,只有一小部分的K与其有较强的…...
Elasticsearch介绍和使用
一、Elasticsearch 强大的搜索和分析能力: Elasticsearch 是一个基于 Lucene 的分布式搜索和分析引擎。它能够快速地对大量数据进行全文搜索、结构化搜索和复杂的数据分析操作。对于大型数据集,它可以高效地处理各种查询需求,包括关键词搜索…...
【Flutter】基础入门:代码基本结构
通过这个简单的 Flutter 示例程序,我们可以快速了解 Flutter 的代码结构,理解每个部分的作用。 import package:flutter/material.dart; void main() { runApp(const MyApp()); } class MyApp extends StatelessWidget { const MyApp({super.key}…...
如何进行数据库缩容 | OceanBase应用实践
作者:关炳文,爱可生 DBA 团队成员,负责数据库相关技术支持。 本文详细介绍了OceanBase V3.2版的集群中,面对数据文件缩容的场景的一套缩容方案,作为大家的参考。 缩容场景 某银行运行的一套采用1-1-1架构的OceanBase…...
机器学习和深度学习的差别
定义和基本原理 机器学习: 定义:机器学习是一种让计算机自动从数据中学习规律和模式的方法,无需明确编程。它通过构建数学模型,利用已知数据进行训练,然后对新的数据进行预测或决策。基本原理:机器学习算…...
RAG拉满-上下文embedding与大模型cache
无论怎么选择RAG的切分方案,仍然切分不准确。 最近,anthropics给出了补充上下文的embedding的方案,RAG有了新的进展和突破。 从最基础的向量查询,到上下文embedding,再到rerank的测试准确度都有了明显的改善…...
前端学习---(2)CSS基础
CSS 用来干什么? CSS 是用来指定文档如何展示给用户的一门语言——如网页的样式、布局、等等。 css语法: 选择器{ 属性名: 属性值; 属性名: 属性值; } h1 {color: red;font-size: 5em; }h1: 选择器 color: 属性 冒号之前是属性,冒号之后是值。 font-size…...
Pandas常用计算函数
目录 排序函数 nlargest函数 nsmallest函数 sort_values函数 df.sort_values Series.sort_values 聚合函数 corr函数-相关性 min函数-最小值 max函数-最大值 mean函数-平均值 sum函数-求和 count函数-统计非空数据 std函数-标准偏差 quantile函数-分位数 排序函…...
C++ | Leetcode C++题解之第473题火柴拼正方形
题目: 题解: class Solution { public:bool makesquare(vector<int>& matchsticks) {int totalLen accumulate(matchsticks.begin(), matchsticks.end(), 0);if (totalLen % 4 ! 0) {return false;}int len totalLen / 4, n matchsticks.s…...
深度解析RLS(Recursive Least Squares)算法
目录 一、引言二、RLS算法的基本思想三、RLS算法的数学推导四、RLS算法的特点五、RLS算法的应用场景六、RLS算法的局限性七、总结 一、引言 在自适应滤波领域,LMS(Least Mean Squares)算法因其计算简单、实现方便而广受欢迎。然而࿰…...
Centos 7.9NFS搭建
原创作者:运维工程师 谢晋 Centos 7.9NFS搭建 NFS服务端安装客户机访问共享配置 NFS服务端安装 SSH连接系统登录到服务端安装nfs服务 # yum -y install nfs-utils2. 安装完成后,查看需要共享的目录,这边共享的是/home目录,如…...
Python库numpy之三
Python库numpy之三 # NumPy数组创建函数二维数组创建函数numpy.eye应用例子numpy.diag应用例子numpy.vander应用例子 # NumPy数组创建函数 二维数组创建函数 numpy.eye 词法:numpy.eye(N, MNone, k0, dtype<class ‘float’>, order‘C’, *, deviceNone, …...
postgresql 安装
一、下载 PostgreSQL: File Browser 下载地址 PostgreSQL: File Browser 上传到服务器,并解压 二、安装依赖 yum install -y perl-ExtUtils-Embed readline-devel zlib-devel pam-devel libxml2-devel libxslt-devel openldap-devel 创建postgresql 和目录 useradd …...
基于机器学习的天气数据分析与预测系统
天气预报是日常生活中非常重要的信息来源,能够帮助人们合理安排日程、预防自然灾害。随着数据科学和机器学习的快速发展,传统的天气预报方法逐渐向基于数据驱动的机器学习方法转变。本文将探讨如何构建一个基于机器学习的天气数据分析与预测系统…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...

