• LeetCode 0816. 模糊坐标


    【LetMeFly】816.模糊坐标

    力扣题目链接:https://leetcode.cn/problems/ambiguous-coordinates/

    我们有一些二维坐标,如 "(1, 3)" 或 "(2, 0.5)",然后我们移除所有逗号,小数点和空格,得到一个字符串S。返回所有可能的原始字符串到一个列表中。

    原始的坐标表示法不会存在多余的零,所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外,一个小数点前至少存在一个数,所以也不会出现“.1”形式的数字。

    最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间(逗号之后)都有一个空格。

     

    示例 1:
    输入: "(123)"
    输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
    
    示例 2:
    输入: "(00011)"
    输出:  ["(0.001, 1)", "(0, 0.011)"]
    解释: 
    0.0, 00, 0001 或 00.01 是不被允许的。
    
    示例 3:
    输入: "(0123)"
    输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
    
    示例 4:
    输入: "(100)"
    输出: [(10, 0)]
    解释: 
    1.0 是不被允许的。
    

     

    提示:

    • 4 <= S.length <= 12.
    • S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。

     

    方法一:枚举

    在主函数中,我们枚举“切割位置”。即将原始字符串切割成非空的两部分,一个代表第一个数,一个代表第二个数

    然后写一个函数vector addPoint(string s),接收参数字符串,返回这个字符串添加至多一个小数点所形成的所有可能的合法数字

    在主函数中,调用addPoint函数,则可分别得到第一个数、第二个数的所有合法数字,再将其一一组合起来添加到答案中

    vector<string> ambiguousCoordinates(string& s) {
        s = s.substr(1, s.size() - 2);  // 去掉原始字符串中的两个括号(0)
        vector<string> ans;
        for (int i = 0; i + 1 < s.size(); i++) {
            vector<string> front = addPoint(s.substr(0, i + 1));  // 为s[0, i]添加零个或一个小数点 所能得到的所有合法数字
            vector<string> back = addPoint(s.substr(i + 1, s.size() - i - 1));  // s[i + 1, s.size() - 1]
            for (string& s1 : front)
                for (string& s2 : back)
                    ans.push_back("(" + s1 + ", " + s2 + ")");  // 分别拼接组合
        }
        return ans;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    那么addPoint函数怎么实现呢?

    我们再写一个函数bool aviliable(string& s),这个函数接收“受至多一个.”且“不为空”的字符串s,并返回s是否为一个合法数字

    那么,addPoint函数中,我们只需要枚举小数点的位置,将小数点插入后调用aviliable函数判断新生成的数是否合法即可

    vector<string> addPoint(string s) {
        vector<string> ans;
        if (aviliable(s))  // 无小数点
            ans.push_back(s);
        for (int i = 0; i + 1 < s.size(); i++) {  // 枚举小数点位置
            string thisS = s.substr(0, i + 1) + "." + s.substr(i + 1, s.size() - i - 1);
            if (aviliable(thisS))
                ans.push_back(thisS);
        }
        return ans;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    最后,aviliable函数怎么实现呢?

    只需要判断是否为以下三种情况:

    1. 0axxx:例如0123(其中 a a a不是小数点)
    2. .xx:例如.3
    3. x.x0:例如1.20

    出现以上三种情况的一种,即为“不合法字符串”

    否则为合法字符串

    bool aviliable(string& s) {  // 只接受至多一个.的s,只接受不为空的s
        if (s.size() > 1 && s[0] == '0' && s[1] != '.')  // 0axxx
            return false;
        if (s[0] == '.')  // .xx
            return false;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '.') {
                if (s.back() == '0')  // x.x0
                    return false;
                if (i == s.size() - 1)
                    return false;
                break;
            }
        }
        return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 时间复杂度 O ( n 3 ) O(n^3) O(n3),其中 n n n是原始字符串的长度
    • 空间复杂度 O ( n 3 ) O(n^3) O(n3)

    AC代码

    C++
    class Solution {
    private:
        bool aviliable(string& s) {  // 只接受至多一个.的s,只接受不为空的s
            if (s.size() > 1 && s[0] == '0' && s[1] != '.')  // 0axxx
                return false;
            if (s[0] == '.')  // .xx
                return false;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == '.') {
                    if (s.back() == '0')  // x.x0
                        return false;
                    if (i == s.size() - 1)
                        return false;
                    break;
                }
            }
            return true;
        }
    
        vector<string> addPoint(string s) {
            vector<string> ans;
            if (aviliable(s))
                ans.push_back(s);
            for (int i = 0; i + 1 < s.size(); i++) {
                string thisS = s.substr(0, i + 1) + "." + s.substr(i + 1, s.size() - i - 1);
                if (aviliable(thisS))
                    ans.push_back(thisS);
            }
            return ans;
        }
    public:
        vector<string> ambiguousCoordinates(string& s) {
            s = s.substr(1, s.size() - 2);
            vector<string> ans;
            for (int i = 0; i + 1 < s.size(); i++) {
                vector<string> front = addPoint(s.substr(0, i + 1));
                vector<string> back = addPoint(s.substr(i + 1, s.size() - i - 1));
                for (string& s1 : front)
                    for (string& s2 : back)
                        ans.push_back("(" + s1 + ", " + s2 + ")");
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    同步发文于CSDN,原创不易,转载请附上原文链接哦~
    Tisfy:https://letmefly.blog.csdn.net/article/details/127727007

  • 相关阅读:
    PAT 乙级1090危险品装箱
    CAS:1802908-00-4|Dde Biotin-PEG4-alkyne|Dde 生物素-PEG4-炔烃
    【11.14】Codeforces 刷题
    Docker安装 Mysql主从同步
    ESP-ADF LVGL GUI开发简易化
    OpenLayers实战,OpenLayers调用手机陀螺仪方向实现指南针效果
    FFplay文档解读-28-视频过滤器三
    C++ Primer学习笔记-----第二章:变量和基本类型
    Ansible FIle模块,使用Ansible File模块进行文件管理
    第2章 Linux多进程开发 2.18 内存映射
  • 原文地址:https://blog.csdn.net/Tisfy/article/details/127727007