[LeetCode] Weekly Contest 283 復習
はじめに
LeetCode Weekly Contest 283 の復習記事です。
2194. Cells in a Range on an Excel Sheet
難易度
Easy
アプローチ
問題文が長々と書いてありますが、単純に二重ループを使うだけの問題です。
解答
class Solution {
public:
vector<string> cellsInRange(string s) {
vector<string> res;
for (char i = s[0]; i <= s[3]; i++) {
for (char j = s[1]; j <= s[4]; j++) {
res.push_back(string(1, i) + string(1, j));
}
}
return res;
}
};
2195. Append K Integers With Minimal Sum
与えらえた配列numsに存在しない数値をk個追加し、追加した数値の合計値が最小になる合計値を求める問題です。
難易度
Medium
アプローチ
まず、この問題を解くには高校数学の等差数列を知っておく必要があります。
numsの取り得る範囲が1 <= nums[i] <= 10^9なので、配列に存在しない値を値が小さい方がから探していくとTLEになります。なので、もう少し工夫をする必要があります。
公差がd、初項がaとしたときに、諸侯から第n項までの和はn / 2 * {2 * a + (n - 1) * d}となります。
まずはnums配列をソートします。その上で各要素をスキャンしながら、nums[i]からnums[i + 1]までの区間の値の累積和を取っていきます。今回のケースにおいては、公差は1と見なすことが出来るため、上記の等差数列の和は、n * a + n * (n - 1) / 2と変換することが出来ます。
解答
この問題の意地悪な所（エッジケース）は、nums配列に同じ数値が入っている場合を考慮するために、setを使って入力配列のデータをユニークにする必要がある事です。
class Solution {
public:
long long minimalKSum(vector<int>& nums, int k) {
long long res = 0;
uint64_t prev = 1;
for (auto x : set<int>(nums.begin(), nums.end())) {
uint64_t n = min((uint64_t)k, x - prev);
res += n * prev + n * (n - 1) / 2;
k -= n;
if (k <= 0) {
break;
}
prev = x + 1;
}
if (k > 0) {
uint64_t n = k;
res += n * prev + n * (n - 1) / 2;
}
return res;
}
};
2196. Create Binary Tree From Descriptions
与えられる配列descriptionsのフォーマットに従い、バイナリツリーを構築する問題です。実装は綺麗に出来なかったものの、個人的には2問目よりもこちらの方が簡単に思いました。
難易度
Medium
アプローチ
解法はいくつか存在すると思いますが、ここではdescriptionsで与えられるノード情報をスキャンしながら、未作成のノードであればノードを新規作成しつつツリーを構成していき、最後にrootになるノードを見つけるO(N)のアプローチで解きます。
解答
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
unordered_map<int, TreeNode*> seen;
unordered_set<int> children;
for (auto& x : descriptions) {
auto par = x[0];
auto child = x[1];
auto isLeft = x[2];
if (seen.find(par) == seen.end()) {
seen[par] = new TreeNode(par);
}
if (seen.find(child) == seen.end()) {
seen[child] = new TreeNode(child);
}
if (isLeft) {
seen[par]->left = seen[child];
} else {
seen[par]->right = seen[child];
}
children.insert(child);
}
for (auto& x : descriptions) {
auto par = x[0];
if (children.find(par) == children.end()) {
return seen[par];
}
}
return nullptr;
}
};
2197. Replace Non-Coprime Numbers in Array
難易度
Hard
アプローチ
完全に数学問題です。また、以下のヒントが与えられているため、素直に愚直にやるだけの下手するとEasyレベルの問題かもしれません。一方、なぜ以下が成り立つのかは、数学的なバッググラウンドが必要そうです…。
It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.
また、LCM（最小公倍数）はGCD（最大公約数）から求めることが出来るという数学の知識を押さえておく必要があります。
LCM(a, b) = (a * b) / GCD(a, b)
解答
class Solution {
public:
vector<int> replaceNonCoprimes(vector<int>& nums) {
vector<int> res;
for (auto& x : nums) {
res.push_back(x);
while (res.size() > 1 && gcd(res[res.size() - 1], res[res.size() - 2]) > 1) {
auto a = res[res.size() - 1];
auto b = res[res.size() - 2];
auto g = gcd(a, b);
res.pop_back();
res.pop_back();
res.push_back((uint64_t)a * b / g);
}
}
return res;
}
};
Discussion