Leetcode Weekly Contest 47
這場很幸運拿到第二名～
給你一個長度為 $n$ 的陣列，請你判斷是否能夠藉由修改至多一個數字，使得整個陣列是非遞減的。
這題可以利用 Greedy 解決。當我們發現第一個 $i$ 使得 $a_i > a_{i+1}$ 的時候，顯然這兩個數字之間至少要有一個數字被修改。 如果修改了 $a_{i+1}$，那顯然為了讓後面的數字能夠接上，又不違背非遞減的條件，把這個數字修改成 $a_i$ 最為恰當。 另一方面，如果能修改 $a_i$，把它變成 $a_{i+1}$ 顯然更好，但這有條件：$a_{i+1} \ge a_{i-1}$ 才行。
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n = (int)nums.size(), cnt=0;
for(int i=0;i+1<n;i++) if(nums[i] > nums[i+1]) {
++cnt;
if(i>0 && nums[i+1] < nums[i-1]) nums[i+1] = nums[i];
else nums[i] = nums[i+1];
}
return cnt<=1;
}
};
一棵高度小於 5 的二元樹上的每一個節點都可以用三位數字來表示：DPV。
其中 D 指的是深度、P 指的是同一個深度由左而又的位置、V 則是這個節點的數值。
給一棵樹上所有節點的數值，請算出所有從樹根到樹葉的路徑上，所有節點數值總和的總和。
由於最多只有 15 個節點，我們可以不必把樹重建出來，直接用算的就好： 第一步先找出所有樹葉（也就是沒有後繼的節點），第二步把每個樹葉的每個祖先數值各加一遍。 所以我們可以利用一個簡單的函式判斷，給定兩個節點 $x=D_xP_xV_x$ 以及 $y=D_yP_yV_y$，判斷 $x$ 是否為 $y$ 的祖先。
判斷的方法很有趣：我們把比較深的那個節點，每次找出他的父節點，直到深度相同即可。
class Solution {
public:
bool is_ancestor(int &x, int &y) {
int Dx=x/100, Dy=y/100;
int Px=x%100/10, Py=y%100/10;
if(Dx>Dy) return false;
while(Dy>Dx) {--Dy; Py=(Py+1)/2; }
if(Px!=Py) return false;
return true;
}
int pathSum(vector<int>& nums) {
int cnt[32]={};
int non_leaf[32]={};
int n = (int)nums.size();
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i!=j && is_ancestor(nums[i], nums[j])) non_leaf[i]=1;
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(!non_leaf[j] && is_ancestor(nums[i], nums[j])) cnt[i]++;
}
}
int ret=0;
for(int i=0;i<n;i++) ret += cnt[i] * (nums[i]%10);
return ret;
}
};
給定 $n$ 以及 $k$，請構造一個 $1$ 到 $n$ 的全排列，使得排列中相鄰兩個數字差的絕對值恰好有 $k$ 種不同的值。$1\le k < n\le 10^4$。
若我們按照 $1, n, 2, n-1, \ldots$ 的方式排列，那他們間隔就是 $n-1, n-2, \ldots$ 全部都不同。 因此我們只要把後半（或前半）$k$ 個數字改成遞增（或遞減），因此後半（或前半）間隔全部都是 $1$。
class Solution {
public:
vector<int> constructArray(int n, int k) {
vector<int> ret;
ret.push_back(1);
for(int i=2,j=n;i<=j;i++,j--) {
ret.push_back(j);
if(i!=j) ret.push_back(i);
}
sort(ret.begin()+(k-1), ret.end());
if(k>1 && ret[k-2]<=n/2) {
reverse(ret.begin()+(k-1), ret.end());
}
return ret;
}
};
給你 $m, n, k$，請找出從 $\{1\times 1, \ldots, m\times n\}$ 總共這 $m\times n$ 個數字之中第 $k$ 小的數字。
對答案 $X$ 二分搜，然後對於每一排可以快速算出有幾個數字 $\le X$。
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int L=1, R=m*n, M, ans=0;
if(m>n) swap(m, n);
while(L<=R) {
M=(L+R)/2;
int w=0;
for(int i=1;i<=m;i++) w += min(n, M/i);
if(w>=k) { ans=M; R = M-1; }
else L = M+1;
}
return ans;
}
};