JavaC++题解leetcode816模糊坐标示例
短信预约 -IT技能 免费直播动态提醒
题目
题目要求
思路：枚举
- 既然要输出每种可能了，那必然不能“偷懒”，就暴力枚举咯；
- 在每个间隔处添加逗号；
- 定义函数
decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性；- 同样在每个间隔添加小数点；
- 注意两种不合法的结构——前导0和后缀0；
- 不要忘记无小数点的整数版本，
- 分别组合两边的不同可能性，根据要求各式加入答案。
Java
class Solution {
String str;
public List<String> ambiguousCoordinates(String s) {
str = s.substring(1, s.length() - 1); // 去除括号
int n = str.length();
List<String> res = new ArrayList<>();
for (int i = 0; i < n - 1; i++) { // 添加逗号
List<String> left = decPnt(0, i), right = decPnt(i + 1, n - 1);
for (var l : left) {
for (var r : right) {
res.add("(" + l + ", " + r + ")");
}
}
}
return res;
}
List<String> decPnt(int sta, int end) {
List<String> res = new ArrayList<>();
if (sta == end || str.charAt(sta) != '0') // 无小数
res.add(str.substring(sta, end + 1));
for (int i = sta; i < end; i++) { // 添加小数点
String inte = str.substring(sta, i + 1), dec = str.substring(i + 1, end + 1);
if (inte.length() > 1 && inte.charAt(0) == '0') // 前导0
continue;
if (dec.charAt(dec.length() - 1) == '0') // 后缀0
continue;
res.add(inte + "." + dec);
}
return res;
}
}
C++
class Solution {
public:
string str;
vector<string> ambiguousCoordinates(string s) {
str = s.substr(1, s.size() - 2); // 去除括号
int n = str.size();
vector<string> res;
for (int i = 0; i < n - 1; i++) { // 添加逗号
vector<string> left = decPnt(0, i), right = decPnt(i + 1, n - 1);
for (auto l : left) {
for (auto r : right) {
res.emplace_back("(" + l + ", " + r + ")");
}
}
}
return res;
}
vector<string> decPnt(int sta, int end) {
vector<string> res;
if (sta == end || str[sta] != '0') // 无小数
res.emplace_back(str.substr(sta, end - sta + 1));
for (int i = sta; i < end; i++) { // 添加小数点
string inte = str.substr(sta, i - sta + 1), dec = str.substr(i + 1, end - i);
if (inte.size() > 1 && inte[0] == '0') // 前导0
continue;
if (dec.back() == '0') // 后缀0
continue;
res.emplace_back(inte + "." + dec);
}
return res;
}
};
Rust
impl Solution {
pub fn ambiguous_coordinates(s: String) -> Vec<String> {
let stri = &s[1.. s.len() - 1];
let n = stri.len();
let mut res = vec![];
for i in 0..n-1 {
for l in Self::decPnt(stri, 0, i) {
for r in Self::decPnt(stri, i + 1, n - 1) {
res.push(format!("({}, {})", l, r));
}
}
}
res
}
fn decPnt(stri: &str, sta: usize, end: usize) -> Vec<String> {
let mut res = vec![];
if sta == end || &stri[sta..sta+1] != "0" { // 无小数
res.push(format!("{}", &stri[sta..end + 1]));
}
for i in sta..end { // 添加小数点
let (inte, dec) = (&stri[sta..i + 1], &stri[i + 1.. end + 1]);
if inte.len() > 1 && inte.starts_with("0") { // 前导0
continue;
}
if (dec.ends_with("0")) { // 后缀0
continue;
}
res.push(format!("{}.{}", inte, dec));
}
res
}
}
总结
也算是简单模拟题吧，收获在于学到了一些快速定位字符串首末的小方法。
以上就是Java C++题解leetcode816模糊坐标示例的详细内容，更多关于Java C++题解模糊坐标的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
