枚举-油漆房子

题目

image-20240113101111678

分析

核心思想是枚举

首先利用set记录每一种颜色

然后依次从set取出一种颜色作为targetColor

遍历房子，如果当前房子的颜色和targetColor不相同，就以当前房子为起点，往后长度为k的区间都涂成targetColor，并且需要的天数递增1

否则就一直向下遍历直到所有房子遍历完

java中HashSet使用

创建

import java.util.HashSet;
HashSet<Integer> set = new HashSet<Integer>();
//HashSet<对象名> 集合名 = new HashSet<Integer>();

放入数据

set.add(data);

遍历：只能用增强型for循环和迭代器

//迭代器
import java.util.Iterator;
for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext();) {
    Integer i = iterator.next();
}

代码

import java.util.Scanner;
import java.util.HashSet;
import java.util.Iterator;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < t; i++) {
            int n = input.nextInt();
            int k = input.nextInt();
            set.clear();
            int[] house = new int[n];
            //存储所有房子的颜色并记录颜色的种类
            for(int j = 0; j < n; j++) {
                int data = input.nextInt();
                house[j] = data;
                set.add(data);
            }
            int minCount = n;
            //从集合中选取一种颜色
            for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext();) {
                Integer nowColor = (Integer)iterator.next();
                int count = 0;
                //遍历房子颜色与当前选取的颜色比较
                for(int x = 0; x < n;) {
                    //如果当前房子颜色与当前选取的颜色不同
                    if(house[x] != nowColor) {
                        x = x + k;
                        count++;
                    } else {
                        x++;
                    }   //if
                }   //for
                if(count < minCount) minCount = count;  //if
            }   //for
            System.out.println(minCount);
        }   //for
        input.close();
    }
}