Add weekly-contest-214

halfrost · halfrost · commit f3888ff449bc · 2020-11-08T11:59:51.000+08:00
diff --git a/.vscode/settings.json b/.vscode/settings.json
@@ -3,6 +3,7 @@
     "go.formatFlags": [
         "-s"
     ],
+    "go.autocompleteUnimportedPackages": true,
     "[go]": {
         "editor.insertSpaces": false,
         "editor.formatOnSave": true,
diff --git a/leetcode/5561.Get-Maximum-in-Generated-Array/5561. Get Maximum in Generated Array.go b/leetcode/5561.Get-Maximum-in-Generated-Array/5561. Get Maximum in Generated Array.go
@@ -0,0 +1,21 @@
+package leetcode
+
+func getMaximumGenerated(n int) int {
+	if n == 0 {
+		return 0
+	}
+	nums, max := make([]int, n+1), 0
+	nums[0], nums[1] = 0, 1
+	for i := 0; i <= n; i++ {
+		if nums[i] > max {
+			max = nums[i]
+		}
+		if 2*i >= 2 && 2*i <= n {
+			nums[2*i] = nums[i]
+		}
+		if 2*i+1 >= 2 && 2*i+1 <= n {
+			nums[2*i+1] = nums[i] + nums[i+1]
+		}
+	}
+	return max
+}
diff --git a/leetcode/5561.Get-Maximum-in-Generated-Array/5561. Get Maximum in Generated Array_test.go b/leetcode/5561.Get-Maximum-in-Generated-Array/5561. Get Maximum in Generated Array_test.go
@@ -0,0 +1,62 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question5561 struct {
+	para5561
+	ans5561
+}
+
+// para 是参数
+// one 代表第一个参数
+type para5561 struct {
+	n int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans5561 struct {
+	one int
+}
+
+func Test_Problem5561(t *testing.T) {
+
+	qs := []question5561{
+
+		{
+			para5561{7},
+			ans5561{3},
+		},
+
+		{
+			para5561{2},
+			ans5561{1},
+		},
+
+		{
+			para5561{3},
+			ans5561{2},
+		},
+
+		{
+			para5561{0},
+			ans5561{0},
+		},
+
+		{
+			para5561{1},
+			ans5561{1},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 5561------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans5561, q.para5561
+		fmt.Printf("【input】:%v      【output】:%v      \n", p, getMaximumGenerated(p.n))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/5562.Minimum-Deletions-to-Make-Character-Frequencies-Unique/5562. Minimum Deletions to Make Character Frequencies Unique.go b/leetcode/5562.Minimum-Deletions-to-Make-Character-Frequencies-Unique/5562. Minimum Deletions to Make Character Frequencies Unique.go
@@ -0,0 +1,24 @@
+package leetcode
+
+import (
+	"fmt"
+	"sort"
+)
+
+func minDeletions(s string) int {
+	frequency, res := make([]int, 26), 0
+	for i := 0; i < len(s); i++ {
+		frequency[s[i]-'a']++
+	}
+	sort.Sort(sort.Reverse(sort.IntSlice(frequency)))
+	fmt.Printf("%v\n", frequency)
+	for i := 1; i <= 25; i++ {
+		if frequency[i] == frequency[i-1] && frequency[i] != 0 {
+			res++
+			frequency[i]--
+			sort.Sort(sort.Reverse(sort.IntSlice(frequency)))
+			i--
+		}
+	}
+	return res
+}
diff --git a/leetcode/5562.Minimum-Deletions-to-Make-Character-Frequencies-Unique/5562. Minimum Deletions to Make Character Frequencies Unique_test.go b/leetcode/5562.Minimum-Deletions-to-Make-Character-Frequencies-Unique/5562. Minimum Deletions to Make Character Frequencies Unique_test.go
@@ -0,0 +1,62 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question5562 struct {
+	para5562
+	ans5562
+}
+
+// para 是参数
+// one 代表第一个参数
+type para5562 struct {
+	s string
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans5562 struct {
+	one int
+}
+
+func Test_Problem5562(t *testing.T) {
+
+	qs := []question5562{
+
+		{
+			para5562{"aab"},
+			ans5562{0},
+		},
+
+		{
+			para5562{"aaabbbcc"},
+			ans5562{2},
+		},
+
+		{
+			para5562{"ceabaacb"},
+			ans5562{2},
+		},
+
+		{
+			para5562{""},
+			ans5562{0},
+		},
+
+		{
+			para5562{"abcabc"},
+			ans5562{3},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 5562------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans5562, q.para5562
+		fmt.Printf("【input】:%v      【output】:%v      \n", p, minDeletions(p.s))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/5563.Sell-Diminishing-Valued-Colored-Balls/5563. Sell Diminishing-Valued Colored Balls.go b/leetcode/5563.Sell-Diminishing-Valued-Colored-Balls/5563. Sell Diminishing-Valued Colored Balls.go
@@ -0,0 +1,54 @@
+package leetcode
+
+import (
+	"container/heap"
+)
+
+func maxProfit(inventory []int, orders int) int {
+	res, mod := 0, 1000000007
+	q := PriorityQueue{}
+	for i := 0; i < len(inventory); i++ {
+		heap.Push(&q, &Item{count: inventory[i]})
+	}
+	for ; orders > 0; orders-- {
+		item := heap.Pop(&q).(*Item)
+		res = (res + item.count) % mod
+		heap.Push(&q, &Item{count: item.count - 1})
+	}
+	return res
+}
+
+// Item define
+type Item struct {
+	count int
+}
+
+// A PriorityQueue implements heap.Interface and holds Items.
+type PriorityQueue []*Item
+
+func (pq PriorityQueue) Len() int {
+	return len(pq)
+}
+
+func (pq PriorityQueue) Less(i, j int) bool {
+	// 注意：因为golang中的heap是按最小堆组织的，所以count越大，Less()越小，越靠近堆顶.
+	return pq[i].count > pq[j].count
+}
+
+func (pq PriorityQueue) Swap(i, j int) {
+	pq[i], pq[j] = pq[j], pq[i]
+}
+
+// Push define
+func (pq *PriorityQueue) Push(x interface{}) {
+	item := x.(*Item)
+	*pq = append(*pq, item)
+}
+
+// Pop define
+func (pq *PriorityQueue) Pop() interface{} {
+	n := len(*pq)
+	item := (*pq)[n-1]
+	*pq = (*pq)[:n-1]
+	return item
+}
diff --git a/leetcode/5563.Sell-Diminishing-Valued-Colored-Balls/5563. Sell Diminishing-Valued Colored Balls_test.go b/leetcode/5563.Sell-Diminishing-Valued-Colored-Balls/5563. Sell Diminishing-Valued Colored Balls_test.go
@@ -0,0 +1,58 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question5563 struct {
+	para5563
+	ans5563
+}
+
+// para 是参数
+// one 代表第一个参数
+type para5563 struct {
+	inventory []int
+	orders    int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans5563 struct {
+	one int
+}
+
+func Test_Problem5563(t *testing.T) {
+
+	qs := []question5563{
+
+		{
+			para5563{[]int{2, 5}, 4},
+			ans5563{14},
+		},
+
+		{
+			para5563{[]int{3, 5}, 6},
+			ans5563{19},
+		},
+
+		{
+			para5563{[]int{2, 8, 4, 10, 6}, 20},
+			ans5563{110},
+		},
+
+		{
+			para5563{[]int{1000000000}, 1000000000},
+			ans5563{21},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 5563------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans5563, q.para5563
+		fmt.Printf("【input】:%v      【output】:%v      \n", p, maxProfit(p.inventory, p.orders))
+	}
+	fmt.Printf("\n\n\n")
+}
