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)

相关推荐

  • Java C++ leetcode面试零矩阵

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 定义两个数组分别记录每行or每列中为0的元素: 0所在的行列清零也就意味着元素所在行or列有0则置零[废话连篇]: 所以一次遍历找出有0的行列,一次遍历根据其将相应元素置零. Java class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length, m = matrix[0].length; boolean[] row

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • Java C++题解leetcode902最大为N的数字组合数位DP

    目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseIn

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++题解leetcode817链表组件示例

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 Java class Solution { public int numComponents(ListNode head, int[] nums) { int res = 0; Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); // 转存nums while (head != null) { if (set.cont

  • Java C++题解leetcode1620网络信号最好的坐标

    目录 题目 思路:暴力模拟 Java C++ Rust 题目 题目要求 思路:暴力模拟 因为数据范围小,所以是万万没想到的逐个遍历…… 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标. Java class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0,

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • Java实现图片裁剪功能的示例详解

    目录 前言 Maven依赖 代码 验证一下 前言 本文提供将图片按照自定义尺寸进行裁剪的Java工具类,一如既往的实用主义. Maven依赖 <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>30.1.1-jre</version> </dependency> <dependen

  • Java实现经典游戏超级玛丽的示例代码

    目录 前言 主要设计 功能截图 代码实现 游戏主界面 马里奥 小怪 总结 前言 在你的童年记忆里,是否有一个蹦跳.顶蘑菇的小人? 如果你回忆起了它,你定然会觉得现在它幼稚.无聊,画面不漂亮,游戏不精彩……但请你记住:这才是真正的游戏,它给了你无限的欢乐! 马里奥是靠吃蘑菇成长,闻名世界的超级巨星.特征是大鼻子.头戴帽子.身穿背带工作服.还留着胡子. 如此经典的游戏,你怎么能错过,快来玩玩吧. <超级玛丽>游戏是用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想.

随机推荐