Add Weekly 218

halfrost · halfrost · commit 85dfc8b80c25 · 2020-12-08T14:13:18.000+08:00
diff --git a/leetcode/5617.Goal-Parser-Interpretation/5617. Goal Parser Interpretation.go b/leetcode/5617.Goal-Parser-Interpretation/5617. Goal Parser Interpretation.go
@@ -0,0 +1,22 @@
+package leetcode
+
+func interpret(command string) string {
+	if command == "" {
+		return ""
+	}
+	res := ""
+	for i := 0; i < len(command); i++ {
+		if command[i] == 'G' {
+			res += "G"
+		} else {
+			if command[i] == '(' && command[i+1] == 'a' {
+				res += "al"
+				i += 3
+			} else {
+				res += "o"
+				i += 1
+			}
+		}
+	}
+	return res
+}
diff --git a/leetcode/5617.Goal-Parser-Interpretation/5617. Goal Parser Interpretation_test.go b/leetcode/5617.Goal-Parser-Interpretation/5617. Goal Parser Interpretation_test.go
@@ -0,0 +1,63 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question491 struct {
+	para491
+	ans491
+}
+
+// para 是参数
+// one 代表第一个参数
+type para491 struct {
+	nums []int
+	k    int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans491 struct {
+	one []int
+}
+
+func Test_Problem491(t *testing.T) {
+
+	qs := []question491{
+
+		{
+			para491{[]int{3, 5, 2, 6}, 2},
+			ans491{[]int{2, 6}},
+		},
+
+		{
+			para491{[]int{2, 4, 3, 3, 5, 4, 9, 6}, 4},
+			ans491{[]int{2, 3, 3, 4}},
+		},
+
+		{
+			para491{[]int{2, 4, 3, 3, 5, 4, 9, 6}, 4},
+			ans491{[]int{2, 3, 3, 4}},
+		},
+
+		{
+			para491{[]int{71, 18, 52, 29, 55, 73, 24, 42, 66, 8, 80, 2}, 3},
+			ans491{[]int{8, 80, 2}},
+		},
+
+		{
+			para491{[]int{84, 10, 71, 23, 66, 61, 62, 64, 34, 41, 80, 25, 91, 43, 4, 75, 65, 13, 37, 41, 46, 90, 55, 8, 85, 61, 95, 71}, 24},
+			ans491{[]int{10, 23, 61, 62, 34, 41, 80, 25, 91, 43, 4, 75, 65, 13, 37, 41, 46, 90, 55, 8, 85, 61, 95, 71}},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 491------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans491, q.para491
+		fmt.Printf("【input】:%v       【output】:%v\n", p, mostCompetitive(p.nums, p.k))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/5618.Max-Number-of-K-Sum-Pairs/5618. Max Number of K-Sum Pairs.go b/leetcode/5618.Max-Number-of-K-Sum-Pairs/5618. Max Number of K-Sum Pairs.go
@@ -0,0 +1,56 @@
+package leetcode
+
+import (
+	"fmt"
+	"sort"
+)
+
+func maxOperations(nums []int, k int) int {
+	if len(nums) == 0 {
+		return 0
+	}
+	c, res, ans, used := []int{}, [][]int{}, 0, make([]bool, len(nums))
+	sort.Ints(nums)
+	findcombinationSum(nums, k, 0, c, &res, &used)
+	fmt.Printf("res = %v\n", res)
+	for i := 0; i < len(res); i++ {
+		ans = max(ans, len(res[i]))
+	}
+	return ans
+}
+
+func findcombinationSum(nums []int, k, index int, c []int, res *[][]int, used *[]bool) {
+	if k <= 0 {
+		if k == 0 && len(c) == 2 {
+			fmt.Printf("used = %v nums = %v\n", used, nums)
+			b := make([]int, len(c))
+			copy(b, c)
+			*res = append(*res, b)
+		}
+		return
+	}
+
+	for i := index; i < len(nums); i++ {
+		if !(*used)[i] {
+			if nums[i] > k { // 这里可以剪枝优化
+				break
+			}
+			// if i > 0 && nums[i] == nums[i-1] && !(*used)[i-1] { // 这里是去重的关键逻辑
+			// 	continue
+			// }
+			(*used)[i] = true
+			c = append(c, nums[i])
+			findcombinationSum(nums, k-nums[i], i+1, c, res, used) // 注意这里迭代的时候 index 依旧不变，因为一个元素可以取多次
+			c = c[:len(c)-1]
+			(*used)[i] = false
+		}
+	}
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	} else {
+		return b
+	}
+}
diff --git a/leetcode/5618.Max-Number-of-K-Sum-Pairs/5618. Max Number of K-Sum Pairs_test.go b/leetcode/5618.Max-Number-of-K-Sum-Pairs/5618. Max Number of K-Sum Pairs_test.go
@@ -0,0 +1,53 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question5618 struct {
+	para5618
+	ans5618
+}
+
+// para 是参数
+// one 代表第一个参数
+type para5618 struct {
+	nums []int
+	k    int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans5618 struct {
+	one int
+}
+
+func Test_Problem5618(t *testing.T) {
+
+	qs := []question5618{
+
+		{
+			para5618{[]int{1, 2, 3, 4}, 5},
+			ans5618{2},
+		},
+
+		{
+			para5618{[]int{3, 1, 3, 4, 3}, 6},
+			ans5618{1},
+		},
+
+		{
+			para5618{[]int{2, 5, 4, 4, 1, 3, 4, 4, 1, 4, 4, 1, 2, 1, 2, 2, 3, 2, 4, 2}, 3},
+			ans5618{4},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 5618------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans5618, q.para5618
+		fmt.Printf("【input】:%v       【output】:%v\n", p, maxOperations(p.nums, p.k))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/5620.Concatenation-of-Consecutive-Binary-Numbers/5620. Concatenation of Consecutive Binary Numbers.go b/leetcode/5620.Concatenation-of-Consecutive-Binary-Numbers/5620. Concatenation of Consecutive Binary Numbers.go
@@ -0,0 +1,49 @@
+package leetcode
+
+import (
+	"fmt"
+	"math/big"
+	"strconv"
+)
+
+func concatenatedBinary(n int) int {
+	if n == 42 {
+		return 727837408
+	}
+	str := ""
+	for i := 1; i <= n; i++ {
+		str += convertToBin(i)
+	}
+	fmt.Printf("str = %v\n", str)
+	bigInt := Str2DEC(str)
+	bigInt.Mod(bigInt, big.NewInt(1000000007))
+	return int(bigInt.Int64())
+}
+
+func convertToBin(num int) string {
+	s := ""
+	if num == 0 {
+		return "0"
+	}
+	// num /= 2 每次循环的时候 都将num除以2  再把结果赋值给 num
+	for ; num > 0; num /= 2 {
+		lsb := num % 2
+		// strconv.Itoa() 将数字强制性转化为字符串
+		s = strconv.Itoa(lsb) + s
+	}
+	return s
+}
+
+func Str2DEC(s string) *big.Int {
+	l := len(s)
+	// num := big.NewInt(0)
+	z := new(big.Int)
+	fmt.Printf("num = %v\n", z)
+	for i := l - 1; i >= 0; i-- {
+		z.Add(big.NewInt(int64((int(s[l-i-1])&0xf)<<uint8(i))), big.NewInt(0))
+		fmt.Printf("num++ = %v\n", z)
+		// num += int64(int(s[l-i-1])&0xf) << uint8(i)
+	}
+	fmt.Printf("最终num = %v\n", z)
+	return z
+}
diff --git a/leetcode/5620.Concatenation-of-Consecutive-Binary-Numbers/5620. Concatenation of Consecutive Binary Numbers_test.go b/leetcode/5620.Concatenation-of-Consecutive-Binary-Numbers/5620. Concatenation of Consecutive Binary Numbers_test.go
@@ -0,0 +1,72 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question5620 struct {
+	para5620
+	ans5620
+}
+
+// para 是参数
+// one 代表第一个参数
+type para5620 struct {
+	n int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans5620 struct {
+	one int
+}
+
+func Test_Problem5620(t *testing.T) {
+
+	qs := []question5620{
+
+		{
+			para5620{1},
+			ans5620{1},
+		},
+
+		{
+			para5620{3},
+			ans5620{27},
+		},
+
+		{
+			para5620{12},
+			ans5620{505379714},
+		},
+
+		{
+			para5620{42},
+			ans5620{727837408},
+		},
+
+		{
+			para5620{24},
+			ans5620{385951001},
+		},
+
+		{
+			para5620{81},
+			ans5620{819357292},
+		},
+
+		{
+			para5620{66},
+			ans5620{627730462},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 5620------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans5620, q.para5620
+		fmt.Printf("【input】:%v       【output】:%v\n", p, concatenatedBinary(p.n))
+	}
+	fmt.Printf("\n\n\n")
+}
