⭐️前面的话⭐️
本篇文章介绍来自牛客试题广场的两道题题解,分别为【最难的问题】和【因子个数】,展示语言java。
小贴士:本专栏所有题目来自牛客->面试刷题必用工具
📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!
📆首发时间:🌴2022年9月29日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《算法》,📚《算法导论》
💬推荐在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
注意事项:本专栏所有题目都来自牛客网,如果有小伙伴还没有注册牛客,可以点击下方链接进行注册,注册完就能立即刷题了。不仅是刷题,上面还有很多有关就业的面经,面试题库,以及名企的模拟面试,我非常推荐它,博主自己用的也很多,也刷了不少题了!下图可以作证:
注册地址:牛客网
有关任何问题都可以与博主交流,你可以在评论区留言,也可以私信我,更可以加上博主的vx与博主一对一交流(文章最下方有)。
NowCoder生活在充满危险和阴谋的年代。为了生存,他首次发明了密码,用于军队的消息传递。假设你是军团中的一名军官,需要把发送来的消息破译出来、并提
供给你的将军。
消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第5个字母替换(例如:消息原文中的每个字母A 都分别替换成字母F),其他字符不 变,并且消息原文的所有字母都是大写的。密码中的字母与原文中的字母对应关系如下。
密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
输入描述:
输入包括多组数据,每组数据一行,为收到的密文。
密文仅有空格和大写字母组成。
输出描述:
对应每一组数据,输出解密后的明文。
示例1
输入
HELLO WORLD
SNHJ
输出
CZGGJ RJMGY
NICE
基本思路: 模拟题
解题思路:
题目的意思就是给你一个密码串,还原为原来的明文字符串,规则就是将大写字母的顺序向左移动五位,如A
,变为V
,F
变为A
。
那么有两种情况,如果字符出现在字母表的顺序在F
之前,则字符的ASCII加上21
,在F
之后的字符串,则字符的ASCII码减去5
。
当然还可以使用哈希表将密码字符与明文字符一一对应起来,根据对应起来的关系,根据密码表的字符查询也可以等到原来的明文。
// write your code here
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String pw = sc.nextLine();
StringBuilder ans = new StringBuilder();
int n = pw.length();
for (int i = 0; i < n; i++) {
char c = pw.charAt(i);
if (c == ' ') ans.append(c);
else if (c < 'F') ans.append((char) (c + 21));
else ans.append((char) (c - 5));
}
System.out.println(ans);
}
}
}
本题为简单模拟题,将密码字符在循环的字母表中向左移动五位即可。
一个正整数可以分解成一个或多个数组的积。例如36=223*3,即包含2和3两个因子。NowCoder最近在研究因子个数的分布规律,现在给出一系列正整数,他希望你开发一个程序输出每个正整数的因子个数。
输入描述:
输入包括多组数据。
每组数据仅有一个整数n (2≤n≤100000)。
输出描述:
对应每个整数,输出其因子个数,每个结果占一行。
示例1
输入
30
26
20
输出
3
2
2
链接:因子个数
来源:牛客网
基本思路: 数学模拟
解题思路:
题目给我们一个数字n,需要我们求构成这个数的素数因子,那么最大的因子肯定不会超过n的平方根,其实这道题很直接,我们可以从小到大枚举素数i
,然后判断n
是否能够被i
整除,如果可以,说明该数为n
的一个因子,并一直将n
除以i
直到不能够除尽为止并更新n
的值,然后将i
变为下一个素数,重复上述的判断。
但是其实不需要枚举出素数,其实从2
开始枚举正整数即可,因为被一个较小的因子除到不能够再整除的时候,后面再除以该因子的倍数肯定也是不能够被整除的,比如一个数被2
整除到的不能够再继续被整除了,那么它一定也不能够被2
的倍数整除。
举一个实际的例子:36=2*2*3*3,被2
整除到不能够被整除时,得到9
,9
是不能够被2
到的倍数整除的。
所以我们只需从2
开始枚举正整数,如果n
能够被整除,因子数加一,并将n
更新为不能再被当前枚举的数整除的那个值,并且更新后的n
的因子一定也会小于等于更新后的n
的开平方的值。
最后简单说一下,就是你可以理解一个数是由若干个素数乘积得来的,那么我们可以从小到大进行枚举,如果n
能够被整除,则将n
中所有的该因子都除尽,并将n
更新为除尽后的数,然后枚举下一个数以此类推。
当然,如果n
本身就是一个素数,最终n
的值会大于1
,所以最后还需要判断n
是否为1
,如果不为1
因子还包括n
本身,计数需要加1
。
// write your code here
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int ans = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) ans++;
while (n % i == 0) {
n /= i;
}
}
if (n != 1) {
ans++;
}
System.out.println(ans);
}
}
}
本题为因数分解题,属于数学问题。
到文章最后,再来安利一下吧,博主也是经常使用,并且也经常在牛客上刷题,题库也非常丰富:牛客网,刷题,面试,内推都有。也欢迎与博主交流有关刷题,技术方面,以及与博主聊聊天,交个朋友也好啊,毕竟有朋自远方来!