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

简单题提取不重复的整数

读取输入字符串：使用 fmt.Scan(&s) 读取用户输入的字符串 s。
初始化状态数组：定义一个布尔数组 st，用于记录每个数字字符是否已经出现过。
从右到左遍历字符串：使用 for 循环从字符串的最后一个字符开始向前遍历。
检查字符是否已出现：对于每个字符，检查它是否已经在 st 数组中标记为 true。
输出未出现过的字符：如果字符未出现过，则输出该字符，并在 st 数组中将对应位置标记为 true。

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	st := [10]bool{}
	for i := len(s) - 1; i >= 0; i-- {
		if !st[s[i]-'0'] {
			fmt.Printf("%c", s[i])
			st[s[i]-'0'] = true
		}
	}
}

中等题句子逆序

读取输入：使用 bufio.NewReader 从标准输入读取一行字符串。
- bufio.Reader.ReadString('\n') 适用于读取多行或者特殊字符输入的场景，读取直到 \n，包含换行符
去除换行符：使用 strings.TrimSpace 会去除字符串前后的空格和换行符，保证最终字符串没有换行。
分割字符串：使用 strings.Split 将字符串按空格分割成单词数组。
反转单词顺序：遍历单词数组，从最后一个单词开始，依次输出每个单词。

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	var line string
	reader := bufio.NewReader(os.Stdin)
	line, _ = reader.ReadString('\n')
	line = strings.TrimSpace(line)
	words := strings.Split(line, " ")
	for i := len(words) - 1; i >= 0; i-- {
		fmt.Printf("%s ", words[i])
	}
}

困难题迷宫问题

方案一：DFS

https://oi-wiki.org/graph/dfs/

DFS 中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

DFS 最显著的特征在于其 递归调用自身。

DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。

package main

import (
	"fmt"
	"strings"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([][]int, n)
	st := make([][]bool, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
		st[i] = make([]bool, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}

	dx, dy := []int{0, 0, 1, -1}, []int{1, -1, 0, 0}
	path := make([]string, 0)
    st[0][0] = true
	var dfs func(int, int)
	dfs = func(x, y int) {
		path = append(path, fmt.Sprintf("(%d,%d)", x, y))
		if x == n-1 && y == m-1 {
			fmt.Print(strings.Join(path, "\n"))
			return
		}
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == 0 && !st[xx][yy] {
				st[xx][yy] = true
				dfs(xx, yy)
				st[xx][yy] = false
			}
		}
		path = path[:len(path)-1]
	}
	dfs(0, 0)
}

方案二：BFS

https://oi-wiki.org/graph/bfs/

BFS 中文名是宽度优先搜索，也叫广度优先搜索。

所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

BFS要求输出路径，只需要将每一个位置（状态）的前一个位置（状态）存入pre数组中，然后根据终止的状态倒推回初始状态即可。

package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([][]int, n)
	st := make([][]bool, n)
	pre := make([][][2]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
		st[i] = make([]bool, m)
		pre[i] = make([][2]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}

	dx, dy := []int{0, 0, 1, -1}, []int{1, -1, 0, 0}

	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	st[0][0] = true
	for len(queue) > 0 {
		x, y := queue[0][0], queue[0][1]
		queue = queue[1:]
		if x == n-1 && y == m-1 {
			break
		}
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == 0 && !st[xx][yy] {
				queue = append(queue, [2]int{xx, yy})
				st[xx][yy] = true
				pre[xx][yy] = [2]int{x, y}
			}
		}
	}

	x, y := n-1, m-1
	path := make([]string, 0)
	for !(x == 0 && y == 0) {
		path = append(path, fmt.Sprintf("(%d,%d)", x, y))
		x, y = pre[x][y][0], pre[x][y][1]
	}
	path = append(path, "(0,0)")
	for i := len(path) - 1; i >= 0; i-- {
		fmt.Println(path[i])
	}
}

#牛客春招刷题训练营##牛客创作赏金赛#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了