τα στοιχεία επικοινωνίας μου
Ταχυδρομείο[email protected]
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 δεν θα αλλάξει .
Τέλος, το 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, εφαρμόστε μια βασική αριθμομηχανή για να υπολογίσετε και να επιστρέψετε την τιμή της.
Επέκταση βραχίονα + στοίβα
Εκτός από τους αριθμούς και τις παρενθέσεις, οι συμβολοσειρές έχουν μόνο δύο τελεστές: το σύμβολο συν και το σύμβολο μείον.
Επομένως, εάν επεκτείνετε όλες τις παρενθέσεις σε μια παράσταση, οι ίδιοι οι αριθμοί δεν θα αλλάξουν στη νέα παράσταση που προκύπτει, αλλά θα αλλάξει μόνο το σύμβολο μπροστά από κάθε αριθμό.
Πρέπει να διατηρηθεί ένα stack ops, στο οποίο το επάνω στοιχείο της στοίβας καταγράφει το σύμβολο κάθε αγκύλης στην τρέχουσα θέση.
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;
}
};