726. Number of Atoms

LeetCode hard original: C# #bit-manipulation #csharp #hard #hash-table #leetcode #sort #stack #string #tree

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Если задана строковая формула, представляющая химическую формулу, return количество атомов. Атомный element всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество elementов. НаVí dụ, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. НаVí dụ, "H2O2He3Mg4" также является формулой.

Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. НаVí dụ, "(H2O2)" и "(H2O2)3" являются формулами.

returns количество всех elementов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые Ví dụы генерируются таким образом, чтобы все значения в выводе помещались в 32-битное số nguyên.

Ví dụ:

Input: formula = "H2O"

Output: "H2O"

C# lời giải

đã khớp/gốc

public class Solution {
    public string CountOfAtoms(string formula) {
        var stack = new Stack<Dictionary<string, int>>();
        stack.Push(new Dictionary<string, int>());
        int n = formula.Length;
        int i = 0;
        while (i < n) {
            if (formula[i] == '(') {
                stack.Push(new Dictionary<string, int>());
                i++;
            } else if (formula[i] == ')') {
                var top = stack.Pop();
                i++;
                int start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                foreach (var name in top.Keys) {
                    int count = top[name];
                    if (stack.Peek().ContainsKey(name)) {
                        stack.Peek()[name] += count * multiplicity;
                    } else {
                        stack.Peek()[name] = count * multiplicity;
                    }
                }
            } else {
                int start = i;
                i++;
                while (i < n && Char.IsLower(formula[i])) {
                    i++;
                }
                string name = formula.Substring(start, i - start);
                start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                if (stack.Peek().ContainsKey(name)) {
                    stack.Peek()[name] += multiplicity;
                } else {
                    stack.Peek()[name] = multiplicity;
                }
            }
        }
        var countMap = stack.Pop();
        var sb = new StringBuilder();
        foreach (var name in countMap.Keys.OrderBy(x => x)) {
            sb.Append(name);
            int count = countMap[name];
            if (count > 1) {
                sb.Append(count);
            }
        }
        return sb.ToString();
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string CountOfAtoms(string formula) {
        var stack = new stack<unordered_map<string, int>>();
        stack.push(new unordered_map<string, int>());
        int n = formula.size();
        int i = 0;
        while (i < n) {
            if (formula[i] == '(') {
                stack.push(new unordered_map<string, int>());
                i++;
            } else if (formula[i] == ')') {
                var top = stack.pop();
                i++;
                int start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                foreach (var name in top.Keys) {
                    int count = top[name];
                    if (stack.Peek().count(name)) {
                        stack.Peek()[name] += count * multiplicity;
                    } else {
                        stack.Peek()[name] = count * multiplicity;
                    }
                }
            } else {
                int start = i;
                i++;
                while (i < n && Char.IsLower(formula[i])) {
                    i++;
                }
                string name = formula.Substring(start, i - start);
                start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                if (stack.Peek().count(name)) {
                    stack.Peek()[name] += multiplicity;
                } else {
                    stack.Peek()[name] = multiplicity;
                }
            }
        }
        var countMap = stack.pop();
        var sb = new StringBuilder();
        foreach (var name in countMap.Keys.OrderBy(x => x)) {
            sb.Append(name);
            int count = countMap[name];
            if (count > 1) {
                sb.Append(count);
            }
        }
        return sb.ToString();
    }
}

Java lời giải

đã khớp/gốc

import java.util.*;

public class Solution {
    public String countOfAtoms(String formula) {
        Stack<Map<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        int n = formula.length();
        int i = 0;
        
        while (i < n) {
            if (formula.charAt(i) == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (formula.charAt(i) == ')') {
                Map<String, Integer> top = stack.pop();
                i++;
                int start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                for (String name : top.keySet()) {
                    int count = top.get(name);
                    stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count * multiplicity);
                }
            } else {
                int start = i;
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String name = formula.substring(start, i);
                start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
            }
        }
        
        Map<String, Integer> countMap = stack.pop();
        StringBuilder sb = new StringBuilder();
        for (String name : new TreeMap<>(countMap).keySet()) {
            sb.append(name);
            int count = countMap.get(name);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }
}

JavaScript lời giải

đã khớp/gốc

var countOfAtoms = function(formula) {
    const stack = [new Map()];
    let i = 0, n = formula.length;
    
    while (i < n) {
        if (formula[i] === '(') {
            stack.push(new Map());
            i++;
        } else if (formula[i] === ')') {
            const top = stack.pop();
            i++;
            let multiplicity = 0;
            while (i < n && !isNaN(formula[i])) {
                multiplicity = multiplicity * 10 + parseInt(formula[i]);
                i++;
            }
            multiplicity = multiplicity || 1;
            for (const [name, count] of top) {
                stack[stack.length - 1].set(name, (stack[stack.length - 1].get(name) || 0) + count * multiplicity);
            }
        } else {
            let start = i;
            i++;
            while (i < n && formula[i] >= 'a' && formula[i] <= 'z') {
                i++;
            }
            const name = formula.slice(start, i);
            let multiplicity = 0;
            while (i < n && !isNaN(formula[i])) {
                multiplicity = multiplicity * 10 + parseInt(formula[i]);
                i++;
            }
            multiplicity = multiplicity || 1;
            stack[stack.length - 1].set(name, (stack[stack.length - 1].get(name) || 0) + multiplicity);
        }
    }
    
    const countMap = stack.pop();
    return Array.from(countMap).sort().map(([name, count]) => name + (count > 1 ? count : '')).join('');
};

Python lời giải

đã khớp/gốc

import collections

def countOfAtoms(formula: str) -> str:
    stack = [collections.Counter()]
    i, n = 0

    while i < n:
        if formula[i] == '(':
            stack.append(collections.Counter())
            i += 1
        elif formula[i] == ')':
            top = stack.pop()
            i += 1
            i_start = i
            while i < n and formula[i].isdigit():
                i += 1
            multiplicity = int(formula[i_start:i] or 1)
            for name, count in top.items():
                stack[-1][name] += count * multiplicity
        else:
            i_start = i
            i += 1
            while i < n and formula[i].islower():
                i += 1
            name = formula[i_start:i]
            i_start = i
            while i < n and formula[i].isdigit():
                i += 1
            multiplicity = int(formula[i_start:i] or 1)
            stack[-1][name] += multiplicity

    result = ''
    for name in sorted(stack[-1]):
        result += name
        if stack[-1][name] > 1:
            result += str(stack[-1][name])
    
    return result

Go lời giải

đã khớp/gốc

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"
)

func countOfAtoms(formula string) string {
    stack := []map[string]int{{}}
    n := len(formula)
    i := 0

    for i < n {
        if formula[i] == '(' {
            stack = append(stack, map[string]int{})
            i++
        } else if formula[i] == ')' {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            i++
            iStart := i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            for name, count := range top {
                stack[len(stack)-1][name] += count * multiplicity
            }
        } else {
            iStart := i
            i++
            for i < n && unicode.IsLower(rune(formula[i])) {
                i++
            }
            name := formula[iStart:i]
            iStart = i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            stack[len(stack)-1][name] += multiplicity
        }
    }

    countMap := stack[0]
    keys := make([]string, 0, len(countMap))
    for key := range countMap {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    result := ""
    for _, name := range keys {
        result += name
        if countMap[name] > 1 {
            result += strconv.Itoa(countMap[name])
        }
    }
    return result
}

Algorithm

Используйте стек для отслеживания текущего уровня скобок.

Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее number, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.

После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.