Задача
В заданной строке дописать после каждого символа «!» символ «?».
Решение.
Проверяем каждый символ строки до тех пор пока не встретится «!», после чего добавляем после него «?».
| Input | Output |
| Hello, world! | Hello, world!? |
| Why are we here?? | Why are we here?? |
| !!!It’s ! a ! problem ! ! | !?!?!?It’s !? a !? problem !? !? |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <string> using namespace std; int main() { string s, s1; getline (cin, s, '\n') ; s1 = s; //запоминаем строку в переменную, которую будем изменять int k = 1; //счетчик, который будет увеличиваться после каждой вставки символа для того, чтобы вставлять символ именно после знака восклицания for (int i = 0; i < s.size(); i ++) { if ( s[i] == '!' ) { s1.insert ( i + k++ , 1 , '?' ); } //вставляем в копию строки знаки вопроса } cout << s1+' ';//выводим измененную строку на экран return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.*; import java.lang.*; import java.io.*; class Str { public static void main (String[] args) throws java.lang.Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine(); StringBuffer sb = new StringBuffer(20); sb.append(s); String s1 = s; //запоминаем строку в переменную, которую будем изменять int k = 1; //счетчик, который будет увеличиваться после каждой вставки символа для того, чтобы вставлять символ именно после знака восклицания for (int i = 0; i < s.length(); i ++) if (s.charAt(i) == '!') sb.insert (i + k++, '?'); //вставляем в копию строки знаки вопроса System.out.println(sb);//выводим измененную строку на экран } } |
А какова сложность алгоритма? Судя по всему, она равна O(n * Insert(n)). То есть, она упирается в сложность операции Insert. А ее сложность, сдается мне, тоже O(n). Итого имеем O(n^2). А хотелось бы линию.
Я конечно могу похвалить Вас за использование класса StringBuffer. Но sb.insert (i + k++, '?'); мало того, что не самая простая и понятная конструкция, так еще и медленная. Процитирую все еще актуальный комментарий Олега Петрова «А какова сложность алгоритма? Судя по всему, она равна O(n * Insert(n)). То есть, она упирается в сложность операции Insert. А ее сложность, сдается мне, тоже O(n). Итого имеем O(n^2). »
Если Вы хотите посимвольно обрабатывать строку, постарайтесь обойтись операцией добавления только в конец StringBuffer — т.е. операция append (т.е. по очереди добавлять символы строки и знак ? когда нужно).
Но можно сделать и попроще — вдруг есть метод класса который все сделает сам? (подсказка: какой-то из вариантов replace).