Re: [閒聊] 每日leetcode
https://leetcode.com/problems/construct-smallest-number-from-di-string/description/
2375. Construct Smallest Number From DI String
給你一個只包含I和D的字串，I表示遞增D表示遞減，返回一個由1~9不重複組成的字串滿足
遞增和遞減特性，且他的數字盡可能小。
思路：
1.用dfs窮舉所有可能，因為要求最小所以從小的數字開始使用。
2.剪枝部份可以去除比答案更大的字串 OR 不滿足遞增遞減的字串。
Java Code:
----------------------------------------------------
class Solution {
private List<Integer> res;
public String smallestNumber(String pattern) {
res = new ArrayList<>();
dfs(pattern, new ArrayList<>(), new boolean[pattern.length() + 1]);
StringBuilder sb = new StringBuilder();
for (int num : res) {
sb.append(num);
}
return sb.toString();
}
void dfs(String pattern, List<Integer> curr, boolean[] used) {
if (curr.size() >= 2) {
for (int i = 1; i < curr.size(); i++) {
if (pattern.charAt(i - 1) == 'I') {
if (curr.get(i) < curr.get(i - 1)) {
return;
}
} else {
if (curr.get(i) > curr.get(i - 1)) {
return;
}
}
}
}
if (curr.toString().compareTo(res.toString()) > 0) {
return;
}
if (curr.size() == pattern.length() + 1) {
res = new ArrayList<>(curr);
}
for (int i = 0; i < used.length; i++) {
if (used[i]) continue;
curr.add(i + 1);
used[i] = true;
dfs(pattern, curr, used);
used[i] = false;
curr.remove(curr.size() - 1);
}
}
}
----------------------------------------------------
--
你跟我說這個我有什麼辦法
https://i.imgur.com/wb5zrOy.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1739977625.A.506.html
討論串 (同標題文章)
完整討論串 (本文為第 1339 之 1552 篇)：