leetcode12 [C++][leetcode] Contiguous Array :: seoftware "Time Limit Exceeded" 시간 초과가 난 코드 모든 가능한 경우의 수를 고려하려고 하니까 시간 초과가 발생한다. class Solution { public: int findMaxLength(vector& nums) { int max_length = 0; for(int i = 0; i 2020. 4. 16. [C++][leetcode] Last Stone Weight :: seoftware 소스코드 class Solution { public: int lastStoneWeight(vector& stones) { if(stones.empty()) return 0; priority_queue pq; for(int i = 0; i 1) { int first = pq.top(); pq.pop(); int second = pq.top(); pq.pop(); if(first != second) pq.push(first-second); } return pq.size()==1?pq.top():0; } }; 1. 우선순위 큐 priority queue 를 사용해서 풀었다. pq를 사용하지 않고 while문 돌 때마다 sort를 수행해도 될 것 같다. 2. pq에 내림차순으로 stones에 있는 원소들을 넣는.. 2020. 4. 13. [C++][leetcode] Diameter of Binary Tree :: seoftware 소스코드 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { int max; void maxDepth(TreeNode* root) { if (root == NULL) { return; } max = std::max(max, height(root->left) + height(root->right)); maxDepth(root->left); maxDepth(root->right); } int height(TreeNode* ro.. 2020. 4. 12. [C++][leetcode] Min Stack :: seoftware 소스코드 class MinStack { stack elements; stack sorted; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { elements.push(x); if(sorted.empty() || sorted.top() >= x) sorted.push(x); } void pop() { if(elements.empty()) return; if(sorted.top() == elements.top()) sorted.pop(); elements.pop(); } int top() { return elements.top(); } int getMin() { return sorted.top(); } .. 2020. 4. 12. [c++][leetcode] Backspace String Compare :: seoftware #은 앞에 문자를 지우는 역할이다. #이 자기 역할을 모두 수행하고 난 후의 문자열을 비교하는 문제 소스코드 class Solution { public: bool backspaceCompare(string S, string T) { stack s_st, t_st; for(int i = 0; i < S.length(); i++){ if(S[i] != '#') s_st.push(S[i]); else if(!s_st.empty()){ s_st.pop(); } } for(int i = 0; i < T.length(); i++){ if(T[i] != '#') t_st.push(T[i]); else if(!t_st.empty()){ t_st.pop(); } } if(s_st.empty() && t_st.empty(.. 2020. 4. 10. [C++][leetcode] Middle of the linked list :: seoftware 소스코드 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { int sz = 0; ListNode *cur = head; while(cur != NULL){ sz++; cur = cur->next; } sz /= 2; cur = head; for(int i = 0; inext; } return cur; } }; head가 포인터이므로 cur도 포인터로 선언해야 한다! 2020. 4. 9. [c++][leetcode] Counting Elements :: seoftware 소스코드 class Solution { public: int countElements(vector& arr) { int answer = 0; unordered_map cnt; for(int i : arr){ cnt[i]++; } for(int i = 0; i 0 && cnt[i+1] > 0){ answer += cnt[i]; } } return answer; } }; unordered_map을 이용하여 arr에 있는 값을 인덱스(i)로 하여 cnt[i] 를 ++해준다. 2020. 4. 7. [C++][leetcode] Best Time to Buy and Sell Stock II :: seoftware 문제 접근방법 prices의 한 원소가 다음 원소와의 차이를 계산하여 양수이면 더해주고 음수이면 넘어간다. 양수이면 가격이 오르는거니까 현재 원소가 buy 가격, 다음 원소가 sell 가격이 된다. 소스코드 class Solution { public: int maxProfit(vector& prices) { int answer = 0; if(prices.size() 0) answer += (prices[i+1] - prices[i]); } return answer; } }; 1. prices의 원소가 1개 이하인 경우에는 buy 와 sell 을 진행하지 않으므로 0을 리턴한다. (이 조건 없으면 런타임 에러) 2. 0부터 전체개수 -1 까지의 모든 가격을 바로 다음 가격과 비교한다. 만약 양수이면 ans.. 2020. 4. 5. [C++][leetcode] Move Zeros :: seoftware 문제 접근방법 1. 0이 아닌 숫자들은 배열의 앞에서부터 채워나가고 0이면 넘어간다. 2. 1번을 하고 남은 배열의 인덱스는 모두 0으로 채운다. 소스코드 class Solution { public: void moveZeroes(vector& nums) { int idx = 0; for(int i : nums){ if(i != 0) { nums[idx] = i; idx++; } } for(int i =idx; i 2020. 4. 5. 이전 1 2 다음
