Leetcode - rotting-oranges
Leetcode - search-suggestions-system

Heap - top buzz words

violet posted @ 5 年前 in 算法 with tags Algorithm Heap array , 436 阅读

Given a list of nail polishes and some collected posted repo on Instagram, you need to find the top words.

nail polish = ["OPI", "ColorClub", "CirqueColor", "DanceLegend", "Masura"]

repo = [

"OPI Original Nail Envy is a nail strengthener with wheat protein",

"ColorClub is a spa brand that is loved for it's great value and bright colors",

"As a top choice for professionals ColorClub is often featured in Nails Magazine.",

"Create amazingly transformed, and unique,  nails with DanceLegend spot-inducing blue top coat! DanceLegend Aquele importado top! "

"Um esmalte holográfico que vale a pena repetir vou reproduzir uma nail art do ano passado e por isso passei ele novamente ColorClub don’t harp on it"

"Booom diaaa! DanceLegend E voltando a programação normal do blog, temos um importadinho na área!"

]

Result: ["colorclub",  "dancelegend"]

 

Use map and a help struct to count the word frequency. And init all struct into a heap with specified sort method. And then pop top times and collect all the names of nail polishes.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
func main() {
    polishes := []string{"OPI", "ColorClub", "CirqueColor", "DanceLegend", "Masura"}
    repos := []string{
        "OPI Original Nail Envy is a nail strengthener with wheat protein",
        "ColorClub is a spa brand that is loved for it's great value and bright colors",
        "As a top choice for professionals ColorClub is often featured in Nails Magazine.",
        "Create amazingly transformed, and unique,  nails with DanceLegend spot-inducing blue top coat! DanceLegend Aquele importado top! ",
        "Um esmalte holográfico que vale a pena repetir vou reproduzir uma nail art do ano passado e por isso passei ele novamente ColorClub don’t harp on it",
        "Booom diaaa! DanceLegend E voltando a programação normal do blog, temos um importadinho na área!",
    }
    topPolishes := 2
 
    result := sortPolish(polishes, repos, topPolishes)
    fmt.Println("result: ", result)
}
 
type Polish struct {
    name      string
    wordCount int
    repoCount map[int]bool
}
 
type PolishHeap []Polish
 
func (h PolishHeap) Len() int { return len(h) }
func (h PolishHeap) Less(i, j int) bool {
    if h[i].wordCount < h[j].wordCount {
        return false
    } else if h[i].wordCount == h[j].wordCount {
        if len(h[i].repoCount) < len(h[j].repoCount) {
            return false
        }
    }
    return true
}
func (h PolishHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
 
func (h *PolishHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(Polish))
}
 
func (h *PolishHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 
func sortPolish(polishes []string, repoStr []string, topPolishes int) []string {
    polishMap := map[string]bool{}
    for _, t := range polishes {
        polishMap[strings.ToLower(t)] = true
    }
    repoMap := map[string]*Polish{}
    for i, q := range repoStr {
        q = strings.ToLower(q)
        repos := strings.Split(q, " ")
        for _, str := range repos {
            if polishMap[str] {
                if _, ok := repoMap[str]; ok {
                    repoMap[str].wordCount++
                    repoMap[str].repoCount[i] = true
                } else {
                    repoMap[str] = &Polish{
                        name:      str,
                        wordCount: 1,
                        repoCount: map[int]bool{
                            i: true,
                        },
                    }
                }
            }
        }
    }
    if len(repoMap) == 0 {
        return []string{}
    }
 
    repoHeap := &PolishHeap{}
    for _, val := range repoMap {
        *repoHeap = append(*repoHeap, *val)
    }
    heap.Init(repoHeap)
 
    result := []string{}
    for i := 0; i < topPolishes; i++ {
        poped := heap.Pop(repoHeap).(Polish)
        result = append(result, poped.name)
    }
 
    return result
}

 

 

Small_feed 评论 (1)
1
[回复]
HBSE Question Paper 说:
3 年前

Haryana Board Model Paper 2023 Class 1 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. HBSE Question Paper Class 1 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter