Leetcode
[LeetCode] Sqrt(x)
class Solution { public: int mySqrt(int x) { int s = 0, e = x; int ans = 0; while (s x) e = mid - 1; else { ans = mid; s = mid + 1; } } return ans; } };
[LeetCode] 153. Find Minimum in Rotated Sorted Array
class Solution { public: int findMin(vector& a) { int low = 0; int high = a.size() - 1; while (low < high) { int mid = low + (high - low) / 2; if (a[mid] < a[high]) high = mid; else low = mid + 1; } return a[low]; } };
[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters
시간 복잡도) O(n * n2) 공간 복잡도) O(n) class Solution { public: int ans = 0; bool isUnique(string s) { set st(s.begin(), s.end()); return (st.size() == s.length()); } // 백트래킹 void solve(vector& arr, int index = 0, string s = "") { if (!isUnique(s)) return; ans = max(ans, (int)s.length()); for (int i = index; i < arr.size(); i++) solve(arr, i + 1, s + arr[i]); } int maxLength(vector& arr) { solve(arr); r..
[LeetCode] Majority Element
#include using Intpair = pair; class Solution { public: int majorityElement(vector& nums) { map m; for (const auto& item : nums) m[item]++; vector v(m.begin(), m.end()); sort(v.begin(), v.end(), [&](Intpair& lRef, Intpair& rRef) { return lRef.second < rRef.second; }); return (*(v.end() - 1)).first; } };
[LeetCode] Remove All Adjacent Duplicates in String II
string removeDuplicates(string str, int k) { stack s; auto begin = str.begin(), end = str.end(); while (begin != end) { auto ch = *begin; if (!s.empty()) { auto& top = s.top(); if (top.first != ch) s.push({ ch, 1 }); else top.second++; if (top.second == k) s.pop(); } else s.push({ ch, 1 }); begin++; } str.clear(); while (!s.empty()) { auto top = s.top(); for (int i = 0; i < top.second; i++) str...
[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] 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()); }