Java C++题解leetcode816模糊坐标示例
目录
- 题目
- 思路:枚举
- Java
- C++
- Rust
- 总结
题目
思路:枚举
- 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯;
- 在每个间隔处添加逗号;
- 定义函数
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++题解模糊坐标的资料请关注我们其它相关文章!
赞 (0)