牛客网字符串排序编程题

2018-10-24 08:42:29来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

一、题目描述

编写一个程序,将输入字符串中的字符按如下规则排序(一个测试用例可能包含多组数据,请注意处理)。

规则 1 :英文字母从 A 到 Z 排列,不区分大小写。

如,输入: Type 输出: epTy

规则 2 :同一个英文字母的大小写同时存在时,按照输入顺序排列。

如,输入: BabA 输出: aABb

规则 3 :非英文字母的其它字符保持原来的位置。

如,输入: By?e 输出: Be?y

样例:

输入:

A Famous Saying: Much Ado About Nothing(2012/8).

输出:

A aaAAbc dFgghh : iimM nNn oooos Sttuuuy (2012/8).

示例1

输入

A Famous Saying: Much Ado About Nothing (2012/8).
#$Y^!#Pf&~#FUyTtAfZhCs&Dly%M@(muOI@Le^mydvc((w$x-cP&t-f$R%CCp)bCck@P-ag

输出

A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).
#$A^!#ab&~#CccCCCcDdef&Fff%g@(hIkl@LM^mmOPP((p$P-Rs&T-t$t%Uuv)wxYy@y-yZ

二、解题思路

1、思路一:字符串分割

  对字符串分割,记录非字母位置和单词长度,再对字母排序,排序后按照单词长度分割,并非字母位置插入相应字符

  最后发现不可行,原因,操作过于繁琐且空间消耗过高,输入不为单词字符串时,问题较多,输入存在用例如下:#$Y^!#Pf&~#FUyTtAfZhCs&Dly%M@(muOI@Le^mydvc((w$x-cP&t-f$R%CCp)bCck@P-ag

2、思路二:字母替换

  将字符串中所有的大小写字符存入一个数组中,将数组排序,然后遍历字符串,当为字母时从数组中获取,并下标后移一位

  难点:所有的字母并不是按照常规排序,而是需要保留原来字符串中的顺序,且从A-Z排序

  尝试一、使用数组的sort()方法,排序结果无法保留原始相同字母的相对位置,且大写字母在前,小写在后

原始:["Y","y","y","y","P","P","p","P","f","F","f","f","U","u","T","t","t","A","a","Z","h","C","c","c","C","C","C","c","s","D","d","l","L","M","m","m","O","I","e","v","w","x","R","b","k","g"]
结果:["A", "C", "C", "C", "C", "D", "F", "I", "L", "M", "O", "P", "P", "P", "R", "T", "U", "Y", "Z", "a", "b", "c", "c", "c", "d", "e",
"f", "f", "f", "g", "h", "k", "l", "m", "m", "p", "s", "t", "t", "u", "v", "w", "x", "y", "y", "y"]

  

  尝试二、在存入字母时对相同字母保持相对位置不变存入数组,再使用arr.sort(function(a,b){return a.toLocaleLowerCase()>=b.toLocaleLowerCase()?1:-1;});排序,排序结果部分保留相对位置,任然有些字母的相对位置发生了变化

let upper = str[i].toLocaleUpperCase();
            let lower = str[i].toLocaleLowerCase();
            if(strArray.indexOf(upper) !== -1 || strArray.indexOf(lower) !== -1) {
               let subscript1 = strArray.lastIndexOf(upper);
               let subscript2 = strArray.lastIndexOf(lower);
               let subscript = Math.max(subscript1,subscript2)
               strArray.splice(subscript+1,0,str[i])
            }else {
               strArray.push(str[i])
            }

 

原始:["Y","y","y","y","P","P","p","P","f","F","f","f","U","u","T","t","t","A","a","Z","h","C","c","c","C","C","C","c","s","D","d","l","L","M","m","m","O","I","e","v","w","x","R","b","k","g"]
结果:["a", "A", "b", "c", "c", "C", "C", "c", "C", "C", "d", "D", "e", "f", "F", "f", "f", "g", "h", "I", "k", "l", "L", 
"M", "m", "m", "O", "P", "P", "P", "p", "R", "s", "t", "T", "t", "U", "u", "v", "w", "x", "Y", "y", "y", "y", "Z"]

  

  尝试三、在存入时使用二维数组,每个子数组的第二个值存放0,1标识当前字母的大小写,存入时全部存小写,然后使用sort()方法排序,结果sort()方法排序会先取数组的第一个值排序,再取第二个值排序,所以排序后即使在将大写转换回来,但相对字母的顺序发生了变化,相同字母在一起,但大写在前小写在后

原始:["Y","y","y","y","P","P","p","P","f","F","f","f","U","u","T","t","t","A","a","Z","h","C","c","c","C","C","C","c","s","D","d","l","L","M","m","m","O","I","e","v","w","x","R","b","k","g"]
结果:A,a,b,C,C,C,C,c,c,c,D,d,e,F,f,f,f,g,h,I,k,L,l,M,m,m,O,P,P,P,p,R,s,T,t,t,U,u,v,w,x,Y,y,y,y,Z 

  思考:自己陷入了误区,字母数组的序列必须用sort()方法来实现

  尝试四、创建26个大写字母的数组,使用for循环去循环遍历所存的字符串的字母的数组,依次从A-Z去判断,存在就放入一个新的数组,这样数组从A-Z进行了排序,字母的相对位置也没有发生变化

 var character = new Array("A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z");
    for(let s=0;s < character.length;s ++)
    {
        for(let k = 0;k < strArray.length; k ++) {
            if(character[s] === strArray[k] || character[s].toLocaleLowerCase() === strArray[k]) {
                resultArray.push(strArray[k])
            }
        }
    }

  

原始:Y,P,f,F,U,y,T,t,A,f,Z,h,C,s,D,l,y,M,m,u,O,I,L,e,m,y,d,v,c,w,x,c,P,t,f,R,C,C,p,b,C,c,k,P,a,g
结果:A,a,b,C,c,c,C,C,C,c,D,d,e,f,F,f,f,g,h,I,k,l,L,M,m,m,O,P,P,p,P,R,s,T,t,t,U,u,v,w,x,Y,y,y,y,Z

三、完整代码

let resultArr = []
while(lines = readline()) {
    resultArr.push(changeString(lines))
}
console.log(resultArr.join("\n"))
function changeString(str) {
    var strArray = [],resultArray = []
    for(let i = 0;i < str.length;i ++) {
        if(/[A-Za-z]/.test(str[i])) {
            strArray.push(str[i])
        }
    }
    var character = new Array("A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z");
    for(let s=0;s < character.length;s ++)
    {
        for(let k = 0;k < strArray.length; k ++) {
            if(character[s] === strArray[k] || character[s].toLocaleLowerCase() === strArray[k]) {
                resultArray.push(strArray[k])
            }
        }
    }
    let index = 0,newstr = "";
    for(let j = 0;j < str.length;j ++) {
        if(/[A-Za-z]/.test(str[j])) {
            newstr += resultArray[index];
            index ++
        }else {
            newstr += str[j]
        }
    }
    return newstr
}

四、总结

  1、在看问题时要发现问题的关键点,例如本题中的关键点:字母排序,大小写相对位置不变,非字母位置不变;

  2、多尝试、发现总结问题,这个方法不行是为什么?哪儿出错了?针对问题寻找其他方法;

  3、不要陷入知识误区,例如本题中的排序,一想到排序就想到使用sort()方法,但方法也有局限性,不要把思想也局限了。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Ajax如何实现从前端不刷新页面就可以到后端取到数据

下一篇:关于截取字符串substr和substring两者的区别