코딩테스트/LeetCode
[LeetCode] Remove All Adjacent Duplicates In String
string removeDuplicates(string str) { stack s; auto begin = str.begin(), end = str.end(); while (begin != end) { auto ch = *begin; if (!s.empty() && s.top() == ch) s.pop(); else s.push(ch); begin++; } str.clear(); while (!s.empty()) { str.push_back(s.top()); s.pop(); } reverse(str.begin(), str.end()); return str; }
[LeetCode] Excel Sheet Column Number
int titleToNumber(string columnTitle) { int sum = 0, time = 1; // A 대문자 아스키 코드는 65부터 시작 while (!columnTitle.empty()) { int val = columnTitle.back() - 64; if (sum == 0) sum += val; else sum += pow(26, time++) * val; columnTitle.pop_back(); } return sum; }
[LeetCode] Evaluate Reverse Polish Notation
알고리즘 풀땐 switch보단 if를 선호한다고 들었는데 사칙연산으로 인해 어쩔 수 없이 사용함. int evalRPN(vector& tokens) { stack s; for (const auto& ch : tokens) { int ans = 0; // 연산 if (!isdigit(ch[0]) && ch.size() == 1) { int n2 = s.top(); s.pop(); int n1 = s.top(); s.pop(); switch (ch[0]) { case '+': ans += n1 + n2; break; case '-': ans += n1 - n2; break; case '*': ans += n1 * n2; break; case '/': ans += n1 / n2; break; } s.push(..
[LeetCode] Rotate Array
void rotate(vector& nums, int k) { deque dq; for (int j = 0; j < nums.size(); j++) dq.push_back(nums[j]); nums.clear(); for (int i = 0; i < k; i++) { int val = dq.back(); dq.pop_back(); dq.push_front(val); } while (!dq.empty()) { nums.push_back(dq.front()); dq.pop_front(); } }
[LeetCode] Merge Sorted Array
void merge(vector& nums1, int m, vector& nums2, int n) { int idx = 0; for (int i = m; i < nums1.size(); i++) nums1[i] = nums2[idx++]; sort(nums1.begin(), nums1.end()); }
[LeetCode] Length of Last Word
매커니즘은 간단하다, 빈 공간을 찾아 위치를 갱신 해주기만 하면 된다. int lengthOfLastWord(string s) { auto start = s.begin(), end = s.end(); string tmp; for (; start != end; start++) { if (*start == ' ') { bool flag = false; for (auto sPos = start; sPos != s.end(); sPos++) { flag = (*sPos == ' '); if (!flag) { tmp = ""; start = sPos; break; } } } if (*start != ' ') tmp += *start; } return tmp.length(); }
[LeetCode] 17 - Letter Combinations of a Phone Number
class Solution { map digitComb { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; vector res; string digits; public: void DFS(int i = 0, string curStr = "") { if (curStr.size() == digits.size()) { res.push_back(curStr); return; } for (auto& c : digitComb[digits[i]]) DFS(i + 1, curStr + c); } vector letterCombinations(string digit..
[LeetCode] 34 - Find First and Last Position of Element in Sorted Array
lower_bound> 찾고자 하는 값의 첫 인덱스 upper_bound> 찾고자 하는 값보다 큰 첫 숫자의 인덱스 find 함수 활용해서 찾고자 하는 숫자가 있는지 확인 vector searchRange(vector& nums, int target) { auto begin = nums.begin(), end = nums.end(); int s = lower_bound(begin, end, target) - begin; int e = upper_bound(begin, end, target) - begin; if (find(begin, end, target) == end) return { -1,-1 }; return { s,e }; }