微信小程序模板网站百度人工客服在线咨询电话
题库链接：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
- 1~n项和：
- 整理为公式：
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则输出""
输入格式
- 合法字符串 如
abcabcabcabcaaa
输出格式
- 最短的循环子串
"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 , … , a n − 1 a_0,a_1,\ldots,a_{n-1} a0,a1,…,an−1。这个数列里面只有 1 和 0，我们将 1 和 0 没有重复跟随并且至少由 3 个数组成的数列的数列称之为「神奇数列」。比如 10101 是一个神奇数列，1011 不是一个神奇数列。他想知道这个序列里面最长的「神奇数列」是哪个，你可以帮帮他吗？
输入格式
- 一行连续的数
s，只有0和1
输出格式
- 一行数
输入样例
0101011101
输出样例
010101
数据范围
- 1 < s . l e n g t h ≤ 5 × 1 0 4 1 < s.length \leq 5 \times 10^4 1<s.length≤5×104
解题思路
- 若
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还无法进行提交代码，题解样例是过了的。如有问题，可以在评论区提问哦~