0


【Java刷题特辑第二章】—— 这些经典笔试题,你确定都做过吗?

✨【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 ^ 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];
    }
}

✨🎉总结

“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉

在这里插入图片描述

标签: Java 算法 笔试

本文转载自: https://blog.csdn.net/Biteht/article/details/124444190
版权归原作者 偷偷敲代码的青花瓷 所有, 如有侵权,请联系我们删除。

“【Java刷题特辑第二章】&mdash;&mdash; 这些经典笔试题,你确定都做过吗?”的评论:

还没有评论