牛客春招刷题训练营-2025.3.11题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 字符串分隔

1. 用0填充字符串以确保其长度是8的倍数。
2. 遍历字符串，每次取8个字符并打印出来。循环的步长为8，因此每次迭代都会打印下一个8字符的子串。

package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanln(&s)
	l := len(s)
	if l%8 != 0 {
		for i := 0; i < 8-l%8; i++ {
			s += "0"
		}
	}
	// fmt.Println(s)
	for i := 0; i < len(s); i += 8 {
		fmt.Println(s[i : i+8])
	}
}

中等题 质数因子

n中最多只含有一个大于根号n的因子

反证法: 如果有两个大于根号n的因子，则相乘会大于n

时间复杂度：

1. 在 2 到 范围枚举
2. 遇到质因子就除净并且输出质因子
3. 最后如果n > 1，说明这就是那个大于根号n的质因子

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	for i := 2; i <= n/i; i++ {
		for n%i == 0 {
			n /= i
			fmt.Printf("%d ", i)
		}
	}
	if n > 1 {
		fmt.Printf("%d", n)
	}
}

困难题 合唱队

最少需要出列多少位同学 ==> 最多保留多少位同学

合唱队形要求实际是求第 i 位同学为结尾的最长上升子序列 + 第 i 位同学为开头最长下降子序列（逆序版的最长上升子序列）

因为在这两个子序列中第 i 位同学被计算了两次，所以要记得减1

计算最长上升子序列（LIS）有两种方案：

1. 动态规划（DP） 时间复杂度为：

   ​ • 定义 dp[i] 表示 以 nums[i] 结尾的最长上升子序列的长度。

   ​ • 递推关系：dp[i] = max(dp[j] + 1), j < i 且 h[j] < h[i]

   也就是说，遍历 h[0] 到 h[i-1]，找到所有比 h[i] 小的元素 h[j]，然后 dp[i] 取它们的最大 dp[j] + 1。

   package main
   
   import (
   	"fmt"
   )
   
   func max(a, b int) int {
   	if a > b {
   		return a
   	}
   	return b
   }
   
   func main() {
   	var n int
   	fmt.Scan(&n)
   	h := make([]int, n)
   	for i := range h {
   		fmt.Scan(&h[i])
   	}
   	
   	l := make([]int, n)
   	for i := range l {
   		l[i] = 1
   	}
   	
   	for i := 1; i < n; i++ {
   		for j := 0; j < i; j++ {
   			if h[i] > h[j] {
   				l[i] = max(l[i], l[j]+1)
   			}
   		}
   	}
   	
   	r := make([]int, n)
   	for i := range r {
   		r[i] = 1
   	}
   	for i := n - 1; i >= 0; i-- {
   		for j := n - 1; j > i; j-- {
   			if h[i] > h[j] {
   				r[i] = max(r[i], r[j]+1)
   			}
   		}
   	}
   
   	mx := 0
   	for i := range h {
   		mx = max(mx, l[i]+r[i]-1)
   	}
   	fmt.Println(n - mx)
   }
   
   

2. 二分查找+贪心 时间复杂度为：

   思路

   利用 贪心+二分查找 维护一个 “最小结尾递增子序列” 的数组 sub，该数组 不一定是最终的 LIS，但长度是对的。

   步骤

   ​ 1. 用 sub 数组来维护当前的 LIS（但不一定是最终 LIS）。

   ​ 2. 对于 h[i]：

   ​ • 如果 h[i] 大于 sub 的最后一个元素，直接追加到 sub 末尾（扩大 LIS）。

   ​ • 如果 h[i] 不能直接接到 sub 末尾，用 二分查找 找到 sub 中第一个大于等于 nums[i] 的位置 替换 这个值（保持 sub 的最小结尾单调递增）。

   3. sub 数组的 长度 就是 LIS 的长度。

      package main
      
      import (
      	"fmt"
      	"sort"
      )
      
      func max(a, b int) int {
      	if a > b {
      		return a
      	}
      	return b
      }
      
      func main() {
      	var n int
      	fmt.Scan(&n)
      	h := make([]int, n)
      	for i := range h {
      		fmt.Scan(&h[i])
      	}
      
      	sub := make([]int, 0)
      	l := make([]int, n)
      	for i, x := range h {
      		idx := sort.SearchInts(sub, x)
      		if idx == len(sub) {
      			sub = append(sub, x)
      		} else {
      			sub[idx] = x
      		}
      		l[i] = len(sub)
      	}
      
      	sub = make([]int, 0)
      	r := make([]int, n)
      	for i := n - 1; i >= 0; i-- {
      		x := h[i]
      		idx := sort.SearchInts(sub, x)
      		if idx == len(sub) {
      			sub = append(sub, x)
      		} else {
      			sub[idx] = x
      		}
      		r[i] = len(sub)
      	}
      
      	mx := 0
      	for i := range h {
      		mx = max(mx, l[i]+r[i]-1)
      	}
      	fmt.Println(n - mx)
      }