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

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

简单题 字符串加密

1. 读取输入：从标准输入读取两个字符串 s 和 t。
2. 初始化映射：使用两个 map，一个 mp 用于记录 s 中出现的字符，另一个 dict 用于存储字符映射关系。
3. 构建映射：
   • 遍历字符串 s，将每个字符添加到 mp 中，并在 dict 中建立从 a 开始的映射关系。
   • 遍历 a 到 z 的所有字符，将不在 s 中的字符添加到 mp 中，并在 dict 中建立从 a 开始的映射关系。
4. 输出结果：遍历字符串 t，根据 dict 中的映射关系输出对应的字符。

package main

import "fmt"

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	mp := make(map[rune]struct{})
	dict := make(map[rune]rune)

	for _, c := range s {
		if _, ok := mp[c]; !ok {
			mp[c] = struct{}{}
			dict[rune('a'+len(dict))] = c
		}
	}
	for c := 'a'; c <= 'z'; c++ {
		if _, ok := mp[c]; !ok {
			mp[c] = struct{}{}
			dict[rune('a'+len(dict))] = c
		}
	}
	for _, c := range t {
		fmt.Printf("%c", dict[c])
	}
}

中等题 从单向链表中删除指定值的节点

1. 读取输入：首先读取链表的节点数 n，然后读取链表的头节点的值。
2. 构建链表：通过循环读取剩余的节点信息，每次读取新节点的值 a 和前驱节点的值 b，然后创建新节点并更新前驱节点的 next 指针。为了方便查找前驱节点，使用一个映射 map[int]*Node 来存储每个节点的值和对应的节点指针。
3. 删除节点：读取要删除的节点值 k，然后在链表中找到该节点并删除它。如果要删除的是头节点，则直接更新头节点为下一个节点；否则，遍历链表找到要删除的节点的前一个节点，并更新其 next 指针。
4. 输出链表：遍历链表并输出每个节点的值。

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func main() {
	var n int
	fmt.Scan(&n)
	mp := make(map[int]*Node)
	head := &Node{value: 0, next: nil}
	fmt.Scan(&head.value)
	mp[head.value] = head
	for i := 1; i < n; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		node := &Node{value: a, next: mp[b].next}
		mp[a] = node
		mp[b].next = node
	}

	var k int
	fmt.Scan(&k)
	if k == head.value {
		head = head.next
	} else {
		pre := head
		for pre != nil && pre.next.value != k {
			pre = pre.next
		}
		if pre != nil {
			pre.next = pre.next.next
		}
	}

	for node := head; node != nil; node = node.next {
		fmt.Printf("%d ", node.value)
	}
}

困难题 走方格的方案数

做法：动态规划

1. 初始化二维数组：创建一个二维数组 dp，其中 dp[i][j] 表示从起点 (0,0) 到达位置 (i,j) 的路径数。

2. 边界条件：

   • 如果在起始点（i == 0 && j == 0）， 初始化 dp[0][0] 的方案数为一。

   • 如果在第一行（i == 0），那么到达 dp[0][j] 的路径数只有一种，即从左边一个格子过来。

   • 如果在第一列（j == 0），那么到达 dp[i][0] 的路径数也只有一种，即从上面一个格子过来。

3. 状态转移方程：

   • 对于其他位置 (i,j)，可以从上面一个格子 (i-1,j) 或左边一个格子 (i,j-1) 过来，因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

4. 输出结果：最终 dp[n][m] 即为从起点到终点的路径数。

这个算法的时间复杂度是 O(n*m)，空间复杂度也是 O(n*m)。

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = 1
			} else if i == 0 {
				dp[i][j] = dp[i][j-1]
			} else if j == 0 {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	fmt.Println(dp[n][m])
}