字节青训营入营考核部分题解

​
题库链接：https://juejin.cn/problemset?utm_source=school&utm_medium=youthcamp&utm_campaign=examine

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 所需最小步数。

输入样例

12 6
34 45
50 30

输出样例

4
6
8

解题思路

• 从x到y的距离为s := abs(x-y)
• 由于每次的步数只能是上次基础上的+1、-1或0。所以，步数的过程由三部分组成：
  • 1~n项和：n*(n+1)/2
  • 前1~n-1项和：n*(n-1)/2
  • i个n
  • 0个或1个1~n之间的数x
• 整理为公式：n^2 = s - i*n - x
• ans = 2*n-1+i+(0|1)

代码

func solution1(xPosition int, yPosition int) int {s := int(math.Abs(float64(yPosition - xPosition)))n := math.Sqrt(float64(s))ans := 2*int(n) - 1// 如果s不为完全平方数if n > float64(int(n)) {res := s - int(n)*int(n)if res%int(n) == 0 {ans += res / int(n)} else {ans += res/int(n) + 1}return ans} else {return ans}
}

2. 找出单独的数

问题描述

有一堆数字，除了一个数字，其它的数字都是成对出现。班上的每个同学拿一个数字，正好将这些数字全部拿完，问如何快速找到拿了单独数字的同学？

输入格式

• 空格分隔输入所有的数字

输出格式

• 单独的那个数字

输入样例(1)

1 1 2 2 3 3 4 5 5

输出样例(1)

4

输入样例(2)

0 1 0 1 2

输出样例(2)

2

解题思路

• 序列中只有一个数是单独的，其余两两配对。
• 考虑异或运算的恒等律和归零率。任何数与自身异或，结果为0；任何书与0异或，结果为其本身。

代码

func solution4(inp []int) int {// Edit your code hereans := 0for _, v := range inp {ans ^= v}return ans
}

3. 字符串最短循环子串

问题描述

• 输入一个字符串，判断其是否完全循环，若是循环的，输出最短的循环子串，否则输出空""
• 如输入 abababab，输出 ab；输入 ab 则输出 ""

输入格式

• 合法字符串 如 abcabcabcabc aaa

输出格式

• 最短的循环子串 "abc" "a"

输入样例

• "abcabcabcabc"

输出样例

• "abc"

数据范围

测试数据集

解题思路

• tag为简单题，应该不是考kmp算法吧，直接双for暴力。
• 外层循环遍历模板串，若原len(inp)%len(s) != 0则跳过此串。
• 内层循环遍历原串，对模板串进行匹配，若匹配失败则退出循环，考虑下一个模板串。

代码

func solution2(inp string) string {if len(inp) < 2 {return ""}for i := 0; i < len(inp); i++ {s := inp[:i+1]if len(inp)%len(s) != 0 {continue}flag := falsefor j := 0; j < len(inp)-len(s); j += len(s) {if s != inp[j:j+len(s)] {flag = truebreak}}if flag {continue}return s}return ""
}

4. 找出最长神奇序列

问题描述

小明是一个中学生，今天他刚刚学习了数列。他在纸上写了一个长度为 n 的正整数序列，$a_0,a_1,\dots ,a_{n-1}$。这个数列里面只有 1 和 0，我们将 1 和 0 没有重复跟随并且至少由 3 个数组成的数列的数列称之为「神奇数列」。比如 10101 是一个神奇数列，1011 不是一个神奇数列。他想知道这个序列里面最长的「神奇数列」是哪个，你可以帮帮他吗？

输入格式

• 一行连续的数 s，只有 0 和 1

输出格式

• 一行数

输入样例

0101011101

输出样例

010101

数据范围

• $1<s.length\le 5\times 10^4$

解题思路

• 若len(inp) < 3，则return ""。
• 遍历该串，使用count来计数，若出现重复则将count = 0。
• 最终求得count的最大值就是ans。

代码

func solution3(inp string) string {if len(inp) < 3 {return ""}// Edit your code heremaxn := 0count := 0var ans stringfor i := 1; i < len(inp); i++ {if inp[i] != inp[i-1] {count++} else {if count > maxn {maxn = countans = inp[i-count-1 : i]count = 0}}}return ans
}

总结

目前，此网站OJ还无法进行提交代码，题解样例是过了的。如有问题，可以在评论区提问哦~
​