小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
2 3 .X. 11 ...XX....XX
1 3
public static void main(String[] args){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int[] len = new int[num]; String[] path = new String[num]; for(int i =0 ;i <num; i++){ len[i] = sc.nextInt(); path[i] = sc.next(); } for(int i =0 ;i <num; i++){ System.out.println(find(len[i], path[i])); } } public static int find(int len, String path){ int res = 0; StringBuffer sb = new StringBuffer(path); for(int i =0; i<sb.length(); i++){ if(sb.charAt(i) == 'X'){ continue; } res++; i = i+2; } return res; }
import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); int n = cin.nextInt(); for (int i = 0; i < n; i++) { int out = 0;//需要的路灯数目 int m = cin.nextInt(); String str = cin.next(); if(str.contains(".")) { if(m<=3) { out=1; System.out.println(out); } else if(m>3) { for(int j=0;j<m;j++) { if(j==0) { if(str.charAt(j)=='.') { out++; j=j+2; } else continue; } else if(j==m-2) { if(str.charAt(j)=='.' || str.charAt(j+1)=='.') { out++; } break; } else if(j==m-1 ) { if(str.charAt(j)=='.') { out++; } break; } else { if(str.charAt(j)=='.') { out++; j=j+2; } else continue; } } System.out.println(out); } } else System.out.println(0); } } }
import java.util.Scanner; public class Main { //思路:小贪心,假如第一个遇到`.`反正都要花费一个灯来照亮,所以就把这个灯安装到下一个位置 //然后来到第4个格子,同时也说明新来到的格子不能依靠前面的灯来把自己照亮 public static int light(String road) { if(road == null || road.length() == 0) { return 0; } int n = road.length(); int ans = 0; //for循环中的变量i: //若遇到'.'则向后移3位, //若遇到'X'则向后移1位 for(int i = 0; i < n; i++) { if(road.charAt(i) == '.') { ans++; i += 2; } } return ans; } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = Integer.valueOf(s.nextLine()); for(int i = 0; i < n; i++) { s.nextLine(); System.out.println(light(s.nextLine())); } } }
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int t = input.nextInt(); int n[] = new int[t]; String s[] = new String[t]; for(int i = 0; i < t; i++) { n[i] = input.nextInt(); s[i] = input.next(); } input.close(); for(int i = 0; i < t; i++) { System.out.println(Solution(s[i])); } } public static int Solution(String s) { int n = s.length(); int k = 0; boolean f = false; for(int i = 0; i < n; i++) { if(s.charAt(i) == '.') { f = true; k = i; break; } } if(!f)//全是障碍物,不需要路灯 return 0; else if( k+3 >= n)//需要照亮的位置在倒数后三个格子里,需要一个路灯 return 1; else//不在后三个格子里,后移3个位置递归计算 return 1 + Solution(s.substring(k+3, n)); } }
import java.util.*; //贪心算法求解:1.当遇到第一个'.'时,表示该位置需要被照亮,此时不安装路灯,在它的下一个位置安装路灯,即sum+1; //因为该路灯位置的下一个位置已经被照亮了,因此下标+2 //遇到‘X’时跳过,因为不需要安装 public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i = 0; i < t; i++){ int n = sc.nextInt(); String s = sc.next(); int sum = 0; for(int j = 0; j < n; j++){ if(s.charAt(j) == '.'){ sum++; j = j + 2; } } System.out.println(sum); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t > 0) { t--; int n = sc.nextInt(); String s = sc.next(); int sum = 0; char[] c = s.toCharArray(); for (int i = 0; i < n; i++) { if (c[i] == '.') { if (i + 2 < n) { c[i] = 'X'; c[i + 1] = 'X'; c[i + 2] = 'X'; sum++; } else if (i + 1 == n - 1) { c[i] = 'X'; c[i + 1] = 'X'; sum++; } else if (i == n - 1) { c[i] = 'X'; sum++; } } } System.out.println(sum); } } }
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner input = new Scanner(System.in); int t = input.nextInt(); for (int i=0;i<t;i++){ int num = input.nextInt(); String s = input.next(); int count = 0; for (int j=0;j<num;j++){ if (s.charAt(j)=='.'){ count++; j = j+2; } } System.out.println(count); } } }