전체 글
-
[leetcode] 239. Sliding Window Maximum알고리즘 2021. 4. 16. 09:43
간만에 하드 문제를 풀어보았다. 문제를 보고선 바로 아래와 같은 풀이를 생각했다. 타임아웃이 예상되었지만, 자비로운 리트코드기에 굉장히 떨어지는 성능으로 통과 시켜줄거라 생각햇지만,, 역시 실패 소스 보시면 아시겠지만 단순하게 우선순위큐를 계속 생성해서 max 값을 리턴하게 해두었다. class Solution { public: vector maxSlidingWindow(vector& nums, int k) { vector ret; for(int i = 0; i = k - 1){ ret.push_back(que.front()); if(que.front() == nums[i - k + 1]){ que.pop_front(); } } } return ret; } }; while문에서 최악의 경우 시간을 좀 잡..
-
-
[leetcode] 26. Remove Duplicates from Sorted Array알고리즘 2021. 4. 14. 20:58
class Solution { public: int removeDuplicates(vector& nums) { int size = nums.size(); for(int i = 0; i 0 && nums[0] == tmp){ i++; nums.erase(nums.begin()); } nums.push_back(tmp); i--; } return nums.size(); } }; 인라인으로 풀라는 조건이 있길래 생각나는대로 배열 뒤에 원소를 붙이고 지나간 원소들은 삭제처리했다. 중간중간에 계속 삭제처리를 해서 타임아웃을 예상했는데 아슬아슬하게 통과되었다. discuss를 보니 좀 더 효율적인 방법이 있던데 아래와 같다. 내 소스가 훨씬 직관적!!! 이라고 말하고 싶다만 역시 효율적인 아래소스가 정해로 보인다...
-
[leetcode] 86. Partition List알고리즘 2021. 4. 14. 19:54
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* ret = new ListNode(); ListNode* dummy = ret; ListNode* bigger = new ListNode(..
-
[leetcode] 130. Surrounded Regions알고리즘 2021. 4. 8. 17:28
class Solution { public: vector visited; vector answer; int mvX[4] = {0,0,1,-1}; int mvY[4] = {1,-1,0,0}; void DFS(int i, int j, vector& board){ if(visited[i][j]) return; visited[i][j] = 1; answer[i][j] = 'O'; for(int k = 0; k= visited.size() || newJ = visited[0].size()) continue; if(board[newI][newJ] == 'O') DFS(newI, newJ, board); } } void solve(vector& board) { visited.assign(boa..
-
[leetcode] 304. Range Sum Query 2D - Immutable알고리즘 2021. 4. 8. 13:14
class NumMatrix { public: vector dp; NumMatrix(vector& matrix) { dp.assign(matrix.size(), vector(matrix[0].size(), 0)); for(int i = 0; i= 0 ? dp[i][j - 1] : 0) - ((i - 1 >= 0 && j - 1 >= 0) ? dp[i - 1][j - 1] : 0) + matrix[i][j]; } } } int sumRegion(int row1, int col1, int row2, int col2) { return dp[row2][col2] - (row1 - 1 >= 0 ? dp[row1 - 1][col2] : 0) - (col1 - 1 >= 0 ? dp[row2][col1 - 1] : 0..
-
[LEETCODE] 34. Find First and Last Position of Element in Sorted Array알고리즘 2021. 4. 8. 10:43
class Solution { public: vector searchRange(vector& nums, int target) { if(nums.size() == 0) return {-1, -1}; int left = 0; int right = nums.size() - 1; while(left target){ right = (left + right)/2 - 1; } else { left = (left + right)/2 + 1; } } // cout
-
[leetcode] 84. Largest Rectangle in Histogram알고리즘 2021. 3. 29. 20:53
class Solution { public: int largestRectangleArea(vector& heights) { stack st; heights.push_back(0); int n = heights.size(), area = 0; for(int i = 0; i heights[i]){ int h = heights[st.top()]; st.pop(); int j = st.empty() ? -1 : st.top(); area = max(area, h * (i - j - 1)); } st.push(i); } return area; } }; 제가 구현한 O(n^2) 풀이는 각각의 인덱스마다 해당 인덱스가 부분적..