-
【LeetCode】726. 原子的数量
【题目描述】
【解题思路】
首先当我看到题目的时候感觉任务很复杂，有大小写字母、有数字、有括号，还得按照字母的顺序输出，一想到还有括号自己就完全没有思路不知道该怎么办？但是这道题目的限制条件是逐渐增加难度，如果大家的逻辑能力不强建议，大家不要上来就全面的考虑问题，这样只会让菜狗的我越想越混乱。根据自己仅有的做题经验，我告诉自己先让代码能满足简单的示例，比如实例中没有括号的情况，然后在这个代码的基础上怎么处理括号问题。
然后简单列举一下我的一些解题办法：
1. 既然有原子的定义，如何找到原子是要解决的问题
2. 每个原子都有对应的数量，如何确定原子对应的数量也是要解决的问题
3. 看到输出的格式是按照的原子的字典序输出，可以很容易想到用Java中的TreeMap保存原子和原子对应的数量
4. 一看到俄罗斯套娃式的括号我的第一反应是用递归的方法
5. 先处理没有括号的情况，在此基础上加入递归的代码
【没有括号的简单情况】
老实说，我感觉这道题如果不让处理括号的话感觉还是挺简单的，就是找到原子，然后找到原子对应的数量，将这样的一个原子数量对<String, Integer>保存在TreeMap中最后统一输出。
这里根据我处理字符串带括号问题的一个习惯，我先做了一个预处理，就是将String类型的输入保存在Deque<Character>类型的双向队列当中进行后续的操作。
先写出代码的大框架
class Solution {
public String countOfAtoms(String formula) {
// String ======> Duque
Deque<Character> formulaDeque = new LinkedList<>();
for(int i = 0; i < formula.length(); ++i) {
formulaDeque.offer(formula.charAt(i));
}
// 解题主要函数， 保存每个原子和其对应的数量
TreeMap<String, Integer> treeMap = countAtoms(formulaDeque);
// 按照要求进行输出
String res = "";
for(String key : treeMap.keySet()) {
if(treeMap.get(key) > 1) {
res += key + treeMap.get(key);
} else {
res += key;
}
}
return res;
}
public TreeMap<String, Integer> countAtoms(Deque<Character> formulaDeque) {
// coding ....
}
}
编写求原子和对应数量的函数countAtoms(Deque formulaDeque)，不考虑括号情况
下面我们将经历放在求解这样的一个函数上。我们可以遍历当前字符串的每一个字符，根据不同的字符类型处理不同情况。例如对于H2O2He3Mg4OT而言：
我们将每次找到的原子和数量保存在String atom = “” 和String digit = “”中。
1. 遇到大写字母
- 可能是原子的第一个大写字母，此时应改追加原子字符
- 也可能是下一个原子的第一个字符，这是就要根据已经找到的atom和digit将其加入到TreeMap中，并且更新atom和digit为找下一个原子数量对做准备。
2. 遇到小写字母
- 追加原子字符
3. 遇到数字
- 追加数字字符
下面贴上代码（注意遍历完好药处理一次atom和digit）
public TreeMap<String, Integer> countAtoms(Deque<Character> formulaDeque) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
String atom = "";
String digit = "";
while(!formulaDeque.isEmpty()) {
char cur = formulaDeque.poll();
if(Character.isUpperCase(cur)) {
if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
atom += cur;
} else { // 结束，遇到下一个大写字母，记录原子和数量
if(digit.equals("")) { // 如果digit为空应该表示为1
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
// 更新
atom = "" + cur;
digit = "";
}
}
if(Character.isLowerCase(cur)) {
atom += cur;
}
if(Character.isDigit(cur)) {
digit += cur;
}
}
// 处理最后一次
if(!atom.equals("")) {
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
}
return treeMap;
}
【处理括号的情况】
一般 “(”, “)” 需要用到递归的思路，大致的思想是
- 遇到“（” 开始递归
-
遇到“）” 结束递归
在开始递归处的代码，我们需要将递归的结果追加到TreeMap中
在结束递归处的代码，因为遇到“）”也可能是一个原子数量对寻找的结束标志，结束递归前要先将此时的atom和digit加入到TreeMap中，除此之外“）”后面可能会跟数字，还要根据会面的数字对此时TreeMap的数据进行翻倍，下面是代码。
public TreeMap<String, Integer> countAtoms(Deque<Character> formulaDeque) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
String atom = "";
String digit = "";
while(!formulaDeque.isEmpty()) {
char cur = formulaDeque.poll();
if(cur == '(') { // 开始递归操作
// 将递归的结果追加到TreeMap
TreeMap<String, Integer> nextTreeMap = countAtoms(formulaDeque);
for(String key : nextTreeMap.keySet()) {
treeMap.put(key, treeMap.getOrDefault(key, 0) + nextTreeMap.get(key));
}
}
if(Character.isUpperCase(cur)) {
if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
atom += cur;
} else { // 结束，遇到下一个大写字母，记录原子和数量
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
// 更新
atom = "" + cur;
digit = "";
}
}
if(Character.isLowerCase(cur)) {
atom += cur;
}
if(Character.isDigit(cur)) {
digit += cur;
}
if(cur == ')') { // 结束递归
// 如果此时atom非空，“）”在成了一次寻找atom和digit对结束，应该返回结果前加入TreeMap
if(!atom.equals("")) {
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
}
// 如果“）”后还有数字，要根据数字值对TreeMap里面的数据进行翻倍操作
String nextDigit = "";
while(!formulaDeque.isEmpty() && Character.isDigit(formulaDeque.peekFirst())) {
nextDigit += formulaDeque.poll();
}
if(!nextDigit.equals("")) {
for(String key : treeMap.keySet()) {
treeMap.put(key, treeMap.get(key) * Integer.parseInt(nextDigit));
}
}
// 返回递归结果
return treeMap;
}
}
if(!atom.equals("")) {
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
}
return treeMap;
}
【最后完整代码】（Java）
class Solution {
public String countOfAtoms(String formula) {
Deque<Character> formulaDeque = new LinkedList<>();
for(int i = 0; i < formula.length(); ++i) {
formulaDeque.offer(formula.charAt(i));
}
TreeMap<String, Integer> treeMap = countAtoms(formulaDeque);
String res = "";
for(String key : treeMap.keySet()) {
if(treeMap.get(key) > 1) {
res += key + treeMap.get(key);
} else {
res += key;
}
}
return res;
}
public TreeMap<String, Integer> countAtoms(Deque<Character> formulaDeque) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
String atom = "";
String digit = "";
while(!formulaDeque.isEmpty()) {
char cur = formulaDeque.poll();
if(cur == '(') {
TreeMap<String, Integer> nextTreeMap = countAtoms(formulaDeque);
for(String key : nextTreeMap.keySet()) {
treeMap.put(key, treeMap.getOrDefault(key, 0) + nextTreeMap.get(key));
}
}
if(Character.isUpperCase(cur)) {
if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
atom += cur;
} else { // 结束，遇到下一个大写字母，记录原子和数量
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
// 更新
atom = "" + cur;
digit = "";
}
}
if(Character.isLowerCase(cur)) {
atom += cur;
}
if(Character.isDigit(cur)) {
digit += cur;
}
if(cur == ')') {
if(!atom.equals("")) {
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
}
String nextDigit = "";
while(!formulaDeque.isEmpty() && Character.isDigit(formulaDeque.peekFirst())) {
nextDigit += formulaDeque.poll();
}
if(!nextDigit.equals("")) {
for(String key : treeMap.keySet()) {
treeMap.put(key, treeMap.get(key) * Integer.parseInt(nextDigit));
}
}
return treeMap;
}
}
if(!atom.equals("")) {
if(digit.equals("")) {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + 1);
} else {
treeMap.put(atom, treeMap.getOrDefault(atom, 0) + Integer.parseInt(digit));
}
}
return treeMap;
}
}
虽然代码效率不高，但是这种化繁为简，由简入深的解题思路还是很值得记录一下的，希望能帮助到大家。
出处：https://www.cnblogs.com/blogs-jch/p/14979657.html
最新更新
python爬虫及其可视化
使用python爬取豆瓣电影短评评论内容
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀（爬取学校通知公告）
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求：requests模块基础使用必知必会
SQL SERVER中递归
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析：SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL，这些神奇的特性你知道吗？
openGauss内核分析：执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
uniapp/H5 获取手机桌面壁纸 (静态壁纸）
[前端] DNS解析与优化
为什么在js中需要添加addEventListener（）？
JS模块化系统
js通过Object.defineProperty() 定义和控制对象
这是目前我见过最好的跨域解决方案！
减少回流与重绘
减少回流与重绘
如何使用KrpanoToolJS在浏览器切图
performance.now() 与 Date.now() 对比