Форум программистов, компьютерный форум CyberForum.ru

оптимизация кода - C++

Восстановить пароль Регистрация
 
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
20.04.2013, 22:29     оптимизация кода #1
Задача: определить, является ли последовательность скобок действительной. Длинна строки не превышает 100000.
Например:
№ Input Output
1 ()(()) VALID
2 )( INVALID
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
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int sum=0;
    char *c = new char[100001];
    cin>>c;
    for(int i = 0 ;i<strlen(c);i++)
    {
        if (c[i]=='(')
            sum++;
        if (c[i]==')')
            sum--;
        if (sum<0 || sum>strlen(c)-i-1)
            break;
    }
    if(sum == 0)
        cout<<"VALID";
    else
        cout<<"INVALID";
    return 0;
}
Код не проходит по времени. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 22:29     оптимизация кода
Посмотрите здесь:

Оптимизация кода C++
C++ Оптимизация кода
Оптимизация кода C++
Оптимизация кода C++
C++ Оптимизация кода
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.04.2013, 22:33     оптимизация кода #2
Цитата Сообщение от Tolyas Посмотреть сообщение
i<strlen(c)
заменить на
C++
1
c[i]
А то у вас сложность квадратичная :)

Добавлено через 1 минуту
Цитата Сообщение от Tolyas Посмотреть сообщение
sum>strlen(c)-i-1
и вот это вот убрать лучше
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
20.04.2013, 22:40  [ТС]     оптимизация кода #3
Спасибо, все прошло, буду знать, что так можно писать в условии. Спасибо.
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
20.04.2013, 23:09     оптимизация кода #4
Можно так
C++
1
2
3
4
5
6
7
8
9
10
    char str[] = "((123))(";
    int count = 0;
    for(int i = 0; str[i]!='\0'; i++){
        if( str[i] == '(' || str[i] == ')' ){ ++count; };
    }
    if( count%2 == 0 ) { 
        printf("1\n"); 
    } else {
        printf("0\n"); 
    };
Добавлено через 10 минут
Хотя, не всегда корректно.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
21.04.2013, 00:05     оптимизация кода #5
Цитата Сообщение от UnsKneD Посмотреть сообщение
Добавлено через 10 минут
Хотя, не всегда корректно.
Конечно, что тут может быть корректно если просто считать кол-во разных скобок одним счетчиком. "))"
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
21.04.2013, 00:28     оптимизация кода #6
или можно через стек (для трёх видов скобок)
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
bool ChkBrackets(const string &Str)
{
    stack<char>Brackets;
 
    for (string::size_type i = 0; i != Str.size(); i++) {
        if ( (Str[i]=='(') || (Str[i]=='{') ||(Str[i]=='[') ) {
            Brackets.push(Str[i]);
        }
        else {
            switch (Str[i]) {
            case ')':
                if (!(Brackets.empty()) && (Brackets.top()=='('))
                    Brackets.pop();
                else return false;
                break;
            case '}':
                if (!(Brackets.empty()) && (Brackets.top()=='{'))
                    Brackets.pop();
                else return false;
                break;
            case ']':
                if (!(Brackets.empty()) && (Brackets.top()=='['))
                    Brackets.pop();
                else return false;
                break;
            }
        }
    }
    return Brackets.empty();
}
 
int main()
{
    string str;
    getline(cin,str);
 
    if (ChkBrackets(str))
        cout<<"OK";
    else
        cout<<"BAD";
    return 0;
}
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
21.04.2013, 02:33  [ТС]     оптимизация кода #7
Olivеr, Этот код не проходит по времени, но я решил эту задачу немного другим способом:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
 
using namespace std;
 
int main()
{
  int s1=0,s2=0,s3=0;
  int i1=0,i2=0,i3=0;
  int *j1,*j2,*j3;
  int n;
  cin>>n;
  char *c = new char[n];
  j1 = new int[n+1];
  j2 = new int[n+1];
  j3 = new int[n+1];
  j1[0]=-1;
  j2[0]=-1;
  j3[0]=-1;
  cin>>c;
  for(int i = 0 ;c[i]!='\0';i++)
  {
    if (c[i]=='(')
    {
      s1++;
      j1[++i1]=i;
    }
    if (c[i]==')')
    {
      s1--;
      if(j1[i1]<j2[i2]||j1[i1]<j3[i3])
      {
        s1=-1;
      }
      i1--;
 
    }
    if (c[i]=='[')
    {
      s2++;
      j2[++i2]=i;
    }
    if (c[i]==']')
    {
      s2--;
      if(j2[i2]<j1[i1]||j2[i2]<j3[i3])
      {
        s2=-1;
      }
      i2--;
    }
    if (c[i]=='{')
    {
      s3++;
      j3[++i3]=i;
    }
    if (c[i]=='}')
    {
      s3--;
      if(j3[i3]<j2[i2]||j3[i3]<j1[i1])
      {
        s3=-1;
      }
      i3--;
    }
    if ((s1<0)||(s2<0)||(s3<0))
      break;
  }
  if((s1 == 0)&&(s2 == 0)&&(s3 == 0))
    cout<<"Yes";
  else
    cout<<"No";
  return 0;
}
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
21.04.2013, 09:28     оптимизация кода #8
Tolyas,
()))))
Yes
(())
No
()
Yes
так должно быть?
myxasa
14 / 14 / 1
Регистрация: 31.05.2012
Сообщений: 210
Записей в блоге: 2
21.04.2013, 10:07     оптимизация кода #9
Olivеr, условия лучше так писать

C++
1
if( !s1 && !s2 && !s3)
на будущее)
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
21.04.2013, 10:53  [ТС]     оптимизация кода #10
Цитата Сообщение от Olivеr Посмотреть сообщение
Tolyas,
так должно быть?
Нет, так не должно быть. Так и не происходит.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 11:09     оптимизация кода
Еще ссылки по теме:

Оптимизация кода C++
C++ Оптимизация кода (C++)
Оптимизация кода C++

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

Или воспользуйтесь поиском по форуму:
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
21.04.2013, 11:09     оптимизация кода #11
myxasa, это Вы, наверное, хотели сказать Tolyas
Yandex
Объявления
21.04.2013, 11:09     оптимизация кода
Ответ Создать тему
Опции темы

Текущее время: 13:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru