코딩테스트/LeetCode

[LeetCode] 45. Jump Game II

auto size = nums.size();if (size == 1) return 0;int ans = 1, end = nums[0], far = nums[0];for (int i = 0; i = size - 1) break; }}return ans;

[LeetCode] 55. Jump Game

bool canJump(vector& nums) { int idx = nums.size() - 1; if (idx == 0) return true; for (int i = idx - 1; i >= 0; i--) { if (nums[i] + i >= idx) idx = i; } return idx == 0;}

[LeetCode] 136. Single Number

로직은 단순하다map에 파라미터로 넘어오는 nums의 개수를 파악하고이후 새로운 벡터를 초기화한 후 오름차순 정렬using IntPair = pair;class Solution{public: int singleNumber(vector& nums) { map m; for (auto& item : nums) m[item]++; vector v(m.begin(), m.end()); sort(v.begin(), v.end(), [&](const IntPair& left, const IntPair& right) -> bool { return left.second  xor 방식int singleNumber(vector& nums) { int ans=0; for(auto& it..

[LeetCode] 1 - Two Sum

class Solution { public: vector twoSum(vector& nums, int target) { unordered_map m; // 예시 2,7,11,15 / 9 for (int i = 0; i 2 : 0 * 9 - 7 = 2 > 2가 존재 * nums[i]=7 > 1, 9 * * int idx = target - nums[i]; if (m.find(idx) == m.end()) m[nums[i]] = i; else return { m[idx],i }; */ /* * 솔루션 2) 해당 값을 조합 * * 9 - 2 = 7 * m에 7이 없음 > m[2] = 0 * * 9 - 7 = ..

[LeetCode] 6 - Zigzag Conversion

class Solution { public: string convert(string s, int numRows) { string res; vector v(numRows); auto iter = s.begin(); int idx = 0; bool flag = true; // 1일 때 항상 일치함 if (numRows == 1) return s; // s의 시작점부터 실행 // 로직) 끝에 다다랐을 때 방향을 지정 while (iter != s.end()) { v[idx].push_back(*iter); idx = (flag) ? idx + 1 : idx - 1; if (idx == numRows - 1 || idx == 0) flag = !flag; iter++; } for (const auto& item..

[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] 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; }