Leetcode Weekly Contest 37
這次比賽寫得異常順手…滿驚訝的其實。 邁向 T-shirt 之路前進吧！
給你 $m$ 個陣列 $(m\ge 2)$，每一個陣列依照由小到大的順序排好了。 請你從兩個不同的陣列中找出兩個數字，使得這兩個數字的差距最大。 全部陣列加起來只有不超過 $10000$ 個數字，所有數字的範圍都在 $[-10000, 10000]$ 之間。
一開始有點緊張，結果就沒看到每個陣列已經排好這個條件。
我的作法是先把所有數字通通塞進一個 multiset $S$ 裡面，然後每一次考慮一個陣列：先把這個陣列數字從整個大 set 移除，然後枚舉這個陣列裡頭所有數字，跟 $S$ 裡面的數字比較、接著再把這些數字塞回去。
但其實有更乾淨的 one-pass 作法：我們維護到前一條陣列為止的最小值和最大值，然後每一次都拿現在這條陣列的最大值與最小值去計算最大差。
class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
multiset<int> s;
for(auto &x: arrays) {
for(auto &&y: x) s.insert(y);
}
int ans=0;
for(auto &x: arrays) {
for(auto &&y: x) s.erase(s.find(y));
for(auto &&y: x) {
ans = max(ans, y-*s.begin());
}
for(auto &&y: x) s.insert(y);
}
return ans;
}
};
給你一棵二元樹的樹根 root，以及兩個數字 v 和 d，請你在所有深度為 d 的非空子樹插入值為 v 的節點，並且回傳新的樹根。
更仔細地說，若 d=1，那麼我們會把 v 放在新的樹根位置，而舊樹根舊會是它的左子樹。若 d>1，那麼我們首先查看所有深度為 d-1 的子樹：若該子樹非空，我們新增兩個數值為 v 的節點，並且把原本的左子樹接在左節點上、右子樹接在右節點上。
這種題目還是看圖比較有用吧。還滿幸運的，如果錯了一次就會 debug 很久。多用幾個 if 總是比較清晰明瞭的。
class Solution {
public:
void go(TreeNode *root, int cur, int v, int d) {
if(root == NULL) return;
if (cur == d-1) {
TreeNode *nl = new TreeNode(v);
nl->left = root->left;
TreeNode *nr = new TreeNode(v);
nr->right = root->right;
root->left = nl;
root->right = nr;
return;
} else {
go(root->left, cur+1, v, d);
go(root->right, cur+1, v, d);
}
}
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if(root == NULL) return root;
if(d==1) {
TreeNode *nr = new TreeNode(v);
nr->left = root;
return nr;
} else {
go(root, 1, v, d);
return root;
}
}
};
給一個正整數 $a$，請找出最小的正整數 $b$ 使得 $b$ 寫成十進位以後每一個位數乘起來會恰好等於 $a$。 如果不存在 $b$ 或是最小的正整數 $b$ 超出 32-bit 有號整數的範圍，就輸出 $0$。
這題以前好像在哪裡看過。印象中 greedy 可以解。 基本上因為數字都不超過 $9$，所以可以 Greedy 從 $9$ 枚舉到 $2$，只要能除得盡 $a$ 就除，這樣可以得到最小的數字(反過來)。
這題最心機的地方是 $a=1$ 的時候要記得輸出東西 $b=1$，此外用 long long 來處理會比較好。當然用 python 會更方便。
class Solution {
public:
int smallestFactorization(int a) {
if (a==1) return 1;
vector<int> ans;
for(int i=9;i>=2;i--) {
while(a%i==0) {
a/=i;
ans.push_back(i);
}
}
if(a>1) return 0;
long long ret = 0;
for(int i=(int)ans.size()-1;i>=0;i--) {
ret = ret * 10 + ans[i];
if (ret >= (1LL<<31))
return 0;
}
return (int)ret;
}
};
CPU 要執行一些給定的工作，每一種工作都用一個大寫英文字母 A-Z 代表。不同的工作用不同的英文字母表示。這些工作可以依照任意順序執行，但有一個奇妙的規定：相同的工作執行的時間點必須要間隔 $n$ 個單位時間。請問從第一個工作執行開始，總共要多少時間才可以執行完所有工作？
這題由於數字範圍不大，可以直接依照時間點 $t=1, 2, \ldots$ 一個個模擬，對於每一個時間點我們暴力找尋當前剩下最多數量的工作，並且把它做掉。如果 $n$ 再大一些我們就必須要使用 priority queue 之類的東西了。
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int t = 0;
int cnt[128] = {};
int prev[128] = {};
for(int i=0;i<='Z';i++) prev[i] = -n-1;
for(auto &&x: tasks) {
cnt[(int)x]++;
}
int all=(int)tasks.size();
while(all>0) {
int best=0;
for(int i='A';i<='Z';i++) if(cnt[i] > 0 && cnt[i] > cnt[best] && prev[i] + n + 1 <= t) {
best = i;
}
if(best) {
--cnt[best];
prev[best] = t;
--all;
}
++t;
}
return t;
}
};
總結：總覺得後面兩題的 greedy 作法需要稍微在腦袋大膽地猜下去。