Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
1

Оптимизировать код

15.07.2019, 04:09. Просмотров 1044. Ответов 5
Метки нет (Все метки)

Для решения задачи :
"Note: Write a solution that only iterates over the string once and uses O(1) additional memory, since this is what you would be asked to do during a real interview.

Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

Example

For s = "abacabad", the output should be
firstNotRepeatingCharacter(s) = 'c'.

There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.

For s = "abacabaabacaba", the output should be
firstNotRepeatingCharacter(s) = '_'.

There are no characters in this string that do not repeat.

Input/Output

[execution time limit] 0.5 seconds (cpp)

[input] string s

A string that contains only lowercase English letters.

Guaranteed constraints:
1 ≤ s.length ≤ 10^5.

[output] char

The first non-repeating character in s, or '_' if there are no characters that do not repeat."

я написал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
char firstNotRepeatingCharacter(std::string s) 
{
 
    int l = s.length();
    if(l==1)
    {
        return s[0];
    }
    for(int i = 0 ; i < l-1;++i)
    {
        int c = 0;
        
        for(int j = 0; j < l  ; ++j)
        {
            if(s[i]==s[j])
            {
                ++c;
            
            }  
        }
        if(c==1)
        {
            return s[i];
        }
            
    }
    
    return '_';
    
}
Но данный код не проходит тест за максимальное допустимое время (0,5 секунд), помогите пожалуйста оптимизировать код либо придумать другой алгоритм,спасибо заранее.

Добавлено через 2 часа 26 минут
upd
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.07.2019, 04:09
Ответы с готовыми решениями:

Оптимизировать код
Доброго времени суток, как можно оптимизировать код что бы он быстрее работал ? Дана...

Оптимизировать код
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар...

Оптимизировать код
Для решения задачи : &quot;Given an array a that contains only numbers in the range from 1 to a.length,...

Как оптимизировать код
Доброй ночи господа у меня к вам такая просьба как можно упростить данный код? #include &lt;iostream&gt;...

5
354 / 222 / 119
Регистрация: 25.06.2019
Сообщений: 823
15.07.2019, 07:57 2
Лучший ответ Сообщение было отмечено plzvtl как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char firstNotRepeatingCharacter(string s) 
{
    string was="";
    int l = s.length();
    for(int j,i = 0 ; i < l; ++i)
    {
        char ch=s[i];
        if((int)was.find(ch)<0)
        {
            was+=ch;
            for(j = i+1; j < l; ++j)
                if(ch==s[j]) break;
            if(j==l) return ch;
        }
    }
    return '_';
}
1
3528 / 1980 / 832
Регистрация: 07.02.2019
Сообщений: 5,309
15.07.2019, 11:41 3
plzvtl, попробуй так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char firstNotRepeatingCharacter(const std::string& s)
{
    std::pair<int, int> buf['z' - 'a' + 1];
    int i{};
    for (auto& ch : s)
    {
        buf[ch - 'a'].first++;
        buf[ch - 'a'].second = i++;
    };
    auto p = std::min_element(std::begin(buf), std::end(buf), [](auto lh, auto rh)
    {
        return
            (lh.first && !rh.first) ||
            (lh.first && (lh.first < rh.first || (lh.first == rh.first && lh.second < rh.second)));
    });
    if (p->first == 1)
        return static_cast<char>(std::distance(std::begin(buf), p) + 'a');
    return '_';
}
1
74 / 55 / 19
Регистрация: 22.11.2015
Сообщений: 193
15.07.2019, 11:54 4
Читабельней
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 14:31  [ТС] 5
Pvt,
вроде правильно переписал.
0
Миниатюры
Оптимизировать код  
354 / 222 / 119
Регистрация: 25.06.2019
Сообщений: 823
15.07.2019, 14:46 6
а вроде нет, скобки считаем, если ненужные ставим - считаем вдвойне
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.07.2019, 14:46

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Нужно оптимизировать код
Вобщем код не принемает сайт, немного нагружает и по времени не проходит задание Август и...

Как оптимизировать код?
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение,...

Нужно оптимизировать код
Гистограмма является многоугольником, сформированным из последовательности прямоугольников,...

Исправить и оптимизировать код
нужна помощь по исправлению ошибок Написал программу она работает все отлично но препод сказал...

Оптимизировать и минимализировать код
Cделал легкую прогу. Понимаю логики 0 в коде. Можете помочь оптимизировать код? А заодно и сделать...

Помогите оптимизировать код
Здравствуйте! Помогите, пожалуйста, оптимизировать его: main.cpp #include &quot;main.h&quot;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.