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

2022年05月10日 阅读数:6
这篇文章主要向大家介绍【Java刷题特辑第二章】—— 这些经典笔试题,你肯定都作过吗?,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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


做者介绍:git

🎓做者:青花瓷
👀做者的Gitee:代码仓库
📌系列文章推荐:
✨1.Java刷题特辑第一章
✨2.算法篇之动态规划
✨3.青蛙跳台阶问题总汇
✨✨我和你们同样都是热爱编程✨,很高兴能在此和你们分享知识,但愿在分享知识的同时,能和你们一块儿共同进步,取得好成绩🤳,今天和你们分享的章节是 ,若是有错误❌,欢迎指正哟😋,咋们废话很少说,跟紧步伐,开始学习吧~😊web

在这里插入图片描述


前言:算法

🎉文章目录,从易到难,层层递进,若是每一道题都吃透,你必定会在作题方面有质的飞跃,关注我,一块儿学习算法,一块儿分享好的题型。博主将持续更新算法,大厂笔试题,经典算法题,易错题,若是以为不错,点点赞支持一下,若是有错误的地方,欢迎指正✨✨编程


✨易错篇

✨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时,相加结束

代码以下:app

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.三角形

连接:题目连接
来源:牛客网svg

给定三条边,请你判断一下能不能组成一个三角形。

输入描述:
输入包含多组数据,每组数据包含三个正整数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];
    }
}


✨🎉总结

“种一颗树最好的是十年前,其次就是如今”
因此,
“让咱们一块儿努力吧,去奔赴更高更远的山海”

若是有错误❌,欢迎指正哟😋

🎉若是以为收获满满,能够动动小手,点点赞👍,支持一下哟🎉

在这里插入图片描述