模糊坐标00

题目链接

模糊坐标

题目描述

注意

• S[0] = “(”, S[S.length - 1] = “)”, 且字符串 S 中的其他元素都是数字
• 4 <= S.length <= 12
• 注意添加的坐标可以为小数，但是必须符合规范，也就是数字前面和后面不能有多余的0

解答思路

• 由题可得，需要将s分割成两个部分，再分别找到两个部分所能组成的数字，然后再将两部分按照题目要求合起来即可
• 关键是如何找到两个部分所能组成的所有数字，对任意一部分，有以下几种情况：
  （1）如果该部分的字符串只有一位，则能且仅能组成一种情况，也就是其本身
  （2）如果该部分的字符串多于一位，且首尾都为0，则一定无法组成规范的数字
  （3）如果该部分的字符串多于一位，且只有首位为0，则只有0.xxxxx这一种情况
  （4）如果该部分的字符串多于一位，且只有末位为0，则只有xxxxxx0这一种情况
  （5）其余情况则不管小数点在何处都符合题意

代码

方法一：

class Solution {
    public List<String> ambiguousCoordinates(String s) {
        int n = s.length();
        List<String> res = new ArrayList<>();
        // 逗号所处的位置
        for(int i = 2; i < n - 1; i++) {
            List<String> part1s = findCombin(s.substring(1, i));
            if(part1s.isEmpty()) continue;
            List<String> part2s = findCombin(s.substring(i, n - 1));
            if(part2s.isEmpty()) continue;
            for(String part1 : part1s) {
                for(String part2 : part2s) {
                    String tmp = "(" + part1 + ", " + part2 + ")";
                    res.add(tmp);
                }
            }
        }
        return res;
    }

    public List<String> findCombin(String s) {
        int len = s.length();
        List<String> list = new ArrayList<>();
        // 如果当前字符串仅有一位，则返回其本身
        if(len == 1) {
            list.add(s);
            return list;
        }
        // 如果整个字符串首位和末位都为0，则不满足题意
        if(s.charAt(0) == '0' && s.charAt(len - 1) == '0') return list;
        // 如果首位为0，则小数点只能在首位后方
        if(s.charAt(0) - '0' == 0) {
            String tmp = "0" + "." + s.substring(1, len);
            list.add(tmp);
            return list;
        }
        // 如果末位为0，则小数必不可能满足题意
        if(s.charAt(len - 1) - '0' == 0) {
            String tmp = s.substring(0, len);
            list.add(tmp);
            return list;
        }
        for(int i = 1; i < len; i++) {
            String tmp = s.substring(0, i) + "." + s.substring(i, len);
            list.add(tmp);
        }
        // 没有小数点的情况
        list.add(s);
        return list;
    }
}
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
45
46
47
48
49
50
51

关键点

• 先将字符串分割成两部分，且每部分至少有一个字符
• 考虑到 不同情况所能组成的数字组合