2022-03-27:class AreaResource {
String area; // area表示的是地区全路径,最多可能有6级,比如:中国,四川,成都 或者 中国,浙江,杭州
String spliter; // 比如:逗号 -> ,
long count; // 表示地区的门店数量
}
现在需要把 List<AreaResource> 进行转换,需要做到同级的地域能合并,
比如:area为中国,四川,成都 ,有10个门店;area为中国,浙江,杭州,有25个门店;area为中国,浙江,义乌,有22个门店,
最终生成的JSON字符串为: {"中国":{"四川":{"成都":10]},"浙江":{"义乌":22,"杭州":25}}}。
请实现下面的方法 public String mergeCount(List<AreaResource> areas) 。
来自北京北明数科信息技术有限公司。
答案2022-03-27:
自然智慧。前缀树。
代码用golang编写。代码如下:
package main
import (
"fmt"
"strings"
)
func main() {
a1 := NewAreaResource("中国,四川,成都", ",", 10)
a2 := NewAreaResource("中国,浙江,杭州", ",", 50)
a3 := NewAreaResource("中国,浙江,杭州", ",", 25)
a4 := NewAreaResource("中国,浙江,义乌", ",", 22)
a5 := NewAreaResource("中国,四川,成都", ",", 15)
a6 := NewAreaResource("中国,四川,攀枝花", ",", 12)
a7 := NewAreaResource("中国,浙江,宁波", ",", 16)
areas := make([]*AreaResource, 0)
areas = append(areas, a1)
areas = append(areas, a2)
areas = append(areas, a3)
areas = append(areas, a4)
areas = append(areas, a5)
areas = append(areas, a6)
areas = append(areas, a7)
ans := mergeCount(areas)
fmt.Println(ans)
}
type AreaResource struct {
area string
spliter string
count int
}
func NewAreaResource(a string, s string, c int) *AreaResource {
ans := &AreaResource{}
ans.area = a
ans.spliter = s
ans.count = c
return ans
}
// 要实现的方法
func mergeCount(areas []*AreaResource) string {
all := NewArea("", 0)
for _, r := range areas {
// 中国,四川,成都 , 10个门店
//path0 := r.area.split(r.spliter)
path0 := strings.Split(r.area, r.spliter)
// 中国 四川 成都
count := r.count
f(path0, 0, all, count)
}
return all.toString()
}
// [中国,四川,成都]
// 0 1 2
func f(path0 []string, index int, pre *Area, count int) {
if index == len(path0) {
pre.count += count
} else {
// 前一个节点 pre 中国
// cur = 四川
cur := path0[index]
if _, ok := pre.next[cur]; !ok {
pre.next[cur] = NewArea(cur, 0)
}
f(path0, index+1, pre.next[cur], count)
}
}
// 自己定义的!前缀树节点
type Area struct {
// 地区名称:中国
// 四川
// 成都
name string
// 中国 key : 省名 value: 下级节点
next map[string]*Area
count int
}
func NewArea(n string, c int) *Area {
ans := &Area{}
ans.name = n
ans.count = c
ans.next = make(map[string]*Area)
return ans
}
func (this *Area) toString() string {
ans := make([]byte, 0)
// : ""
// str = "中国":
// str = "成都":100
if this.name != "" {
ans = append(ans, []byte("\""+this.name+"\""+":")...)
}
if len(this.next) == 0 {
ans = append(ans, []byte(fmt.Sprint(this.count))...)
} else {
// "中国":{ 四川如何如何,河南如何如何,江苏如何如何}
//ans.append("{");
ans = append(ans, []byte("{")...)
for _, child := range this.next {
ans = append(ans, []byte(child.toString()+",")...)
}
ans[len(ans)-1] = '}'
}
return string(ans)
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_12_4_week/Code02_MergeArea.java)