Может ли кто-нибудь сказать мне, как реализовать программу для проверки строки, содержит все уникальные символы?
Определить, имеет ли строка все уникальные символы?
Ответ 1
Если вы говорите о строке ASCII:
-
Создайте массив int [0-255], один для каждого символьного индекса, инициализируется до нуля.
-
Прокрутка каждый символ в строке и приращение соответствующей позиции массива для этого символа
-
Если позиция массива уже содержит 1, то этот символ уже встречается. Результат = > Не уникально.
-
Если вы доберетесь до конца строки без появления (3), Результат = > строка уникальна.
Ответ 2
Сортировка символов в строке с использованием выбранного вами алгоритма (например, встроенная функция qsort), затем сканирование проверки строки для последовательных повторяющихся букв; если вы дойдете до конца, не найдя ни одного, строка содержит все уникальные символы.
Альтернативой может быть использование какой-либо структуры, которая имеет один ведро для каждого символа, который может содержать строка, все инициализируются до нуля; вы просматриваете строку, увеличивая значение ведра, соответствующее текущему символу. Если вы увеличиваете ведро, у которого уже есть 1 внутри, вы уверены, что ваша строка содержит дубликаты.
Это может отлично работать с char и массивом (размером UCHAR_MAX+1), но он быстро выходит из-под контроля, когда вы начинаете разбираться с широкими символами. В таком случае вам понадобится хэш-таблица или какой-нибудь другой "серьезный" контейнер.
Лучший алгоритм зависит от длины проверяемых строк, размера каждого символа, скорости алгоритма сортировки и стоимости выделения/использования структуры для хранения частот символов.
Ответ 3
#include <iostream>
#include <string>
using namespace std;
bool isUnique(string _str)
{
bool char_set[256];
int len = _str.length();
memset(char_set, '\0', 256);
for(int i = 0; i < len; ++i)
{
int val = _str[i]- '0';
if(char_set[val])
{
return false;
}
char_set[val] = true;
}
return true;
}
int main()
{
cout<<"Value: "<<isUnique("abcd")<<endl;
return 0;
}
Ответ 4
Сделайте набор букв и подсчитайте значения.
set("adoihgoiaheg")= set(['a', 'e', 'd', 'g', 'i', 'h', 'o']):
def hasUniqueLetters(str):
return (len(set(str)) == len(str))
>>> hasUniqueLetters("adoihgoiaheg")
False
Ответ 5
Используйте массив из 256 элементов. Заполните его 0. Теперь перейдите к строке, в которой соответствующая запись в массиве будет равна 1, если она равна 0. В противном случае в строке повторяются символы.
Ответ 6
Задайте массив булевых элементов, равный значению, установленному в false. (Постоянное время). Сканирование строки; для каждого символа, осмотрите массив в слоте characater; если true, строка имеет повторяющиеся символы. Если false, установите для этого слота значение true и продолжайте. Если вы дойдете до конца, не встретив дубликата, их нет, и строка содержит только уникальные символы. Время выполнения: O (n), когда n - длина строки, с довольно маленькой константой.
Ответ 7
Аналогично (и без массивов) используйте ТАЙНУЮ ТАБЛИЦУ!
//код psuedo:
- просматривайте каждую char строки
- hash char и посмотреть его в хеш-таблице
- Если таблица имеет хеш, верните FALSE//, поскольку она не уникальна
- __ else сохранить хэш
- вернитесь к шагу # 1, пока не закончите.
Время выполнения O (n) и пространство памяти лучше, так как вам не нужен массив из 256 (asciis)
Ответ 8
#include <stdio.h>
#define ARR_SIZE 32
unsigned char charFlag[ARR_SIZE];
void initFlag() {
int i = 0;
for (i = 0; i < ARR_SIZE; i++)
charFlag[i] = 0;
}
int getFlag(int position) {
int val = 0;
int flagMask = 1;
int byteIndex = position / 8;
int locPos = position % 8;
flagMask = flagMask << locPos;
// flagMask = ~flagMask;
val = charFlag[byteIndex] & flagMask;
val = !(!val);
// printf("\nhex: %x\n", val);
return val;
}
void setFlag(int position) {
int flagMask = 1;
int byteIndex = position / 8;
int locPos = position % 8;
flagMask = flagMask << locPos;
charFlag[byteIndex] = charFlag[byteIndex] | flagMask;
}
int isUniq(char *str) {
int is_uniq = 1;
do {
char *lStr = str;
int strLen = 0;
int i;
if (str == 0)
break;
while (*lStr != 0) {
lStr++;
strLen++;
}
initFlag();
lStr = str;
for (i = 0; i < strLen; i++) {
if (getFlag(lStr[i]))
break;
setFlag(lStr[i]);
}
if (i != strLen)
is_uniq = 0;
} while (0);
return is_uniq;
}
int main() {
char *p = "abcdefe";
printf("Uniq: %d\n", isUniq(p));
return 0;
}
Ответ 9
Используйте HashTable, добавьте ключ для каждого символа вместе с количеством вхождений в качестве значения. Прокрутите по клавишам HashTable, чтобы увидеть, встретили ли вы счет > 1. Если это так, выведите false.
Ответ 10
Простое решение будет использовать 2 цикла. Никакая дополнительная структура данных не требуется для отслеживания символов.
bool has_unique_char(char *str,int n)
{
if(n==0)
return true;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(str[i] == str[j])
return false;
}
}
return true;
}
Ответ 11
bool isUnique(char st[],int size)
{
bool char_set[256]=false;
for(int i=0;i<size;i++)
{
if(char_set[st[i]]-'0')
return false;
char_set[st[i]-'0')=true;
}
return true;
}
Ответ 12
мой первоначальный ответ также выполнял аналогичную технику массива и подсчитывал появление символа.
но я делал это в C, и я думаю, что это может быть просто с помощью манипуляции с указателем и полностью избавиться от массива.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void main (int argc, char *argv[])
{
char *string;
if (argc<2)
{
printf ("please specify a string parameter.\n");
exit (0);
}
string = argv[1];
int i;
int is_unique = 1;
char *to_check;
while (*string)
{
to_check = string+1;
while (*to_check)
{
//printf ("s = %c, c = %c\n", *string, *to_check);
if (*to_check == *string)
{
is_unique = 0;
break;
}
to_check++;
}
string++;
}
if (is_unique)
printf ("string is unique\n");
else
printf ("string is NOT unique\n");
}
Ответ 13
Без использования дополнительной памяти:
#define UNIQUE_ARRAY 1
int isUniqueArray(char* string){
if(NULL == string ) return ! UNIQUE_ARRAY;
char* current = string;
while(*current){
char* next = current+1;
while(*next){
if(*next == *current){
return ! UNIQUE_ARRAY;
}
next++;
}
current++;
}
return UNIQUE_ARRAY;
}
Ответ 14
Я верю, что есть гораздо более простой способ:
int check_string_unique(char *str)
{
int i = 0;
int a = 0;
while (str[i])
{
a = i + 1; // peak to the next character
while (str[a])
{
if (str[i] == str[a]) // you found a match
return (0); // false
a++; // if you've checked a character before, there no need to start at the beggining of the string each time. You only have to check with what is left.
}
i++; //check each character.
}
return (1); //true!
}
Ответ 15
Надеюсь, это поможет вам.
#include <iostream>
using namespace std;
int main() {
string s;
cin>>s;
int a[256]={0};
int sum=0;
for (int i = 0; i < s.length();i++){
if(a[s[i]]==0)++sum;
a[s[i]]+=1;
}
cout<<(sum==s.length()?"yes":"no");
return 0;
}
Ответ 16
это оптимальное решение задачи. он принимает только целочисленную переменную и может определить, является ли она уникальной или нет независимо от размера строки.
сложность
лучший случай O (1)
наихудший случай O (n)
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - ‘a’;
if ((checker & (1 << val)) > 0)
return false;
checker |= (1 << val);
}
return true;
}