怎么做网站跟域名,建德网站优化公司,网页制作教程零基础学会,网站建设广金手指六六十四文章目录 科大讯飞 0713找01不能出现太多其他 科大讯飞 0713
找01
牛牛拥有一个长度为 n 的01 串#xff0c;现在他想知道#xff0c;对于每个字符#xff0c;在它前面的最近的不同字符的下标是多少#xff1f;
输入描述
本题为多组测试数据#xff0c;第一行输入一个… 文章目录 科大讯飞 0713找01不能出现太多其他 科大讯飞 0713
找01
牛牛拥有一个长度为 n 的01 串现在他想知道对于每个字符在它前面的最近的不同字符的下标是多少
输入描述
本题为多组测试数据第一行输入一个正整数 T(1t100)代表测试数据组数。对于每组测试数据第一行输入一个正整数 n(1n1000)代表初始 01串的长度。第二行输入一个长度为 n的01 串代表初始字符串。
输出描述
对于每组测试数据一行输出 n 个整数 a1,a2,…,an其中 ai 代表初始字符串中第 i 个位置的字符前面最近的不同字符的下标是 ai特殊的如果前面不存在不同字符则输出 -1 表示不存在。
示例 1
输入
1
4
1101输出
-1 -1 2 3遍历字符串遇到01串变化的位置就更新索引并填充到结果中
package kedaxunfeiimport (bufiofmtos
)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 1kn105,1Ai109
输出描述
一行一个整数表示答案。如果不存在出现次数少于等于k次的数字输出-1
示例 1
输入
5 2
1 1 1 2 3输出
2用map记录每个数字出现的次数最后遍历map选值最小的
package kedaxunfeiimport (bufiofmtos
)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)
}
