Dada una persona que está en la posición actual_pos y una ruta de string binaria que son los movimientos que tomó la persona, si la ruta [i] = ‘0’ entonces la persona se movió un paso hacia la izquierda, y si la ruta [i] = ‘1’ entonces el persona se movió un paso a la derecha. La tarea es encontrar el recuento de las distintas posiciones que visitó la persona.
Ejemplos:
Entrada: current_pos = 5, ruta = “011101”
Salida: 4
Los movimientos dados son izquierda, derecha, derecha, derecha, izquierda y derecha,
es decir, 5 -> 4 -> 5 -> 6 -> 7 -> 6 -> 7
El número de posiciones distintas son 4 (4, 5, 6 y 7).Entrada: pos_actual = 3, ruta = “110100”
Salida: 3
3 -> 4 -> 5 -> 4 -> 5 -> 4 -> 3
Acercarse:
- Declare una array puntos[] para almacenar todos los puntos por los que pasa la persona.
- Inicialice la primera posición de esta array en la posición actual current_pos .
- Atraviese la ruta de la string y haga lo siguiente:
- Si el carácter actual es ‘0’ , entonces la persona viajó a la izquierda. Así que disminuya la posición actual en 1 y guárdela en points[] .
- Si el carácter actual es ‘1’ , entonces la persona viajó a la derecha. Así que incrementa la posición actual en 1 y guárdala en points[] .
- Cuente el número total de elementos distintos en puntos[] . Consulte Contar elementos distintos en una array para conocer los diferentes métodos de contar el número de elementos distintos en una array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to return the number
// of distinct elements in an array
int countDistinct(int arr[], int len)
{
set<int> hs;
for (int i = 0; i < len; i++) {
// add all the elements to the HashSet
hs.insert(arr[i]);
}
// Return the size of hashset as
// it consists of all unique elements
return hs.size();
}
// Function to return the count of
// positions the person went to
int getDistinctPoints(int current_pos, string path)
{
// Length of path
int len = path.length();
// Array to store all the points traveled
int points[len + 1];
// The first point is the current_pos
points[0] = current_pos;
// For all the directions in path
for (int i = 0; i < len; i++) {
// Get whether the direction was left or right
char ch = path[i];
// If the direction is left
if (ch == '0') {
// Decrement the current position by 1
current_pos--;
// Store the current position in array
points[i + 1] = current_pos;
}
// If the direction is right
else {
// Increment the current position by 1
current_pos++;
// Store the current position in array
points[i + 1] = current_pos;
}
}
return countDistinct(points, len + 1);
}
// Driver code
int main()
{
int current_pos = 5;
string path = "011101";
cout << (getDistinctPoints(current_pos, path));
return 0;
}
// contributed by Arnab Kundu
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to return the count of
// positions the person went to
public static int getDistinctPoints(int current_pos, String path)
{
// Length of path
int len = path.length();
// Array to store all the points traveled
int points[] = new int[len + 1];
// The first point is the current_pos
points[0] = current_pos;
// For all the directions in path
for (int i = 0; i < len; i++) {
// Get whether the direction was left or right
char ch = path.charAt(i);
// If the direction is left
if (ch == '0') {
// Decrement the current position by 1
current_pos--;
// Store the current position in array
points[i + 1] = current_pos;
}
// If the direction is right
else {
// Increment the current position by 1
current_pos++;
// Store the current position in array
points[i + 1] = current_pos;
}
}
return countDistinct(points, len + 1);
}
// Utility function to return the number
// of distinct elements in an array
public static int countDistinct(int arr[], int len)
{
HashSet<Integer> hs = new HashSet<Integer>();
for (int i = 0; i < len; i++) {
// add all the elements to the HashSet
hs.add(arr[i]);
}
// Return the size of hashset as
// it consists of all unique elements
return hs.size();
}
// Driver code
public static void main(String[] args)
{
int current_pos = 5;
String path = "011101";
System.out.print(getDistinctPoints(current_pos, path));
}
}
Python3
# Utility function to return the number # of distinct elements in an array def countDistinct(arr, Len): hs = dict() for i in range(Len): # add all the elements to the HashSet hs[arr[i]] = 1 # Return the size of hashset as # it consists of all unique elements return len(hs) # Function to return the count of # positions the person went to def getDistinctPoints(current_pos, path): # Length of path Len = len(path) # Array to store all the points traveled points = [0 for i in range(Len + 1)] # The first pois the current_pos points[0] = current_pos # For all the directions in path for i in range(Len): # Get whether the direction # was left or right ch = path[i] # If the direction is left if (ch == '0'): # Decrement the current position by 1 current_pos -= 1 # Store the current position in array points[i + 1] = current_pos # If the direction is right else: # Increment the current position by 1 current_pos += 1 # Store the current position in array points[i + 1] = current_pos return countDistinct(points, Len + 1) # Driver code current_pos = 5 path = "011101" print(getDistinctPoints(current_pos, path)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
// Function to return the count of
// positions the person went to
public static int getDistinctPoints(int current_pos,
string path)
{
// Length of path
int len = path.Length;
// Array to store all the points traveled
int[] points = new int[len + 1];
// The first point is the current_pos
points[0] = current_pos;
// For all the directions in path
for (int i = 0; i < len; i++) {
// Get whether the direction was left or right
char ch = path[i];
// If the direction is left
if (ch == '0') {
// Decrement the current position by 1
current_pos--;
// Store the current position in array
points[i + 1] = current_pos;
}
// If the direction is right
else {
// Increment the current position by 1
current_pos++;
// Store the current position in array
points[i + 1] = current_pos;
}
}
return countDistinct(points, len + 1);
}
// Utility function to return the number
// of distinct elements in an array
public static int countDistinct(int[] arr, int len)
{
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < len; i++) {
// add all the elements to the HashSet
hs.Add(arr[i]);
}
// Return the size of hashset as
// it consists of all unique elements
return hs.Count;
}
// Driver code
public static void Main(string[] args)
{
int current_pos = 5;
string path = "011101";
Console.Write(getDistinctPoints(current_pos, path));
}
}
// This code is contributed by shrikanth13
PHP
<?php
// PHP implementation of the approach
// Utility function to return the number
// of distinct elements in an array
function countDistinct($arr, $len)
{
$hs = array();
for ($i = 0; $i < $len; $i++)
{
// add all the elements to the HashSet
array_push($hs, $arr[$i]);
}
$hs = array_unique($hs);
// Return the size of hashset as
// it consists of all unique elements
return count($hs);
}
// Function to return the count of
// positions the person went to
function getDistinctPoints($current_pos, $path)
{
// Length of path
$len = strlen($path);
// Array to store all the points traveled
$points = array();
// The first point is the current_pos
$points[0] = $current_pos;
// For all the directions in path
for ($i = 0; $i < $len; $i++)
{
// Get whether the direction was left or right
$ch = $path[$i];
// If the direction is left
if ($ch == '0')
{
// Decrement the current position by 1
$current_pos--;
// Store the current position in array
$points[$i + 1] = $current_pos;
}
// If the direction is right
else
{
// Increment the current position by 1
$current_pos++;
// Store the current position in array
$points[$i + 1] = $current_pos;
}
}
return countDistinct($points, $len + 1);
}
// Driver code
$current_pos = 5;
$path = "011101";
echo getDistinctPoints($current_pos, $path);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the count of
// positions the person went to
function getDistinctPoints(current_pos, path)
{
// Length of path
let len = path.length;
// Array to store all the points traveled
let points =
Array.from({length: len + 1}, (_, i) => 0);
// The first point is the current_pos
points[0] = current_pos;
// For all the directions in path
for (let i = 0; i < len; i++) {
// Get whether the direction was left or right
let ch = path[i];
// If the direction is left
if (ch == '0') {
// Decrement the current position by 1
current_pos--;
// Store the current position in array
points[i + 1] = current_pos;
}
// If the direction is right
else {
// Increment the current position by 1
current_pos++;
// Store the current position in array
points[i + 1] = current_pos;
}
}
return countDistinct(points, len + 1);
}
// Utility function to return the number
// of distinct elements in an array
function countDistinct(arr, len)
{
let hs = new Set();
for (let i = 0; i < len; i++) {
// add all the elements to the HashSet
hs.add(arr[i]);
}
// Return the size of hashset as
// it consists of all unique elements
return hs.size;
}
// Driver code
let current_pos = 5;
let path = "011101";
document.write(getDistinctPoints(current_pos, path));
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por AbhijeetSridhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA