宝石手串__牛客网

Java

牛客643664499号

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int count = in.nextInt();

int i = 1;

do { // 注意 while 处理多个 case

int num = in.nextInt();

String verifyStr = in.next();

verifyStr += verifyStr; // 模拟环形

Map<Character, Integer> map = new HashMap<>();

int minValue = verifyStr.length();

for (int j = 0 ; j < verifyStr.length(); j++) {

if (map.get(verifyStr.charAt(j)) != null) {

int distance = j - map.get(verifyStr.charAt(j)) - 1; // 相同字符间间隔字符数

if (distance + 1 != num) // 相同字符距离等于起始字符长度，则无效

minValue = Math.min(j - map.get(verifyStr.charAt(j)) - 1, minValue);

}

map.put(verifyStr.charAt(j), j);

}

System.out.println(minValue == verifyStr.length() ? -1 : minValue);

} while (i++ < count);

}

发表于 2025-11-27 00:11:15 回复(0)

Java

牛客281381469号

把原字符串再复制一份，模拟收尾相连的字符串，比如原字符串为ac，我们把它变为acac，
从头开始遍历字符串，用HashMap时刻记录各个元素最近出现的位置，求出距离最小值。
注意，如果遍历结束，距离最小值为字符串的长度 - 1，说明原字符串没有相同元素，返回-1。
否则返回距离的最小值。
import java.util.Scanner;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            int n = in.nextInt();
            in.nextLine();
            String s = in.nextLine();
            String str = s + s;
            Map<Character, Integer> map = new HashMap<>();
            char[] chars = str.toCharArray();
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < chars.length; j++) {
                if (map.containsKey(chars[j])) {
                    min = Math.min(min, j - map.get(chars[j]) - 1);
                }
                map.put(chars[j], j);
            }
            if (min == s.length() - 1) {
                System.out.println(-1);
            } else {
                System.out.println(min);
            }
        }
    }
}

发表于 2025-07-22 15:15:04 回复(0)

Java

正在卷的山羊很胖墩墩

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n=in.nextInt();

while(in.hasNext()){

int l=in.nextInt();

in.nextLine();

String[] arr = in.nextLine().split("");

HashMap<String,List<Integer>> map =new HashMap<>();

int res = arr.length;

for(int i=0;i<arr.length;i++){

if(!map.containsKey(arr[i])){

map.put(arr[i],new ArrayList<>());

map.get(arr[i]).add(i);

}else{

//求当前位与前一位相同字符的距离

int k1 = i - map.get(arr[i]).get(map.get(arr[i]).size()-1)-1;

//求当前位与第一位字符的距离（首尾相连）

int k2 = arr.length-1-i+map.get(arr[i]).get(0);

res=(k1<k2?k1:k2)<res?(k1<k2?k1:k2):res;

map.get(arr[i]).add(i);

}

if(res==arr.length){

res=-1;

}

System.out.println(res);

}

发表于 2025-04-22 12:57:57 回复(0)

Java

牛客430757235号

/* Map<Character,List<Integer>> 想过但居然真的可以实现！！！感谢D老师

一个一个比较也可以但是复杂度是O(宝石手串数量*单个手串数量中宝石数的2次方) 在用例5/20会过不去时间超了（单个宝石手串有50000个宝石离谱！！）但是用以下代码复杂度是O(宝石手串数量*单个手串数量中宝石数)

*/

import java.util.Scanner;

import java.util.Map;

import java.util.HashMap;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int q = in.nextInt();

in.nextLine();

while(q-- >0) {

int w = in.nextInt();

in.nextLine();

String b = in.nextLine();

if(w==2){

System.out.println(-1);

continue;

}

Map<Character,List<Integer>> c = new HashMap<>();

for(int i = 0;i<w;i++){

char d = b.charAt(i);

if(!c.containsKey(d)){

c.put(d,new ArrayList<>());

}

c.get(d).add(i);

}//统计了所有有重复字符的位置并且用列表存起来了

//剔除2种情况 1.手串长度为2已经剔除了 2.没有重复的字符所有都唯一存在输出-1 这是list的列表长度为1

int min = Integer.MAX_VALUE;

for(List<Integer> e:c.values()){

if(e.size()<2){

continue;

}

Collections.sort(e);

List<Integer> f = new ArrayList<>(e);

f.add(f.get(0)+w);

for(int i = 0;i<f.size()-1;i++){

int x = f.get(i);

int y = f.get(i+1);

int z = y-x;

min = Math.min(min,Math.min(z,w-z));

}

if(min == Integer.MAX_VALUE){System.out.println(-1);

}else {

System.out.println(min-1);//输出为间隔字符这里min要-1

}

发表于 2025-03-17 16:05:35 回复(0)

宝石手串

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题