Java工程师丨面试真题(二)

简介: Java工程师丨面试真题(二)

一、附加题

描述

二阶魔方又叫小魔方,是2*2*2的立方形结构。每一面都有4个块,共有24个块。每次操作可以将任意一面逆时针或者顺时针旋转90°,如将上面逆时针旋转90°操作如下。

编辑

Nero在小魔方上做了一些改动,用数字替换每个块上面的颜色,称之为数字魔方。魔方上每一面的优美度就是这个面上4个数字的乘积,而魔方的总优美度就是6个面优美度总和。

现在Nero有一个数字魔方,他想知道这个魔方在操作不超过5次的前提下能达到的最大优美度是多少。

魔方展开后每一块的序号如下图:

编辑

输入描述:

输入一行包含24个数字,按序号顺序给出魔方每一块上面的数字。所有数大小范围为[-100,100]。

输出描述:

输出一行包含一个数字,表示最大优美度。

示例1

输入:

2 -3 -2 3 7 -6 -6 -7 9 -5 -9 -3 -2 1 4 -9 -1 -10 -5 -5 -10 -4 8 2

输出:

8281

题解:

import java.util.*;
public class Main {
    /**
     * 记录三种旋转需要变动的下标,共三组下标
     * 每组下标里,每4个下标形成一个轮回
     */
    private static int[][] map = new int[][]{
        {0,1,3,2,7,5,22,9,6,4,23,8},
        {6,7,13,12,2,8,17,11,3,14,16,5},
        {4,5,11,10,0,6,16,20,2,12,18,22}
    };
    /**
     * main
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 读取输入
        Scanner sc = new Scanner(System.in);
        int[] n = new int[24];
        for (int i = 0; i < 24; i++) {
            n[i] = sc.nextInt();
        }
        // 输出结果
        System.out.println(resolve(n, -1, 5));
    }
    /**
     * 分析当前状态
     * @param n 当前状态
     * @param type 达到当前状态时的最后一个操作类型
     * @param remain 剩余操作数
     * @return 可以达到的最大优美度
     */
    private static int resolve(int[] n, int type, int remain) {
        // 非法状态
        if (remain < 0) return Integer.MIN_VALUE;
        // 当前状态优美度
        int max = compute(n);
        // 尝试转动,不可与type类型相同
        if (type != 0) max = Math.max(max, turn(n, 0, remain));
        if (type != 1) max = Math.max(max, turn(n, 1, remain));
        if (type != 2) max = Math.max(max, turn(n, 2, remain));
        return max;
    }
    /**
     * 按照类型转动魔方多次并分析
     * @param n 当前状态
     * @param type 转动类型
     * @param remain 剩余操作数
     * @return 转动可以达到的最大优美度
     */
    private static int turn(int[] n, int type, int remain) {
        // 转动一次
        turn(n, type);
        int max = resolve(n, type, remain-1);
        // 转动两次
        turn(n, type);
        max = Math.max(max, resolve(n, type, remain-2));
        // 转动三次,相当于逆向转动一次
        turn(n, type);
        max = Math.max(max, resolve(n, type, remain-1));
        // 转动四次,还原初始状态
        turn(n, type);
        return max;
    }
    /**
     * 转动操作
     * @param n 当前状态
     * @param type 转动类型
     */
    private static void turn(int[] n, int type) {
        // 每四个下标一轮回
        for (int i = 0, tmp = 0; i < 12; i++) {
            if (i % 4 == 0) tmp = n[map[type][i]];
            if (i % 4 == 3) n[map[type][i]] = tmp;
            else n[map[type][i]] = n[map[type][i+1]];
        }
    }
    /**
     * 计算当前状态的优美度
     * @param n 当前状态
     * @return 优美度
     */
    private static int compute(int[] n) {
        return n[0]*n[1]*n[2]*n[3] +
               n[6]*n[7]*n[12]*n[13] +
               n[4]*n[5]*n[10]*n[11] +
               n[8]*n[9]*n[14]*n[15] +
               n[16]*n[17]*n[18]*n[19] +
               n[20]*n[21]*n[22]*n[23];
    }
}

二、编程题1

描述

有一个推箱子的游戏, 一开始的情况如下图:

编辑

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;

..S0.. -> ...S0.

注意不能将箱子推动到'#'上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。

输入描述:

第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);

后面为n行字符串,每行字符串有m字符, 表示游戏盘面;

输出描述:

一个数字,表示最少几步能完成游戏,如果不能,输出-1;

示例1

输入:

3 6
.S#..E
.#.0..
......

输出:

11

题解:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        char[][] chas=new char[n][m];
        // 人的起始位置S 以及箱子的位置
        int startX=0,startY=0,boxX=0,boxY=0;
        // 判断位置 ,即人要先找到箱子,再推着箱子往前走
        for(int i=0;i&amp;lt;n;i++){   
            String string=sc.next();
            for(int j=0;j&amp;lt;m;j++){
                chas[i][j]=string.charAt(j);
                if(chas[i][j]==&amp;#39;S&amp;#39;){
                    startX=i;
                    startY=j;
                }
                if(chas[i][j]==&amp;#39;0&amp;#39;){
                    boxX=i;
                    boxY=j;
                }
            }
        }
        System.out.println(solve(chas,startX,startY,boxX,boxY));
    }
    public static class Node{
        int px;  // 人的位置
        int py;
        int bx;  //箱子的位置
        int by;
        int step;  //从初始位置到现在节点所走的步数
        public Node(int px,int py,int bx,int by){
            this.px=px;
            this.py=py;
            this.bx=bx;
            this.by=by;
        }
    }
    private static int solve(char[][] chas,int startX, int startY,int boxX,int boxY) {
        Node start=new Node(startX, startY,boxX,boxY);
        int n=chas.length;
        int m=chas[0].length;
        // iswalked四维数组,可以用来存储走过的路径以防重复。
        int[][][][] iswalked=new int[n][m][n][m];
        // 每个节点都有dir4个方向的移动,分别是  下右上左   
        int[][] movedir=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};  
        Queue&amp;lt;Node&amp;gt; que=new LinkedList&amp;lt;&amp;gt;();  //利用队列实现BFS
        start.step=0;
        que.add(start);
        //开始BFS广度搜索最短路径
        while(!que.isEmpty()){
            Node cur=que.poll();
            int newBx=cur.bx;
            int newBy=cur.by;
            for(int i=0;i&amp;lt;4;i++){  // 向4个方向走
                //人在箱子左边或右边
                if(cur.px==cur.bx){
                     if (cur.py+movedir[i][1]==cur.by){
                         newBy = cur.by+movedir[i][1];
                     }else{
                         newBy = cur.by;
                     }
                }  
              //人在箱子上面或下面 
                if(cur.py==cur.by){
                    if(cur.px+movedir[i][0]==cur.bx){
                        newBx = cur.bx+movedir[i][0];
                    }else{
                        newBx = cur.bx;
                    }
               }
                // 箱子找到了要随人往4个方向动;没找到则箱子不动人动
                Node next=new Node(cur.px+movedir[i][0], cur.py+movedir[i][1],newBx,newBy); 
                //不能让人在没找到箱子之前出地图或者自己提前到目的地
                if(next.px&amp;lt;0||next.px&amp;gt;=n||next.py&amp;lt;0||next.py&amp;gt;=m||chas[next.px][next.py]==&amp;#39;#&amp;#39;   
                        ||next.bx&amp;lt;0||next.bx&amp;gt;=n||next.by&amp;lt;0||next.by&amp;gt;=m
                        ||chas[next.bx][next.by]==&amp;#39;#&amp;#39;){
                    continue;
                }
                // 0说明这条路径没有走过
                if(iswalked[next.px][next.py][next.bx][next.by]==0){  
                    iswalked[next.px][next.py][next.bx][next.by]=1;
                    next.step=cur.step+1;
                    if(chas[next.bx][next.by]==&amp;#39;E&amp;#39;){   //此时把箱子推到终点了
                        return next.step;  // 最先到终点的就是最短路径
                    }
                    que.add(next);
                }
            }
        }
        return -1;
    }
}

三、编程题2

描述

有n个房间,现在i号房间里的人需要被重新分配,分配的规则是这样的:先让i号房间里的人全都出来,接下来按照 i+1, i+2, i+3, ... 的顺序依此往这些房间里放一个人,n号房间的的下一个房间是1号房间,直到所有的人都被重新分配。

现在告诉你分配完后每个房间的人数以及最后一个人被分配的房间号x,你需要求出分配前每个房间的人数。数据保证一定有解,若有多解输出任意一个解。

输入描述:

第一行两个整数n, x (2<=n<=10^5, 1<=x<=n),代表房间房间数量以及最后一个人被分配的房间号;

第二行n个整数 a_i(0<=a_i<=10^9) ,代表每个房间分配后的人数。

输出描述:

输出n个整数,代表每个房间分配前的人数。

示例1

输入:

3 1
6 5 1

输出:

4 4 4

题解:

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt() - 1;
        long[] room = new long[n];
        long min = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            room[i] = scanner.nextInt();
            if (room[i] < min)
                min = room[i];
        }
        //get min_index
        int minIndex = x;
        while (room[minIndex] != min) {
            minIndex = minIndex > 0 ? minIndex - 1 : n - 1;
        }
        // remove the round number.
        for (int i = 0; i < n; i++) {
            room[i] -= min;
        }
        // remove the tail
        int remain = 0;
        for (int i = x; i != minIndex; i = i > 0 ? i - 1 : n - 1) {
            room[i] -= 1;
            remain += 1;
        }
        room[minIndex] += remain + n * min;
        //print the result
        for (int i = 0; i < n; i++) {
            System.out.print(room[i] + " ");
        }
    }
}

四、字母交换

描述

【编码题】字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?

输入描述:

第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)

输出描述:

一个非负整数,表示操作之后,连续最长的相同字母数量。

示例1

输入:

abcbaa 2

输出:

2

说明:

使2个字母a连续出现,至少需要3次操作。即把第1个位置上的a移动到第4个位置。
所以在至多操作2次的情况下,最多只能使2个b或2个a连续出现。

题解:

import java.util.*;
public class Main{
    static int res = 1;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String str = input.split(" ")[0];
        int m = Integer.parseInt(input.split(" ")[1]);
        HashMap<Character, List<Integer>> map = new HashMap<>();
        char[] chars = str.toCharArray();
        int len = chars.length;
        for(int i = 0; i < len; i++){
            List<Integer> list = map.getOrDefault(chars[i], new ArrayList<>());
            list.add(i);
            map.put(chars[i], list);
        }
        for(int i = 0; i < len; i++){
            char c = chars[i];
            List<Integer> list = map.get(c);
            moveTogether(list, i, m);
            /*
            int lessCount = 0;
            for(int num : list){
                if(num < i){
                    lessCount++;
                }
                else{
                    break;
                }
            }
            int greatCount = list.size()-1-lessCount;
            for(int j = 0; j < lessCount; i++){
                int cur = list.get(j);
                // 现在这个节点的位置在cur,要移动到          (0 1 j 3 4 ... lessCount-1)i
                // lesscount-2的时候对应i-2
                // lesscount-1的时候对应i-1
                int target = i + j - lessCount;
                int times = 
            }
        }
*/
    }
                System.out.println(res);
    }
            // 在times步内,尽可能把list里面的数字移动到mid周围
        public static void moveTogether(List<Integer> list, int mid, int times){
            int len = list.size();
            int mid_index = 0;
            for(int i = 0; i < len; i++){
                if(list.get(i) == mid){
                    mid_index = i;
                    break;
                }
            }
            int left_index = mid_index-1;
            int right_index = mid_index+1;
            int count = 1;
            // mid为中心的左右边界
            int left_mid = mid-1;
            int right_mid = mid+1;
            while(times > 0){
                if(left_index < 0 && right_index >= len){
                    break;
                }
                // 看一下左边和右边哪个更近一点
                int left_dist;
                if(left_index < 0)    
                    left_dist = Integer.MAX_VALUE / 2;
                else    
                    left_dist = left_mid - list.get(left_index);
                int right_dist;
                if(right_index >= len)   {
                    right_dist = Integer.MAX_VALUE / 2;
                } 
                else {
                    right_dist = list.get(right_index) - right_mid; 
                }    
                if(left_dist > right_dist){
                    // 右边靠更加近一点
                    if(times < right_dist)    break;
                    times -= right_dist;
                    right_mid++;
                    count++;
                    right_index++;
                }
                else{
                    if(times < left_dist)    break;
                    times -= left_dist;
                    left_mid--;
                    left_index--;
                    count++;
                }
            }
            res = Math.max(count, res);
        }
}
相关文章
|
2月前
|
架构师 前端开发 Java
Java开发工程师的职业规划应该是什么样的?
Java开发工程师的职业规划涵盖多个阶段,包括初入行业(0-1年)、技能提升(1-3年)、技术专家(3-5年)及管理或专家路线选择(5年以上)。各阶段设定了明确的技能要求与职业目标,从掌握Java基础、常用框架到深入研究高级技术、微服务架构乃至担任管理职务或成为技术专家。通过持续学习与实践,结合个人兴趣,Java工程师可在技术或管理领域找到合适的发展方向,最终实现职业成功。
326 83
|
17天前
|
存储 安全 算法
Java面试题之Java集合面试题 50道(带答案)
这篇文章提供了50道Java集合框架的面试题及其答案,涵盖了集合的基础知识、底层数据结构、不同集合类的特点和用法,以及一些高级主题如并发集合的使用。
39 1
Java面试题之Java集合面试题 50道(带答案)
|
6天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
20 5
|
5天前
|
存储 Java
[Java]面试官:你对异常处理了解多少,例如,finally中可以有return吗?
本文介绍了Java中`try...catch...finally`语句的使用细节及返回值问题,并探讨了JDK1.7引入的`try...with...resources`新特性,强调了异常处理机制及资源自动关闭的优势。
14 1
|
14天前
|
Java 程序员
Java 面试高频考点:static 和 final 深度剖析
本文介绍了 Java 中的 `static` 和 `final` 关键字。`static` 修饰的属性和方法属于类而非对象,所有实例共享;`final` 用于变量、方法和类,确保其不可修改或继承。两者结合可用于定义常量。文章通过具体示例详细解析了它们的用法和应用场景。
21 3
|
2月前
|
设计模式 Java 关系型数据库
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
本文是“Java学习路线”专栏的导航文章,目标是为Java初学者和初中高级工程师提供一套完整的Java学习路线。
334 37
|
17天前
|
Java
Java面试题之cpu占用率100%,进行定位和解决
这篇文章介绍了如何定位和解决Java服务中CPU占用率过高的问题,包括使用top命令找到高CPU占用的进程和线程,以及使用jstack工具获取堆栈信息来确定问题代码位置的步骤。
41 0
Java面试题之cpu占用率100%,进行定位和解决
|
21天前
|
存储 安全 Java
java基础面试题
java基础面试题
21 2
|
21天前
|
缓存 NoSQL Java
Java中redis面试题
Java中redis面试题
28 1
|
22天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
50 2