Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Una frase se considera palíndromo si, después de convertir todos los caracteres mayúsculos a minúsculas y eliminar todos los caracteres no alfanuméricos, la frase se lee igual al derecho y al revés.
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;
}
};
Dadas las cadenas s y t, determine si s es una subsecuencia de t.
Una subsecuencia se refiere a una nueva cadena formada eliminando algunos caracteres de la cadena original sin cambiar las posiciones relativas de los caracteres restantes.
doble puntero
Inicialice dos punteros i y j, apuntando a las posiciones iniciales de s y t respectivamente.
Para cada coincidencia codiciosa, si la coincidencia es exitosa, i y j se desplazarán hacia la derecha al mismo tiempo, coincidiendo con la siguiente posición de s. Si la coincidencia falla, j se desplazará hacia la derecha e i no cambiará. .
Finalmente, i se mueve al final de s, lo que indica que s es una subsecuencia de 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};
}
};
No existe una relación de orden entre el antes y el después, solo use punteros dobles.
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;
}
};
Tabla de picadillo
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;
}
};
formación
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;
}
};
Dadas dos cadenas s y t, determine si son isomorfas.
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();
}
};
Primero dividimos la ruta de cadena dada en una lista de varias cadenas según /, registradas como nombres.
Las cadenas contenidas en los nombres sólo pueden ser las siguientes:
Para cadenas vacías y un punto, no se requiere procesamiento.
Para dos puntos o nombres de directorio, se necesita una pila para mantener cada nombre de directorio en la ruta. Cuando encuentre dos puntos, siempre que la pila no esté vacía, cambie al nivel anterior (abre el directorio superior de la pila) y, cuando encuentre un nombre de directorio, colóquelo en la pila.
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;
}
};
Diseñe una pila que admita operaciones push, pop y top y que pueda recuperar el elemento más pequeño en tiempo constante.
Pila auxiliar
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();
}
};
Dada una expresión de cadena s, implemente una calculadora básica para calcular y devolver su valor.
Expansión de soporte + pila
Además de los números y los paréntesis, las cadenas sólo tienen dos operadores: signo más y signo menos.
Por lo tanto, si expande todos los paréntesis en una expresión, los números en sí no cambiarán en la nueva expresión resultante, solo lo hará el signo delante de cada número.
Es necesario mantener una operación de pila, en la que el elemento superior de la pila registra el símbolo de cada paréntesis en la posición actual.
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;
}
};
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]