題目鏈接：

726.原子數(shù)量

題目難度：困難?

題目描述：

給定一個化學式formula（作為字符串），返回每種原子的數(shù)量。

原子總是以一個大寫字母開始，接著跟隨0個或任意個小寫字母，表示原子的名字。

如果數(shù)量大于 1，原子后會跟著數(shù)字表示原子的數(shù)量。如果數(shù)量等于 1 則不會跟數(shù)字。例如，H2O 和 H2O2 是可行的，但 H1O2 這個表達是不可行的。

兩個化學式連在一起是新的化學式。例如?H2O2He3Mg4 也是化學式。

一個括號中的化學式和數(shù)字（可選擇性添加）也是化學式。例如 (H2O2) 和 (H2O2)3 是化學式。

給定一個化學式，輸出所有原子的數(shù)量。格式為：第一個（按字典序）原子的名子，跟著它的數(shù)量（如果數(shù)量大于 1），然后是第二個原子的名字（按字典序），跟著它的數(shù)量（如果數(shù)量大于 1），以此類推。

示例 1:

輸入: formula = "H2O" 輸出: "H2O" 解釋: 原子的數(shù)量是 {'H': 2, 'O': 1}。

示例 2:

輸入: formula = "Mg(OH)2" 輸出: "H2MgO2" 解釋: 原子的數(shù)量是 {'H': 2, 'Mg': 1, 'O': 2}。

示例 3:

輸入: formula = "K4(ON(SO3)2)2" 輸出: "K4N2O14S4" 解釋: 原子的數(shù)量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

注意:

• 所有原子的第一個字母為大寫，剩余字母都是小寫。
• formula的長度在[1, 1000]之間。
• formula只包含字母、數(shù)字和圓括號，并且題目中給定的是合法的化學式。

解題思路與解題代碼：

# -*- coding: UTF-8 -*- class Solution(object):def countOfAtoms(self, formula):stack = list()# 第一步將每個元素、數(shù)字、括號獨立出來，也就是說有的元素有兩個字母組成，有的數(shù)字是10以上的# 因此要把他們組合i = 0n = len(formula)while i < n:if formula[i].isalpha():if formula[i].islower():c = stack.pop()c = c + formula[i]stack.append(c)else:stack.append(formula[i])i += 1elif formula[i] == '(':stack.append(formula[i])i += 1elif formula[i] == ')':stack.append(formula[i])i += 1else:num_str = formula[i]i += 1while i < n and formula[i].isdigit():num_str += formula[i]i += 1stack.append(num_str)# 組合結(jié)果如下# print stack# ['K', '4', '(', 'O', 'N', '(', 'S', 'O', '3', ')', '2', ')', '2']# 第二步 有的元素只有一個，因此要把1補齊i = 0m = len(stack)-1tmp_stack = list()for i in range(m):tmp_stack.append(stack[i])if stack[i].isalpha():if not stack[i+1].isdigit():tmp_stack.append("1")tmp_stack.append(stack[m])if stack[m].isalpha():tmp_stack.append("1")stack = tmp_stack# 補齊結(jié)果如下# print stack# ['K', '4', '(', 'O', '1', 'N', '1', '(', 'S', '1', 'O', '3', ')', '2', ')', '2']# 第三步，開始遍歷，進行計算，每次遇到一個“）”都往回找“（”，把括號外的數(shù)字乘進去，并組合元素和數(shù)字stack2 = list()i = 0l = len(stack)while i < l:if stack[i].isalpha():stack2.append([stack[i],stack[i+1]])i += 2elif stack[i] == '(':stack2.append(stack[i])i += 1elif stack[i] == ')':num = int(stack[i+1])tmp = list()c = stack2.pop()while i > 0 and c != '(':c1 = [c[0], str(int(c[1]) * num)]tmp.append(c1)c = stack2.pop()stack2.extend(tmp)i += 2# print stack2# [['K', '4'], ['S', '4'], ['O', '12'], ['N', '2'], ['O', '2']]# 第四步，計算基本完成，將結(jié)果中重復元素合并，result_dict = {}for i in stack2:if result_dict.has_key(i[0]):count = result_dict[i[0]] + int(i[1])result_dict[i[0]] = countelse:result_dict[i[0]] = int(i[1])result = ""sor = sorted(result_dict)for key in sor:if result_dict[key] == 1:result += keyelse:result += str(key)+str(result_dict[key])print result# K4N2O14S4return result# a = Solution() # a.countOfAtoms("K4(ON(SO3)2)2")

?時間復雜度： O(n)

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode-726. 原子的数量(python2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。