?【Java刷题特辑第二章】—— 这些经典笔试题,你确定都做过吗?
作者介绍:
🎓作者:青花瓷?
👀作者的Gitee:代码仓库
📌系列文章推荐:
?1.Java刷题特辑第一章
?2.算法篇之动态规划
?3.青蛙跳台阶问题总汇
??我和大家一样都是热爱编程?,很高兴能在此和大家分享知识,希望在分享知识的同时,能和大家一起共同进步,取得好成绩🤳,今天和大家分享的章节是 ,如果有错误?,欢迎指正哟😋,咋们废话不多说,跟紧步伐,开始学习吧~😊
前言:
🎉文章目录,
从易到难,层层递进,如果每一道题都吃透,你一定会在做题方面有质的飞跃,关注我,一起学习算法,一起分享好的题型。博主将持续更新算法,大厂笔试题,经典算法题,易错题,如果觉得不错,点点赞支持一下,如果有错误的地方,欢迎指正??
?易错篇
?1.不使用加减乘除做加法
链接：题目链接
来源：牛客网
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 -10 \le n \le 1000?10≤n≤1000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(1)O(1)
示例1
输入
1,2
输出
3
示例2
输入
0,0
输出
0
解题思路:
这道题涉及的知识点是位运算,首先我们需要先知道为运算符有哪些,具体有什么作用
二进制位异或运算相当于对应位相加，不考虑进位
比如： 1 ^ 1 = 0 —> 1 + 1 = 0 (当前位值为0，进一位)
1 ^ 0 = 1 —> 1 + 0 = 1 (当前位值为1)
0 ^ 0 = 0 —> 0 + 0 = 0 (当前位值为0)
2.二进制位与运算相当于对应位相加之后的进位
比如： 1 & 1 = 1 —> 1 + 1 = 0 (当前位的值进一位)
1 & 0 = 0 —> 1 + 0 = 1 (当前位的值不进位)
0 & 0 = 0 —> 0 + 0 = 0 (当前位的值不进位)
3.两个数相加：对应二进制位相加的结果 + 进位的结果比如：3 + 2 --> 0011 + 0010 --> 0011 ^ 0010 + ((0011 & 0010) << 1)
—> (0011 ^ 0010) ^ ((0011 & 0010) << 1)，当进位之后的结果为0时，相加结束
代码如下:
public class Solution {
public int Add(int num1,int num2) {
//使用 按位与 ,查看进制位,运算中需要进位/以将结果左移一位,继续运算
int n1 = (num1 & num2) << 1;
//按位异或,可以计算得到不考虑进位相加的结果
int n2 = num1 ^ num2;
//如果不含进制位直接返回n2,否则将两个结果继续相加,直到结果中没有进制位
return n1 == 0 ? n2 : Add(n1,n2);
}
}
?2.三角形
链接：题目链接
来源：牛客网
给定三条边，请你判断一下能不能组成一个三角形。
输入描述:
输入包含多组数据，每组数据包含三个正整数a、b、c（1≤a, b, c≤10^100）。
输出描述:
对应每一组数据，如果它们能组成一个三角形，则输出“Yes”；否则，输出“No”。
示例1
输入
1 2 3
2 2 2
输出
No
Yes
解题思路:
我们都知道,给你三条边,判断能不能构成三角形,最基本的判断方法就是看两边之和是否大于第三边,这道题看似简单,我们只需要进行判断就行了,但是有一个易错点,就是题上给定的三个正整数的取值范围,特别大,我们使用常规的Int类型是不可取的
因此这道题,我们使用 BigInteger
在 Java 中，有许多数字处理的类，比如 Integer类，但是Integer类有一定的局限性。
我们都知道 Integer 是 Int 的包装类，int 的最大值为 2^31-1。若希望描述更大的整数数据时，使用Integer 数据类型就无法实现了，所以Java中提供了BigInteger 类。
BigInteger类型的数字范围较Integer，Long类型的数字范围要大得多，它支持任意精度的整数，也就是说在运算中 BigInteger 类型可以准确地表示任何大小的整数值而不会丢失任何信息。
代码如下:
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
BigInteger a = sc.nextBigInteger();
BigInteger b = sc.nextBigInteger();
BigInteger c = sc.nextBigInteger();
//判断是不是三角形,只需要满足两边之和大于第三边即可
if(a.add(b).compareTo(c) > 0 && a.add(c).compareTo(b) > 0 && b.add(c).compareTo(a) > 0) {
System.out.println("Yes");
}else{
System.out.println("No");
}
}
}
}
?3.变态跳台阶
链接：题目链接
来源：牛客网
一只青蛙一次可以跳上1级台阶，也可以跳上2级…它也可以跳上n级。
求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围：1 \le n \le 201≤n≤20
进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(1)O(1)
示例1
输入
3
输出
4
示例2
输入
1
输出
1
解题思路:
这道题是,
青蛙跳台阶(斐波那契)的 一个延伸,这道题我们需要记住它的推导公式,以后遇到要熟悉知。
用Fib(n)表示青蛙跳上n阶台阶的跳法数，青蛙一次性跳上n阶台阶的跳法数1(n阶跳)，设定Fib(0) = 1；
当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1;
当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2) = Fib(1) + Fib(0) = 2;
当n = 3 时，有三种跳的方式，第一次跳出一阶后，后面还有Fib(3-1)中跳法；
第一次跳出二阶后，后面还有Fib(3-2)中跳法；第一次跳出三阶后，后面还有Fib(3-3)中跳法
Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法；
第一次跳出二阶后，后面还有Fib(n-2)中跳法...第一次跳出n阶后, 后面还有 Fib(n-n)中跳法.
Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+...+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+...+Fib(n-1)
又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+...+Fib(n-2)
两式相减得：Fib(n)-Fib(n-1)=Fib(n-1) --> Fib(n) = 2*Fib(n-1) (n >= 2)
递归等式如下：
代码如下:
public class Solution {
public int jumpFloorII(int target) {
if(target <=1) {
return 1;
}
return 2*jumpFloorII(target-1);
}
}
?4.青蛙跳台阶问题的汇总
?5.快到碗里来
链接:题目链接
来源：牛客网
小喵们很喜欢把自己装进容器里的（例如碗），但是要是碗的周长比喵的身长还短，它们就进不去了。
现在告诉你它们的身长，和碗的半径，请判断一下能否到碗里去。
输入描述:
输入有多组数据。
每组数据包含两个整数n (1≤n≤2^128) 和r (1≤r≤2^128)，分别代表喵的身长和碗的半径。
圆周率使用3.14。
输出描述:
对应每一组数据，如果喵能装进碗里就输出“Yes”；否则输出“No”。
示例1
输入
6 1
7 1
9876543210 1234567890
输出
Yes
No
No
解题思路:
这个题目很容易理解，只要输入的
猫的身长小于碗的周长即可,通过输入碗半径计算得到周长，与输入的猫的身长相比较。周长等于=2*π*r
注意
题目给定的输入数据的范围特别大,并且还有小数 == > 浮点形类型
代码如下:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
//小猫的身长
Double n = sc.nextDouble();
//碗的半径
Double m = sc.nextDouble();
if(n < 2*m*3.14) {//注意这里:小猫身长必须小于碗,等于都不行哈
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
}
?不易读懂题目篇
?1.星际密码
链接：题目链接
来源：牛客网
星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
|1 1|^n => |Xn ..|
|1 0| |.. ..|
例如n=2时，
|1 1|^2 => |1 1| * |1 1| => |2 1|
|1 0| |1 0| |1 0| |1 1|
即2对应的数是“0002”。
输入描述:
输入有多组数据。
每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)
输出描述:
对应每一组输入，输出一行相应的密码。
示例1
输入
6
18 15 21 13 25 27
5
1 10 100 1000 10000
输出
418109877711037713937811
00010089410135017501
解题思路:
这道题其实没有想的那么困难,其实是一道很简单的一道题目,只是可能说我们在牛客上做题的时候,把这个矩阵,这个题目描述的有些抽象,不是太好理解,没关系,让我来带大家来好好拿捏这道题
做这道题之前,我们需要知道 矩阵 是如何相乘的:
我们知道矩阵如何相乘之后,我们根据题目说的去一步一步的推导:
注意这里的输出格式,题目要求的是:
如果这个数不足4位则用0来填充,如果大于4位则只输出最后4位
因此我们这里需要一个格式化处理:String.format
String.format()函数:将括号里的量,按照自己想要的格式拼接成一个字符串,然后输出
"%04d":十进制数,输入4位,不足4位就补0,如果本身大于4位,就正常输出
代码如下:
// write your code here
import java.util.*;
public class Main{
public static void main(String[] args){
//注意,数组的索引是从0开始的,题上给出的xi的范围是在0-10000
//所以这里数组的长度应该是10001
int[] nums = new int[10001];
nums[1] = 1;
nums[2] = 2;
for(int i = 3; i < 10001;i++){
nums[i] = nums[i - 1] + nums[i - 2];
//输出后四位
nums[i] = nums[i] % 10000;
}
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
StringBuilder sb = new StringBuilder();
int n = sc.nextInt();
for(int i = 0; i < n; i++){
int xi = sc.nextInt();
//将结果用字符串拼接起来
//
sb.append(String.format("%04d", nums[xi]));
}
System.out.println(sb);
}
}
}
?2.树根
链接：题目链接
来源：牛客网
数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。
比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。
再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。
现在给你一个正整数，输出它的数根。
输入描述:
输入包含多组数据。
每组数据数据包含一个正整数n（1≤n≤10E1000）。
输出描述:
对应每一组数据，输出该正整数的数根。
示例1
输入
24
39
输出
6
3
解题思路:
这道题可能最大的坑在于n是长整数，故用字符数组就能很好解决。
1.接收到字符串得到各个数字,并且每位求和
2.循环对大于9的数字进行10取余和整除操作,将两个结果进行相加得到树根
代码如下:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String line = sc.nextLine();
while(line.length() > 1) {
int n = 0;
for(int i = 0;i < line.length();i++) {
n += line.charAt(i) - '0';
}
line = String.valueOf(n);
}
System.out.println(line);
}
}
}
?3.微信红包
链接:题目链接
来源:牛客
描述
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
数据范围： 1 \le n \le 1000 \1≤n≤1000 ,红包金额满足 1 \le gift_i \le 100000\1≤gift
i
?
≤100000
示例1
输入：
[1,2,3,2,2],5
复制
返回值：
2
复制
示例2
输入：
[1,1,2,2,3,3],6
复制
返回值：
0
解题思路:
这道题解题的关键在于:如果
一个数出现次数超过一半了，排序过后，必然排在中间，则最后遍历
整个数组查看是否符合即可
代码如下:
import java.util.*;
public class Gift {
public int getValue(int[] gifts, int n) {
// 1. 先对数组进行排序
Arrays.sort(gifts);
// 2. 找到数组的中间值
int mid = gifts[n/2];
// 3. 遍历数组 判断红包金额出现的次数是否超过红包总数的一ban
// 如果超过返回 数组中间值,如果没有返回0
int count = 0;//记录出现的次数
for(int i =0;i < n;i++) {
if(gifts[i] == mid) {
count++;
}
}
// 4.判断
if(count > n/2) {
return gifts[n/2];
}else {
return 0;
}
}
}
?4.洗牌
链接:题目链接
来源:牛客
题目描述:
示例1
输入：
3
3 1
1
2
3
4
5
6
3 2
1
2
3
4
5
6
2 2
1
1
1
1
复制
输出：
1 4 2 5 3 6
1 5 4 3 2 6
1 1 1 1
解题思路:
代码如下:
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int m = scanner.nextInt();
while(m!=0){
int n = scanner.nextInt();
int k = scanner.nextInt();
int [] arr = new int[2*n];
//计算下标
for(int i = 0; i < 2*n;i++){
int temp = i;
for(int j = 0; j < k ;j++){
if(temp < n){
temp = 2*temp;
}else{
temp = 2*(temp-n) + 1;
}
}
//temp为元素经历k次之后的下标
arr[temp] = scanner.nextInt();
}
//输出
for(int i = 0;i < 2*n;i++){
if(i == 2*n-1){
System.out.print(arr[i]);
}else {
System.out.print(arr[i]+" ");
}
}
System.out.println();
m--;
}
}
}
}
? 5.MP3光标位置
链接:题目链接
来源:牛客
题目描述:
解题思路:
当歌曲数目少于等于4，其只有一页。
1.当当前是U操作时，分两种情况：① 光标指向第1首时，经过U操作得光标指向第n首；② 否则光标所在位置–。
2.当当前是D操作时，分两种情况：① 光标指向第n首时，经过U操作得光标指向第1首；② 否则光标所在位置++。
歌曲数目>4，大于1页。
1.当当前是U操作时，分三种情况：①光标指向第1首且本页开始位置也为第1首时，经过U操作得光标指向第n首，光标所在页的页首为n-3；除第①种情况，若光标所在位置为其所在页的页首位置，光标随页首位置均–；③光标不在该页页首位置，光标所在位置–；
2.当当前是D操作时，分三种情况：①光标指向第n首时且本页页首位置为n-3时，经过U操作得光标指向第1首，光标所在页的页首也指向第1首；除第①中情况，若光标所在位置为其所在页页尾位置（页首位置+3），光标随页首位置++，② ③光标不在该页页尾位置，光标位置所在位置++。
代码如下:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
// 输入多个这里 循环输入
int m = s.nextInt();//歌曲数量
String str1 = s.next();//命令
int top = 1;//指向每一页第一首歌;
int index = 1;//光标的位置
//开始判断指令
for (int i = 0; i < str1.length(); i++) {
//U 指令时
// 判断 光标位置,和 歌的位置
if(str1.charAt(i) == 'U') {
//1.判断特殊位置 光标在头一页 页首的时候
if(top == index) {
//光标在top位置时,如果top位置等于1,那么要翻页
top = top==1?m-3:top-1;//指向那首歌
}
index = index==1?m:index - 1;
}else if(str1.charAt(i) == 'D') {
// 2.光标在最后一页 页尾的时候
if(top+3 == index) {//top 始终指向每一页第一首歌,top+3 ---说明index在页尾
top = index== m ? 1 : top+1;//判断
}
index = index == m ? 1: index + 1;//判断光标位置
}
}
// 判断 < 4 的情况
if(m < 4) {
top = 1;
for (int i = 0; i < 3 && i< m-1; i++) {
System.out.print(top + i + " ");
}
System.out.println(top + m - 1);
}else{
for (int i = 0; i < 3; i++) {
System.out.print(top + i + " ");
}
System.out.println(top + 4 - 1);
}
System.out.println(index);
}
}
?字符串篇
?1.字符串反转
链接:题目链接
来源:力扣
描述
接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
输入描述：
输入一行，为一个只包含小写字母的字符串。
输出描述：
输出该字符串反转后的字符串。
示例1
输入：
abcd
复制
输出：
dcba
解题思路:
将字符串反转,调用
reverse函数可以直接对字符串反转,然后输出
代码如下:
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
StringBuilder sb = new StringBuilder(str);
sb.reverse();//字符串反转
System.out.println(sb);
}
}
?2.公共字串计算 (DP问题)
如果对
DP问题还不熟练,或者还不知道如何下手的UU们,可以去参考我前面发的一篇博客,希望对你有帮助哟?😊
算法篇之动态规划
链接:题目链接
来源:牛客
描述
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1\le s\le 150\1≤s≤150
进阶：时间复杂度：O(n^3)\O(n
3
) ，空间复杂度：O(n)\O(n)
输入描述：
输入两个只包含小写字母的字符串
输出描述：
输出一个整数，代表最大公共子串的长度
示例1
输入：
asdfas
werasdfaswer
复制
输出：
6
解题思路:
代码如下:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
System.out.println(GetMaxLen(str1,str2));
}
}
public static int GetMaxLen(String str1,String str2) {
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
int len1= arr1.length;
int len2 = arr2.length;
int[][] maxSubLen = new int[len1+1][len2+1];
int maxLen = 0;
for(int i = 1;i <= len1;i++) {
for(int j = 1;j <= len2;j++) {
if(arr1[i -1] == arr2[j -1]) {
maxSubLen[i][j] = maxSubLen[i-1][j-1] + 1;
}
if(maxLen < maxSubLen[i][j]) {
maxLen = maxSubLen[i][j];
}
}
}
return maxLen;
}
}
?3.计算字符串的编辑距离 (DP问题)
链接:题目链接
来源:牛客
描述
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。
数据范围：给定的字符串长度满足 1 \le len(str) \le 1000 \1≤len(str)≤1000
输入描述：
每组用例一共2行，为输入的两个字符串
输出描述：
每组用例输出一行，代表字符串的距离
示例1
输入：
abcdefg
abcdef
复制
输出：
1
解题思路:
总结:
若
两个字符相等，即str1[i-1] == str2[j-1]，则在这一个位置的编辑距离和上一个字符相同，因此对应的数组dp[i][j]=dp[i-1][j-1]
若两个字符不相等，可删除str1[i-1]这个字符，则dp[i][j] = 1 + dp[i-1][j]；删除str2[j-1]这个字符，则dp[i][j] = 1 + dp[i][j-1]；修改str1[i-1]使它与str2[i-1]相等，则dp[i][j] = 1 + dp[i-1][j-1]
代码如下:
import java.util.*;
public class Main{
public static void main(String [] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()){
String str1 = scanner.nextLine();
String str2 = scanner.nextLine();
System.out.println(getDistance(str1,str2));
}
}
public static int getDistance (String str1,String str2){
char[] wd1 = str1.toCharArray();
char[] wd2 = str2.toCharArray();
int len1 = wd1.length;
int len2 = wd2.length;
//定义一个矩阵
int[][] dist = new int[len1 + 1][len2 + 1];
//初始状态： F（i，0） =i ; F（0，j) == j
for(int i =1; i<= len1; i++){
dist[i][0] = i;
}
for(int j =0; j<=len2 ;j++){
dist[0][j] = j;
}
for(int i =1; i<= len1; i++){
for(int j =1; j<= len2;j++){
//判断插入和删除的最小值
dist[i][j] = Math.min(dist[i-1][j], dist[i][j-1]) +1;
if(wd1[i -1] == wd2[j-1]){
//如果相等，不需要替换
dist[i][j] = Math.min(dist[i][j] , dist[i-1][j-1]);
}else{
dist[i][j] = Math.min(dist[i][j] , dist[i-1][j-1] +1);
}
}
}
return dist[len1][len2];
}
}
?🎉总结
“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”
如果有错误?,欢迎指正哟😋
🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉
