Java题目训练——两种排序方法和最小公倍数

绝地灬酷狼 2023-09-30 20:38 18阅读 0赞

### 一、两种排序方法 ###

1.  题目描述：

考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法：

1.根据字符串的字典序排序。例如：

"car" < "carriage" < "cats" < "doggies < "koala"

2. 根据字符串的长度排序。例如：

"car" < "cats" < "koala" < "doggies" < "carriage"

考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。

1.  输入描述：输入第一行为字符串个数n(n ≤ 100) 接下来的n行,每行一个字符串,字符串长度均小于100，均由小写字母组成

1.  输出描述：如果这些字符串是根据字典序排列而不是根据长度排列输出"lexicographically",如果根据长度排列而不是字典序排列输出"lengths",如果两种方式都符合输出"both"，否则输出"none"

1.  补充说明：

> 示例1  
> 输入：  
> 3  
> a  
> aa  
> bbb  
> 输出：  
> both

**解题思路：**

分别写两个方法测试长度和按字典排序是否符合要求，其中长度需要遍历序列，如果出现后面的字符串比前面的字符串长，则不符合；按字典顺序思路相同，也是通过遍历，借助compareTo方法进行检测，需要注意的是，按字典顺序不能只比较每个字符串首字母的顺序，如果首字母顺序相同，应当继续比较第二个字母的顺序，依次这样。

import java.util.Scanner;
     
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            String x = "";
            String[] ans = new String[n];
            for(int i = 0; i < n; i++){
                x = sc.next();
                ans[i] = x;
            }
             
            judge(ans);
        }
         
        public static boolean dict(String[] ans){
            for(int i = 0; i < ans.length - 1; i++){
                if(ans[i].compareTo(ans[i+1]) > 0){
                    return false;
                }
            }
            return true;
        }
         
        public static boolean len(String[] ans){
            for(int i = 0; i < ans.length - 1; i++){
                if(ans[i].length() > ans[i+1].length()){
                    return false;
                }
            }
            return true;
        }
         
        public static void judge(String[] ans){
            if(ans.length == 0){
                System.out.println("both");
            }else if(dict(ans)&&len(ans)){
                System.out.println("both");
            }else if(dict(ans)){
                System.out.println("lexicographically");
            }else if(len(ans)){
                System.out.println("lengths");
            }else{
                System.out.println("none");
            }
        }
    }

### 二、求最小公倍数 ###

1.  题目描述：

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

1.  数据范围：1<=a，b<=100000

1.  输入描述：输入两个正整数A和B。

1.  输出描述：输出A和B的最小公倍数。

补充说明：

> **示例1**  
> **输入：**  
> 5 7  
> **输出：**  
> 35

> **示例2**  
> **输入：**  
> 2 4  
> **输出：**  
> 4

**解题思路：**

我们较为擅长于求最大公约数，此处有一个结论：两个数的乘积 = 这两个数的 最大公约数 \* 最小公倍数。所以我们一般通过求出这两个数的最大公约数从而得到最小公倍数。

import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int a = in.nextInt();
            int b = in.nextInt();
             
            int max = max(a,b);
            int min = (a*b)/max;
            System.out.println(min);
             
        }
         
        public static int max(int a,int b){ // 求最大公约数
            int temp = 0;
            if(a < b){
                temp = a;
                a = b;
                b = temp;     
            }
             
            int min = 0;
            while(b != 0){//辗转相除法
                min = a % b;
                a = b;
                b = min;
            }
            return a;
        }
    }

如有建议或想法，欢迎一起讨论学习~