【Java版oj】day08两种排序方法、最小公倍数

ゝ一纸荒年。 2024-03-25 12:09 69阅读 0赞

**目录**

一、两种排序方法

（1）原题再现

（2）问题分析

（3）完整代码

二、最小公倍数

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、两种排序方法 ##
> 
> ### （1）原题再现 ###
> 
> [两种排序方法\_\_牛客网][Link 1]
> 
> 考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法：
> 
> 1.根据字符串的字典序排序。例如：  
> "car" < "carriage" < "cats" < "doggies < "koala"  
> 2.根据字符串的长度排序。例如：  
> "car" < "cats" < "koala" < "doggies" < "carriage"  
> 考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。
> 
> **输入描述:**
> 
> 输入第一行为字符串个数n(n ≤ 100) 接下来的n行,每行一个字符串,字符串长度均小于100，均由小写字母组成
> 
> **输出描述:**
> 
> 如果这些字符串是根据字典序排列而不是根据长度排列输出"lexicographically", 如果根据长度排列而不是字典序排列输出"lengths", 如果两种方式都符合输出"both"，否则输出"none"
> 
> ### （2）问题分析 ###
> 
> 本题在我看来是对字符串String类型的考察，直接使用String的相关方法做是最简单的，当中需要注意的是在String类中有一个**compareTo**方法，内部设置直接就是按照字典序设定的。strA.compareTo(strB)；返回得到一个int类型。如果**字符串strA按照字典序排在字符串strB的前面**，就会得到一个**小于0的数**；反之，如果**字符串strA按照字典序排在字符串strB的后面**，就会得到一个**大于0的数**；**两个字符串相等，就会得到0**。如果知道这个方法，题目就会很好做，不然就得对字符串里的每一个字符逐一比较，很有可能会遗漏一些情况。
> 
> 关于String的更多相关知识指路：
> 
> [Java基础之神奇String类（一）\_小熊爱吃软糖吖的博客-CSDN博客][Java_String_-CSDN]
> 
> [Java基础之神奇String类（二）\_小熊爱吃软糖吖的博客-CSDN博客][Java_String_-CSDN 1]
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     public class Main{
>     
>     	public static void main(String[] args) {
>     		// TODO 自动生成的方法存根
>     		Scanner sc=new Scanner(System.in);
>     		int n=sc.nextInt();
>     		String [] str=new String[n];
>     		for(int i=0;i<n;i++) {
>     			String s=sc.next();
>     			str[i]=s;
>     		}
>     		if(len(str)&&!lex(str)) {
>     			System.out.println("lengths");
>     			
>     		}else if(lex(str)&&!len(str)) {
>     			
>     			System.out.println("lexicographically");
>     		}else if(lex(str)&&len(str)) {
>     			
>     			System.out.println("both");
>     		}else {
>     			
>     			System.out.println("none");
>     		}				
>     	}
>     		
>     	public static boolean len(String [] str) {
>     		for(int i=1;i<str.length;i++) {
>     			if(str[i-1].length()>=str[i].length()){
>     				return false;
>     			}
>     		}
>     		return true;
>     	}
>     	public static boolean lex(String [] str) {
>     		for(int i=1;i<str.length;i++) {
>     			if(str[i-1].compareTo(str[i])>0) {
>     				return false;
>     			}
>     		}
>     		return true;	
>     	}		
>     }
> 
> ![f3e2754b0e40478d89dcb95f69ed4c73.png][]

> ## 二、最小公倍数 ##
> 
> ### （1）原题再现 ###
> 
> [求最小公倍数\_\_牛客网][Link 2]
> 
> 正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。
> 
> ### （2）问题分析 ###
> 
> 这道题很常见，最容易想到的方式是暴力求解，利用一个for循环，从1一直到a\*b，直到找出最小的公倍数。在我看来，记住公式是最快捷的方法，**两个数的乘积=最大公约数\*最小公倍数**。**求解最大公约数**可以用**辗转相除法**：两数中较大的数（max）为除数，较小的数（min）为被除数，当max%min!=0时，将min赋值给max，max除以min的余数赋值给min,直至==0时，较小的数（min）就是最大公约数。得到最大公约数就可以很容易求解最小公倍数了。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     public class Main {
>     	public static void main(String[] args) {
>     		Scanner sc=new Scanner(System.in);
>     		int a=sc.nextInt();
>     		int b=sc.nextInt();
>     		int LCD=a*b/GCD(a,b);
>     		System.out.println(LCD);
>     		
>     	}
>     	public static int GCD(int a,int b) {//最大公约数
>     		int x=Math.min(a, b);
>     		int y=Math.max(a, b);
>     		while(y%x!=0) {
>     			int rel=y%x;
>     			y=x;
>     			x=rel;
>     		}
>     		return x;
>     	}
>     }
> 
> ![ab537d5f959f44a184783fc9631b798b.png][]

--------------------

![958ed217a7034e0f9f505475d5e5e6b0.png][]

[Link 1]: https://ac.nowcoder.com/questionTerminal/839f681bf36c486fbcc5fcb977ffe432?commentTags=Java
[Java_String_-CSDN]: https://blog.csdn.net/m0_63372226/article/details/127191621?spm=1001.2014.3001.5502
[Java_String_-CSDN 1]: https://blog.csdn.net/m0_63372226/article/details/127254884?spm=1001.2014.3001.5502
[f3e2754b0e40478d89dcb95f69ed4c73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1574a032b33e404daa88cca831bf7d9f.png
[Link 2]: https://ac.nowcoder.com/questionTerminal/22948c2cad484e0291350abad86136c3?answerType=1
[ab537d5f959f44a184783fc9631b798b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/eaf67abd812e45009cf80034ce6282f1.png
[958ed217a7034e0f9f505475d5e5e6b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d809e096210049419b43a6505c540e48.png