本文主要是介绍726. Number of Atoms,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接
思路
思路1
设置两个栈,一个放括号,另一个放Map,放一个左括号,就放一个Map,括号出栈时,把另一个栈头的map弹出,值加入到新的栈顶map。
public String countOfAtoms(String formula) {Deque<Character> stack1 = new ArrayDeque<>();Deque<Map<String, Integer>> stack2 = new ArrayDeque<>();Map<String, Integer> map = new HashMap<>();stack2.push(map);for (int i = 0; i < formula.length(); ) {char c = formula.charAt(i);if (c == '(') {stack1.push('(');stack2.push(new HashMap<>());i++;continue;}if (c == ')') {int num = 0;int j = i+1;for (; j < formula.length(); j++) {char c1 = formula.charAt(j);if (Character.isDigit(c1)) {num = num * 10 + Character.getNumericValue(c1); // bug2 = 写为了 +=} else {break;}}i = j;stack1.pop();Map<String, Integer> poll = stack2.poll();Map<String, Integer> peek = stack2.peek();for (String key: poll.keySet()) {if (peek.containsKey(key)) {peek.put(key, peek.get(key) + poll.get(key) * num);} else {peek.put(key, poll.get(key) * num); // bug1 没有乘以num}}continue;}if (Character.isUpperCase(c)) {String s = Character.toString(c);int num = 0;int j = i+1;for (; j < formula.length(); j++) {char c1 = formula.charAt(j);if (Character.isLowerCase(c1)) {s += Character.toString(c1);} else {break;}}for (; j < formula.length(); j++) {char c1 = formula.charAt(j);if (Character.isDigit(c1)) {num = num * 10 + Character.getNumericValue(c1);} else {break;}}num = num == 0 ? 1 : num;Map<String, Integer> peek = stack2.peek();if (peek.containsKey(s)) {peek.put(s, peek.get(s) + num);} else {peek.put(s, num);}i = j;continue;}System.out.println("出错了!" + i);}Map<String, Integer> pop = stack2.pop();List<String> list = new ArrayList<>();list.addAll(pop.keySet());Collections.sort(list);StringBuffer sb = new StringBuffer();for (String k: list) {Integer v = pop.get(k);sb.append(k);if (v > 1) {sb.append(v);}}return sb.toString();
}
优化
看了评论区的答案,发现存在括号的栈没有必要存在,可以去掉。
总结
思路正确,过程有两个bug。
1、没有乘以num;
2、= 写成了 +=
这篇关于726. Number of Atoms的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!