2024字节青训营入营考核

发表于 分类于 ， 阅读次数：
神秘字节青训营和ta的算法考核，虽然没啥大用

想学前端就报了下，反正一大堆原题随便写写复健了
都是用go写的，严格来说没那么算法()
加上题目难度很神秘，感觉是字节在用来测试代码平台(什么ai时代下的牛马)
做完要求的就跑路了

简单

计算从位置 x 到 y 的最少步数

问题描述
小F正在进行一个 AB 实验，需要从整数位置 x 移动到整数位置 y。每一步可以将当前位置增加或减少，且每步的增加或减少的值必须是连续的整数（即每步的移动范围是上一步的 -1，+0 或 +1）。首末两步的步长必须是 1。求从 x 到 y 的最少步数。

输入描述 输入包含两个整数 x 和 y，表示起始位置和目标位置。

思路

由题意可得，最少步数就是找出\(|x-y|\)里最长的一段上升子序列，再倒序一下，然后取最大值处理下剩余步，剩下的差值必然可以分解为若干个最大步数与一个比最大值小一点的数
设\(\displaystyle\sum_{i=0}^n\)为\(S\)，\(|x-y|\)为\(C\)
那么只用找出满足\(S+S-n+(C-2S+n)\bmod n+(C-2S+n)\mid n=C\)的\(n\)即可

伪代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
c := int(math.Abs(float64(xPosition) - float64(yPosition)))
if c < 4 {
	return c
}
count, now := 0, 0
for i := 1; ; i++ {
	count += i
	if (2*count - i) > c {
		count -= i
		break
	}
	now = i
}
ans := 2*now - 1
if (c-2*count+now)%now != 0 {
	ans++
}
ans += (c - 2*count + now) / now
return ans

寻找独特数字卡片

问题描述
在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求：

设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。 尽量减少额外空间的使用，以体现你的算法优化能力。

思路

map秒了 

1
2
3
4
5
6
7
8
9
10
11
card := make(map[int]int)
for _,v := range(inp) {
	card[v] += 1
	// fmt.Println(card[i],i)
}
for k,v := range(card){
	// fmt.Println(k)
	if v == 1{
		return k
	}
}

数字字符串格式化

问题描述
小M在工作时遇到了一个问题，他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式，并且保留小数部分。小M还发现，有时候输入的数字字符串前面会有无用的 0，这些也需要精简掉。请你帮助小M编写程序，完成这个任务。

思路

strings就行 

1
2
3
4
5
6
7
8
9
s = strings.TrimLeft(s, "0")
n := strings.Index(s,".")
if n == -1 {
	n = len(s)
}
for k := n - 3; k > 0; k -= 3 {
	s = s[:k] + "," + s[k:]
}
return s

小C的排列询问

问题描述
小C拿到了一个排列，她想知道在这个排列中，元素x和y是否是相邻的。排列是一个长度为n的数组，其中每个数字从1到n恰好出现一次。 你的任务是判断在给定的排列中，x和y是否是相邻的。

思路
大模拟

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
if n < 2 {
		return false
	}
	for k, v := range a {
		if v == x {
			if k == 0 {
				if a[k+1] == y {
					return true
				} else {
					return false
				}
			} else if k == len(a)-1 {
				if a[k-1] == y {
					return true
				} else {
					return false
				}
			} else {
				if a[k-1] == y || a[k+1] == y {
					return true
				} else {
					return false
				}
			}

		}
	}
	return false

找出整型数组中占比超过一半的数

问题描述
小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

思路
遍历 

1
2
3
4
5
6
7
mi := make(map[int]int)
for _,i := range array {
	mi[i]++
	if mi[i] > len(array)/2 {
		return i
	}
}

小F的永久代币卡回本计划

问题描述
小F最近迷上了玩一款游戏，她面前有一个永久代币卡的购买机会。该卡片的价格为 a 勾玉，每天登录游戏可以返还 b 勾玉。小F想知道她至少需要登录多少天，才能让购买的永久代币卡回本。

思路
神秘难度 

1
2
3
4
5
ans := a/b 
if a%b != 0 {
  ans +=1
}
return ans

构造特定数组的逆序拼接

问题描述
小U得到了一个数字n，他的任务是构造一个特定数组。这个数组的构造规则是：对于每个i从1到n，将数字n到i逆序拼接，直到i等于n为止。最终，输出这个拼接后的数组。

思路
神秘金字塔 

1
2
3
4
5
6
7
var s []int
for i := 1; i <= n; i++ {
	for j := n; j >= i; j-- {
		s = append(s, j)
	}
}
return s

比赛配对问题

问题描述
算瑞士轮

思路

1
2
3
4
5
6
7
8
9
ans := 0
for n != 1 {
	ans += n / 2
	if n%2 != 0 {
		n += 1
	}
	n /= 2
}
return ans

小U的数字插入问题

问题描述
小U手中有两个数字 a 和 b。第一个数字是一个任意的正整数，而第二个数字是一个0到9之间的整数。
她的任务是将第二个数字 b 插入到第一个数字 a 的某个位置，以形成一个最大的可能数字。

思路
找到第一个比b小的位置插进去就好了 

1
2
3
4
5
6
7
8
9
10
11
12
13
sa := strconv.Itoa(a)
sb := strconv.Itoa(b)
for k, _ := range sa {
	if sb[0] > sa[k] {
		sa = sa[:k] + sb + sa[k:]
		break
	}
}
   if sa == strconv.Itoa(a) {
       sa += sb
   }
ans, _ := strconv.Atoi(sa)
return ans

组成字符串ku的最大次数

问题描述
给定一个字符串s，该字符串中只包含英文大小写字母。
你需要计算从字符串中最多能组成多少个字符串 "ku"。每次可以随机从字符串中选一个字符，并且选中的字符不能再使用。
字符串中的字符大小写可以忽略，即大写和小写字母视为相同。

思路
转下大小写用strings秒了

1
2
s = strings.ToLower(s)
return min(strings.Count(s,"k"),strings.Count(s,"u"))

中等

超市里的货物架调整

问题描述
在一个超市里，有一个包含n个格子的货物架，每个格子中放有一种商品，商品用小写字母 a 到 z 表示。
当顾客进入超市时，他们会依次从第一个格子查找到第n个格子，寻找自己想要购买的商品。
如果在某个格子中找到该商品，顾客就会购买它并离开；如果中途遇到一个空格子，或查找完所有格子还没有找到想要的商品，顾客也会离开。

作为超市管理员，你可以在顾客到来之前重新调整商品的顺序，以便尽可能多地出售商品。当第一个顾客进入后，商品位置不能再调整。你需要计算在最优调整下，最多可以卖出多少件商品。

思路

因为遇到空格子也会离开，所以每件商品最多被购买一次(因为第二次来会先遇到空的)，map存商品然后遍历顾客置0即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
good := make(map[byte]int)
for i := 0; i < n; i++ {
	good[s[i]] = 1
}
count := 0
for i := 0; i < m; i++ {
	if good[c[i]] == 1 {
		count++
		good[c[i]] = 0
	} else {
		return count
	}
}
return count

观光景点组合得分问题

问题描述
一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，也就是两者评分之和减去它们之间的距离。 小R想知道，在哪种情况下能够获得观光景点组合的最高得分。

思路
贪心 

1
2
3
4
5
6
7
8
9
10
11
12
13
max := func(a, b int) int {
	if a > b {
		return a
	}
	return b
}
count := 0
for i, v := range values {
	for j := i + 1; j < len(values); j++ {
		count = max(count, values[j]+v+i-j)
	}
}
return count

数组元素之和最小化

问题描述
小C希望构造一个包含n个元素的数组，且满足以下条件：

  • 数组中的所有元素两两不同。
  • 数组所有元素的最大公约数为 k。
  • 数组元素之和尽可能小。 任务是输出该数组元素之和的最小值。

思路

谜底写在谜面上了 输出\(\displaystyle\sum_{i=0}^n*k\)即可

最少前缀操作问题

问题描述
小U和小R有两个字符串，分别是S和T，现在小U需要通过对S进行若干次操作，使其变成T的一个前缀。
操作可以是修改S的某一个字符，或者删除S末尾的字符。现在你需要帮助小U计算出，最少需要多少次操作才能让S变成T的前缀。

思路

因为只能从最后面删，所以直接遍历更改就好了，先判断下需不需要删 

1
2
3
4
5
6
7
8
9
10
11
12
ans := 0
n := len(S)
if len(S) > len(T) {
	ans = len(S) - len(T)
	n = len(T)
}
for i := 0; i < n; i++ {
	if S[i] != T[i] {
		ans++
	}
}
return ans

环形数组中的最大贡献值

问题描述
小S希望找到一对下标，使得它们的贡献值尽可能大。环形数组的特点是最左和最右的元素也是相邻的。你需要帮助她找到最大贡献值。

思路

和前面那题一样，加个取最小值就好了 

1
2
3
4
5
6
7
ans := 0
for i := 0; i < n; i++ {
	for j := i+1; j < n; j++ {
		ans = max(ans, (a[i]+a[j])*min((j-i), (n-j+i)))
	}
}
return ans

困难

最大UCC子串计算

问题描述
小S有一个由字符 'U' 和 'C' 组成的字符串S，并希望在编辑距离不超过给定值m的条件下，尽可能多地在字符串中找到 "UCC" 子串。

编辑距离定义为将字符串S转化为其他字符串时所需的最少编辑操作次数。允许的每次编辑操作是插入、删除或替换单个字符。你需要计算在给定的编辑距离限制m下，能够包含最多 "UCC" 子串的字符串可能包含多少个这样的子串。

例如，对于字符串"UCUUCCCCC"和编辑距离限制m = 3，可以通过编辑字符串生成最多包含3个"UCC"子串的序列。

思路

神秘大模拟啊
遍历一下字符串分别找UCC,UC,CC,U,C就好了，最少步数就从前往后减，剩下的就全组UCC
卡最久的还是在debug go的range上

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
s = strings.ToUpper(s)
ucc, uc, cc, u, c := 0, 0, 0, 0, 0
for k := 0; k < len(s); k++ {
	if s[k] == 'U' {
		if k == len(s)-1 {
			u++
		} else if k+1 == len(s)-1 {
			if s[k+1] == 'U' {
				u++
			} else {
				uc++
				break
			}
		} else {
			if s[k+1] == 'U' {
				u++
			} else if s[k+2] == 'C' {
				ucc++
				k = k + 2
			} else {
				uc++
				k = k + 1
			}
		}
	} else {
		if k == len(s)-1 {
			c++
		} else if k+1 == len(s)-1 {
			if s[k+1] == 'U' {
				c++
			} else {
				cc++
				break
			}
		} else {
			if s[k+1] == 'U' {
				c++
			} else {
				cc++
				k = k + 1
			}
		}
	}
}
ans := ucc
if m-uc > 0 {
	ans += uc
	m -= uc
} else {
	ans += m
	return ans
}
if m-cc > 0 {
	ans += cc
	m -= cc
} else {
	ans += m
	return ans
}
if m-2*u > 0 {
	ans += u
	m -= 2 * u
} else {
	ans += m / 2
	return ans
}
if m-2*c > 0 {
	ans += c
	m -= 2 * c
} else {
	ans += m / 2
	return ans
}
ans += m / 3
// fmt.Println(ucc, uc, cc, u, c)
return ans // Placeholder