科大訊飛 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)}