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 kedaxunfei

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

func Find01Main() {
	Reader := bufio.NewReader(os.Stdin)
	Writer := bufio.NewWriter(os.Stdout)
	defer Writer.Flush()
	var n int
	fmt.Fscanf(Reader, "%d\n", &n)
	for i := 0; i < n; i++ {
		var strSize int
		var str string
		fmt.Fscanf(Reader, "%d\n", &strSize)
		fmt.Fscanf(Reader, "%s\n", &str)
		var result []int
		var res = -1
		for 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 kedaxunfei

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

func NotExistTooMuch() {
	Reader := bufio.NewReader(os.Stdin)
	Writer := bufio.NewWriter(os.Stdout)
	var n, k int
	defer 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 int
	var maxRes = 100000
	for key, value := range maps {

		if value <= k {
			if key < maxRes {
				maxRes = key
				res = key
			}
		}
	}
	fmt.Fprintf(Writer, "%d", res)

}