模拟笔试 - 卡码网周赛第二十一期(23年美团笔试真题)

第一题:小美的排列询问 

 

解题思路:
简单题,一次遍历数组,判断  是否有和x、y相等并且相连  即可。

可优化逻辑:因为x和y是后输入的,必须存储整个数组,但是上面说了 **排列是指一个长度为n的数组,其中 1 到 n 每个元素恰好出现一次。**可以充分利用该信息创建一个大小为n+1的数组存储各个元素的所在位置,这样最终直接判断x和y所在位置差是否为1即可判断结果。、

解法一 :哈希表(比较灵活运用哈希表)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //int[] arr = new int[n];
        //map 记录每个元素所在的位置
        int[] map = new int[n+1];
        for (int i = 0; i < n; i++) {
            int ai = scanner.nextInt();
            map[ai] = i;
        }
        int x = scanner.nextInt();
        int y = scanner.nextInt();

        if(Math.abs(map[x]-map[y])==1){
            System.out.println("Yes");
            return;
        }
        System.out.println("No");
    }
}

Math.abs 是 Java 中 java.lang.Math 类的一个静态方法,用于返回一个数的绝对值。绝对值指的是一个数在数轴上距离原点的距离,因此它始终是非负数。这个方法有多个重载版本,可以处理不同的数据类型,包括 intlongfloat 和 double

 时空复杂度

时间复杂度 :O(n)。一次遍历数组。

空间复杂度 :O(``n``)。哈希表所占空间

解法二:直接模拟(简单粗暴,易想到的方法)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int x = scanner.nextInt();
        int y = scanner.nextInt();

        //遍历数组arr,只有x在前,y在后,或者x在后,y在前的情况满足题意,属于Yes
        for (int i = 0; i < n - 1; i++) {
            if ((arr[i] == x && arr[i + 1] == y) || (arr[i] == y && arr[i + 1] == x)) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

第二题:小美走公路

解题思路

注意,本题和LeetCode1184.公交站间的距离完全一致。

题目要求计算最短距离,实际上一共只有两条可能的路径:顺时针从x走到y和逆时针从x走到y

因此只需要计算顺时针和逆时针的两个结果进行比较即可。

唯一需要注意的地方就是边界,即第n站到第1站的距离的计算,这里可以通过 逻辑判断 是否到达边界,也可以通过 取余的方式避免边界问题

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取站的数量
        int[] distances = new int[n]; // 存储各站之间的距离
        for (int i = 0; i < n; i++) {
            distances[i] = scanner.nextInt(); // 读取各站之间的距离
        }
        int x = scanner.nextInt(); // 读取出发站
        int y = scanner.nextInt(); // 读取目的站

        int clockwiseDistance = 0; // 顺时针方向的距离
        int counterClockwiseDistance = 0; // 逆时针方向的距离

        // 计算顺时针距离
        // 从出发站到目的站,顺时针方向逐个累加距离
        for (int i = x - 1; i != y - 1; i = (i + 1) % n) {
            clockwiseDistance += distances[i];
        }

        // 计算逆时针距离
        // 从目的站到出发站,逆时针方向逐个累加距离
        for (int i = y - 1; i != x - 1; i = (i + 1) % n) {
            counterClockwiseDistance += distances[i];
        }

        // 输出顺时针和逆时针两种情况下的最短距离
        System.out.println(Math.min(clockwiseDistance, counterClockwiseDistance));
    }
}

 (i + 1) % n : 是一种常见的操作,用于在循环列表(或环形缓冲区、圆形队列)中循环递增索引。这个操作确保了当索引增加到列表的末尾时,它会自动回到开头,从而实现环形访问。这里是详细解释:

  • i:当前的索引。
  • i + 1:下一个索引。
  • % n:取模运算符,n 是列表的长度。

作用

当 i 增加时,(i + 1) 可能会超过数组的最大索引(即 n-1)。为了使索引在超出数组边界时回到起点(形成一个环),使用了取模操作 % n

例如:

  • 当 i 为 0 到 n-2 时,(i + 1) % n 简单地返回 i + 1
  • 当 i 为 n-1(即最后一个元素的索引)时,(i + 1) % n 返回 0,这样就回到了数组的开头。

为了防止顺时针 x到y遇到边界(y在x前时有可能)或者y逆时针走,一定会遇到边界。都需要处理。

 如果用逻辑判断的方法:

这个代码使用逻辑判断来处理数组索引超出边界的情况,使得索引在到达数组边界时正确循环。这样,可以计算两个站之间的最短距离。

// 将站的编号转换为数组的索引(转化为从索引x 到 索引 y) -- 这么操作更方便理解

        int x = scanner.nextInt(); // 读取出发站的编号(假设从1开始)
        int y = scanner.nextInt(); // 读取目的站的编号(假设从1开始)

        // 将站的编号转换为数组的索引(转化为从索引x 到 索引 y)
        x = x - 1;
        y = y - 1;

        int clockwiseDistance = 0; // 初始化顺时针方向的距离
        int counterClockwiseDistance = 0; // 初始化逆时针方向的距离

        // 计算顺时针距离
        // 从出发站开始,按顺时针方向逐个累加距离,
        // 直到到达目的站。通过判断 i == n 确保索引在数组末尾时回到开头。
        int i = x;
        while (i != y) {
            clockwiseDistance += distances[i];
            i++;
            if (i == n) {
                i = 0; // 超出数组末尾,回到开头
            }
        }

        // 计算逆时针距离
        // 从目的站开始,按逆时针方向逐个累加距离,直到回到出发站。
        // 通过判断 i == -1 确保索引在数组开头时回到末尾。
        i = y;
        while (i != x) {
            i--;
            if (i == -1) {
                i = n - 1; // 超出数组开头,回到末尾
            }
            counterClockwiseDistance += distances[i];
        }

力扣解法 :更秒,直接 交换起始地和目的地的位置,再计算相关索引的距离值的和,再比较 

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        // 如果start 在 des后面,交换二者
        if (start > destination) {
            int temp = start;
            start = destination;
            destination = temp;
        }
    
        int sum1 = 0, sum2 = 0;
    
        // 遍历整个distance数组
        for (int i = 0; i < distance.length; i++) {
            // 计算从start到destination的总距离
            if (i >= start && i < destination) { //顺时针总距离
                sum1 += distance[i];
            } else { //i < start && i >= destination 逆时针总距离
                // 计算从destination到start的总距离
                sum2 += distance[i];
            }
        }
    
        // 返回从start到destination和从destination到start的距离中较小的值
        return Math.min(sum1, sum2);
    }
}

 第三题:小美的蛋糕切割

第四题:小美的字符串变换

解题思路

这个问题的需求其实是很明确的,根据题意我们需要做两件事

  • 找到所有可以摆列的方式,需要满足x*y=n,假设其中x为小的,那么可以枚举1到k(k*k=n,不需要枚举到n),找到所有的枚举方式
  • 每一个具体的枚举,通过DFS或者BFS的方式,找到其中的联通块数量。具体实现上标记每个位置是否访问,然后从一个方块如果未访问,那么联通块+1然后向四周搜索拓展、标记。
 解法一:DFS
import java.util.*;

public class Main {
    // 方法用于计算最小权值,输入为整数n和字符串s
    public static int minWeight(int n, String s) {
        int minW = Integer.MAX_VALUE; // 初始化最小权值为最大整数值
        
        // 遍历所有可能的矩阵大小,找到所有满足x*y=n的x和y
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                int x = i;
                int y = n / i;
                
                // 构建矩阵 (情况1: x为行数,y为列数)
                char[][] matrix = new char[x][y];
                for (int j = 0; j < x; j++) {
                    for (int k = 0; k < y; k++) {
                        matrix[j][k] = s.charAt(j * y + k); // 将字符串s的字符填入矩阵
                    }
                }
                
                // 计算矩阵的权值并更新最小权值
                minW = Math.min(minW, countConnected(matrix));
                
                // 情况2: 交换x和y的位置
                x = n / i;
                y = i;
                
                // 构建矩阵
                matrix = new char[x][y];
                for (int j = 0; j < x; j++) {
                    for (int k = 0; k < y; k++) {
                        matrix[j][k] = s.charAt(j * y + k); // 将字符串s的字符填入矩阵
                    }
                }
                
                // 计算矩阵的权值并更新最小权值
                minW = Math.min(minW, countConnected(matrix));
            }
        }
        return minW; // 返回最小权值
    }

    // 计算矩阵的连通块数量
    public static int countConnected(char[][] matrix) {
        int count = 0; // 初始化连通块计数器
        boolean[][] visited = new boolean[matrix.length][matrix[0].length]; // 记录访问状态的数组
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向的移动向量

        // 遍历矩阵的每个元素
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // 如果该位置未被访问
                if (!visited[i][j]) {
                    count++; // 连通块计数加一
                    dfs(matrix, visited, directions, i, j); // 执行深度优先搜索
                }
            }
        }
        return count; // 返回连通块的数量
    }

    // 深度优先搜索连通块
    public static void dfs(char[][] matrix, boolean[][] visited, int[][] directions, int x, int y) {
        visited[x][y] = true; // 标记为已访问,避免重复计算
        // 遍历四个方向
        for (int[] direction : directions) {
            int nx = x + direction[0];
            int ny = y + direction[1];
            // 如果新位置在矩阵范围内且未被访问且与当前字符相同,则递归调用DFS
            if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && !visited[nx][ny] && matrix[nx][ny] == matrix[x][y]) {
                dfs(matrix, visited, directions, nx, ny);
            }
        }
    }

    // 主方法
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象以读取输入
        int n = scanner.nextInt(); // 读取整数n
        scanner.nextLine(); // 读取换行符
        String s = scanner.nextLine(); // 读取字符串s
        System.out.println(minWeight(n, s)); // 调用minWeight方法并输出结果
    }
}

第五题:小美的树上染色

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/705999.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

搭建一个好玩的 RSS 订阅网站记录

全文相关链接 Github仓库创建链接Railway官网Supabase官网f-droid上的co.appreactor.news应用下载链接Railway账户使用量估算链接 全文相关代码 原文地址: https://blog.taoshuge.eu.org/p/270/ Dockerfile FROM docker.io/miniflux/miniflux:2.1.3环境变量 DATABASE_URL…

UniApp或微信小程序中scroll-view组件使用show-scrollbar在真机Android或IOS中隐藏不了滚动条的解决办法

show-scrollbar 属性 不论是使用 变量 还是直接使用 布尔值或者直接使用 css 都是在 ios、Android 上是都没有效果。。 真机中还是出现滚动条 解决办法 添加下面CSS ::-webkit-scrollbar {display: none;width: 0 !important;height: 0 !important;-webkit-appearance: no…

Charles代理https接口到本地

一、操作手册 1、安装工具 1.1、安装代理软件Charles 软件下载地址&#xff1a;Download a Free Trial of Charles • Charles Web Debugging Proxy 1.2、安装https代理插件&#xff1a;&#xff08;有问题自行百度解决&#xff09; 2、配置策略 以下以https接口为例&…

mysql索引B+树可视化演示地址

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

RISE - Ultimate Project Manager CRM 3.6.1 中文版安装指南

RISE 是一个多用途项目管理系统&#xff0c;有助于任何类型的企业管理他们的工作。它可以节省您管理客户、项目、销售和团队成员的日常时间。可提高客户满意度和工作绩效。 安装系统 登录宝塔&#xff0c;添加站点 输入域名和数据库信息&#xff0c;PHP版本至少是8.1 添加完成…

下载kibana-7.10.2教程

1、官网下载地址&#xff1a; Download Kibana Free | Get Started Now | Elastic 2、进入 Kibana下载界面&#xff0c;点击 View past releases 查看过去的版本 3、选择版本 Elasticsearch 7.10.2&#xff0c;点击 Download 4、点击 LINUX 64-BIT&#xff0c;进行下载 5、下…

docker-compose Install it-tools

IT-Tools前言 IT-Tools是一款开源的个人工具箱,专为IT从业人员打造,支持Docker私有化部署,包含众多实用的IT工具。其功能丰富多样,涵盖二维码生成、数据格式转换、MAC地址生成等,可满足用户多样化的需求。 前提要求 安装 docker docker-compose 参考创建一键部署it-tool…

码农学点儿经济学-博傻理论

博傻理论 一位石油大佬去天堂开会&#xff0c;他兴冲冲地跑进会议室&#xff0c;却发现座无虚席&#xff0c;早已经没了他的座位。于是他灵机一动&#xff0c;大喊一声&#xff1a;大家注意啦&#xff01;听说&#xff0c;有人在地狱发现了石油&#xff01;此言一出&#xff0c…

电脑桌面上用来记事的便签软件

便签软件已成为我们日常生活中不可或缺的记录工具。想象一下&#xff0c;在繁忙的工作中&#xff0c;你突然需要记下一个重要事项或临时想法&#xff0c;这时&#xff0c;一个便捷、高效的便签软件就显得尤为重要。它能帮助我们迅速捕捉信息&#xff0c;轻松管理琐碎事务&#…

22 CRT工具安装流程

22 CRT工具安装流程 SecureCRT 9.5 说明书 SecureCRT 9.5是一款由VanDyke Software开发的终端仿真程序。它为Windows、Mac和Linux操作系统提供了强大的SSH&#xff08;Secure Shell&#xff09;客户端功能。SecureCRT 9.5提供了对Telnet、RLogin、Serial和X.509等协议的支持&…

C# WPF 读写CAN数据

C# WPF 读写CAN数据 CAN 分析仪 分析仪资料下载 官方地址&#xff1a;https://www.zhcxgd.com/1.html CSDN&#xff1a; 项目配置 复制Dll库文件 文件在上面的资料里面 设置不安全代码 CAN C#工具类 CAN_Tool.cs using Microsoft.VisualBasic; using System; using Sys…

el-select filterable模糊搜索在iOS手机上无法弹出软键盘,解决方案

前提&#xff1a; el-select filterable模糊搜索在iOS手机上无法弹出软键盘&#xff0c;在手机上使用时&#xff0c;iOS手机&#xff0c;该组件无法唤起软键盘&#xff0c;导致没法进行模糊搜素。 于是。开始去找原因&#xff0c;发现主要是因为 组件中&#xff0c;input上有一…

Day 21:2807. 在链表中插入最大公约数

Leetcode 2807. 在链表中插入最大公约数 给你一个链表的头 head &#xff0c;每个结点包含一个整数值。 在相邻结点之间&#xff0c;请你插入一个新的结点&#xff0c;结点值为这两个相邻结点值的 最大公约数 。 请你返回插入之后的链表。 两个数的 最大公约数 是可以被两个数字…

【MySQL】(基础篇十) —— 汇总数据(聚集函数)

汇总数据 本文介绍什么是SQL的聚集函数以及如何利用它们汇总表的数据。 聚集函数 我们经常需要汇总数据而不用把它们实际检索出来&#xff0c;为此MySQL提供了专门的函数。使用这些函数&#xff0c;MySQL查询可用于检索数据&#xff0c;以便分析和报表生成。这种类型的检索例…

css设置滚动条样式;滚动条设置透明

滚动条透明代码 .resizable-div {resize: both;/* 允许水平和垂直调整大小 */overflow: auto;/* 确保内容超出边界时出现滚动条 */ } /* 滚动条整体样式 */ .resizable-div::-webkit-scrollbar {width: 4px; /* 竖直滚动条宽度 */height: 4px; /* 水平滚动条高度 */ }/* 滚动条…

CCF 矩阵重塑

第一题&#xff1a;矩阵重塑&#xff08;一&#xff09; 本题有两种思路 第一种 &#xff08;不确定是否正确 但是100分&#xff09; #include<iostream> using namespace std; int main(){int n,m,p,q,i,j;cin>>n>>m>>p>>q;int a[n][m];for(i…

共模信号与差模信号

差模信号又称串模信号&#xff0c;指的是两根线之间的信号差值&#xff1b;而共模信号又称对地信号&#xff0c;指的是两根线分别对地的信号。 差模信号&#xff1a;大小相等&#xff0c;方向相反的信号。共模信号&#xff1a;大小相等&#xff0c;方向相同的信号。 对于两输…

【机器学习】QLoRA:基于PEFT亲手微调你的第一个AI大模型

目录 一、引言 二、量化与微调—原理剖析 2.1 为什么要量化微调? 2.2 量化&#xff08;Quantization&#xff09; 2.2.1 量化原理 2.2.2 量化代码 2.3 微调&#xff08;Fine-Tuning&#xff09; 2.3.1 LoRA 2.3.2 QLoRA 三、量化与微调—实战演练&#xff1a;以Qwen…

springboot集成swagger、knife4j

1. 集成swagger2 1.1 引入依赖 <!-- https://mvnrepository.com/artifact/io.springfox/springfox-swagger2 --><dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.9.2</vers…

jadx+android studio+雷电模拟器 动态调试apk

# 环境准备 1.雷电模拟器&#xff0c;开启root 2.jadx&#xff1a; https://sourceforge.net/projects/jadx.mirror/files/v1.5.0/jadx-gui-1.5.0-with-jre-win.zip/download 3.java jdk 11 https://www.oracle.com/cn/java/technologies/javase/jdk11-archive-downloads.…