首页 > 试题广场 >

两种排序方法

[编程题]两种排序方法

热度指数：32999 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法： 1.根据字符串的字典序排序。例如：
"car" < "carriage" < "cats" < "doggies < "koala"
2.根据字符串的长度排序。例如：
"car" < "cats" < "koala" < "doggies" < "carriage"
考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。

输入描述:

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

输出描述:

如果这些字符串是根据字典序排列而不是根据长度排列输出"lexicographically",

如果根据长度排列而不是字典序排列输出"lengths",

如果两种方式都符合输出"both"，否则输出"none"

示例1

输入

3
a
aa
bbb

输出

both

算法知识视频讲解

Java

来学习的小张

import java.util.*;
public class Main{
   
 public static boolean iszd(String[] str){
        for(int i= 0; i<str.length-1; i++){
            if(str[i].compareTo(str[i+1]) > 0){
                return false;
            }
        }
        return true;
    }
     
    //字符串长度判断
    public static boolean iscd(String[] str){
         
        for(int i= 0; i<str.length-1; i++){
            if(str[i].length() >  str[i+1].length()){
                 return false;
            }
        }
        return true;
    }
        
public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        String[] str = new String[n];
        for(int i = 0;i < n;i++){
            str[i] = sc.nextLine();
        }
      
          //  boolean zd = iszd(arr);
           // boolean cd = iscd(arr);
            if(iszd(str) && iscd(str)){
                System.out.println("both");
            }else if(iszd(str)){
                System.out.println("lexicographically");
            }else if(iscd(str)){
                System.out.println("lengths");
            }else{
                System.out.println("none");
            }
    }
}

发表于 2022-03-30 17:53:17 回复(0)

Java

我叫马牛逼

public class Main{
public static boolean isLengths(String[] str){//判断是不是按长度排列
        for(int i=0;i< str.length-1;i++){
            if(str[i].length()>str[i+1].length()){
                return false;
            }
        }
        return true;
    }

    //判断两个字符串是不是字典序排列——str1是不是在字典中是在str2前面
    public static boolean isLex(String str1,String str2){
        //字典序的话字母相同也是要分长度的：比如car<carriage
        int l=min(str1.length(),str2.length());//找出str1和str2中较小长度（不能找较大长度，否则小的那个会越界）
        for(int i=0;i<l;i++){
            if(str1.charAt(i)<str2.charAt(i)){
                return true;
            }
            if(str1.charAt(i)>str2.charAt(i)){
                return false;
            }
        }
        //走到这里没有return 说明前面一部分字母都是相同的
        //但是car在字典中不能排在carriage后——也就是str1=="carriage",str2=="car"不能直接返回true
        if(str1.charAt(l-1)==str2.charAt(l-1)){
            //不能直接if(str1.length()>str2.length())
            //有可能出现carriage 和 cats这种情况，本来是字典序没问题，
            // 但是前者长度大于后者会进入里面的if，你直接return false就错了，所以外层套一个if，判断末尾结束字符是否一样
            if(str1.length()>str2.length()){
                return false;
            }
        }
        return true;
    }

    public static boolean isLexicographically(String[] str){//判断是不是字典序排列
        int k=0;//标记对比次数，如果要return true,需要全部对比完
        // 比如字符串组str中有3个，你要对比1和2,2和3，共对比2次。如果str中有n个，要对比n-1次
        for(int i=0;i<str.length-1;i++){
            if(isLex(str[i],str[i+1])){
                k++;
                if(k==str.length-1){
                    return true;
                }
            }else{
                break;//进入else说明上面isLex返回的是false，也就是：不是字典排序
            }
        }
        return false;
    }

    public static void main(String[]args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        scanner.nextLine();//把n产生的回车回收一下

        String[] arr=new String[n];
        int x=0;//标记是不是按长度排列，不是——x=0，是——x=1
        int y=0;//标记是不是按字典序排列，不是——y=0，是——y=1

        for(int i=0;i<n;i++){
            arr[i]=scanner.nextLine();
        }

        if(isLengths(arr)){
            x=1;
        }
        if(isLexicographically(arr)){
            y=1;
        }

        if(y==1&&x==0){//根据字典序排列,但不是根据长度排列
            System.out.println("lexicographically");
        }
        if(y==0&&x==1){//根据长度排列,但不是根据字典序排列
            System.out.println("lengths");
        }if(y==1&&x==1){//都是
            System.out.println("both");
        }if(y==0&&x==0){//都不是
            System.out.println("none");
        }
    }
    
}

写了一个多小时终于全部通过了

发表于 2022-03-28 21:35:29 回复(1)

Java

一笑而过19

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            String[] original = new String[n];
            PriorityQueue<String> strQ = new PriorityQueue<>(new Comparator<String>(){
                public int compare(String s1, String s2){
                    return s1.compareTo(s2);
                }
            });
            PriorityQueue<String> lenQ = new PriorityQueue<>(new Comparator<String>(){
                public int compare(String s1, String s2){
                    return s1.length() - s2.length();
                }
            });
            for(int i = 0; i < n; i++){
                String cur = sc.next();
                original[i] = cur;
                strQ.add(cur);
                lenQ.add(cur);
            }
            boolean strFlag = true;
            boolean lenFlag = true;
            int index = 0;
            while(!strQ.isEmpty()){
                if(original[index] != strQ.poll()){
                    strFlag = false;
                }
                if(original[index] != lenQ.poll()){
                    lenFlag = false;
                }
                index++;
            }
            if(strFlag && lenFlag){
                System.out.println("both");
            }else if(strFlag){
                System.out.println("lexicographically");
            }else if(lenFlag){
                System.out.println("lengths");
            }else{
                System.out.println("none");
            }
        }
        sc.close();
    }
}

发表于 2020-08-17 15:11:24 回复(0)

Java

黄色以上

import java.util.Scanner;
public class Main {
   static boolean ifZidian = true;
   static boolean ifLength = true;
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = Integer.valueOf(sc.nextLine());
       String[] s = new String[n];
       for(int i=0;i<n;i++) {
           s[i] = sc.nextLine();
       }
       for(int i=0;i<n-1;i++) {
           if(ifZidian==false && ifLength==false) break;
           if(s[i].compareTo(s[i+1])>0) ifZidian=false;
           if(s[i].length()-s[i+1].length()>0) ifLength = false;
       }
       if(ifZidian==true && ifLength==false) System.out.println("lexicographically");
       else if(ifZidian==false && ifLength==true) System.out.println("lengths");
       else if(ifZidian==true && ifLength==true) System.out.println("both");
       else System.out.println("none");
   }
}

发表于 2018-07-21 17:13:06 回复(0)

Java

Murphy16

import java.util.Scanner;

public class SortString {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int length=sc.nextInt();
        String [] str=new String[length];
        for(int i=0;i<length;i++){

            str[i]=sc.next();
        }
        sortString(str,length);
    }
    private static void sortString(String[] str, int length) {
        boolean a=true;
        int len[] =new int[length];
        for(int i=0;i<length;i++){
            len[i]=str[i].length();
        }
        //确定是否为长度递增
        for(int i=0;i<length-1;i++){
            if(len[i+1]-len[i]<0){
                a=false;
            }
        }
        //去顶是否为字典增
        boolean b=true;
        for(int i=0;i<length-1;i++){
            //String 方法 compareTo 得int型变量大于0 书名是字典序增的
            int temp=str[i].compareTo(str[i+1]);
            if(temp>0){b=false;}
        }

        if(a&&b){
            System.out.println("both");
        }
        if(a&&(!b)){
            System.out.println("lengths");
        }
        if((!a)&&b){
            System.out.println("lexicographically");
        }
        if((!a)&&(!b)){
            System.out.println("none");
        }
    }
}

发表于 2018-07-09 11:04:45 回复(0)

Java

黄小斜

Java中的String默认按照字典序进行排序，字典序相同再按长度排序。
要按长度排序直接实现一个比较器即可，这里直接用lambda表达式
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        int n = Integer.parseInt(line);
        String []s = new String[n];
        for(int i = 0; i < n;i ++) {
            line = scanner.nextLine();
            s[i]  = line;
        }
        if (lexicographically(s) && lengths(s)) {
            System.out.println("both");
        }
        else if (lexicographically(s)) {
            System.out.println("lexicographically");
        }
        else if (lengths(s)) {
            System.out.println("lengths");
        }
        else {
            System.out.println("none");
        }
    }
    public static boolean lexicographically(String []s) {
        String[] sort = Arrays.copyOf(s, s.length);
        Arrays.sort(sort);
        for (int i = 0;i < s.length;i ++) {
            if (!s[i].equals(sort[i])) {
                return false;
            }
        }
        return true;
    }
    public static boolean lengths(String []s) {
        String[] sort = Arrays.copyOf(s, s.length);
        Arrays.sort(sort, (a,b) -> a.length() - b.length());
        for (int i = 0;i < s.length;i ++) {
            if (!s[i].equals(sort[i])) {
                return false;
            }
        }
        return true;
    }
}

发表于 2018-05-21 15:54:22 回复(0)

Java

l_yabo

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            boolean[] flags = {true, true}; // {lexicographically, lengths}
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) arr[i] = sc.next();
            for (int i = 0, j = 1; i < n - 1 && j < n; i++, j++) {
                String s1 = arr[i];
                String s2 = arr[j];
                if (s1.compareTo(s2) > 0) flags[0] = false;
                if (s1.length() > s2.length()) flags[1] = false;
                if (!flags[0] && !flags[1]) break;
            }
            
            if (flags[0] && flags[1]) System.out.println("both");
            else if (flags[0] && !flags[1]) System.out.println("lexicographically");
            else if (!flags[0] && flags[1]) System.out.println("lengths");
            else System.out.println("none");
        }
    }
}

发表于 2018-04-10 03:39:06 回复(0)

Java

咖啡新东方

public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String str[] = new String[n];
        boolean lexicographically = true;
        boolean lengths = true;
        for (int i = 0; i < n; i++) {
            str[i] = scanner.nextLine();
            if (i != 0) {
                lexicographically = lexicographically && isGreater(str[i - 1], str[i]);
                lengths = lengths && (str[i].length() > str[i - 1].length());
            }
        }
        if (lexicographically && lengths)
            System.out.println("both");
        else if (lexicographically)
            System.out.println("lexicographically");
        else if (lengths)
            System.out.println("lengths");
        else
            System.out.println("none");
    }

    public static boolean isGreater(String a, String b) {
        int len = Math.min(a.length(), b.length());
        boolean flag = true;
        for (int i = 0; i < len; i++) {
            if (a.charAt(i) > b.charAt(i))
                return false;
            if (a.charAt(i) < b.charAt(i))
                return true;
        }
        if (a.length() > b.length())
            return false;
        return true;
    }

发表于 2018-03-07 15:04:06 回复(0)

Java

傻傻傻傻

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt(); in.nextLine();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < count; i++)
            list.add(in.nextLine());
        List<String> listCopy = new ArrayList<>(list);
        Collections.sort(listCopy);
        boolean isSorted1 = false, isSorted2 = true;

        if (listCopy.equals(list)) isSorted1 = true;
        for (int i = 0; i < count - 1; i++) {
            if (list.get(i).length() > list.get(i+1).length())
                isSorted2 = false;
        }
        if (isSorted1 && isSorted2) System.out.println("both");
        else if (isSorted1 && !isSorted2) System.out.println("lexicographically");
        else if (!isSorted1 && isSorted2) System.out.println("lengths");
        else System.out.println("none");
    }
}
---------------------------------------------------------------------------
//参考高票答案
import java.util.*;
import static java.lang.System.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        String[] strings = new String[count];
        for (int i = 0; i < count; i++)
            strings[i] = in.next();

        boolean isLexicographical = isLexicographical(strings);
        boolean isSortedByLen = isSortByLen(strings);

        if (isLexicographical && isSortedByLen) out.println("both");
        else if (isLexicographical) out.println("lexicographically");
        else if (isSortedByLen) out.println("lengths");
        else out.println("none");
    }
    private static boolean isSortByLen(String[] strings) {
        boolean res = true;
        for (int i = 0; i < strings.length - 1; i++)
            if (strings[i].length() > strings[i + 1].length())
                res = false;
        return res;
    }
    private static boolean isLexicographical(String[] strings) {
        boolean res = true;
        for (int i = 0; i < strings.length - 1; i++)
            if (strings[i].compareTo(strings[i + 1]) > 0)
                res = false;
        return res;
    }
}

编辑于 2017-12-18 19:57:36 回复(0)

Java

初生小牛不怕虎

import java.util.LinkedList; import java.util.Scanner;  public class Main
{  public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);  LinkedList<String> strings = new LinkedList<>();  while (scanner.hasNext()) {  int n = Integer.parseInt(scanner.nextLine());  for (int i = 0; i < n; i++) {
                strings.add(i, scanner.nextLine());  }  boolean A = ifLengths(strings);  boolean B = ifLexicographically(strings);  if (A && B) {
                System.out.println("both");  }  else if (A) {
                System.out.println("lengths");  }  else if (B) {
                System.out.println("lexicographically");  }  else {
                System.out.println("none");  }
        }
    }  private static boolean ifLexicographically (LinkedList<String> strings) {  int length = strings.size();  int i;  for (i = 0; i < length - 1; i++) {  if (strings.get(i + 1).compareTo(strings.get(i)) < 0) {  break;  }
        }  return (i == length - 1);   }  private static boolean ifLengths (LinkedList<String> strings) {  int length = strings.size();  int i;  for (i = 0; i < length - 1; i++) {  if (strings.get(i + 1).length() < strings.get(i).length()) {  break;  }
        }  return (i == length - 1);   }
}

这个题其实蛮简单的，因为字符串的compare（）函数直接就可以解决两个字符串按字典序的先后顺序，然后length（）又可以直接确定按照长度的先后顺序，所以这道题是蛮简单的

发表于 2017-11-23 19:42:20 回复(0)

Java

指offer的剑在哪？

两个字符串使用字典排序进行判断使用：compareTo()；

import java.util.Scanner;
public class StringUtil{
		
	//两种排序方法
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = Integer.valueOf(in.nextLine());
			String str[] = new String[n+1];
			for(int i=1; i<=n; i++){
				str[i] = in.nextLine();
			}
			boolean zd = iszd(str);
			boolean cd = iscd(str);
			if(zd && cd)
				System.out.println("both");
			else if(zd)
				System.out.println("lexicographically");
			else if(cd)
				System.out.println("lengths");
			else
				System.out.println("none");
		}	
	}
	
	//字典判断
	public static boolean iszd(String[] str){
		for(int i=1; i<str.length-1; i++){
			if(str[i].compareTo(str[i+1]) >= 0)
				return false;
		}
		return true;
	}
	
	//字符串长度判断
	public static boolean iscd(String[] str){
		
		for(int i=1; i<str.length-1; i++){
			if(str[i].length() >= str[i+1].length())
				return false;
		}
		return true;
	}
}

发表于 2017-09-07 01:25:33 回复(0)

Java

Jungggle

import java.util.Scanner;

public class Main {

public static int compare(char[] c1, char[] c2) {

int i = 0;

for (i = 0; i < c1.length && i < c2.length; i++) {

if (c1[i] != c2[i])

break;

}

if (i < c1.length && i < c2.length) {

return c2[i] - c1[i];

}

return c2.length - c1.length;

}

public static void main(String[] args) {

try (Scanner scanner = new Scanner(System.in)) {

A: while (scanner.hasNext()) {

int n = scanner.nextInt();

if (n <= 1)

System.out.println("both");

char[] c1 = scanner.nextLine().toCharArray();

boolean isLenSort = true, isDirSort = true;

char[] last = c1;

for (int i = 1; i <= n; i++) {

char[] c = scanner.nextLine().toCharArray();

if (isLenSort && (c.length < last.length))

isLenSort = false;

if (isDirSort && compare(c, last) > 0)

isDirSort = false;

// if(!isLenSort&&!isDirSort)

// continue A;

last = c;

}

if (isLenSort && isDirSort)

System.out.println("both");

else if (isLenSort)

System.out.println("lengths");

else if (isDirSort)

System.out.println("lexicographically");

else

System.out.println("none");

}

k eng 坑->只能由小到大

发表于 2017-08-16 15:33:18 回复(0)

Java

萨仁朝格图（大家去脉脉沟通）

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        ArrayList<String> s = new ArrayList<String>();
        for(int i = 0; i < n; i++)
            s.add(sc.nextLine());
        if(isDicSort(s) && (!isLagIng(s)))
            System.out.print("lexicographically");
        else if((!isDicSort(s)) && isLagIng(s))
            System.out.print("lengths");
        else if(isDicSort(s) && isLagIng(s))
            System.out.print("both");
        else if(!isDicSort(s) && !isLagIng(s))
            System.out.print("none");
    }
    public static boolean isDicSort(ArrayList<String> s){
        ArrayList<String> s1 = (ArrayList<String>)s.clone();
        Collections.sort(s1);
        for(int i = 0; i < s.size(); i++){
            if(!s.get(i).equals(s1.get(i)))
                return false;
        }
        return true;
    }
    public static boolean isLagIng(ArrayList<String> s){
        for(int i = 1; i < s.size(); i++){
            if(s.get(i).length() <= s.get(i-1).length())
                return false;
        }
        return true;
    }
}

发表于 2017-08-11 19:34:50 回复(0)

Java

ONE＆ONLY

import java.util.*;

public class Main

{

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);

int n=0;

ArrayList<String> list = null;

if(sc.hasNext())

{

n = sc.nextInt();

sc.nextLine();//行末多个换行。需要跳到第二行

list = new ArrayList<>(n);

for(int i =0;i<n;i++)

{

list.add(sc.nextLine().trim());

}

boolean isLex = true;

boolean isLen = true;

int len = list.get(0).length();

for(int i = 0;i<list.size()-1;i++)

{

if(list.get(i).compareTo(list.get(i+1))>0)

isLex =false;

if(list.get(i).length()>list.get(i+1).length())

isLen=false;

}

if(isLex)

{

if(isLen)

System.out.println("both");

else

System.out.println("lexicographically");

}

else

{

if(isLen)

System.out.println("lengths");

else

System.out.println("none");

}

sc.close();

}

发表于 2017-08-10 15:35:03 回复(0)

提交观点

问题信息

字符串排序

来自：网易2017内推笔试编...

难度：

14条回答 133收藏 24149浏览

通过挑战的用户

查看代码

小熊爱找工作吖

2023-03-14 02:46:18
木木是木木

2023-03-13 23:43:08
36度的手指编程

2023-02-18 11:09:54
沙天琦

2023-02-08 17:07:50
王安迅

2023-01-15 02:53:06

两种排序方法

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题