LWC 58:726. Number of Atoms

LWC 58:726. Number of Atoms

传送门:726. Number of Atoms

Problem:

Given a chemical formula (given as a string), return the count of each atom. An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name. 1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible. Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula. A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas. Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:

Input: formula = “H2O” Output: “H2O” Explanation: The count of elements are {‘H’: 2, ‘O’: 1}.

Example 2:

Input: formula = “Mg(OH)2” Output: “H2MgO2” Explanation: The count of elements are {‘H’: 2, ‘Mg’: 1, ‘O’: 2}.

Example 3:

Input: formula = “K4(ON(SO3)2)2” Output: “K4N2O14S4” Explanation: The count of elements are {‘K’: 4, ‘N’: 2, ‘O’: 14, ‘S’: 4}.

Note:

All atom names consist of lowercase letters, except for the first character which is uppercase.

The length of formula will be in the range [1, 1000].

Formula will only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.

思路: 递归真的是个好东西,思路比较暴力,如果没有遇到括号,则按照传统的检测字符和数字进行更新即可。如果检测到括号,则先得到括号内的元素和个数的映射,接着乘上大括号外的第一个num,再将第三部分的答案组合进来即可。

比如:

H2O2(SO2)23(OH)23

上述字符串可以组成三部分

lf = "H2O2"
mid = "(SO2)23" 
rt = "(OH)23"

只有mid需要特殊处理,把{s = 1 * 32, O = 2 * 23 = 46}
而一旦解决mid,则rt跟着被解决,lf在之前就被解决了,具体看代码,不解释了。

代码如下:

    public String countOfAtoms(String formula) {
        Map<String, Integer> map = go(formula.toCharArray(), 0, formula.length() - 1);

        StringBuilder sb = new StringBuilder();
        List<String> set = new ArrayList<>(map.keySet());
        Collections.sort(set);
        for (String key : set) {
            sb.append(key);
            if (map.get(key) > 1) {
                sb.append(map.get(key));
            }
        }
        return sb.toString();
    }

    public Map<String, Integer> go(char[] cs, int s, int e){
        if (s > e) return new HashMap<>();

        Map<String, Integer> ans = new HashMap<>();
        int idx = new String(cs).substring(s, e + 1).indexOf("(");
        if (idx != -1) idx += s;
        if (idx == -1) {

            StringBuilder sb = new StringBuilder();
            for (int i = s; i <= e;) {
                if (Character.isUpperCase(cs[i])) {
                    sb.append(cs[i]);
                    i ++;

                    if (i <= e && Character.isUpperCase(cs[i])) {
                        String ele = sb.toString();
                        if (!ans.containsKey(ele)) {
                            ans.put(ele, 1);
                        }
                        else {
                            ans.put(ele, ans.get(ele) + 1);
                        }
                        sb = new StringBuilder();
                    }
                    else if (i <= e && Character.isLowerCase(cs[i])) {
                        while (i <= e && Character.isLowerCase(cs[i])) {
                            sb.append(cs[i]);
                            i ++;
                        }
                        if (i <= e && !Character.isDigit(cs[i])){
                            String ele = sb.toString();
                            if (!ans.containsKey(ele)) {
                                ans.put(ele, 1);
                            }
                            else {
                                ans.put(ele, ans.get(ele) + 1);
                            }
                            sb = new StringBuilder();
                        }
                    }

                    if (i <= e && Character.isDigit(cs[i])) {
                        int num = 0;
                        while (i <= e && Character.isDigit(cs[i])) {
                            num = num * 10 + cs[i] - '0';
                            i ++;
                        }

                        String ele = sb.toString();
                        if (!ans.containsKey(ele)) {
                            ans.put(ele, num);
                        }
                        else {
                            ans.put(ele, ans.get(ele) + num);
                        }

                        sb = new StringBuilder();
                    }
                }
            }

            String ele = sb.toString();
            if (!ele.isEmpty()) {
                if (!ans.containsKey(ele)) {
                    ans.put(ele, 1);
                }
                else {
                    ans.put(ele, ans.get(ele) + 1);
                }
            }
            return ans;
        }
        else {
            Map<String, Integer> lf = go(cs, s, idx - 1);

            StringBuilder sb = new StringBuilder();
            int p = 1;
            Map<String, Integer> include;
            int num = 0;
            int j = -1;
            for (int i = idx + 1; i <= e; ++i) {
                sb.append(cs[i]);
                if (cs[i] == '(') {
                    p ++;
                }
                else if (cs[i] == ')') {
                    p --;
                    if (p == 0) {
                        j = i + 1;
                        while (j <= e && Character.isDigit(cs[j])) {
                            num = num * 10 + cs[j] - '0';
                            j ++;
                        }
                        break;
                    }
                }
            }
            String ele = sb.toString().substring(0, sb.length() - 1);
            include = go(ele.toCharArray(), 0, ele.length() - 1);

            for (String key : include.keySet()) {
                include.put(key, include.get(key) * num);
            }

            Map<String, Integer> rt = go(cs, j, e);

            add(ans, lf);
            add(ans, include);
            add(ans, rt);

            return ans;
        }
    }

    public void add(Map<String, Integer> ans, Map<String, Integer> tmp) {
        for (String key : tmp.keySet()) {
            if (!ans.containsKey(key)) {
                ans.put(key, tmp.get(key));
            }
            else {
                ans.put(key, ans.get(key) + tmp.get(key));
            }
        }
    }

注意一些细节: 首先,对于字符串”H2O2BeBe49”这样的formula,第一次一定会遇到大写字符,接着把大写字母后的小写字母全部给append上,这样只会遇到两种情况:下一个字符为数字,或者下一个字符为大写字符。

如过遇到字符,则计算num,如果遇到大写字符,则formula省略了1,需要加上。

代码更新如下:

    public String countOfAtoms(String formula) {
        Map<String, Integer> map = go(formula.toCharArray(), 0, formula.length() - 1);

        StringBuilder sb = new StringBuilder();
        List<String> set = new ArrayList<>(map.keySet());
        Collections.sort(set);
        for (String key : set) {
            sb.append(key);
            if (map.get(key) > 1) {
                sb.append(map.get(key));
            }
        }
        return sb.toString();
    }

    public Map<String, Integer> go(char[] cs, int s, int e){
        if (s > e) return new HashMap<>();

        Map<String, Integer> ans = new HashMap<>();
        int idx = new String(cs).substring(s, e + 1).indexOf("(");
        if (idx != -1) idx += s;
        if (idx == -1) {

            StringBuilder sb = new StringBuilder();
            for (int i = s; i <= e;) {
                if (Character.isUpperCase(cs[i])) {
                    sb.append(cs[i]);
                    i ++;

                    while (i <= e && Character.isLowerCase(cs[i])){
                        sb.append(cs[i]);
                        i ++;
                    }

                    if (i <= e && !Character.isDigit(cs[i])){
                        String ele = sb.toString();
                        if (!ans.containsKey(ele)) {
                            ans.put(ele, 1);
                        }
                        else {
                            ans.put(ele, ans.get(ele) + 1);
                        }
                        sb = new StringBuilder();
                    }
                    else if (i <= e && Character.isDigit(cs[i])) {

                        int num = 0;
                        while (i <= e && Character.isDigit(cs[i])) {
                            num = num * 10 + cs[i] - '0';
                            i ++;
                        }

                        String ele = sb.toString();
                        if (!ans.containsKey(ele)) {
                            ans.put(ele, num);
                        }
                        else {
                            ans.put(ele, ans.get(ele) + num);
                        }

                        sb = new StringBuilder();
                    }
                }
            }

            String ele = sb.toString();
            if (!ele.isEmpty()) {
                if (!ans.containsKey(ele)) {
                    ans.put(ele, 1);
                }
                else {
                    ans.put(ele, ans.get(ele) + 1);
                }
            }
            return ans;
        }
        else {
            Map<String, Integer> lf = go(cs, s, idx - 1);

            StringBuilder sb = new StringBuilder();
            int p = 1;
            Map<String, Integer> include;
            int num = 0;
            int j = -1;
            for (int i = idx + 1; i <= e; ++i) {
                sb.append(cs[i]);
                if (cs[i] == '(') {
                    p ++;
                }
                else if (cs[i] == ')') {
                    p --;
                    if (p == 0) {
                        j = i + 1;
                        while (j <= e && Character.isDigit(cs[j])) {
                            num = num * 10 + cs[j] - '0';
                            j ++;
                        }
                        break;
                    }
                }
            }
            String ele = sb.toString().substring(0, sb.length() - 1);
            include = go(ele.toCharArray(), 0, ele.length() - 1);

            for (String key : include.keySet()) {
                include.put(key, include.get(key) * num);
            }

            Map<String, Integer> rt = go(cs, j, e);
            add(ans, lf);
            add(ans, include);
            add(ans, rt);

            return ans;
        }
    }

    public void add(Map<String, Integer> ans, Map<String, Integer> tmp) {
        for (String key : tmp.keySet()) {
            if (!ans.containsKey(key)) {
                ans.put(key, tmp.get(key));
            }
            else {
                ans.put(key, ans.get(key) + tmp.get(key));
            }
        }
    }     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏塔奇克马敲代码

第 15 章 面向对象程序设计

2053
来自专栏青枫的专栏

day03_js学习笔记_02_js的内建对象、js的函数

593
来自专栏向治洪

HashMap实现原理分析

HashMap实现原理分析 HashMap主要是用数组来存储数据的,我们都知道它会对key进行哈希运算,哈系运算会有重复的哈希值,对于哈希值的冲突,HashMa...

2435
来自专栏陈纪庚

javascript冷知识

  如果放在数值前的话,对数值不会产生任何影响,不过放在其他的数据类型前面的话,就等于调用number()将他转为数字,布尔值false被转为0,ture被转为...

723
来自专栏拭心的安卓进阶之路

Java 集合深入理解(14):Map 概述

终于把 List 常用的几种容器介绍完了,接下来开始 Map 的相关介绍。 什么是 Map Java 中的 Map 接口 是和 Collection 接口 同...

1998
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十七】Set接口集合详解

三、Set接口 Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行nu...

3489
来自专栏青枫的专栏

TreeSet集合的add()方法的源码解析

662
来自专栏闻道于事

Java之异常处理

Java异常处理 异常:异常就是Java程序在运行过程中出现的错误。 异常由来:问题也是现实生活中一个具体事务,也可以通过java 的类的形式进行描述,并封装成...

2736
来自专栏数据处理

__new__,__init__

1373
来自专栏奔跑的蛙牛技术博客

泛型程序设计

当程序调用泛型类型,如果擦除返回类型,编译器将插入强制类型转换 Pair<Employee> buddies = . . Employee buddy = ...

431

扫码关注云+社区