моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Фраза считается палиндромом, если она читается одинаково в прямом и обратном порядке после преобразования всех символов верхнего регистра в нижний регистр и удаления всех небуквенно-цифровых символов.
class Solution {
public:
bool isPalindrome(string s) {
int left = 0;
int right = s.size()-1;
while(left < right){
while(left < right && !isalnum(s[left])){
left++;
}
while(left < right && !isalnum(s[right])){
right--;
}
if(left < right && tolower(s[left]) != tolower(s[right])){
return false;
}
left++;
right--;
}
return true;
}
};
Учитывая строки s и t, определите, является ли s подпоследовательностью t.
Подпоследовательность относится к новой строке, образованной путем удаления некоторых символов из исходной строки без изменения относительных положений остальных символов.
двойной указатель
Инициализируйте два указателя i и j, указывающие на начальные позиции s и t соответственно.
Для каждого жадного сопоставления, если сопоставление прошло успешно, i и j будут одновременно сдвинуты вправо, что соответствует следующей позиции s. Если совпадение не удалось, j будет сдвинуто вправо, а i не изменится. .
Наконец, я перемещаюсь в конец s, указывая, что s является подпоследовательностью t.
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.size();
int m = t.size();
int sIndex = 0, tIndex = 0;
while(sIndex < n && tIndex < m){
if(s[sIndex] == t[tIndex]){
sIndex++;
tIndex++;
}else{
tIndex++;
}
}
return sIndex == n;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size()-1;
while(left < right){
int num = numbers[left] + numbers[right];
if(num == target){
return {left+1, right+1};
}else if(num < target){
left++;
}else{
right--;
}
}
return {0,0};
}
};
Между «до» и «после» нет отношения порядка, просто используйте двойные указатели.
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
sort(ransomNote.begin(), ransomNote.end());
sort(magazine.begin(), magazine.end());
int i = 0, j = 0, m = ransomNote.size(), n = magazine.size();
while(i<m && j<n){
if(ransomNote[i] == magazine[j]){
i++;
j++;
}else{
j++;
}
}
return i == m;
}
};
Хеш-таблица
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<int, int> count;
for(char c : magazine){
count[c]++;
}
for(char c : ransomNote){
if(count[c] == 0){
return false;
}else{
count[c]--;
}
}
return true;
}
};
множество
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int count[26] = {};
for(char c : magazine){
count[c-'a']++;
}
for(char c : ransomNote){
if(count[c-'a'] == 0){
return false;
}else{
count[c-'a']--;
}
}
return true;
}
};
Даны две строки s и t. Определите, изоморфны ли они.
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char, char> s2t;
unordered_map<char, char> t2s;
for(int i=0; i<s.size(); i++){
char x = s[i];
char y = t[i];
if((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)){
return false;
}
s2t[x] = y;
t2s[y] = x;
}
return true;
}
};
vector<string> splitString(string& str){
istringstream iss(str);
vector<string> res;
string word;
while(iss >> word){
res.push_back(word);
}
return res;
}
class Solution {
public:
vector<string> splitString(string s){
istringstream iss(s);
vector<string> res;
string word;
while(iss >> word){
res.push_back(word);
}
return res;
}
bool wordPattern(string pattern, string s) {
unordered_map<char, string> char2s;
unordered_map<string, char> s2char;
vector<string> words = splitString(s);
if(pattern.size() != words.size()){
return false;
}
for(int i=0; i<pattern.size(); i++){
char c = pattern[i];
string word = words[i];
if((char2s.count(c) && char2s[c] != word) || (s2char.count(word) && s2char[word] != c)){
return false;
}
char2s[c] = word;
s2char[word] = c;
}
return true;
}
};
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for(int i = 0; i<s.size(); i++){
char ch = s[i];
if(ch == '(' || ch == '[' || ch == '{'){
stk.push(ch);
}else{
if(stk.empty()){
return false;
}
char topCh = stk.top();
if((topCh =='[' && ch == ']') || (topCh =='(' && ch == ')') || (topCh =='{' && ch == '}')){
stk.pop();
}else{
return false;
}
}
}
return stk.empty();
}
};
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if(n % 2 == 1){
return false;
}
unordered_map<char, char> pairs = {
{']','['},
{'}','{'},
{')','('}
};
stack<char> stk;
for(char ch:s){
if(pairs.count(ch)){
if(stk.empty() || stk.top() != pairs[ch]){
return false;
}
stk.pop();
}else{
stk.push(ch);
}
}
return stk.empty();
}
};
Сначала мы разбиваем заданный путь к строке на список из нескольких строк в соответствии с /, записанных как имена.
Строки, содержащиеся в именах, могут быть только следующими:
Для пустых строк и точки обработка не требуется.
Для двух точек или имен каталогов необходим стек для хранения каждого имени каталога в пути. При встрече двух точек, пока стек не пуст, переключитесь на предыдущий уровень (вытолкните верхний каталог стека), а при обнаружении имени каталога поместите его в стек.
class Solution {
public:
vector<string> splitString(string &path){
vector<string> res;
string temp;
for(char c : path){
if(c == '/'){
res.push_back(temp);
temp.clear();
}else{
temp += c;
}
}
res.push_back(temp);
return res;
}
string simplifyPath(string path) {
vector<string> names = splitString(path);
vector<string> stk;
for(int i=0; i<names.size(); i++){
if(names[i] == ".."){
if(!stk.empty()){
stk.pop_back();
}
}else if(!names[i].empty() && names[i] != "."){
stk.push_back(names[i]);
}
}
string res;
if(stk.empty()){
res = "/";
}else{
for(int i=0; i<stk.size(); i++){
res += "/" + stk[i];
}
}
return res;
}
};
Спроектируйте стек, который поддерживает операции push, pop и top и может извлекать наименьший элемент за постоянное время.
Вспомогательный стек
class MinStack {
stack<int> stk;
stack<int> min_stk;
public:
MinStack() {
min_stk.push(INT_MAX);
}
void push(int val) {
stk.push(val);
min_stk.push(min(min_stk.top(), val));
}
void pop() {
stk.pop();
min_stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for(int i=0; i<tokens.size(); i++){
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
if(tokens[i] == "+"){
stk.push(num1 + num2);
}else if(tokens[i] == "-"){
stk.push(num1 - num2);
}else if(tokens[i] == "*"){
stk.push(num1 * num2);
}else{
stk.push(num1 / num2);
}
}else{
stk.push(stoi(tokens[i]));
}
}
return stk.top();
}
};
Учитывая строковое выражение s, реализуйте базовый калькулятор для вычисления и возврата его значения.
Расширение скобок + стек
Помимо чисел и круглых скобок, строки имеют только два оператора: знак плюс и знак минус.
Следовательно, если раскрыть все круглые скобки в выражении, сами числа в полученном новом выражении не изменятся, изменится только знак перед каждым числом.
Необходимо поддерживать операции стека, в которых верхний элемент стека записывает символ каждой скобки в текущей позиции.
1+2+(3-(4+5)):
class Solution {
public:
int calculate(string s) {
stack<int> ops;
ops.push(1);
int sign = 1;
int ret = 0;
int i = 0;
int n = s.size();
while(i < n){
if(s[i] == ' '){
i++;
}else if(s[i] == '+'){
sign = ops.top();
i++;
}else if(s[i] == '-'){
sign = -ops.top();
i++;
}else if(s[i] == '('){
ops.push(sign);
i++;
}else if(s[i] == ')'){
ops.pop();
i++;
}else{
long num = 0;
while(i < n && s[i] >= '0' && s[i] <= '9'){
num = num * 10 + s[i]-'0';
i++;
}
ret += sign * num;
}
}
return ret;
}
};