题解 | #字符串排序#
字符串排序
https://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584
这题其实没什么难点, 考验的更多就是编码能力
你得知道并能写出一个稳定的排序, 只会快排的选手直接就暴毙了
首先扫一遍全字符串, 如果不是英文字母就直接放进对应的位置, 英文字母就放进候选列表中
然后把候选列表进行排序, 我自己选的是用归并排序
然后对着填回去就行, 实话讲这题如果没有查 ascii 表我就完犊子了, 确实不记得编码都是多少了
// 合并两个 arr func merge(arr1, arr2 []byte) []byte { mergeList := []byte{} var p1, p2 int for p1 < len(arr1) && p2 < len(arr2) { if arr1[p1]%26 <= arr2[p2]%26 { mergeList = append(mergeList, arr1[p1]) p1++ } else { mergeList = append(mergeList, arr2[p2]) p2++ } } for p1 < len(arr1) { mergeList = append(mergeList, arr1[p1]) p1++ } for p2 < len(arr2) { mergeList = append(mergeList, arr2[p2]) p2++ } return mergeList } // 递归分治 func mergeSort(arr []byte) []byte { if len(arr) < 2 { return arr } mid := len(arr) / 2 return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:])) } func main() { raw := []string{} var s string for { n, _ := fmt.Scan(&s) if n == 0 { break } raw = append(raw, s) } fullString := strings.Join(raw, " ") // 完整的 input string letterOnly := []byte{} // 只含有英文字母的候选列表 res := make([]byte, len(fullString)) for i := range fullString { c := fullString[i] // 因为排序的逻辑是大小写不论, 只论先后顺序, 所以将 A-Z 映射到 0~25, a-z 映射到 26~51 // 所以比较的时候和 26 取余数后比较就可以忽略大小写, 但是同时又保存了大小写的信息 if c >= 'a' && c <= 'z' { letterOnly = append(letterOnly, c-6-65) } else if c >= 'A' && c <= 'Z' { letterOnly = append(letterOnly, c-65) } else { res[i] = c // 如果不是英文字母, 对应的位置直接填入这个字符 } } sortedList := mergeSort(letterOnly) p := 0 for i := range res { if res[i] == 0 { c := sortedList[p] if c > 25 { // 如果 > 25, 说明是 a-z 的字母, 恢复它原本的 ascii 码 c += 71 } else { // 同理 c += 65 } res[i] = c p++ } } rs := string(res) fmt.Println(rs) }