題目
給定一個字串str，只由‘X’和‘.’兩種字符構成，‘X’表示墻，不能放燈，也不需要點亮，‘.’表示居民點，可以放燈，需要點亮，如果燈放在i位置，可以讓i-1， i和i+1三個位置被點亮，回傳如果點亮str中所有需要點亮的位置，至少需要幾盞燈，
package com.harrison.class09;
import java.util.HashSet;
public class Code03_Light {
// 方法一：貪心
public static int minLight1(String road) {
char[] str = road.toCharArray();
int index = 0;
int lights = 0;
while (index < str.length) {// 一旦越界，說明都已經決定好了，回傳最少的燈數
if (str[index] == 'X') {// i位置是X，直接去i++做決定
index++;
} else {// i位置是點 分情況討論
lights++;
if (index + 1 == str.length) {// 不需要放燈了
break;
}
if (str[index + 1] == 'X') {// i+1位置是X，必須在i位置放燈，然后去i+2位置做決定
index = index + 2;
} else {// i+1位置是. 不管i+2位置是X還是. 都在i+1位置放燈，然后去i+3位置做決定
index = index + 3;
}
}
}
return lights;
}
// str[index....]位置，自由選擇放燈還是不放燈
// str[0..index-1]位置呢？已經做完決定了，那些放了燈的位置，存在lights里
// 要求選出能照亮所有.的方案，并且在這些有效的方案中，回傳最少需要幾個燈
public static int process2(char[] str, int index, HashSet<Integer> lights) {
if (index == str.length) {// 結束的時候
for (int i = 0; i < str.length; i++) {
if (str[i] != 'X') {// 如果當前位置是點的話
if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
return Integer.MAX_VALUE;
}
}
}
return lights.size();
} else {
// str還沒結束
// i位置無論是'X'還是'.'，都有一個選擇，那就是不放燈
// no 當前i位置沒有放燈，回傳后續的最好燈數
int no = process2(str, index + 1, lights);
int yes = Integer.MAX_VALUE;// yes 只有'.'才會變
if (str[index] == '.') {
lights.add(index);
yes = process2(str, index + 1, lights);
lights.remove(index);
}
return Math.min(no, yes);
}
}
// 方法二：暴力解
public static int minLight2(String road) {
if (road == null || road.length() == 0) {
return 0;
}
return process2(road.toCharArray(), 0, new HashSet<>());
}
public static String generateRandomString(int len) {
char[] ans = new char[(int) (Math.random() * (len + 1))];
for (int i = 0; i < ans.length; i++) {
ans[i] = Math.random() < 0.5 ? 'X' : '.';
}
return String.valueOf(ans);
}
public static void main(String[] args) {
int len = 20;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
String test = generateRandomString(len);
int ans1 = minLight1(test);
int ans2 = minLight2(test);
if (ans1 != ans2) {
System.out.println("oops!");
}
}
System.out.println("finish!");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/386656.html
標籤：其他
下一篇：整型提升——隱式型別轉換