华为社招机考-字符串解压缩
缘起
最近参加华为的社招,有个牛客网的机考题。总分400分,共两道题,任选一道题,160分即可算即可。
从网上搜索了下,题目是这样的
题目介绍
将一段压缩后的字符串解压缩,并且排序输出。
解压规则:
每个字符串后面跟着一个数字,表示这个字符串的重复次数。例如,”a5”解压后的结果为”aaaaa”;’abc3’解压后的结果为”abcabcabc”。
排序规则:
1、根据每个字符串的重复次数升序排序,然后输出结果。例如,”a3b2”,输出的结果为”bbaaa”。 2、如果字符重复次数一样,则根据ASCII编码顺序做升序排序,然后输出结果。例如,”b2a2”,输出的结果为”aabb”。
输入描述:
输入的原始字符串仅包含字母与数字
输出描述:
输出的结果字符串仅包含字母
示例1
输入
a11b2bac3bad3abcd2
输出
abcdabcdbbbacbacbacbadbadbadaaaaaaaaaaa
我的实现
func decompress(s string) string {
// using map to store freq
freq := make(map[string]int)
var key = ""
var num = 0
for i := 0; i < len(s); i++ {
v := s[i]
if v >= '0' && v <= '9' {
//store string frequency
num = num*10 + int(s[i]-'0')
//for keeping get numbers
for i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9' {
num = num*10 + int(s[i+1]-'0')
i++
}
// set freq
freq[key] = num
//set key = "" and num = 0
key = ""
num = 0
} else {
// set new key
key = key + string(v)
}
}
// sort nums freq low to high
sortRes := sortFreq(freq)
//print numbers
var res = ""
for k := 0; k < len(sortRes); k++ {
f := freq[sortRes[k]]
for j := 0; j < f; j++ {
res = res + sortRes[k]
}
}
return res
}
type kv struct {
Key string
Value int
}
func sortFreq(m map[string]int) []string {
var kvs []kv
for k, v := range m {
kv := kv{
Key: k,
Value: v,
}
kvs = append(kvs, kv)
}
sort.Slice(kvs, func(i, j int) bool {
if kvs[i].Value < kvs[j].Value {
return i > j
}
if kvs[i].Value == kvs[j].Value {
return kvs[i].Key < kvs[j].Key
}
return i < j
})
var res []string
for i := 0; i < len(kvs); i++ {
res = append(res, kvs[i].Key)
}
return res
}
Read other posts