내 연락처 정보
우편메소피아@프로톤메일.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의 부분 수열인지 확인합니다.
하위 시퀀스는 나머지 문자의 상대적 위치를 변경하지 않고 원래 문자열에서 일부 문자를 삭제하여 형성된 새로운 문자열을 나타냅니다.
이중 포인터
각각 s와 t의 초기 위치를 가리키는 두 개의 포인터 i와 j를 초기화합니다.
각각의 탐욕스러운 일치에 대해 일치가 성공하면 i와 j가 동시에 오른쪽으로 이동하고 일치가 실패하면 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;
}
};
푸시, 팝, 상단 작업을 지원하고 일정한 시간에 가장 작은 요소를 검색할 수 있는 스택을 설계합니다.
보조 스택
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;
}
};