릿코드(LEETCODE)
weekly-contest-187
cepiloth
2020. 5. 5. 20:55
반응형
https://leetcode.com/contest/weekly-contest-187/
1번 문제 - 1436. Destination City
https://leetcode.com/contest/weekly-contest-187/problems/destination-city/
문자열 배열 [["B","C"],["D","B"],["C","A"]] 일때
D->B->C->A 로 경로를 나타낼 수 있다. 마지막 최종 경로인 A 를 출력 하는 문제이다.
시작점과 끝점은 1 번만 나오게 된다.
class Solution {
public:
// 마지막은 항상 뒤에 있음으로
string destCity(vector<vector<string>> & paths) {
map<string, pair<int,int>> m;
for (int i = 0; i < paths.size(); i++) {
for (int j = 0; j < paths[i].size(); j++) {
if (j == 0) {
m[paths[i][j]];
m[paths[i][j]].first = 1;
}
if (j == 1) {
m[paths[i][j]];
m[paths[i][j]].second = 1;
}
}
}
string sol;
for (auto a : m) {
pair<int, int> p = a.second;
if (p.first == 0 && p.second == 1) {
sol = a.first;
break;
}
}
return sol;
}
};
2번 문제 - 1437. Check If All 1's Are at Least Length K Places Away
1 과 1 사이에 거리가 k 보다 작다면 false
class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
vector<int> arr;
int size = nums.size();
int i = 0;
while (size != i) {
if (nums[i] == 0) {
int cand = 0;
for (int j = i; j < nums.size(); j++) {
if (nums[j] == 0) {
cand++;
}
else {
break;
}
}
arr.push_back(cand);
i += cand;
}
else {
i++;
}
}
for (int i = 0; i<arr.size(); i++) {
if (arr[i] < k)
return false;
}
return true;
}
};
3번 문제 - 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int i = 0, j;
multiset<int> m;
for (j = 0; j < A.size(); ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
}
return j - i;
}
};
반응형