вся история решения проблемы leetcode Hard и мои ошибки
Это воскресенье !!! Я думал решить какую-то задачу калькулятора на leetcode, потому что недавно я работал над решением выражения, которое содержит побитовое и, побитовое или и побитовое нет, я расскажу вам позже в другом посте об этой истории.
Во-первых, просто расскажите о проблеме базового калькулятора, поэтому прочитайте условие задачи.
Проблема
224. Базовый калькулятор ( Сложный ) 4069 лайков 325 дизлайков
Получив строку s, представляющую допустимое выражение, реализуйте базовый калькулятор для его вычисления и возвращайте результат вычисления.
Примечание. Вам запрещено использовать какие-либо встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример 1:
Input: s = "1 + 1" Output: 2
Пример 2:
Input: s = " 2-1 + 2 " Output: 3
Пример 3:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
Ограничения:
1 <= s.length <= 3 * 105sсостоит из цифр'+','-','(',')'и' '.sпредставляет допустимое выражение.'+'не используется как унарная операция (т. е."+1"и"+(2 + 3)"недействительны).'-'можно использовать как унарную операцию (т. е. допустимы"-1"и"-(2 + 3)").- Во входных данных не будет двух последовательных операторов.
- Каждое число и текущее вычисление помещаются в 32-битное целое число со знаком.
Решение
Итак, давайте начнем, если вы не читали, не волнуйтесь, я уверен, что вы занимались этой простой математикой в старшей школе.
Я дал почти 3 попытки решить эту проблему, из которых 2 были неправильными, и позже она была принята. (Внутренняя ошибка возникла из-за проблемы с сетью, так что не принимайте во внимание)
Решение №1 [ 18.09.2022 13:36 Неверный ответ ]
Я был уверен, что пробел нужно отбросить, а цифры могут быть больше 1, поэтому я буду отслеживать цифры во временной переменной и отслеживать оператор, который в этом случае «+» или «-».
и это мое решение простое, чистое и приятное, пока я его не представил.
class Solution {
public int calculate(String s) {
// ignore space and brackets
// care about only digits and '+' and '-'
int temp = 0;
int result = 0;
int plusSign = 1;
for(char x: s.toCharArray()) {
if(x == '+' || x == '-') {
result += (plusSign)*temp;
plusSign = (x=='+') ? 1 : -1;
temp = 0;
} else if(x >= '0' && x <= '9') {
temp = 10*temp + (x-'0');
}
}
result += (plusSign*temp);
return result;
}
}
Решение №2 [ 18.09.2022 13:43 Неверный ответ ]
Когда я выполнил решение № 1 и получил неправильный ответ для приведенного ниже случая
Тогда я глубоко вздохнул и подумал, как я мог забыть этот случай, будучи студентом-математиком?
Затем я изменяю свой код, проверяя знак перед скобками. Если знак перед скобками минус, я инвертирую все внутренние знаки, значит, если это минус, я буду считать его плюсом, а если это плюс, я буду считать это минусом .
а затем я написал этот простой, чистый и потный код, пока не отправил его.
class Solution {
public int calculate(String s) {
int temp = 0;
int result = 0;
int plusSign = 1;
boolean invertMode = false;
for(char x: s.toCharArray()) {
if(x == '+' || x == '-') {
result += (plusSign)*temp;
plusSign = (x=='+') ? 1 : -1;
if(invertMode) plusSign *= -1;
temp = 0;
} else if(x >= '0' && x <= '9') {
temp = 10*temp + (x-'0');
} else if(x == '(') {
if(plusSign == -1) invertMode = true;
else invertMode = false;
} else if(x == ')') {
invertMode = false;
}
}
result += (plusSign*temp);
return result;
}
}
Решение#3 [ 18.09.2022 13:47 Принято ]
Угадайте, что я получил?
После двух быстрых попыток у меня появилось некоторое недоверие к своим навыкам кодирования, но потом я понял, что виноваты были мои математические навыки, потому что я не учёл вложенные скобки.
💡 Whenever you have to deal with nested brackets then Stack is what you are looking for.
Итак, я взял стек и вставил логическое значение, которое указывает знаки, которые нужно инвертировать или нет, и выталкивал их, когда встречал закрывающую скобку.
Затем я модифицирую код, а затем запускаю этот сложный, дерьмовый код.
class Solution {
public int calculate(String s) {
int temp = 0;
int result = 0;
int plusSign = 1;
Stack<Boolean> stack = new Stack<>();
for(char x: s.toCharArray()) {
if(x == '+' || x == '-') {
result += (plusSign)*temp;
plusSign = (x=='+') ? 1 : -1;
if(!stack.isEmpty() && stack.peek()) plusSign *= -1;
temp = 0;
} else if(x >= '0' && x <= '9') {
temp = 10*temp + (x-'0');
} else if(x == '(') {
if(plusSign == -1) {
stack.push(true);
} else {
stack.push(false);
}
} else if(x == ')') {
stack.pop();
}
}
result += (plusSign*temp);
return result;
}
}
Угадайте, что я получил?
я! ты правильно угадал, умный мальчик. (Я знаю, что вы прочитали заголовок)
Я сделал глубокий вдох и открыл среду, чтобы рассказать вам всю эту историю, ребята, я имею в виду, что не знаю, почему она помечена, поскольку трудная проблема может быть из-за глупой ошибки или крайних случаев, которые мы пропустили в спешке.
Кого это волнует (я не участвую в интервью)? Я решил проблему!!!
Вот мой код после некоторой умной оптимизации кода, чтобы сделать его чистым.
- Сначала я убрал проверку на пустой стек, поэтому вставил 1 значение.
- Я ввел целочисленное значение вместо логического.
class Solution {
public int calculate(String s) {
int temp = 0;
int result = 0;
int plusSign = 1;
Stack<Integer> stack = new Stack<>();
stack.push(1);
for(char x: s.toCharArray()) {
if(x == '+' || x == '-') {
result += (plusSign)*temp;
plusSign = stack.peek() * (x=='+' ? 1 : -1);
temp = 0;
} else if(x >= '0' && x <= '9') {
temp = 10*temp + (x-'0');
} else if(x == '(') {
stack.push(plusSign);
} else if(x == ')') {
stack.pop();
}
}
result += (plusSign*temp);
return result;
}
}
Так что, если вы дочитали до конца, пожалуйста, проголосуйте, чтобы я мог знать, сколько из вас дочитали до конца со мной.
