首页 > 试题广场 >

两种排序方法

[编程题]两种排序方法

热度指数：33006 时间限制：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

算法知识视频讲解

想奔跑的蜗牛

/*
字典序排序，字符串大小排序
*/

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string>vec;

 //按照字典序排序
bool  lexicographically(){

    int i=0;
    string s;

    while((i+1) < vec.size()){
        if(vec[i].compare(vec[i+1]) >0)
            return 0;
        i++;
    }
    return 1;
}

//按照字符串大小排序
bool Lenths(){

    int i=0;
    while((i+1) <vec.size() ){
        if(vec[i+1].size() < vec[i].size() )
            return 0;
        i++;
    }
    return 1;
}

int main(){

    string s;
    int n,i=0;
    bool b1,b2;

    cin>>n;
    while(i < n){
        cin>>s;
        vec.push_back(s);
        i++;
    }

    b1=lexicographically();
    b2=Lenths();

    if(b1 && b2)
        cout<<"both";
    else if(b1 && !b2)
        cout<<"lexicographically";
    else if(!b1 && b2)
        cout<<"lengths";
    else
        cout<<"none";


    return 0;
}

发表于 2016-08-11 10:43:09 回复(6)

月佩弦

import java.util.Scanner;

/**
 * Created by Genge on 2016-08-20.
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            String[] words = new String[n];
            for (int i = 0; i < n; i ++) {
                words[i] = scanner.next();
            }
            System.out.println(validate(words));
        }
        scanner.close();
    }

    private static String validate(String[] words) {
        boolean isABC = isAbc(words);
        boolean isLEN = isLen(words);
        if (isABC && isLEN) {
            return "both";
        }
        if (isABC) {
            return "lexicographically";
        }
        if (isLEN) {
            return "lengths";
        }
        return "none";
    }

    private static boolean isLen(String[] words) {
        boolean result = true;
        for (int i = 1; i < words.length; i++) {
            if (words[i].length() <= words[i - 1].length()) {
                result = false;
                break;
            }
        }
        return result;
    }

    private static boolean isAbc(String[] words) {
        boolean result = true;
        for (int i = 1; i < words.length; i++) {
            if (words[i].compareTo(words[i - 1]) <= 0) {
                result = false;
                break;
            }
        }
        return result;
    }
}

发表于 2016-08-20 11:54:59 回复(1)

元气の悟空

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(string a,string b){
    return a.length()<b.length();
}
bool equal(string a[],string b[],int N){
    for(int i=0;i<N;i++)
        if(a[i]!=b[i]) return false;
    return true;
}
string a[105],b[105],c[105];
int main(){
    int i,n;
    for(cin>>n,i=0;i<n;i++) cin>>a[i],b[i]=c[i]=a[i];
    sort(b,b+n),sort(c,c+n,cmp);
    if(equal(a,b,n)&&equal(a,c,n)) printf("both");
    if(equal(a,b,n)&&(!equal(a,c,n))) printf("lexicographically");
    if((!equal(a,b,n))&&equal(a,c,n)) printf("lengths");
    if((!equal(a,b,n))&&(!equal(a,c,n))) printf("none");
}

发表于 2017-09-22 15:03:54 回复(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)

牛客8912096号

#include<iostream>
#include<string.h>
using namespace std;

int main()
{
    int n,i,j;
    int x=0,y=0;
    char a[100][100];
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
     for(i=0;i<n-1;i++){
        if(strlen(a[i])>strlen(a[i+1])){
            x=1;
            break;
        }
            
    }
    for(i=0;i<n-1;i++){
        if(strcmp(a[i],a[i+1])>0){
            y=1;
            break;
        }
    }
    if(x==1 && y==0)
        cout<<"lexicographically"<<endl;
    else if(x==0 && y==1)
        cout<<"lengths"<<endl;
    else if(x==0 && y==0)
        cout<<"both"<<endl;
    else
        cout<<"none"<<endl;
    return 0;
}

发表于 2016-08-11 11:12:49 回复(2)

CrazyCodingGirl

简单粗暴的方法

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
        {
        bool flag1=0,flag2 = 0;
        vector<string>  str(n);
        for(auto &i:str)
            cin>>i;
        for(int i=1;i<str.size();i++)
            {
            if(flag1==0&&str[i-1]>str[i])
                flag1 =1;
            if(flag2==0&&str[i-1].size()>str[i].size())
                flag2 = 1;
            if(flag1&&flag2)
                break;
        }
        if(flag1==0&flag2==0)
            cout<<"both"<<endl;
        else if(flag1==0)
            cout<<"lexicographically"<<endl;
        else if(flag2==0)
            cout<<"lengths"<<endl;
        else
            cout<<"none"<<endl;
    }
	return 0;
}

发表于 2017-08-11 16:25:13 回复(2)

牛客677436号

import java.util.*;
public class Main{
    public static boolean isLen(String[] strings){
        int length=strings[0].length();
        for(int i=1;i<strings.length;i++){
            if(length<=strings[i].length()){
                length=strings[i].length();
            }
            else{
                return false;//不是根据长度排的
            }
        }
        return true;
    }
    public static boolean abc(String[] strings){
        ArrayList<String> list=new ArrayList<>();
		for (int i = 0; i < strings.length; i++) {
			list.add(strings[i]);
		}
		Collections.sort(list);
		String[] strings2=new String[strings.length];
		for (int i = 0; i < strings2.length; i++) {
			strings2[i]=list.get(i);
		}
		for (int i = 0; i < strings2.length; i++) {
			if (strings[i]!=strings2[i]) {
				return  false;//不是根据字母顺序
			}
		}
        return true;//根据字母顺序
    }
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
            int n=s.nextInt();
            String[] strings=new String[n];
            for(int i=0;i<n;i++){
                strings[i]=s.next();
            }
            if(isLen(strings)&abc(strings)){
                System.out.println("both");
            }
            else if(isLen(strings)==false&abc(strings)==true){
                System.out.println("lexicographically");
            }
            else if(isLen(strings)==true&abc(strings)==false){
                System.out.println("lengths");
            }
            else{
                System.out.println("none");
            }
        }
    }
}

发表于 2016-08-11 20:16:32 回复(1)

无忧♜

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            str[i] = in.next();
        }
        if (lexicographically(str)){
            if (lengths(str)){
                System.out.println("both");
            }else {
                System.out.println("lexicographically");
            }
        }else {
            if (lengths(str)){
                System.out.println("lengths");
            }else {
                System.out.println("none");
            }
        }
    }

    public static boolean lexicographically(String[] str){
        if (str.length <= 1){
            return true;
        }
        for (int i = 1; i < str.length; i++) {
            if (str[i-1].compareTo(str[i]) > 0){
                return false;
            }
        }
        return true;
    }

    public static boolean lengths(String[] str){
        if (str.length <= 1){
            return true;
        }
        for (int i = 1; i < str.length; i++) {
            if (str[i-1].length() > str[i].length()){
                return false;
            }
        }
        return true;
    }
}

发表于 2022-03-29 16:07:25 回复(0)

喝醉了Ta的梦,晚安

#include<iostream>
using namespace std;
#include<string>
#include<vector>

int main()
{
    vector<string> vs;
    string s;
    int n;cin>>n;
    vs.resize(n);
    for(auto& e:vs)
    {
        cin>>e;
    }
    bool lsort = true;
    bool dsort = true;
    for(int i=0;i<n-1;++i)
    {
        if(vs[i].length()>vs[i+1].length())
        {
            lsort = false;
            break;
        }
    }
    for(int i=0;i<n-1;++i)
    {
        if(vs[i]>vs[i+1])
        {
            dsort = false;
            break;
        }
    }
    if(lsort&&dsort)
        cout<<"both"<<endl;
    else if(lsort||dsort){
        if(lsort)
            cout<<"lengths"<<endl;
        if(dsort)
            cout<<"lexicographically"<<endl;
    }
    else 
        cout<<"none"<<endl;
    return 0;
}

发表于 2021-10-22 19:32:35 回复(0)

C/C++

hello古斯卡

#include<iostream>
#include<string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string str[n];
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
    }
    bool p1 = true;
    bool p2 = true;
    for (int j = 1; j < n; ++j) {
        if (str[j - 1] > str[j]) {
            p1 = false;
        }
        if (str[j - 1].size() > str[j].size()) {
            p2 = false;
        }
    }

    string res;
    if (p1 && p2) {
        res = "both";
    } else if (p1 && !p2) {
        res = "lexicographically";
    } else if (!p1 && p2) {
        res = "lengths";
    } else {
        res = "none";
    }
    cout << res << endl;
    return 0;
}

发表于 2019-10-20 19:45:36 回复(0)

C/C++

Debug丶

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    int nCount;
    while (cin >> nCount)
    {
        vector<string> vecInput;
        vecInput.resize(nCount);
        for (int i = 0; i < nCount; ++i)
            cin >> vecInput[i];
         
        bool isLex = true, isLength = true;
        for (int i = 1; i < nCount; ++i)
        {
            int nSize1 = vecInput[i - 1].size(), nSize2 = vecInput[i].size(), nIndex = 0;
            while (nIndex < nSize1 && nIndex < nSize2)
            {
                if (vecInput[i - 1][nIndex] > vecInput[i][nIndex])
                {
                    isLex = false;
                    break;
                }
                else if (vecInput[i - 1][nIndex] < vecInput[i][nIndex])
                    break;
                ++nIndex;
            }
            if (nIndex < nSize1 && nIndex == nSize2)
                isLex = false;
            if (isLex == false)
                break;
        }
        for (int i = 1; i < nCount; ++i)
        {
            if (vecInput[i].size() < vecInput[i - 1].size())
            {
                isLength = false;
                break;
            }
        }
        if (isLex && isLength)
            cout << "both" << endl;
        else if (isLex)
            cout << "lexicographically" << endl;
        else if (isLength)
            cout << "lengths" << endl;
        else
            cout << "none" << endl;
    }
}

编辑于 2019-08-15 13:17:40 回复(0)

WalkingCoder

//每次和前一个比就行了  不需要数组
public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        Integer n = Integer.parseInt(scanner.nextLine());
        boolean lexicographically = true;
        boolean lengths = true;
        String pre = "";
        for(int i=0;i<n;i++){
            String s = scanner.nextLine();
            lengths = lengths&&s.length()>=pre.length();
            lexicographically = lexicographically&&s.compareTo(pre)>=0;
            pre = s;
        }
        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");
    }

编辑于 2018-10-09 20:20:17 回复(1)

范尼斯特尔鲁一

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {     public static void main(String[] args) {         Scanner s=new Scanner(System.in);         List<String> l=new ArrayList<String>();
        int aa=s.nextInt();         while(s.hasNext())         {             String m=s.nextLine();             l.add(m);         }         if((isABC(l))&&(isLength(l)))         {             System.out.println("both");         }else if((isABC(l)==false)&&(isLength(l)==true))         {             System.out.println("lengths");         }         else if((isABC(l)==true)&&(isLength(l)==false))         {             System.out.println("lexicographically");         }         else if((isABC(l)==false)&&(isLength(l)==false))         {             System.out.println("none");         }              }     public static boolean isABC(List al)     {         boolean f=true;         for(int i=0;i<al.size();i++)         {             if(i+1<al.size())             {                 String s1=(String)al.get(i);                 String s2=(String)al.get(i+1);                 if(s1.compareTo(s2)<0)                 {                     continue;                 }                 else                 {                     f=false;                 }             }         }         return f;     }     public static boolean isLength(List al)     {         boolean f=true;         for(int i=0;i<al.size();i++)         {             if(i+1<al.size())             {                 String s1=(String)al.get(i);                 String s2=(String)al.get(i+1);                 if(s2.length()-s1.length()>0)                 {                     continue;                 }                 else                 {                     f=false;                 }             }         }         return f;     }
}

发表于 2018-09-06 10:50:17 回复(0)

DJy201807201027569

只考虑前字符串数组的前四项即可。即判断字符串个数n<=2;n=3;n>=4三种情况下最大的取前四个即可百分百通过本题不需要写循环

发表于 2018-08-23 06:12:53 回复(1)

Keven·

#include<stdio.h>
#include<string.h>
int main()
{
    int i,n,flag0=0,flag1=0;
    scanf("%d",&n);
    getchar();
    char a[n][100];
    memset(a,0,sizeof(a));
    for (i=0;i<n;i++)
    {
        gets(a[i]);
        if (i==0)
        continue;
        if (flag0==0&&(strcmp(a[i],a[i-1])<0))
        flag0=1;
        if (flag1==0&&strlen(a[i])<strlen(a[i-1]))
        flag1=1;
    }
    if (flag0==0&&flag1==0)
    printf("both");
    else if (flag0==0&&flag1==1)
    printf("lexicographically");
    else if (flag0==1&&flag1==0)
    printf("lengths");
    else
    printf("none");
}

发表于 2018-02-14 00:36:43 回复(0)

Jason_liu


	





	import java.util.Scanner; 



	





	public class TwoSort2 {



	    public static boolean bol = true; 



	    public static boolean abc = true; 



	





	    public static void main(String[] args) {



	        Scanner sc = new Scanner(System.in);



	        while (sc.hasNext()) {



	            int n = Integer.parseInt(sc.nextLine());



	            String[] str = new String[n];



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



	                str[i] = sc.nextLine();



	            }



	            getResult(str);



	            if (abc && bol) {



	                System.out.println("both");



	            } else if (abc && !bol) {



	                System.out.println("lexicographically");



	            } else if (!abc && bol) {



	                System.out.println("lengths");



	            } else 



	                System.out.println("none");



	        }



	    }



	





	    public static void getResult(String[] arr) {



	        int x = 0;



	        char a, b;



	        for (int i = 0; i < arr.length; i++) {



	            int y = 0;



	            boolean j = true; 



	            if (x < arr[i].length()) {



	                x = arr[i].length();



	            } else {



	                bol = false;



	            }



	            if (i < arr.length - 1) {



	                while (j) {



	                    if (y < arr[i].length() && y < arr[i + 1].length()) {



	                        a = arr[i].charAt(y);



	                        b = arr[i + 1].charAt(y);



	                        if (a == b) {



	                            j = true;



	                            y++;



	                        } else if (a > b) {



	                            abc = false;



	                            j = false;



	                        } else if (a < b) {



	                            j = false;



	                        }



	                    }



	                    else if(y >= arr[i].length() && y<arr[i+1].length()) {



	                        j=false;



	                    }



	                    else if(y <= arr[i].length() && y >= arr[i + 1].length()) {



	                        abc = false;



	                        j = false;



	                    }



	                }



	            }



	        }



	    }



	}

编辑于 2018-01-30 15:22:57 回复(0)

C/C++

nbgao

#include <iostream>

using namespace std;

string s[110];

int main()
{     int n;     cin>>n>>s[0];     string t = s[0];     int l = t.length();     bool flag1 = true, flag2 = true;     for(int i=1;i<n;i++)     {         cin>>s[i];         if(s[i] < t)             flag1 = false;         t = s[i];         if(s[i].length() < l)             flag2 = false;         l = t.length();     }     if(flag1 && flag2)         cout<<"both"<<endl;     else if(flag1 && !flag2)         cout<<"lexicographically"<<endl;     else if(!flag1 && flag2)         cout<<"lengths"<<endl;     else         cout<<"none"<<endl;     return 0;
}

发表于 2018-01-11 00:59:26 回复(0)

◉‿◉.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool mycompare(string str1,string str2)
{
int len1 = str1.size();
int len2 = str2.size();
int len = len1 > len2 ? len2 : len1;
for(int i = 0; i < len; )
{
if (str1[i] == str2[i])
i++;
else
return str1[i] < str2[i];
}
return len1 < len2;
}
bool islexicographically(vector<string>& strs)
{
int size = strs.size();
if (size <= 1) return true;
for (int i = 0; i < size-1; i++)
{
if (!mycompare(strs[i], strs[i+1]))
return false;
}
return true;
}

bool islengthly(vector<string>& strs)
{
int size = strs.size();
if (size <= 1) return true;
for (int i = 0; i < size-1; i++)
{
if (strs[i].size() > strs[i+1].size())
return false;
}
return true;
}

int main()
{
int n;
cin>>n;
n++;
string temp;
vector<string> strs;
while(n--)
{
getline(cin, temp);
strs.push_back(temp);
}
if (islengthly(strs) && islexicographically(strs))
cout<<"both";
else if (islengthly(strs))
cout<<"lengths";
else if (islexicographically(strs))
cout<<"lexicographically";
else
cout<<"none";
}

发表于 2017-12-19 11:13:56 回复(0)

小朋友吃饭了

#include <iostream>
#include <algorithm>
#include <cstring>
#include"stdlib.h"
using namespace std;

int main()
{
        int n;

cin>>n;
    char *p[10000];
    char *mm[10000];
    char *mm1[10000];
    int q[10000];
    int jiaohuan;
    char *com;
for(int i=0;i<n;i++)
{
     p[i]=new char[10000];
     mm[i]=new char[10000];
     cin>>p[i];
     mm[i]=p[i];mm1[i]=p[i];
}
for(int j=0;j<n;j++)
{

     q[j]=strlen(mm[j]);
}
for(int t=0;t<n;t++)
{
     for(int m=0;m<n-t-1;m++)
     {
     if(strcmp(p[m],p[m+1])>0)
     {
         com=p[m];
         p[m]=p[m+1];
         p[m+1]=com;


     }
     if(q[m]>q[m+1])
     {

         com=mm[m+1];
         mm[m+1]=mm[m];
         mm[m]=com;
jiaohuan=q[m+1];
q[m+1]=q[m];
q[m] =jiaohuan;

         }

     }
    /*     if(q[t]>q[t+1])
     {

         com=mm[t+1];
         mm[t+1]=mm[t];
         mm[t]=com;
         q[t]=strlen(mm[t]);
     }
    */
}
int count1=0;int count2=0;
for(int uu=0;uu<n;uu++){
if(strcmp(p[uu],mm1[uu])==0)
{
     count1++;
    // cout<<"both";
}
if(strcmp(mm[uu],mm1[uu])==0)
{
     count2++;
     //cout<<"lexicographically";
}
/* if(strcmp(p[uu],mm1[uu])!=0&&strcmp(mm[uu],mm1[uu])==0)
{
     cout<<"lengths";
}
if(strcmp(p[uu],mm1[uu])!=0&&strcmp(mm[uu],mm1[uu])!=0)
{
     cout<<"none";
}*/

}
if(count1==n&&count2==n)
{
cout<<"both";
}
if(count1==n&&count2!=n)
{
    cout<<"lexicographically";
}
if(count2==n&&count1!=n)
{
cout<<"lengths";
}
if(count2!=n&&count1!=n)
{
cout<<"none";
}
    system("pause");
    return 0;
}

发表于 2017-09-16 20:21:10 回复(0)

C/C++

卡玛酱

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
	int n,notLen=0,notLex=0;
	cin>>n;
	string s;
	vector<string> vs;
	for(int i=0;i<n;i++){
		cin>>s;
		vs.push_back(s);
	}
	for(int i=0;i<vs.size()-1;i++){
		if(vs[i].compare(vs[i+1])>0){
			notLex=1;
		}
		if(vs[i].size()>vs[i+1].size()){
			notLen=1;
		}
		if(notLen==1&&notLex==1) break;
	}
	if(notLex==1&&notLen==1){
		cout<<"none"<<endl;
	}else if(notLex==1&&notLen==0){
		cout<<"lengths"<<endl;
	}else if(notLex==0&&notLen==1){
		cout<<"lexicographically"<<endl;
	}else if(notLex==0&&notLen==0){
		cout<<"both"<<endl;
	}
	return 0;
}

发表于 2017-08-30 13:26:17 回复(0)