Dada la string str que contiene solo puntos y asteriscos. Un punto representa espacios libres y 
representa lámparas. Una lámpara en la posición 
puede difundir su luz en las ubicaciones i-1, i e i+1 . Determine el número mínimo de lámparas necesarias para iluminar toda la string.
Ejemplos:
Entrada: str = “……”
Salida: 2
Inicialmente no hay lámparas, por lo que toda la string está a oscuras. Instalaremos lámparas en las posiciones 2 y 5. La lámpara en la posición 2 iluminará 1, 2, 3 y la lámpara en la posición 5 iluminará 4, 5, 6, por lo que se ilumina toda la string.Entrada: str = “*.*”
Salida: 0
Enfoque: si no tenemos un asterisco , por cada 3 puntos necesitamos una lámpara, por lo que la respuesta es ceil (D/3), donde D es el número de puntos. El problema se puede resolver creando una copia de la string dada, y para cada asterisco en la primera string, colocamos un asterisco en sus índices adyacentes en la segunda string.
Entonces, si la string dada es “…**..” , entonces la segunda string será “..****”. .
Después de eso, contamos el número de puntos en cada bloque de puntos consecutivos y encontramos el número de lámparas necesarias para ese bloque. Para cada bloque, la respuesta será ceil(D/3) y la suma total de estas lámparas será el respuesta para la string completa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
void check(int n, string s)
{
// Create the modified string with
// v[i-1] = v[i + 1] = * where s[i] = *
char v[n];
for(int i = 0; i < n; i++)
{
if (s[i] == '*')
{
v[i] = '*';
// Checking valid index and then replacing
// "." with "*" on the surrounding of a *
if (i > 0 && i < n - 1)
{
v[i + 1] = '*';
v[i - 1] = '*';
}
if (i == 0 && n != 1)
{
v[i + 1] = '*';
}
if (i == n - 1 && n != 1)
{
v[i - 1] = '*';
}
}
else
{
// Just copying if the character is a "."
if (v[i] != '*')
{
v[i] = '.';
}
}
}
// Creating the string with the list v
string str(v);
string word = "";
char dl = '*';
// to count the number of split strings
int num = 0;
// adding delimiter character at the end
// of 'str'
str = str + dl;
// length of 'str'
int l = str.size();
// traversing 'str' from left to right
vector<string> res;
for (int i = 0; i < l; i++) {
// if str[i] is not equal to the delimiter
// character then accumulate it to 'word'
if (str[i] != dl)
word += str[i];
else {
// if 'word' is not an empty string,
// then add this 'word' to the array
// 'substr_list[]'
if ((int)word.size() != 0)
res.push_back(word);
// reset 'word'
word = "";
}
}
int ans = 0;
for(auto x : res)
{
// Continuing if the string length is 0
if (x.length() == 0)
{
continue;
}
// Adding number of lamps for each block of "."
ans += ceil(x.length() * 1.0 / 3);
}
cout << ans << "\n";
}
int main() {
string s = ".....";
int n = s.length();
check(n, s);
return 0;
}
// This code is contributed by NishaBharti.
Java
// Java implementation of the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to print minimum amount
// of lamps needed to be installed
static void check(int n, String s)
{
// Create the modified string with
// v[i-1] = v[i + 1] = * where s[i] = *
char v[] = new char[n];
for(int i = 0; i < n; i++)
{
if (s.charAt(i) == '*')
{
v[i] = '*';
// Checking valid index and then replacing
// "." with "*" on the surrounding of a *
if (i > 0 && i < n - 1)
{
v[i + 1] = '*';
v[i - 1] = '*';
}
if (i == 0 && n != 1)
{
v[i + 1] = '*';
}
if (i == n - 1 && n != 1)
{
v[i - 1] = '*';
}
}
else
{
// Just copying if the character is a "."
if (v[i] != '*')
{
v[i] = '.';
}
}
}
// Creating the string with the list v
String xx = new String(v);
// Splitting the string into blocks
// with "*" as delimiter
String x[] = xx.split("\\*");
int ans = 0;
for(String xi : x)
{
// Continuing if the string length is 0
if (xi.length() == 0)
{
continue;
}
// Adding number of lamps for each block of "."
ans += Math.ceil(xi.length() * 1.0 / 3);
}
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
String s = "......";
int n = s.length();
check(n, s);
}
}
// This code is contributed by Kingash
Python3
# Python3 implementation of the above approach
import math
# Function to print minimum amount
# of lamps needed to be installed
def check(n, s):
# Create the modified string with
# v[i-1] = v[i + 1] = * where s[i] = *
v = [""] * n
for i in range(n):
if (s[i] == "*"):
v[i] = "*"
# Checking valid index and then replacing
# "." with "*" on the surrounding of a *
if (i > 0 and i < n - 1):
v[i + 1] = "*"
v[i - 1] = "*"
if (i == 0 and n != 1):
v[i + 1] = "*"
if (i == n - 1 and n != 1):
v[i - 1] = "*"
else:
# Just copying if the character is a "."
if (v[i] != "*"):
v[i] = "."
# Creating the string with the list v
xx = ''.join(v)
# Splitting the string into blocks
# with "*" as delimiter
x = xx.split("*")
s = 0
for i in range(len(x)):
# Continuing if the string length is 0
if (x[i] == ""):
continue
# Adding number of lamps for each block of "."
s += math.ceil(len(x[i]) / 3)
print(s)
# Driver code
s = "......"
n = len(s)
check(n, s)
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to print minimum amount
// of lamps needed to be installed
static void check(int n, string s)
{
// Create the modified string with
// v[i-1] = v[i + 1] = * where s[i] = *
char[] v = new char[n];
for (int i = 0; i < n; i++) {
if (s[i] == '*') {
v[i] = '*';
// Checking valid index and then replacing
// "." with "*" on the surrounding of a *
if (i > 0 && i < n - 1) {
v[i + 1] = '*';
v[i - 1] = '*';
}
if (i == 0 && n != 1) {
v[i + 1] = '*';
}
if (i == n - 1 && n != 1) {
v[i - 1] = '*';
}
}
else {
// Just copying if the character is a "."
if (v[i] != '*') {
v[i] = '.';
}
}
}
// Creating the string with the list v
string xx = new string(v);
// Splitting the string into blocks
// with "*" as delimiter
string[] x = xx.Split("\\*");
int ans = 0;
foreach(string xi in x)
{
// Continuing if the string length is 0
if (xi.Length == 0) {
continue;
}
// Adding number of lamps for each block of "."
ans += (int)(Math.Ceiling(xi.Length * 1.0 / 3));
}
Console.Write(ans);
}
// Driver Code
public static void Main(string[] args)
{
string s = "......";
int n = s.Length;
check(n, s);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript implementation of the above approach
const check = (n, s) => {
// Create the modified string with
// v[i-1] = v[i + 1] = * where s[i] = *
let v = new Array(n).fill('');
for (let i = 0; i < n; i++)
{
if (s[i] == '*')
{
v[i] = '*';
// Checking valid index and then replacing
// "." with "*" on the surrounding of a *
if (i > 0 && i < n - 1) {
v[i + 1] = '*';
v[i - 1] = '*';
}
if (i == 0 && n != 1) {
v[i + 1] = '*';
}
if (i == n - 1 && n != 1) {
v[i - 1] = '*';
}
}
else {
// Just copying if the character is a "."
if (v[i] != '*') {
v[i] = '.';
}
}
}
// Creating the string with the list v
let str = v.join('');
let word = "";
let dl = '*';
// to count the number of split strings
let num = 0;
// adding delimiter character at the end
// of 'str'
str = str + dl;
// length of 'str'
let l = str.length;
// traversing 'str' from left to right
let res = [];
for (let i = 0; i < l; i++) {
// if str[i] is not equal to the delimiter
// character then accumulate it to 'word'
if (str[i] != dl)
word = word + str[i];
else {
// if 'word' is not an empty string,
// then add this 'word' to the array
// 'substr_list[]'
if (word.length != 0)
res.push(word);
// reset 'word'
word = "";
}
}
let ans = 0;
for (let x in res) {
// Continuing if the string length is 0
if (res[x].length == 0) {
continue;
}
// Adding number of lamps for each block of "."
ans += Math.ceil(res[x].length * 1.0 / 3);
}
document.write(`${ans}<br/>`);
}
let s = ".....";
let n = s.length;
check(n, s);
// This code is contributed by rakeshsahni
</script>
Producción:
2
Complejidad de tiempo: O (n) ya que estamos haciendo un recorrido de bucle único
Complejidad espacial: O (n) ya que estamos creando una array de caracteres
Nota: donde n es el tamaño de la string dada