Массивы символов в C
Строки C ++
Массивы char в стиле C работают и в C ++. Однако C ++ предоставляет строку, которая намного мощнее массивов C.
Объявление строки:
string A; // declares an empty string
string A = "Hello"; // declares string initialized to "Hello".Доступ к i-му элементу:
A[i] // O(1)Размер (количество элементов) строки:
A.length() // O(1)Добавление к строке
Другая строка
A += "Hello"; // Appends Hello to the string. O(n) operationОдиночный персонаж
A.push_back('H'); // Append character H to the string.
// O(1) operation.Вопросы по моделированию струн
Вопрос 1: самый длинный общий префикс
Учитывая массив строк A, вам необходимо найти самую длинную строку S, которая является префиксом ВСЕ строк в массиве.
Самый длинный общий префикс для пары строк S1 и S2 - это самая длинная строка S, которая является префиксом обеих строк S1
и S2.
Например, самый длинный общий префикс "abcdefgh" и "abcefgh" - это "abc".
Например
Input 1: A = ["abcdefgh", "aefghijk", "abcefgh"] Output 1: "a" Explanation 1: Longest common prefix of all the strings is "a".Input 2: A = ["abab", "ab", "abcd"]; Output 2: "ab" Explanation 2: Longest common prefix of all the strings is "ab".
Решение:
Примечание: префикс должен быть префиксом ВСЕХ строк.
Итак, вы можете выбрать любую случайную строку из массива и начать проверку ее символов с самого начала, чтобы увидеть, могут ли они быть частью общей подстроки.
string Solution::longestCommonPrefix(vector<string> &strs) {
if (strs.size() == 0) return "";
string ans = "";
for (int i = 0; i < strs[0].length(); i++) {
// checking if character i qualifies to be in the answer.
bool isQualified = true;
for (int j = 1; j < strs.size(); j++) {
if (i >= strs[j].length() || strs[j][i] != strs[0][i]) {
isQualified = false;
break;
}
}
if (!isQualified) break;
ans.push_back(strs[0][i]);
}
return ans;
}Вопросы о строковом поиске
Вопрос 2: реализовать StrStr
strstr - найти подстроку (иголку) в строке (стоге сена).
Возвращает индекс первого появления иголки в стоге сена или -1, если иголка не является частью стога сена.
Решение:
Давайте сначала подумаем о более простой проблеме. Как узнать, равны ли две струны?
Реализация strstr - это простая симуляция.
Рассмотрим каждый индекс i для ответа. Определите, равны ли следующие две строки:
1) игольная нить и,
2) Нанизывайте стог сена из индекса i длиной, равной длине иглы.
Обратите внимание, что сложность этого решения составляет O (M * N), где M - длина стога сена, а N - длина иголки.
bool isEqual(const string A, const string B, int n, int m, int i) {
for(int j = 0; j < m; j ++)
if(A[j+i] != B[j])
return false;
return true;
}
int Solution::strStr(const string A, const string B) {
if(A.size() == 0 || B.size() == 0)
return -1;
int n = A.size();
int m = B.size();
for(int i = 0; i < (n-m+1); i ++)
if(isEqual(A, B, n, m, i))
return i;
return -1;
}Примечание: чтобы решить его за O (M), мы можем использовать алгоритм KMP:
Строковые хитрые вопросы
Вопрос 3: Минимум скобок!
Дана строка A круглых скобок ‘(‘ или ‘).’
Задача состоит в том, чтобы найти минимальное количество круглых скобок ‘(‘ или ‘)’ (в любых позициях), которые мы должны добавить, чтобы полученная строка скобок стала действительной.
Строка действительна, если:
- Открытые скобки должны быть закрыты соответствующей закрывающей скобкой.
- Открытые скобки должны быть закрыты в правильном порядке.
Ограничения проблемы
1 <= |A| <= 105
A[i] = ‘(‘ or A[i] = ‘)’
Формат ввода
Первый и единственный аргумент - строка A.
Формат вывода
Верните единственное целое число, обозначающее минимальное количество круглых скобок ‘(‘ или ‘)’ (в любых позициях), которые мы должны добавить в A, чтобы полученная строка скобок стала действительной.
Пример ввода
Вход 1:
A = "())"
Вход 2:
A = "((("
Пример вывода
Выход 1:
1
Выход 2:
3
Пример объяснения
Объяснение 1:
One '(' is required at beginning.
Объяснение 2:
Three ')' is required at end.
Решение:
Во-первых, попробуйте найти решение, чтобы проверить, действительна строка или нет.
Для каждого дополнительного ‘),’ нам нужно добавить соответствующий ‘(‘ в начале строки.
Мы отслеживаем баланс строки i: e, количество "(" минус число ")". Строка действительна, если ее баланс равен 0, каждый префикс имеет неотрицательный баланс.
Теперь рассмотрим баланс каждого префикса A. Если он когда-либо отрицательный (скажем, -1), мы должны добавить скобку '(' в начале. Также, если баланс S положительный (скажем, + P) , мы должны добавить P раз скобки ')' в конце.
Сложность времени: O (n), где n = A.length ()
int Solution::solve(string a) {
int openBrackets = 0, req=0;
for(int i=0;i<a.length();i++) {
if(a[i]=='(') {
openBrackets++;
} else {
if(openBrackets>0) openBrackets--;
else {
req++;
}
}
}
req+=openBrackets;
return req;
}Word Вопросы
Вопрос 4: Длина последнего слова
Если строка s состоит из букв верхнего / нижнего регистра и пробелов ' ', вернуть длину последнего слова в строке.
Если последнее слово не существует, вернитесь. 0.
Примечание. Слово определяется как последовательность символов, состоящая только из непробельных символов.
Пример:
Учитывая s = "Hello World",
вернуть 5 как length("World") = 5.
Решение:
Основной поворот здесь - отказ от использования библиотечных функций и обход строки только один раз.
Попробуйте ответить на эти вопросы, используя один цикл:
Как определить конец строки?
Как определить, где начинается слово?
Что, если вы сохранили длину текущего слова?
Вы сбрасываете длину слова, когда начинается следующее слово (Когда начинается новое слово?)
Верните последнюю длину, которая у вас есть.
int Solution::lengthOfLastWord(const string A) {
int cnt=0;
int i=A.length()-1;
while(A[i]==' ') //looping from last and encountering a first alphanumeric character
i--;
for(;i>=0 && A[i]!=' ';i--) //from that point to the first space encountered
cnt++;
return cnt;
}Вопросы по синтаксическому анализу строк
Вопрос 5: Атои
Реализуйте atoi для преобразования строки в целое число.
Пример:
Input : "9 2704"
Output : 9Решение:
Нам нужно обработать только четыре случая:
- Удаляет все ведущие пробелы
- Знак числа
- Переполнение
- Некорректный ввод
Обнаружить переполнение сложно. Было бы полезно, если бы вы обнаружили переполнение до того, как число собирается переполниться.
So:
- Если число положительное, а текущее число больше MAX_INT / 10, и вы собираетесь добавить цифру, ваше число обязательно выйдет за край.
- Если текущее число = MAX_INT / 10, то на основе последней цифры мы можем определить, будет ли число переполнено.
int atoi(const string &str) {
int sign = 1, base = 0, i = 0;
while (str[i] == ' ') { i++; }
if (str[i] == '-' || str[i] == '+') {
sign = (str[i++] == '-') ? -1 : 1;
}
while (str[i] >= '0' && str[i] <= '9') {
if (base > INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
if (sign == 1) return INT_MAX;
else return INT_MIN;
}
base = 10 * base + (str[i++] - '0');
}
return base * sign;
}Строковые математические вопросы
Вопрос 6: от римского к целому числу
Дана строка A, представляющая римское число.
Преобразуйте A в целое число.
A гарантированно находится в диапазоне от 1 до 3999.
Например
Input 1: A = "XIV" Output 1: 14Input 2: A = "XX" Output 2: 20
Решение:
Обратите внимание, как различаются числа XVI (10 + 5 + 1) и XIV (10–1 + 5).
В одном случае мы добавляем числовое значение буквы, а в других - вычитаем его. Как это можно смоделировать?
Главное - заметить, что буква с наибольшим значением всегда встречается в начале строки в допустимом римском числовом представлении.
Всякий раз, когда буква с меньшим значением предшествует букве с более высоким значением, это означает, что ее значение должно быть добавлено как отрицательное по отношению к значению этой буквы.
Во всех остальных случаях значения добавляются.
