题解 | #字符串排序#

这题其实没什么难点, 考验的更多就是编码能力

你得知道并能写出一个稳定的排序, 只会快排的选手直接就暴毙了

首先扫一遍全字符串, 如果不是英文字母就直接放进对应的位置, 英文字母就放进候选列表中

然后把候选列表进行排序, 我自己选的是用归并排序

然后对着填回去就行, 实话讲这题如果没有查 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)
}