Java C++題解leetcode816模糊坐標(biāo)示例

更新時(shí)間：2023年01月16日 11:56:57 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode816模糊坐標(biāo)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目

題目要求

思路：枚舉

既然要輸出每種可能了，那必然不能“偷懶”，就暴力枚舉咯；
在每個(gè)間隔處添加逗號(hào)；
定義函數(shù)decPnt(sta, end)分別列舉逗號(hào)左右兩邊的數(shù)能構(gòu)成的可能性；
- 同樣在每個(gè)間隔添加小數(shù)點(diǎn)；
- 注意兩種不合法的結(jié)構(gòu)——前導(dǎo)0和后綴0；
- 不要忘記無小數(shù)點(diǎn)的整數(shù)版本，
分別組合兩邊的不同可能性，根據(jù)要求各式加入答案。

Java

class Solution {
    String str;
    public List<String> ambiguousCoordinates(String s) {
        str = s.substring(1, s.length() - 1); // 去除括號(hào)
        int n = str.length();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) { // 添加逗號(hào)
            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') // 無小數(shù)
            res.add(str.substring(sta, end + 1));
        for (int i = sta; i < end; i++) { // 添加小數(shù)點(diǎn)
            String inte = str.substring(sta, i + 1), dec = str.substring(i + 1, end + 1);
            if (inte.length() > 1 && inte.charAt(0) == '0') // 前導(dǎo)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); // 去除括號(hào)
        int n = str.size();
        vector<string> res;
        for (int i = 0; i < n - 1; i++) { // 添加逗號(hào)
            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') // 無小數(shù)
            res.emplace_back(str.substr(sta, end - sta + 1));
        for (int i = sta; i < end; i++) { // 添加小數(shù)點(diǎn)
            string inte = str.substr(sta, i - sta + 1), dec = str.substr(i + 1, end - i);
            if (inte.size() > 1 && inte[0] == '0') // 前導(dǎo)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" { // 無小數(shù)
            res.push(format!("{}", &stri[sta..end + 1]));
        }
        for i in sta..end { // 添加小數(shù)點(diǎn)
            let (inte, dec) = (&stri[sta..i + 1], &stri[i + 1.. end + 1]);
            if inte.len() > 1 && inte.starts_with("0") { // 前導(dǎo)0
                continue;
            }
            if (dec.ends_with("0")) { // 后綴0
                continue;
            }
            res.push(format!("{}.{}", inte, dec));
        }
        res
    }
}