هذه إحدى مشكلات LeetCode التي استمتعت بحلها. لقد قمت بحلها في Golang، وأنا بالفعل مبتدئ في Go، وبدأت التعلم فيها منذ أسبوع واحد فقط.

حدس

هذه المشكلة هي نسخة أخرى من تنفيذ برنامج الآلة الحاسبة الذي يأخذ سلسلة ويقيمها. يجب عليك الحل عن طريق مقارنة الأقواس الداخلية بالأقواس الخارجية حتى تحصل على النتيجة النهائية. من الأفضل وصف هذه المشكلات من خلال المكدس، فأنت تقوم فقط بتنفيذ CallStack الذي عند فتح قوس جديد، تقوم بالدفع إلى المكدس، وعند إغلاقه، تقوم فقط بالخروج من المكدس. في الإغلاق الأخير نستدعي Eval للحصول على النتيجة النهائية.

لدينا 3 عمليات يمكن إجراؤها في الآلة الحاسبة لدينا، وهناك بعض الحقائق المعروفة عنها:

• و: يكون صحيحًا حتى تجد خطأ (خطأ واحد يكفي)
• OR: إنه خطأ حتى تجد صحيحًا (صحيح واحد يكفي)
• Not: إنه عكس الوسيطة الخاصة به.

لذلك، لا نحتاج إلى الاحتفاظ بجميع القيم لكل عملية لمعرفة نتيجتها النهائية. إذا كنا نحل و، فما عليك سوى الحفاظ على ما إذا وجدت خطأ أم لا، إذا كان OR، فاحتفظ بما إذا وجدت صحيحًا أم لا، وإذا كان NOT، فستكون بالفعل قيمة واحدة ستقيمها على أنها قيمة معاكسة.

يقترب

نقوم بتنفيذ بنية مخصصة: CallStack، التي تحتوي على شريحتين، واحدة للعملية وواحدة للقيمة التي سنقوم بتقييمها.

مكدس الاستدعاءات له طرق:

• Push: يستخدم لدفع القيم والعمليات إلى الشريحتين الموجودتين لدينا. تدفع العمليات قيمة جديدة إلى الشريحتين، وتقوم القيم (t أو f) فقط بتعديل آخر قيمة تم إدخالها في شريحة القيم.
• Pop: قم بإزالة القيمة الأخيرة من الشريحتين، وقم بتقييم القيمة المنبثقة بالعملية المنبثقه واستخدم النتيجة لتعديل القيمة الأخيرة الجديدة بعد التفرقع.
• Eval: يتم استدعاؤه عندما يكون آخر قوس إغلاق لتقييم آخر قيمة متبقية في شريحة القيم مع آخر عملية متبقية في شريحة العمليات.

يمكن تحسين الحل بشكل أكبر من خلال إنهاء تقييم Ands بمجرد العثور على خطأ، و Ors بمجرد العثور على صحيح، سأترك ذلك لك لتفعله إذا أردت :)

تعقيد

• تعقيد الوقت:

  
  على)

• تعقيد الفضاء:

  
  على)

شفرة

اكتب بنية CallStack { العمليات []سلسلة القيم [] كثافة العمليات } وظيفة NewCallStack() *CallStack { العودة &CallStack{ العمليات: جعل ([]سلسلة، 0)، القيم: جعل ([]int، 0)، } } وظيفة (s *CallStack) PushOperation(op string) { s.operations = إلحاق (s.operations، المرجع) فار newVal int تبديل المرجع { الحالة لا: نيو فال = 0 تقصير: نيو فال = 1 } s.values ​​= إلحاق (s.values، newVal) } func (s *CallStack) PushValue(op string, char string) { تبديل المرجع { حالة و: إذا شار == ​​"و" { s.values[len(s.values)-1] = -1 } حالة أو: إذا شار == ​​"ر" { s.values[len(s.values)-1] = -1 } الافتراضي: // لا إذا شار == ​​"ر" { s.values[len(s.values)-1] = 1 } آخر { s.values[len(s.values)-1] = -1 } } } func (s *CallStack) Push(char string) { تبديل شار { الحالة لا، و، أو: s.pushOperation(شار) تقصير: s.pushValue(s.operations[len(s.operations) - 1], char) } } func eval (سلسلة المرجع، val int) bool { تبديل المرجع { حالة و: إذا فال == 1 { العودة صحيحا } آخر { العودة كاذبة } حالة أو: إذا فال == -1 { العودة صحيحا } آخر { العودة كاذبة } الافتراضي: // لا إذا فال type CallStack struct { operations []string values []int } func NewCallStack() *CallStack { return &CallStack{ operations: make([]string, 0), values: make([]int, 0), } } func (s *CallStack) pushOperation(op string) { s.operations = append(s.operations, op) var newVal int switch op { case Not: newVal = 0 default: newVal = 1 } s.values = append(s.values, newVal) } func (s *CallStack) pushValue(op string, char string) { switch op { case And: if char == "f" { s.values[len(s.values)-1] = -1 } case Or: if char == "t" { s.values[len(s.values)-1] = -1 } default: // Not if char == "t" { s.values[len(s.values)-1] = 1 } else { s.values[len(s.values)-1] = -1 } } } func (s *CallStack) Push(char string) { switch char { case Not, And, Or: s.pushOperation(char) default: s.pushValue(s.operations[len(s.operations) - 1], char) } } func eval(op string, val int) bool { switch op { case And: if val == 1 { return true } else { return false } case Or: if val == -1 { return true } else { return false } default: // Not if val