字节青训营考核题库任务 15 题
前言
直入主题。
最近字节青训营又开了，入营的考核是在题库刷 10 道简单题，4 道中等题，1 道困难题，这里我就分享一下我的题解，由于题目数量较多，难度较大，所以没有详细的解题思路（题目难度不小，我有很多题也是 GPT + 百度搞了许久才做出来的，如果代码上没有我的注释，可能那道题是我 CV 的，阿巴阿巴）
我也是第一次参加字节青训营，据说进去会有字节的内推 . . . 另外就是青训营的教学视频？如果有鱼友打算参加的话，可以参考我的题解（其实这也是我发这篇文章的原因，有需要可以直接 CV 提交）
简单题 * 10
1、计算位置 x 到 y 的最少步数
AB 实验同学每天都很苦恼如何可以更好地进行 AB 实验，每一步的流程很重要，我们目标为了缩短所需的步数。
我们假设每一步对应到每一个位置。从一个整数位置 x 走到另外一个整数位置 y，每一步的长度是正整数，每步的值等于上一步的值 -1， +0，+1。求 x 到 y 最少走几步。并且第一步必须是 1，最后一步必须是 1，从 x 到 y 最少需要多少步。
样例说明
- 整数位置
x为12，另外一个整数位置y为6，我们需要从x走到y，最小的步数为：1，2，2，1，所以我们需要走4步。 - 整数位置
x为34，另外一个整数位置y为45，我们需要从x走到y，最小的步数为：1，2，3，2，2，1，所以我们需要走6步。 - 整数位置
x为50，另外一个整数位置y为30，我们需要从x走到y，最小的步数为：1，2，3，4，4，3，2，1，所以我们需要走8步。
输入格式
输入包含 2 个整数 x，y。（0<=x<=y<2^31）
输出格式
对于每一组数据，输出一行，仅包含一个整数，从 x 到 y 所需最小步数。
输入样例
▼text复制代码12 6 34 45 50 30
输出样例
▼text复制代码4 6 8
代码
▼go复制代码package main import ( "fmt" "math" ) func solution(x int, y int) int { if x > y { x, y = y, x } diff := y - x // 两个数的差值 ans := math.MaxInt/2 // 序列必定存在：1 2 3 ... k k-1 k-2 ... 1 // 计算出必定存在的值后，再找其他数字 for i := 2; i < diff; i++ { v := f(i) + f(i-1) if v > diff { // 超过差值，证明 ans 已经计算出来了，跳出循环 break } r := diff-v // 还差 r 的距离 flag := 0 if r % i == 0 { // 如果需要添加的步数刚刚好，就需要把 i*2 多加的步数-1 flag = 1 } // i*2 就是基础步数 + 1 // 举例：i == 4，目标 5，那就需要 2 步，而 r/i == 1 // 如果 i == 4，目标 4，那就只需要 1 步，而 r/i == 1 ans = min(ans, 2*i + r/i - flag) } return ans } func f(x int) int { // 求 1~x 走的路程（等差数列） return (1 + x) * x / 2 } func main() { // You can add more test cases here fmt.Println(solution(12, 6)) fmt.Println(solution(34, 45)) fmt.Println(solution(50, 30)) fmt.Println(solution(12, 6) == 4) fmt.Println(solution(34, 45) == 6) fmt.Println(solution(50, 30) == 8) }
2、环状 DNA 序列整理
环状 DNA 又称超螺旋，即一段碱基序列呈现环状，在分析时，需要将相同序列的环状 DNA 分到相同组内，现需将环状碱基序列按照最小表示法进行排序。
一段长度为 n 的碱基序列，按照顺时针方向，碱基序列可以从任意位置起开始该序列顺序，因此长度为 n 的碱基序列有 n 种表示法。例如：长度为 6 的碱基序列 CGAGTC，有 CGAGTC、GAGTCC、AGTCCG 等表示法。在这些表示法中，字典序最小的称为“最小表示”。
输入一个长度为 n（n <= 100）的环状碱基序列（只包含 A、C、G、T 这 4 种碱基）的一种表示法，输出该环状碱基序列的最小表示。
例如：
ATCA 的最小表示是 AATC
CGAGTC 的最小表示是 AGTCCG
输入描述
一段 DNA 碱基序列
输出描述
DNA 碱基序列的最小表示
备注：
n <= 100
DNA 由大写英文字母 A、G、C、T 组成
示例 1
输入：ATCA
输出：AATC
示例 2
输入：CGAGTC
输出：AGTCCG
代码
▼go复制代码package main import ( "fmt" "strings" ) func solution(s string) string { // 生成所有可能的起始位置的序列 var sequences []string for start := 0; start < len(s); start++ { sequences = append(sequences, s[start:]+s[:start]) } // 初始化最小表示为第一个序列 minSeq := sequences[0] // 遍历所有序列，找到字典序最小的 for _, seq := range sequences { if strings.Compare(seq, minSeq) < 0 { // s1<s2 返回-1 minSeq = seq } } return minSeq } func main() { // You can add more test cases here fmt.Println(solution("ATCA") == "AATC") fmt.Println(solution("CGAGTC") == "AGTCCG") fmt.Println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG") == "AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG") }
3、Base32 编码和解码
你需要实现一个 Base32 的编码和解码函数。
相比于 Base32，你可能更熟悉 Base64，Base64 是非常常见的用字符串形式表示二进制数据的方式，在邮件附件、Web 中的图片中都有广泛的应用。
Base32 是 Base64 的变种，与 Base64 不同的地方在于 Base64 以 6 bit 为一组作为索引，而 Base32 以 5 bit 为一组作为索引，每一组用一个 ASCII 字符表示。Base 64 总共需要 64 个字符表示，而 Base32 则只需要 32 个字符表示。
Base32 的编码流程如下：
- 对二进制数据进行预处理：如果二进制数据的 bit 数目不不是 5 的倍数的话，在末尾补 0 直至为 5 的倍数
- 以 5 bit 为一组进行分组
- 将每一组的 5 bit 二进制转换为索引（0 - 31）
- 在索引 - 字符转换表中查询索引对应的字符
- 根据原始二进制数据的 bit 数目除以 40 后的余数，确定末尾需要补 0 的数目
- 如果原始二进制数据 bit 数目除以 40 后的余数是 0 的话，不需要补 +
- 如果原始二进制数据 bit 数目除以 40 后的余数是 8 的话，补 6 个 +
- 如果原始二进制数据 bit 数目除以 40 后的余数是 16 的话，补 4 个 +
- 如果原始二进制数据 bit 数目除以 40 后的余数是 24 的话，补 3 个 +
- 如果原始二进制数据 bit 数目除以 40 后的余数是 32 的话，补 1 个 +
Base32 的索引 - 字符转换表见下方。
索引：0 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
字符：9 8 7 6 5 4 3 2 1 0 m n b v c x z a s d f g h j k l p o i u y t
示例
编码
- 输入：字符串
foo - 字符
f的 ASCII 编号为 102，字符o的 ASCII 编号为 111 - 将字符串
foo以 ASCII 编号形式表达为 102 111 111 的序列 - 将 102 111 111 的序列转换为二进制表示，即 01100110 01101111 01101111，将二进制字符串以 40 个为一组进行分割
- 最后一组的二进制字符串长度为 24，不是 5 的倍数，因此在最后补 0，直至其能被 5 整除（在此例子中，补 1 个即可），二进制字符串表示为： 01100110 01101111 01101111 0
- 每 5 bit 为一组，表示为：01100 11001 10111 10110 11110
- 将每一组转换为十进制的索引，表示为：12 25 23 22 30，对应字符
bljhy - 由于最终输出字符串长度不是 8 的倍数，在输出最后补充 3 个
+ - 查询索引 - 字符转换表后，可以得出最终的输出为：
bljhy+++
Input data: foo
Input in Unicode: 102 111 111
Unicode in binary (8-bit): 01100110 01101111 01101111 0
Unicode in binary (5-bit): 01100 11001 10111 10110 11110
Decimal: 12 25 23 22 30
Pad: + + +
Output: b l j h y + + +
解码
- 输入：
bljhy+++ - 查询索引 - 字符转换表后，可知原始的二进制数据组为：01100 11001 10111 10110 11110
- 由末尾 3 个
+可知在编码时原始二进制数据最后一组的个数为 24 个，由此可知最后一组数据为：01100110 01101111 01101111 - 将二进制数据转换为 ASCII 编号后可知，原始字符串的 Unicode 序列为：102 111 111
- 将 Unicode 序列转换为字符串，即可得出原始字符串，为：
foo
输入示例
foo
b0zj5+++
- 第一行为需要编码的原始字符串：
rawStr - 第二行为需要解码的 Base32 字符串：
encodedStr
输出示例
bljhy+++
bar
解释：
- 第一行编码后的输出为
bljhy+++ - 第二行解码后的输出为
bar
数据范围
rawStr[n] 为 ASCII 的可显示字符，rawStr.length < 2048
encodedStr 为使用此算法编码后的 Base32 字符序列，encodedStr.length < 4096
代码
▼go复制代码package main import ( "fmt" "strings" ) func base32Encode(rawStr string) string { base32Chars := "9876543210mnbvcxzasdfghjklpoiuyt" var binaryString string for _, char := range rawStr { binaryString += fmt.Sprintf("%08b", char) } // 添加补齐的0 paddingLength := (5 - len(binaryString)%5) % 5 binaryString += strings.Repeat("0", paddingLength) // 将二进制字符串分成5位一组 var base32Indices []int for i := 0; i < len(binaryString); i += 5 { index := binaryString[i : i+5] val := 0 fmt.Sscanf(index, "%b", &val) base32Indices = append(base32Indices, val) } // 使用base32Chars编码 var encodedStr strings.Builder for _, index := range base32Indices { encodedStr.WriteByte(base32Chars[index]) } // 处理padding originalLength := len(rawStr) * 8 remainder := originalLength % 40 switch remainder { case 8: encodedStr.WriteString("++++++") case 16: encodedStr.WriteString("++++") case 24: encodedStr.WriteString("+++") case 32: encodedStr.WriteString("+") } return encodedStr.String() } func base32Decode(encodedStr string) string { base32Chars := "9876543210mnbvcxzasdfghjklpoiuyt" parts := strings.Split(encodedStr, "+") var decodedResult strings.Builder for _, part := range parts { // 将base32字符转换为二进制字符串 var binaryString strings.Builder for _, char := range part { index := strings.IndexRune(base32Chars, char) binaryString.WriteString(fmt.Sprintf("%05b", index)) } // 根据padding长度调整 paddingCount := (8 - len(part)%8) % 8 bitsToRemove := 0 switch paddingCount { case 6: bitsToRemove = 2 case 4: bitsToRemove = 4 case 3: bitsToRemove = 1 case 1: bitsToRemove = 3 } // 移除多余的bits binaryStr := binaryString.String() if bitsToRemove > 0 { binaryStr = binaryStr[:len(binaryStr)-bitsToRemove] } // 将二进制字符串转换为字符 for i := 0; i < len(binaryStr); i += 8 { b := binaryStr[i : i+8] var val int fmt.Sscanf(b, "%b", &val) decodedResult.WriteByte(byte(val)) } } return decodedResult.String() } func solution(rawStr, encodedStr string) string { encodedResult := base32Encode(rawStr) decodedResult := base32Decode(encodedStr) result := fmt.Sprintf("%s:%s", encodedResult, decodedResult) fmt.Println(result) return result } func main() { // You can add more test cases here fmt.Println(solution("foo", "b0zj5+++") == "bljhy+++:bar") fmt.Println(solution("The encoding process represents 40-bit groups of input bits as output strings of 8 encoded characters. Proceeding from left to right, a 40-bit input group is formed by concatenating 5 8bit input groups. These 40 bits are then treated as 8 concatenated 5-bit groups, each of which is translated into a single character in the base 32 alphabet. When a bit stream is encoded via the base 32 encoding, the bit stream must be presumed to be ordered with the most-significant- bit first. That is, the first bit in the stream will be the high- order bit in the first 8bit byte, the eighth bit will be the low- order bit in the first 8bit byte, and so on.", "bljhy+++b0zj5+++") == "maf3m164vlahyl60vlds9i6svuahmiod58l3mi6sbglhmodfcbz61b8vb0fj1162c0jjmi6d58jhb160vlk2mu89b0fj1il9b4ls9oogcak2mu89cvp25pncbuls9oo359i79lncbvjh1ln558ahzknsb4aj1lnscbj7917zc0jh3ln4bafhill9bll3yo09vashbu89cajs9id0buf21n89b5z61b8vb0fj1160vlk2mu89bul3yunz58fj3163vul3pln558a2s166vuj33knfbgj37u60vlds9v0928a3su89v4j29unf58dj5oogc8lsi17fv8sj3l093zk79kd0cals9knsbfz21p64vkz21id4b4p3ml89b4ls9c89bvjhiko8cashiknfbgs79v0vb0fj1162c0jjmi6d4zz3mkn6v9z3yla9cuf3sko158fj316fc0zhiiobb4p3ml89v4j21ol9b5z23pncbuh3m166v8zj5kn6casj5160vkz21p6458a37io459ld5168vak3zkn7bgp7i189muf3moa9b5z35pnf58lj1id4b4hs9pnd58shikoxbash116hv4zs9u61bfz35kndbfz63ba9bgj33oo5v4j3cn89caf3m167v4p79iofc0sh7o09vgpj3u89b0ss9i6sbgljmon4bzz21ol9b0ss9oosbasj5ln558ohsu6158p3zl09vgjj3u8vcvfhcod0blfh3kncczhs9kd0czz3bpnscvp7i17fv8zj1160cbh79u61bfz3bpnscvp79kd0czz3soa9caf3m16dcal3mknv58ohso6b58a3m16fv8ss9p60buf7p16xc0s3mia9b0fj1160vkz21p6458d3siddczz6zkd0czz35ynfbfh79u61bfz3mpn2v8p3z167v4p79uo0vah79kd458p3zl09vajjcn09vul31lns58a3su89v4j79u61bfz3bpnscvp79c67v4p79kdlcassk168vls79iox58jhinz+:foobar") }
4、DNA 序列还原
给定一段受损的 DNA 碱基序列 dna1，在每次只操作一个碱基的情况下，将其以最少的操作步骤将其还原到未受损的 DNA 碱基序列 dna2。
只可以对 DNA 碱基序列中的一个碱基进行三种操作：
- 增加一个碱基
- 去除一个碱基
- 替换一个碱基
输入描述:
输入两段 DNA 碱基序列，每段分一行输入
第一行为第一段受损的 DNA 碱基序列 dna1
第二行为第二段未受损的 DNA 碱基序列 dna2
输出描述:
最小操作步骤数
备注:
0 <= dna1.length, dna2.length <= 500
dna1 和 dna2 由大写英文字母 A、G、C、T 组成
示例 1
输入
AGCTTAGC
AGCTAGCT
输出
2
说明
AGCTTAGC -> AGCTAGC（删除 T）
AGCTAGC -> AGCTAGCT（增加 T）
示例 2
输入
AGCCGAGC
GCTAGCT
输出
4
说明
AGCCGAGC -> GCCGAGC（删除 A）
GCCGAGC -> GCTGAGC（将 C 替换为 T）
GCTGAGC -> GCTAGC（删除 G）
GCTAGC -> GCTAGCT（增加 T）
代码
▼go复制代码package main import ( "fmt" "math" ) func solution(dna1, dna2 string) int { m := len(dna1) n := len(dna2) // 创建一个 (m+1) x (n+1) 的DP表 dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } // 初始化第一列和第一行 for i := 0; i <= m; i++ { dp[i][0] = i // 将dna1的前i个字符转换为空需要i次删除 } for j := 0; j <= n; j++ { dp[0][j] = j // 将空转换为dna2的前j个字符需要j次插入 } // 填充DP表 for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if dna1[i-1] == dna2[j-1] { dp[i][j] = dp[i-1][j-1] // 无需操作 } else { dp[i][j] = int(math.Min( float64(dp[i-1][j-1]), // 替换 math.Min( float64(dp[i-1][j]), // 删除 float64(dp[i][j-1]), // 插入 ), )) + 1 } } } return dp[m][n] } func main() { // 测试用例 fmt.Println(solution("AGCTTAGC", "AGCTAGCT") == 2) fmt.Println(solution("AGCCGAGC", "GCTAGCT") == 4) // 其他测试用例 fmt.Println(solution("", "") == 0) fmt.Println(solution("A", "G") == 1) fmt.Println(solution("AGT", "AGT") == 0) fmt.Println(solution("AGT", "AGTC") == 1) fmt.Println(solution("AGT", "AG") == 1) fmt.Println(solution("AGT", "CGT") == 1) }
5、创意标题匹配
在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 bidword 对创意中的通配符（通配符是用成对 {} 括起来的字符串，可以包含 0 个或者多个字符）进行替换 ，用来提升广告投放体验。例如：“{末日血战} 上线送 SSR 英雄，三天集齐无敌阵容！”，会被替换成“帝国时代游戏下载上线送 SSR 英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和一句标题，判断这句标题是否从该创意替换生成的。
输入格式
第一行输入为 N，代表有 N 个标题
第二行代表含有通配符的创意，创意中包含大小写英文字母和成对的花括号
第三行到第 N + 2 行，代表 N 句标题，每个标题只包含大小写英文字母
输出格式
N 行，每行为“True”或者“False”，判断该句标题是否符合创意
输入样例
4
ad{xyz}cdc{y}f{x}e
adcdcefdfeffe
adcdcefdfeff
dcdcefdfeffe
adcdcfe
输出样例
True
False
False
True
说明
adcdcefdfeffe 可以看作 ad{}cdc{efd}f{eff}e 或者 ad{}cdc{efdfe}f{f}e 替换生成，但是无论哪种替换方式都是符合该创意 ad{xyz}cdc{y}f{x}e。
数据范围
N <= 10
标题和创意的长度小于等于 100
代码
▼go复制代码package main import ( "fmt" "strings" ) // 定义一个结构体来表示创意的每一部分 type Part struct { value string isWildcard bool } // 解析模板，将固定部分和通配符部分分开 func parseCreative(creative string) []Part { var parts []Part var sb strings.Builder for i := 0; i < len(creative); i++ { c := creative[i] if c == '{' { // 如果有积累的固定部分，添加到列表 if sb.Len() > 0 { parts = append(parts, Part{sb.String(), false}) sb.Reset() } } else if c == '}' { // 通配符结束，添加到列表 parts = append(parts, Part{sb.String(), true}) sb.Reset() } else { sb.WriteByte(c) } } // 添加剩余的固定部分 if sb.Len() > 0 { parts = append(parts, Part{sb.String(), false}) } return parts } // 递归匹配函数 func matchHelper(title string, tIndex int, parts []Part, pIndex int) bool { // 如果所有部分都匹配完毕，检查标题是否也完全匹配 if pIndex == len(parts) { return tIndex == len(title) } currentPart := parts[pIndex] if !currentPart.isWildcard { // 固定部分需要精确匹配 if strings.HasPrefix(title[tIndex:], currentPart.value) { return matchHelper(title, tIndex+len(currentPart.value), parts, pIndex+1) } return false } // 通配符部分，可以匹配任意长度，包括空字符串 for i := tIndex; i <= len(title); i++ { if matchHelper(title, i, parts, pIndex+1) { return true } } return false } // 解决方案函数 func solution(n int, template string, titles []string) string { parts := parseCreative(template) var sb strings.Builder for i := 0; i < n; i++ { if matchHelper(titles[i], 0, parts, 0) { sb.WriteString("True") } else { sb.WriteString("False") } if i == n-1 { break } sb.WriteString(",") } return sb.String() } func main() { // 测试用例 testTitles1 := []string{"adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"} testTitles2 := []string{"CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"} testTitles3 := []string{"abcdefg", "abefg", "efg"} fmt.Println(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) == "True,False,False,True") fmt.Println(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) == "False,False,False,False,False,True") fmt.Println(solution(3, "a{bdc}efg", testTitles3) == "True,True,False") }
6、打点计数器
小明想发明一台打点计数器，这个计数器有这样的一个功能：
-
它可以接收一个递增的数据范围（形如[3, 9]），其中第一个数字代表起始，第二个数字代表结束
-
这个数据范围中包含几个数字，打点计数器就会打几个点
-
在传入的多组数据范围中，如果出现了范围的重复，机器则不会重复打点
你可以帮助小明算一算，在不同的情况下，计数器会打出几个点么？
输入格式
一个二维数组
输出格式
一个整数，表达在输入是这个数组的情况下，计数器打出的点数
输入样例(1)
[ [1,4], [7, 10], [3, 5] ]
输出样例(1)
7
输入样例(2)
[ [1,2], [6, 10], [11, 15] ]
输出样例(2)
9
数据范围
- 数字范围 [-10^9, 10^9]，数组长度 < 2^16
代码
▼go复制代码package main import ( "fmt" "sort" ) type Interval [][]int func (a Interval) Len() int { return len(a) } func (a Interval) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a Interval) Less(i, j int) bool { return a[i][0] < a[j][0] } func solution(inputArray [][]int) int { if inputArray == nil || len(inputArray) == 0 { return 0 } // 按起始点排序 sort.Sort(Interval(inputArray)) // 初始化第一个区间 start := inputArray[0][0] rightBound := inputArray[0][1] res := 0 for i := 1; i < len(inputArray); i++ { if inputArray[i][0] > rightBound { // 不重叠，累加当前区间长度 res += rightBound - start start = inputArray[i][0] rightBound = inputArray[i][1] } else { // 重叠，更新 rightBound = max(rightBound, inputArray[i][1]) } } res += rightBound - start return res } // 辅助函数：计算最大值 func max(a, b int) int { if a > b { return a } return b } func main() { // 测试用例 testArray1 := [][]int{{1, 4}, {7, 10}, {3, 5}} testArray2 := [][]int{{1, 2}, {6, 10}, {11, 15}} fmt.Println(solution(testArray1) == 7) fmt.Println(solution(testArray2) == 9) }
7、多米诺骨牌
多米诺骨牌游戏规则非常简单，将骨牌按一定间距的尺寸排成单行，或分行排成一片。推倒第一张骨牌，其余发生连锁反应依次倒下，或形成一条长龙，或形成一幅图案。
小 A 觉得多米诺骨牌超级没意思，所以他想了点小花招。
小 A 将 n 个多米诺骨牌放在一条线上，每一块都垂直竖立。他同时将一些骨牌向左或向右推倒。注意：不会出现连续向左或者向右推的情况。 每过一秒，被推向左边或右边的骨牌会将左边或右边的相邻骨牌推倒。当一个骨牌，其左边倒向它的骨牌数目与其右边倒向它的骨牌数目相等时，由于力的平衡，该骨牌将依然保持竖立。
给定小 A 最初推骨牌的方向，求出最后依然保持竖立的骨牌数目和位置。
输入格式
输入数据第一行包括一个整数 n（1≤n≤3000），表示这一行多米诺骨牌的数目。下一行包括一个长度为 n 的字符串，字符串的第 i 个字符意义如下：
“L”，第 i 个字符将要被向左推。
“R”，第 i 个字符将要被向右推。
“.”，第 i 个字符不会被推。
输出格式
首先输出保持竖立的骨牌数目。如果保持竖立的骨牌数目不为 0，下一行输出保持竖立的骨牌的位置，骨牌位置从 1 到 n。
每两个数之间用一个空格隔开，注意最后一个数后面没有空格。
输入样例
14
.L.R...LR..L..
5
R....
1
.
输出样例
4
3 6 13 14
0
1
1
代码
▼go复制代码package main import ( "fmt" "strings" ) func solution(num int, data string) string { // 初始化leftTime和rightTime数组 leftTime := make([]int, num) rightTime := make([]int, num) inf := num + 1 for i := 0; i < num; i++ { leftTime[i] = inf rightTime[i] = inf } // 从左到右遍历，处理向右推的情况 pushTime := inf for i := 0; i < num; i++ { c := data[i] if c == 'R' { pushTime = 0 rightTime[i] = min(rightTime[i], pushTime) } else if c == 'L' { pushTime = inf } else { if pushTime != inf { pushTime += 1 if pushTime < rightTime[i] { rightTime[i] = pushTime } } } } // 从右到左遍历，处理向左推的情况 pushTime = inf for i := num - 1; i >= 0; i-- { c := data[i] if c == 'L' { pushTime = 0 leftTime[i] = min(leftTime[i], pushTime) } else if c == 'R' { pushTime = inf } else { if pushTime != inf { pushTime += 1 if pushTime < leftTime[i] { leftTime[i] = pushTime } } } } // 收集保持竖立的骨牌位置 var sb strings.Builder count := 0 for i := 0; i < num; i++ { if leftTime[i] == rightTime[i] { count++ } } if count == 0 { return "0" } else { sb.WriteString(fmt.Sprintf("%d:", count)) first := true for i := 0; i < num; i++ { if leftTime[i] == rightTime[i] { if !first { sb.WriteString(",") } sb.WriteString(fmt.Sprintf("%d", i+1)) // 位置从1开始 first = false } } return sb.String() } } func main() { // 测试用例 fmt.Println(solution(14, ".L.R...LR..L..") == "4:3,6,13,14") fmt.Println(solution(5, "R....") == "0") fmt.Println(solution(1, ".") == "1:1") }
8、叠盘子
小明是个讲究生活质量的人，家里的一切都井井有条，比如说家中的盘子都是一个系列，每个盘子都标有唯一的一个整数作为标识。在每次吃完饭后，小明都会将这些盘子按照特定的顺序叠放收拾起来，收拾的规则如下：
-
盘子叠放后会被分为多堆，每一堆都可能是由一个或多个盘子组成
-
叠放在同一堆的盘子的序号都是不间断递增的（例如 1，2，3 为不间断递增，而 1，3，4 则只是普通的递增），并且这些盘子的数量至少是 3 个
-
这些盘子的序号在被叠放之前就是递增的
请问你可以编写一个程序，帮助小明算一算盘子该如何叠放么？
输入格式
空格分隔输入所有的数字
输出格式
一个字符串，每个堆被逗号分隔开，如果堆中只有一个盘子，就用序号表达；如果堆中有多个盘子，用『起始编号』+『-』+『终止编号』来表达。
输入样例(1)
-3 -2 -1 2 10 15 16 18 19 20
输出样例(1)
"-3--1,2,10,15,16,18-20"
输入样例(2)
-6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20
输出样例(2)
"-6,-3-1,3-5,7-11,14,15,17-20"
输入样例(3)
1 2 7 8 9 10 11 19
输出样例(3)
"1,2,7-11,19"
代码
▼go复制代码package main import ( "fmt" "strconv" "strings" ) func solution(plates string) string { // 将字符串按空格分割成整数 parts := strings.Fields(plates) var numbers []int for _, part := range parts { num, _ := strconv.Atoi(part) numbers = append(numbers, num) } var res strings.Builder i := 0 for i < len(numbers) { if i == len(numbers)-1 { // 处理最后一个元素 res.WriteString(strconv.Itoa(numbers[i])) break } start, end := numbers[i], numbers[i] cnt := 1 j, k := i+1, i for j < len(numbers) { // 检查连续的数 if numbers[j]-numbers[k] == 1 { cnt++ end = numbers[j] j++ k++ } else { break } } if cnt >= 3 { // 如果有连续3个或以上的数，用 "start-end" 表示 res.WriteString(strconv.Itoa(start) + "-" + strconv.Itoa(end) + ",") i = j } else { // 否则直接加入当前数字 res.WriteString(strconv.Itoa(numbers[i]) + ",") i++ } } // 移除最后的逗号 result := res.String() if result[len(result)-1] == ',' { result = result[:len(result)-1] } return result } func main() { // 测试用例 fmt.Println(solution("-3 -2 -1 2 10 15 16 18 19 20") == "-3--1,2,10,15,16,18-20") fmt.Println(solution("-6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20") == "-6,-3-1,3-5,7-11,14,15,17-20") fmt.Println(solution("1 2 7 8 9 10 11 19") == "1,2,7-11,19") }
9、二分数字
给定一个数组，请你把数组里的数字分为两组，使一组数字和的个位数等于 A（1 ≤ A ≤ 9），且剩余数字和的个位数等于 B（1 ≤ B ≤ 9）；或者一组数字的个数为零，但剩余数字和的个位数等于 A 或 B。请问一共有多少种划分方式？
备注：
-
数组里的数字可以相等，但每个数字都是独一无二的。 比如数组 a 等于[1, 1, 1]，A 等于 1，B 等于 2，则一共有三组划分方式： 第一种： A：a[0] B：a[1]、a[2] 第二种： A：a[1] B：a[0]、a[2] 第三种： A：a[2] B：a[0]、a[1]
-
可以将所有数字都划分到同一组，使其和的个位数等于 A 或 B；另一组为空 比如数组 a 等于[1, 1, 1]，A 等于 3，B 等于 5，则共有一组划分方式： A：a[0]、a[1]、a[2] B：空
输入格式
输入第一行包含三个整数 n、A、B（1 ≤ n ≤ 100000，1 ≤ A ≤ 9，1 ≤ B ≤ 9），n 代表需要数组中的数字个数。
第二行，有 n 个元素，代表数组内的数字（1 ≤ 每个数字 ≤ 9）。
输出格式
输出一共有多少种划分方式，结果对 10000007 取余。
输入样例
样例 1
3 1 2
1 1 1
样例 2
3 3 5
1 1 1
样例 3
2 1 1
1 1
输出样例
样例 1
3
样例 2
1
样例 3
2
代码
▼go复制代码package main import ( "fmt" ) const MOD = 10000007 // 解决方案函数 func solution(n, A, B int, numbers []int) int { // 初始化动态规划表 dp := make([][]int, 10) // dp[a][b] 表示和的个位数为 a 的组 1 和 和的个位数为 b 的组 2 的方案数 for i := range dp { dp[i] = make([]int, 10) } dp[0][0] = 1 // 初始条件：两组的和的个位数都是 0 时，只有 1 种划分方式 // 遍历每个数字进行动态规划 for _, num := range numbers { // 创建一个新的 dp 来保存状态转移后的结果 newDP := make([][]int, 10) for i := range newDP { newDP[i] = make([]int, 10) } // 遍历当前 dp 中的所有可能状态 for a := 0; a < 10; a++ { for b := 0; b < 10; b++ { if dp[a][b] == 0 { continue } // 将当前数字 num 放入组 1 newDP[(a+num)%10][b] = (newDP[(a+num)%10][b] + dp[a][b]) % MOD // 将当前数字 num 放入组 2 newDP[a][(b+num)%10] = (newDP[a][(b+num)%10] + dp[a][b]) % MOD } } // 更新 dp dp = newDP } // 统计符合条件的划分方式 result := dp[A][B] // 另外要统计当其中一个组为空的情况 result = (result + dp[A][0]) % MOD result = (result + dp[0][B]) % MOD return result } func main() { // 测试用例 fmt.Println(solution(3, 1, 2, []int{1, 1, 1}) == 3) fmt.Println(solution(3, 3, 5, []int{1, 1, 1}) == 1) fmt.Println(solution(2, 1, 1, []int{1, 1}) == 2) }
10、飞行棋分组
现在桌子上有一堆飞行棋棋子，有 N 个，每个棋子上标有数字序号，现在想让你帮忙给这堆飞行棋分成 M 组，需要满足：
- 每个分组只能包含 5 个棋子
- 每个棋子只能出现在一个分组里
- 每个分组里的棋子的数字序号相同
请问可以完成上述分组么？
输入格式
空格分割的飞行棋棋子序号，如：1 3 4 5 6 5 4
输出格式
是否可以完成分组，如果可以输出 true，否则输出 false
输入样例(1)
1 2 3 4 5
上述棋子只有 5 个只能分为一组，但组内棋子序号不一致，所以无法完成分组，输出 false
输出样例(2)
1 1 1 1 2 1 2 2 2 2
上述棋子可以分为两组，[1, 1, 1, 1, 1] 和 [2, 2, 2, 2, 2] 两组，可以完成分组，输出 true
数据范围
- 棋子数量：
1 <= N <= 10^5 - 棋子序号：
1 <= pieces[i] <= 40
代码
▼go复制代码package main import ( "fmt" ) func solution(nums []int) string { // 使用map记录每个数字出现的次数 countMap := make(map[int]int) for _, num := range nums { countMap[num]++ } // 检查是否有数字出现的次数少于5次 for _, count := range countMap { if count < 5 { return "False" } } return "True" } func main() { // 测试用例 fmt.Println(solution([]int{1, 3, 4, 5, 6, 5, 4}) == "False") fmt.Println(solution([]int{1, 1, 1, 1, 2, 1, 2, 2, 2, 2}) == "True") fmt.Println(solution([]int{ 11, 45, 49, 37, 45, 38, 3, 47, 35, 49, 26, 16, 24, 4, 45, 39, 28, 26, 14, 22, 4, 49, 18, 4, 4, 26, 47, 14, 1, 21, 9, 26, 17, 12, 44, 28, 24, 24, 10, 31, 33, 32, 23, 41, 41, 19, 17, 24, 28, 46, 28, 4, 18, 23, 48, 45, 7, 21, 12, 40, 2, 19, 19, 28, 32, 6, 27, 43, 6, 18, 8, 27, 9, 6, 6, 31, 37, 15, 26, 20, 43, 3, 14, 40, 20}) == "False") }
中等题 * 4
11、青海湖租车之旅
油价飞升的今天，我们尽量减少花费。我们出门旅游，有时候租车去旅游也是一种不错的方式。这次我们这次旅游是从「青海湖」到「景点 X」，景点 X 可以是「敦煌」、「月牙泉」等，线路的路径是唯一的，假设我们每走 1 km 消耗 1 L 的油，车油箱容量 400L。比如：如果「景点 X」是敦煌，我们在青海湖租车前油箱是 200L 的，在「景点 X」（敦煌）还车的时候也是 200L 的，路上有很多加油站，加油站在青海湖和「景点 X」的连线上。
输入格式
第 1 行表示「青海湖」到「景点 X」的距离，距离最远不超过 10000 km。 第 2 行表示接下来 N 行表示 N 个加油站（N 为正整数）。 接下来 N（1 <= N <= 100）行表示，每一个加油站情况。每一个加油站包括距离「景点 X」的距离 a km（0 <= a <= 10000），以及每升汽油的价格 b 元（0 <= b <= 2000），a 和 b 均为正整数。
输出格式
如果不能到达目的地「景点 X」，输出 Impossible。 如果能到达目的地「景点 X」，输出最小花费多少元。
输入样例： 500 4 100 1 200 30 400 40 300 20
输出样例： 4300
代码
▼go复制代码package main import ( "fmt" "math" "sort" ) func solution(distance, n int, gasStations [][]int) string { gasStations = append(gasStations, []int{distance}) sort.Slice(gasStations, func(i, j int) bool { return gasStations[i][0] < gasStations[j][0] }) dis := make([]int, n+1) dis[0] = gasStations[0][0] for i := 1; i <= n; i++ { dis[i] = gasStations[i][0] - gasStations[i-1][0] } // dp 数组初始化为一个非常大的值 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, 401) for j := range dp[i] { dp[i][j] = math.MaxInt32 } } dp[0][200] = 0 for i := 1; i <= n; i++ { if gasStations[i-1][0] == distance { n = i - 1 break } for j := 0; j <= 400; j++ { for k := 0; k <= 400; k++ { if j+dis[i-1]-k >= 0 && len(gasStations[i-1]) > 1 { dp[i][j] = min(dp[i][j], dp[i-1][k]+(j+dis[i-1]-k)*gasStations[i-1][1]) } } } } if n < 1 || 200+dis[n-1] < 0 || dp[n][200+dis[n-1]] == math.MaxInt32 { return "Impossible" } return fmt.Sprintf("%d", dp[n][200+dis[n-1]]) } func main() { // 测试用例 gasStations1 := [][]int{{100, 1}, {200, 30}, {400, 40}, {300, 20}} gasStations2 := [][]int{{100, 999}, {150, 888}, {200, 777}, {300, 999}, {400, 1009}, {450, 1019}, {500, 1399}} gasStations3 := [][]int{{101}, {100, 100}, {102, 1}} gasStations4 := [][]int{{34, 1}, {105, 9}, {9, 10}, {134, 66}, {215, 90}, {999, 1999}, {49, 0}, {10, 1999}, {200, 2}, {300, 500}, {12, 34}, {1, 23}, {46, 20}, {80, 12}, {1, 1999}, {90, 33}, {101, 23}, {34, 88}, {103, 0}, {1, 1}} fmt.Println(solution(500, 4, gasStations1) == "4300") fmt.Println(solution(500, 7, gasStations2) == "410700") fmt.Println(solution(500, 3, gasStations3) == "Impossible") fmt.Println(solution(100, 20, gasStations4) == "0") fmt.Println(solution(100, 0, [][]int{}) == "Impossible") }
12、简单四则计算
油价飞升的今天，我们尽量减少花费。我们出门旅游，有时候租车去旅游也是一种不错的方式。这次我们这次旅游是从「青海湖」到「景点 X」，景点 X 可以是「敦煌」、「月牙泉」等，线路的路径是唯一的，假设我们每走 1 km 消耗 1 L 的油，车油箱容量 400L。比如：如果「景点 X」是敦煌，我们在青海湖租车前油箱是 200L 的，在「景点 X」（敦煌）还车的时候也是 200L 的，路上有很多加油站，加油站在青海湖和「景点 X」的连线上。
输入格式
第 1 行表示「青海湖」到「景点 X」的距离，距离最远不超过 10000 km。 第 2 行表示接下来 N 行表示 N 个加油站（N 为正整数）。 接下来 N（1 <= N <= 100）行表示，每一个加油站情况。每一个加油站包括距离「景点 X」的距离 a km（0 <= a <= 10000），以及每升汽油的价格 b 元（0 <= b <= 2000），a 和 b 均为正整数。
输出格式
如果不能到达目的地「景点 X」，输出 Impossible。 如果能到达目的地「景点 X」，输出最小花费多少元。
输入样例： 500 4 100 1 200 30 400 40 300 20
输出样例： 4300
代码
▼go复制代码package main import ( "fmt" "math" "sort" ) func solution(distance, n int, gasStations [][]int) string { gasStations = append(gasStations, []int{distance}) sort.Slice(gasStations, func(i, j int) bool { return gasStations[i][0] < gasStations[j][0] }) dis := make([]int, n+1) dis[0] = gasStations[0][0] for i := 1; i <= n; i++ { dis[i] = gasStations[i][0] - gasStations[i-1][0] } // dp 数组初始化为一个非常大的值 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, 401) for j := range dp[i] { dp[i][j] = math.MaxInt32 } } dp[0][200] = 0 for i := 1; i <= n; i++ { if gasStations[i-1][0] == distance { n = i - 1 break } for j := 0; j <= 400; j++ { for k := 0; k <= 400; k++ { if j+dis[i-1]-k >= 0 && len(gasStations[i-1]) > 1 { dp[i][j] = min(dp[i][j], dp[i-1][k]+(j+dis[i-1]-k)*gasStations[i-1][1]) } } } } if n < 1 || 200+dis[n-1] < 0 || dp[n][200+dis[n-1]] == math.MaxInt32 { return "Impossible" } return fmt.Sprintf("%d", dp[n][200+dis[n-1]]) } func main() { // 测试用例 gasStations1 := [][]int{{100, 1}, {200, 30}, {400, 40}, {300, 20}} gasStations2 := [][]int{{100, 999}, {150, 888}, {200, 777}, {300, 999}, {400, 1009}, {450, 1019}, {500, 1399}} gasStations3 := [][]int{{101}, {100, 100}, {102, 1}} gasStations4 := [][]int{{34, 1}, {105, 9}, {9, 10}, {134, 66}, {215, 90}, {999, 1999}, {49, 0}, {10, 1999}, {200, 2}, {300, 500}, {12, 34}, {1, 23}, {46, 20}, {80, 12}, {1, 1999}, {90, 33}, {101, 23}, {34, 88}, {103, 0}, {1, 1}} fmt.Println(solution(500, 4, gasStations1) == "4300") fmt.Println(solution(500, 7, gasStations2) == "410700") fmt.Println(solution(500, 3, gasStations3) == "Impossible") fmt.Println(solution(100, 20, gasStations4) == "0") fmt.Println(solution(100, 0, [][]int{}) == "Impossible") }
13、及格如此简单
为了响应国家全面发展的响应，学校提供了“德”、“智”、“体”、“美”、“劳” 等多门课程供同学们选择学习。
每位同学必修 3 门课程，可选修其他 3 门及以上课程。
小 A 同学选了 n 门选修课程，马上要期末考核了，请你帮小 A 同学算一算，如果小 A 同学要及格的话，他所学所有课程的成绩共有多少种组合的方式。
注意：
- 同学的所有学习课程的平均分 >= 60 分 即为及格
- 每门课程满分 100 分，只有 20 道选择题，每题 5 分，答错 0 分，答对 5 分
- 成绩的总组合数对 202220222022 取模
输入
整数 n （3 <= n <= 1000）小 A 同学选修的课程数
输出
一个整数，表示小 A 同学所学课程能及格的成绩组合方式个数（对 202220222022 取模即可）
代码
▼go复制代码package main import ( "fmt" "strconv" ) const MOD int64 = 202220222022 func solution(n int) string { n += 3 old_dp := make([]int64, 101) old_dp[0] = 1 var new_dp []int64 for i := 1; i <= n; i++ { MaxScore := 100 * i new_dp = make([]int64, MaxScore+1) for j := 0; j <= MaxScore; j += 5 { for k := 0; k <= 100; k += 5 { if j-k <= (i-1)*100 && j-k >= 0 { if old_dp[j-k] > 0 { new_dp[j] = (new_dp[j] + old_dp[j-k]) % MOD } } else if j-k < 0 { break } } } old_dp = new_dp } var ans int64 = 0 for i := 60 * n; i <= 100 * n; i += 5 { ans = (new_dp[i] + ans) % MOD } return strconv.FormatInt(ans, 10) } func main() { // You can add more test cases here fmt.Println(solution(3) == "19195617") fmt.Println(solution(6) == "135464411082") fmt.Println(solution(49) == "174899025576") fmt.Println(solution(201) == "34269227409") fmt.Println(solution(888) == "194187156114") }
14、链表聚集交换
将一个链表通过交换位置的操作使链表中的 value 为 k 的节点都聚到一起，给出需要的最少交换次数。
输入描述
输入第一行为链表的长度，取值范围 1~1000
输入第二行为链表的节点，如 1 2 3 代表链表 1->2->3，每个节点 value 为整数，取值范围 0~10000
输入第三行为 k
示例
输入: 5 1,2,1,2,1 2
输出: 1
解释：只需要交换 1 次即可变成 2,2,1,1,1 或 1,2,2,1,1 或 1,1,2,2,1 或 1,1,1,2,2
输入: 5 0,0,1,0,0 1
输出: 0
解释：不需要操作
输入: 11 6,1,6,3,6,10,40,6,6,12,6 6
输出：3
解释：交换 3 次可变成 12,1,40,3,10,6,6,6,6,6,6
代码
▼go复制代码package main import ( "fmt" ) func solution(length int, linkedList []int, k int) int { // 首先统计链表中等于 k 的元素数量，确定窗口大小 countK := 0 for _, val := range linkedList { if val == k { countK++ } } // 如果没有等于 k 的元素，或者所有元素都等于 k，则不需要交换 if countK == 0 || countK == length { return 0 } // 初始化 'bad'，表示在当前窗口内不等于 k 的元素数量 bad := 0 for i := 0; i < countK; i++ { if linkedList[i] != k { bad++ } } // 最小交换次数初始化为第一个窗口的 'bad' 值 minSwaps := bad // 使用滑动窗口技术，窗口大小为 countK for i := 1; i <= length-countK; i++ { // 移出窗口的元素，如果不等于 k，减少 'bad' 计数 if linkedList[i-1] != k { bad-- } // 进入窗口的元素，如果不等于 k，增加 'bad' 计数 if linkedList[i+countK-1] != k { bad++ } // 更新最小交换次数 if bad < minSwaps { minSwaps = bad } } return minSwaps } func main() { fmt.Println(solution(5, []int{1, 2, 1, 2, 1}, 2) == 1) fmt.Println(solution(5, []int{0, 0, 1, 0, 0}, 1) == 0) fmt.Println(solution(11, []int{6, 1, 6, 3, 6, 10, 40, 6, 6, 12, 6}, 6) == 3) }
15、进制求和转换
给定两个二进制字符串，返回他们的和（用十进制字符串表示）。输入为非空字符串且只包含数字 1 和 0 ，请考虑大数问题。时间复杂度不要超过 O(n^2)，其中 n 是二进制的最大长度。
输入格式
每个样例只有一行，两个二进制字符串以英文逗号“,”分割
输出格式
输出十进制格式的两个二进制的和
输入样例：
101,110
输出样例：
11
数据范围：
每个二进制不超过 100 个字符，JavaScript 语言下请考虑大数的情况。
代码
▼go复制代码package main import ( "fmt" "strconv" ) func solution(binary1, binary2 string) string { s := []int{} t := 0 i, j := len(binary1)-1, len(binary2)-1 for i >= 0 || j >= 0 { var a, b int if i >= 0 { a = int(binary1[i] - '0') i-- } else { a = 0 } if j >= 0 { b = int(binary2[j] - '0') j-- } else { b = 0 } sum := a + b + t if sum == 3 { s = append(s, 1) t = 1 } else if sum == 2 { s = append(s, 0) t = 1 } else if sum == 1 { s = append(s, 1) t = 0 } else { s = append(s, 0) t = 0 } } if t == 1 { s = append(s, 1) } ans := 0 mi := 1 for _, it := range s { ans += it * mi mi *= 2 } return strconv.Itoa(ans) } func main() { // You can add more test cases here fmt.Println(solution("101", "110") == "11") fmt.Println(solution("111111", "10100") == "83") fmt.Println(solution("111010101001001011", "100010101001") == "242420") fmt.Println(solution("111010101001011", "10010101001") == "31220") }
写在最后
希望对大家有所帮助~
