JavaC++题解leetcode816模糊坐标示例

Jacinthe ·

更新时间:2024-11-13

· 641 次阅读

题目

思路：枚举

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
    }
}