LeetCode 周賽 364
T1. 最大二進制奇數(shù)（Easy）
- 標(biāo)簽：貪心
T2. 美麗塔 I（Medium）
- 標(biāo)簽：枚舉卖毁、前后綴分解揖曾、單調(diào)棧
T3. 美麗塔 II（Medium）
- 標(biāo)簽：枚舉、前后綴分解亥啦、單調(diào)棧
T4. 統(tǒng)計樹中的合法路徑數(shù)目（Hard）
- 標(biāo)簽：DFS翩肌、質(zhì)數(shù)
T1. 最大二進制奇數(shù)（Easy）
https://leetcode.cn/problems/maximum-odd-binary-number/description/
題解（模擬）
簡單模擬題，先計算 的個數(shù)禁悠，將其中一個
置于最低位，其它
置于最高位：
class Solution {
fun maximumOddBinaryNumber(s: String): String {
val cnt = s.count { it == '1' }
return StringBuilder().apply {
repeat(cnt - 1) {
append("1")
}
repeat(s.length - cnt) {
append("0")
}
append("1")
}.toString()
}
}
class Solution:
def maximumOddBinaryNumber(self, s: str) -> str:
n, cnt = len(s), s.count("1")
return "1" * (cnt - 1) + "0" * (n - cnt) + "1"
class Solution {
public:
string maximumOddBinaryNumber(string s) {
int n = s.length();
int cnt = 0;
for (auto& e : s) {
if (e == '1') cnt++;
}
string ret;
for (int i = 0; i < cnt - 1; i++) {
ret.push_back('1');
}
for (int i = 0; i < n - cnt; i++) {
ret.push_back('0');
}
ret.push_back('1');
return ret;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
線性遍歷兑宇；
- 空間復(fù)雜度：
不考慮結(jié)果字符串碍侦。
T2. 美麗塔 I（Medium）
https://leetcode.cn/problems/beautiful-towers-i/description/
同 T3. 美麗塔 I
T3. 美麗塔 II（Medium）
https://leetcode.cn/problems/beautiful-towers-ii/description/
問題分析
初步分析：
- 問題目標(biāo)： 構(gòu)造滿足條件的方案，使得數(shù)組呈現(xiàn)山狀數(shù)組隶糕，返回元素和瓷产；
- 方案條件： 從數(shù)組的最大值向左側(cè)為遞減，向右側(cè)也為遞減枚驻。
思考實現(xiàn)：
- 在 T2. 美麗塔 I（Medium） 中的數(shù)據(jù)量只有
，我們可以枚舉以每個點作為山峰（數(shù)組最大值）的方案再登，從山頂依次向兩側(cè)遞減尔邓，使得當(dāng)前位置不高于前一個位置晾剖，整體的時間復(fù)雜度是
；
- 在 T3. 美麗塔 II（Medium） 中數(shù)據(jù)量有
梯嗽，我們需要思考低于平方時間復(fù)雜度的方法齿尽。
思考優(yōu)化：
以示例 [6,5,3,9,2,7] 為例，我們觀察以 和
作為山頂?shù)膬蓚€方案：
以 3 作為山頂：
3 3 |3 3| 2 2
以 9 作為山頂
3 3 |3 9| 2 2
可以發(fā)現(xiàn)：以 作為山頂?shù)淖髠?cè)與以
為山頂?shù)挠覀?cè)在兩個方案之間是可以復(fù)用的灯节，至此發(fā)現(xiàn)解決方法：我們可以分別預(yù)處理出以每個節(jié)點作為山頂?shù)那熬Y和后綴的和：
-
表示以
作為山頂時左側(cè)段的前綴和循头；
-
表示以
那么炎疆，最佳方案就是 的最大值卡骂。 現(xiàn)在，最后的問題是如何以均攤
的時間復(fù)雜度計算出每個元素前后綴的和形入？
思考遞推關(guān)系：
繼續(xù)以示例 [6,5,3,9,2,7] 為例：
- 以
為山頂全跨，前綴為
- 以
為山頂，需要保證左側(cè)元素不大于
- 以
為山頂，需要保證左側(cè)元素不大于
- 以
為山頂，需要保證左側(cè)元素不大于
- 以
為山頂，需要保證左側(cè)元素不大于
- 以
為山頂绍赛，需要保證左側(cè)元素不大于
提高抽象程度：
觀察以上步驟吗蚌，問題的關(guān)鍵在于修改操作：由于數(shù)組是遞增的，因此修改的步驟就是在「尋找小于等于當(dāng)前元素 的上一個元素」纯出，再將中間的元素削減為
蚯妇。「尋找上一個更小元素」暂筝，這是單調(diào)棧的典型場景箩言。
題解一（枚舉）
枚舉以每個元素作為山頂?shù)姆桨福?/p>
class Solution {
fun maximumSumOfHeights(maxHeights: List<Int>): Long {
val n = maxHeights.size
var ret = 0L
for (i in maxHeights.indices) {
var curSum = maxHeights[i].toLong()
var pre = maxHeights[i]
for (j in i - 1 downTo 0) {
pre = min(pre, maxHeights[j])
curSum += pre
}
pre = maxHeights[i]
for (j in i + 1 ..< n) {
pre = min(pre, maxHeights[j])
curSum += pre
}
ret = max(ret, curSum)
}
return ret
}
}
class Solution:
def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
n, ret = len(maxHeights), 0
for i in range(n):
curSum = maxHeights[i]
pre = maxHeights[i]
for j in range(i + 1, n):
pre = min(pre, maxHeights[j])
curSum += pre
pre = maxHeights[i]
for j in range(i - 1, -1, -1):
pre = min(pre, maxHeights[j])
curSum += pre
ret = max(ret, curSum)
return ret
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
int n = maxHeights.size();
long long ret = 0;
for (int i = 0; i < n; i++) {
long long curSum = maxHeights[i];
int pre = maxHeights[i];
for (int j = i + 1; j < n; j++) {
pre = min(pre, maxHeights[j]);
curSum += pre;
}
pre = maxHeights[i];
for (int j = i - 1; j >= 0; j--) {
pre = min(pre, maxHeights[j]);
curSum += pre;
}
ret = max(ret, curSum);
}
return ret;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
種方案焕襟；
- 空間復(fù)雜度：
題解二（前后綴分解 + 單調(diào)棧）
使用單點棧維護前后綴數(shù)組，為了便于邊界計算鸵赖，我們構(gòu)造長為 的數(shù)組务漩。以示例
[6,5,3,9,2,7] 為例：
0, 5, 6, 10, 4, 5
13, 8, 6, 2, 1, 0
class Solution {
fun maximumSumOfHeights(maxHeights: List<Int>): Long {
val n = maxHeights.size
val suf = LongArray(n + 1)
val pre = LongArray(n + 1)
// 單調(diào)棧求前綴
val stack = java.util.ArrayDeque<Int>()
for (i in 0 until n) {
// 彈出棧頂
while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) {
stack.pop()
}
val j = if (stack.isEmpty()) -1 else stack.peek()
pre[i + 1] = pre[j + 1] + 1L * (i - j) * maxHeights[i]
stack.push(i)
}
// 單調(diào)棧求后綴
stack.clear()
for (i in n - 1 downTo 0) {
// 彈出棧頂
while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) {
stack.pop()
}
val j = if (stack.isEmpty()) n else stack.peek()
suf[i] = suf[j] + 1L * (j - i) * maxHeights[i]
stack.push(i)
}
// 合并
var ret = 0L
for (i in 0 until n) {
ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i])
}
return ret
}
}
class Solution:
def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
n = len(maxHeights)
suf = [0] * (n + 1)
pre = [0] * (n + 1)
stack = []
# 單調(diào)棧求前綴
for i in range(n):
# 彈出棧頂
while stack and maxHeights[stack[-1]] > maxHeights[i]:
stack.pop()
j = stack[-1] if stack else -1
pre[i + 1] = pre[j + 1] + (i - j) * maxHeights[i]
stack.append(i)
# 單調(diào)棧求后綴
stack = []
for i in range(n - 1, -1, -1):
# 彈出棧頂
while stack and maxHeights[stack[-1]] > maxHeights[i]:
stack.pop()
j = stack[-1] if stack else n
suf[i] = suf[j] + (j - i) * maxHeights[i]
stack.append(i)
# 合并
ret = 0
for i in range(n):
ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i])
return ret
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
int n = maxHeights.size();
vector<long long> suf(n + 1, 0);
vector<long long> pre(n + 1, 0);
stack<int> st;
// 單調(diào)棧求前綴
for (int i = 0; i < n; i++) {
// 彈出棧頂
while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) {
st.pop();
}
int j = st.empty() ? -1 : st.top();
pre[i + 1] = pre[j + 1] + 1LL * (i - j) * maxHeights[i];
st.push(i);
}
// 單調(diào)棧求后綴
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
// 彈出棧頂
while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) {
st.pop();
}
int j = st.empty() ? n : st.top();
suf[i] = suf[j] + 1LL * (j - i) * maxHeights[i];
st.push(i);
}
// 合并
long long ret = 0;
for (int i = 0; i < n; i++) {
ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i]);
}
return ret;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
次；
- 空間復(fù)雜度：
T4. 統(tǒng)計樹中的合法路徑數(shù)目（Hard）
https://leetcode.cn/problems/count-valid-paths-in-a-tree/description/
這道題似乎比 T3 還簡單一些肾砂。
問題分析
初步分析：
- 問題目標(biāo)： 尋找滿足條件的方案數(shù)；
-
問題條件： 路徑
上質(zhì)數(shù)的數(shù)目有且僅有
- 問題要素： 路徑和 - 表示路徑上質(zhì)數(shù)的數(shù)目镐确。
思考實現(xiàn)：
-
子問題： 對于以根節(jié)點 x 的原問題，可以分為 3 種情況：
- 左子樹可以構(gòu)造的方案數(shù)
- 右子樹可以構(gòu)造的方案數(shù)
- 如果根節(jié)點為質(zhì)數(shù)：「從根到子樹節(jié)點的路徑和為
的數(shù)目」與「從根到其它子樹節(jié)點的路徑和為
題解（DFS）
構(gòu)造 DFS 函數(shù)饼煞，子樹的 DFS 返回值為兩個值：
-
：到子樹節(jié)點和為
-
：到子樹節(jié)點和為
返回結(jié)果時：
- 如果根節(jié)點為質(zhì)數(shù)砖瞧，那么只能與
- 如果根節(jié)點為非質(zhì)數(shù)，那么
在子樹的計算過程中還會構(gòu)造結(jié)果：
由于題目說明 與
是相同路徑，我們可以記錄當(dāng)前子樹左側(cè)已經(jīng)計算過的
和
的累加和竭翠，再與當(dāng)前子樹的
與
做乘法：
class Solution {
companion object {
val U = 100000
val primes = LinkedList<Int>()
val isPrime = BooleanArray(U + 1) { true }
init {
isPrime[1] = false
for (i in 2 .. U) {
if (isPrime[i]) primes.add(i)
for (e in primes) {
if (i * e > U) break
isPrime[i * e] = false
if (i % e == 0) break
}
}
}
}
fun countPaths(n: Int, edges: Array<IntArray>): Long {
val graph = Array(n + 1) { LinkedList<Int>() }
for ((from, to) in edges) {
graph[from].add(to)
graph[to].add(from)
}
var ret = 0L
// return 0 和 1 的數(shù)量
fun dfs(i: Int, pre: Int): IntArray {
// 終止條件
var cnt = IntArray(2)
if (isPrime[i]) {
cnt[1] = 1
} else {
cnt[0] = 1
}
// 遞歸
for (to in graph[i]) {
if (to == pre) continue // 返祖邊
val (cnt0, cnt1) = dfs(to, i)
// 記錄方案
ret += cnt0 * cnt[1] + cnt1 * cnt[0]
// 記錄影響
if (isPrime[i]) {
cnt[1] += cnt0
} else {
cnt[0] += cnt0
cnt[1] += cnt1
}
}
return cnt
}
dfs(1, -1) // 隨機選擇根節(jié)點
return ret
}
}
U = 100000
primes = deque()
isPrime = [True] * (U + 1)
isPrime[1] = False
for i in range(2, U + 1):
if isPrime[i]: primes.append(i)
for e in primes:
if i * e > U: break
isPrime[i * e] = False
if i % e == 0: break
class Solution:
def countPaths(self, n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
ret = 0
def dfs(i, pre):
nonlocal ret # 修改外部變量
cnt = [0, 0]
# 終止條件
if isPrime[i]:
cnt[1] = 1
else:
cnt[0] = 1
for to in graph[i]:
if to == pre: continue # 返祖邊
cnt0, cnt1 = dfs(to, i)
# 記錄方案
ret += cnt0 * cnt[1] + cnt1 * cnt[0]
# 記錄影響
if isPrime[i]:
cnt[1] += cnt0
else:
cnt[0] += cnt0
cnt[1] += cnt1
return cnt
dfs(1, -1) # 隨機選擇根節(jié)點
return ret
const int U = 100000;
list<int> primes;
bool isPrime[U + 1];
bool inited = false;
void init() {
if (inited) return;
inited = true;
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i <= U; ++i) {
if (isPrime[i]) primes.push_back(i);
for (auto e : primes) {
if (i * e > U) break;
isPrime[i * e] = false;
if (i % e == 0) break;
}
}
}
class Solution {
public:
long long countPaths(int n, vector<vector<int>>& edges) {
init();
vector<list<int>> graph(n + 1);
for (const auto& edge : edges) {
int from = edge[0];
int to = edge[1];
graph[from].push_back(to);
graph[to].push_back(from);
}
long long ret = 0;
// return 0 和 1 的數(shù)量
function<vector<int>(int, int)> dfs = [&](int i, int pre) -> vector<int> {
// 終止條件
vector<int> cnt(2, 0);
if (isPrime[i]) {
cnt[1] = 1;
} else {
cnt[0] = 1;
}
// 遞歸
for (auto to : graph[i]) {
if (to == pre) continue; // 返祖邊
vector<int> subCnt = dfs(to, i);
int cnt0 = subCnt[0];
int cnt1 = subCnt[1];
// 記錄方案
ret += cnt0 * cnt[1] + cnt1 * cnt[0];
// 記錄影響
if (isPrime[i]) {
cnt[1] += cnt0;
} else {
cnt[0] += cnt0;
cnt[1] += cnt1;
}
}
return cnt;
};
dfs(1, -1); // 隨機選擇根節(jié)點
return ret;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：預(yù)處理時間為
振坚，建圖時間 和 DFS 時間為
- 空間復(fù)雜度：預(yù)處理空間為
枚舉質(zhì)數(shù)
枚舉法：枚舉
，判斷它是不是質(zhì)數(shù)传货，整體時間復(fù)雜度是
// 暴力求質(zhì)數(shù)
fun getPrimes(max: Int): IntArray {
val primes = LinkedList<Int>()
for (num in 2..max) {
if (isPrime(num)) primes.add(num)
}
return primes.toIntArray()
}
// 質(zhì)數(shù)判斷
fun isPrime(num: Int): Boolean {
var x = 2
while (x * x <= num) {
if (num % x == 0) return false
x++
}
return true
}
Eratosthenes 埃氏篩：如果
是質(zhì)數(shù)屎鳍，那么
、
一定不是質(zhì)數(shù)问裕。我們設(shè)
isPrime[i]表示是否為質(zhì)數(shù)逮壁。從小開始遍歷，如果
為什么要從
,
開始標(biāo)記，而不是
// 埃氏篩求質(zhì)數(shù)
val primes = LinkedList<Int>()
val isPrime = BooleanArray(U + 1) { true }
for (i in 2..U) {
// 檢查是否為質(zhì)數(shù)逗堵，這里不需要調(diào)用 isPrime() 函數(shù)判斷是否質(zhì)數(shù)秉氧，因為它沒被小于它的數(shù)標(biāo)記過，那么一定不是合數(shù)
if (!isPrime[i]) continue
primes.add(i)
// 標(biāo)記
var x = i * i
while (x <= U) {
isPrime[x] = false
x += i
}
}
Euler 歐氏線性篩：盡管我們從
// 線性篩求質(zhì)數(shù)
val primes = LinkedList<Int>()
val isPrime = BooleanArray(U + 1) { true }
for (i in 2..U) {
// 檢查是否為質(zhì)數(shù)帅刊，這里不需要調(diào)用 isPrime() 函數(shù)判斷是否質(zhì)數(shù)，因為它沒被小于它的數(shù)標(biāo)記過漂问，那么一定不是合數(shù)
if (isPrime[i]) {
primes.add(i)
}
// 標(biāo)記
for (e in primes) {
if (i * e > U) break
isPrime[i * e] = false
if (i % e == 0) break
}
}
推薦閱讀
LeetCode 上分之旅系列往期回顧：
