25秋招面试算法题 （Go版本）

科大讯飞 0713

找01

牛牛拥有一个长度为 n 的01 串，现在他想知道，对于每个字符，在它前面的最近的不同字符的下标是多少？

输入描述

本题为多组测试数据，第一行输入一个正整数 T(1<=t<=100)，代表测试数据组数。对于每组测试数据，第一行输入一个正整数 n(1<=n<=1000)，代表初始 01串的长度。第二行输入一个长度为 n的01 串，代表初始字符串。

输出描述

对于每组测试数据，一行输出 n 个整数 a1,a2,…,an，其中 ai 代表初始字符串中第 i 个位置的字符前面，最近的不同字符的下标是 ai，特殊的，如果前面不存在不同字符，则输出 -1 表示不存在。

示例 1

输入

1
4
1101

输出

-1 -1 2 3

遍历字符串，遇到01串变化的位置就更新索引，并填充到结果中

package kedaxunfeiimport ("bufio""fmt""os"
)func Find01Main() {Reader := bufio.NewReader(os.Stdin)Writer := bufio.NewWriter(os.Stdout)defer Writer.Flush()var n intfmt.Fscanf(Reader, "%d\n", &n)for i := 0; i < n; i++ {var strSize intvar str stringfmt.Fscanf(Reader, "%d\n", &strSize)fmt.Fscanf(Reader, "%s\n", &str)var result []intvar res = -1for index, _ := range str {if index == 0 {result = append(result, res)continue}if str[index-1] != str[index] {res = index}result = append(result, res)}fmt.Println(result)}}

不能出现太多

给定n个数字A1,A2,…An，请求出这些数字中出现次数小于等于k的最小的数。

输入描述

第一行正整数n,k，接下来一行n个正整数，第i个表示Ai 1<=k<=n<=10^5,1<=Ai<=109

输出描述

一行一个整数，表示答案。如果不存在出现次数少于等于k次的数字，输出-1

示例 1

输入

5 2
1 1 1 2 3

输出

2

用map记录每个数字出现的次数，最后遍历map选值最小的

package kedaxunfeiimport ("bufio""fmt""os"
)func NotExistTooMuch() {Reader := bufio.NewReader(os.Stdin)Writer := bufio.NewWriter(os.Stdout)var n, k intdefer Writer.Flush()fmt.Fscanf(Reader, "%d %d\n", &n, &k)nums := make([]int, n)maps := make(map[int]int)for i := 0; i < n; i++ {fmt.Fscanf(Reader, "%d", &nums[i])if _, ok := maps[nums[i]]; ok {maps[nums[i]]++} else {maps[nums[i]] = 1}}var res intvar maxRes = 100000for key, value := range maps {if value <= k {if key < maxRes {maxRes = keyres = key}}}fmt.Fprintf(Writer, "%d", res)}

其他

LCA
最近公共祖先（LCA, Lowest Common Ancestor）是树算法中的经典问题之一。给定一个二叉树和树中的两个节点，LCA 是指这两个节点的最深的公共祖先节点。

package mainimport "fmt"// TreeNode 定义二叉树的节点结构
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// lowestCommonAncestor 寻找最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil || root == p || root == q {return root}left := lowestCommonAncestor(root.Left, p, q)right := lowestCommonAncestor(root.Right, p, q)if left != nil && right != nil {return root}if left != nil {return left}return right
}// 辅助函数：构建二叉树
func buildTree() *TreeNode {root := &TreeNode{Val: 3}root.Left = &TreeNode{Val: 5}root.Right = &TreeNode{Val: 1}root.Left.Left = &TreeNode{Val: 6}root.Left.Right = &TreeNode{Val: 2}root.Right.Left = &TreeNode{Val: 0}root.Right.Right = &TreeNode{Val: 8}root.Left.Right.Left = &TreeNode{Val: 7}root.Left.Right.Right = &TreeNode{Val: 4}return root
}func main() {root := buildTree()p := root.Left       // 节点5q := root.Left.Right // 节点2ancestor := lowestCommonAncestor(root, p, q)fmt.Printf("最近公共祖先是: %d\n", ancestor.Val)
}