Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
1

оптимизация кода

20.04.2013, 22:29. Просмотров 606. Ответов 10
Метки нет (Все метки)

Задача: определить, является ли последовательность скобок действительной. Длинна строки не превышает 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;
}
Код не проходит по времени. Заранее спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 22:29
Ответы с готовыми решениями:

Оптимизация кода
Помогите оптимизировать код. суть программы такая, принимает на вход колличество бегунов и в...

Оптимизация кода
Как можно оптимизировать данный программный код? Ответ объяснить void func() { for (int i...

Оптимизация кода
Пожалуйста форумчане как можно сократить этот код Особенно от 27 до 90 строки #include &lt;iostream&gt;...

Оптимизация кода
Доброго времени сутки господа у меня к вам вопрос как можно оптимызуваты данный код? #include...

Оптимизация кода (C++)
Добрый вечер. У меня есть две функции. Вопрос:&quot;Как оптимизировать этот код, пользуясь тем, что тела...

10
diagon
Higher
1940 / 1206 / 120
Регистрация: 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
и вот это вот убрать лучше
1
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
20.04.2013, 22:40  [ТС] 3
Спасибо, все прошло, буду знать, что так можно писать в условии. Спасибо.
0
UnsKneD
алкокодер
155 / 151 / 41
Регистрация: 27.12.2012
Сообщений: 550
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 минут
Хотя, не всегда корректно.
0
20.04.2013, 23:09
Tulosba
:)
Эксперт С++
4751 / 3245 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
21.04.2013, 00:05 5
Цитата Сообщение от UnsKneD Посмотреть сообщение
Добавлено через 10 минут
Хотя, не всегда корректно.
Конечно, что тут может быть корректно если просто считать кол-во разных скобок одним счетчиком. "))"
0
Olivеr
413 / 409 / 95
Регистрация: 06.10.2011
Сообщений: 832
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;
}
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;
}
0
Olivеr
413 / 409 / 95
Регистрация: 06.10.2011
Сообщений: 832
21.04.2013, 09:28 8
Tolyas,
()))))
Yes
(())
No
()
Yes
так должно быть?
0
myxasa
14 / 14 / 8
Регистрация: 31.05.2012
Сообщений: 210
Записей в блоге: 2
21.04.2013, 10:07 9
Olivеr, условия лучше так писать

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

Оптимизация кода
Нужно както упростить програму /* Дан массив а если в нем встречается такой элемент что а &lt;a ...

оптимизация кода
Добрый вечер всем. У меня такая проблема: написал прогу, необходимо продемонстрировать ее работу....

Оптимизация кода
main: #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &quot;keyBuffer.h&quot; #include &quot;pause.h&quot;...


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

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

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