引言

今天又做到了 Leetcode 169. 多数元素 这一道题. 我依稀记得最优的解法叫做什么摩尔投票法. 但是我对它的印象竟然只有这个名字本身了 Orz. 对于这个算法本身倒是忘得一干二净. 于是我打算系统性地学习一下这个算法的原理, 并将它总结出来写成这篇博客. 不知道在哪里看到的一句话 :

Intro

前两个项目还算简单, 比较不复杂. 但是今天这个第三个项目难度确实是上升了(看游戏规则就知道这个有多复杂了). 感觉像是植物大战僵尸

所以我打算为他写一篇博客来整理一下写代码时候的思路. 话不多说, 让我们进入正题吧 !

Trees

Q1: Prune Min

Write a function that prunes a Tree t mutatively. t and its branches always have zero or two branches. For the trees with two branches, reduce the number of branches from two to one by keeping the branch that has the smaller label value. Do nothing with trees with zero branches.

Prune the tree in a direction of your choosing (top down or bottom up). The result should be a linear tree.

BNF

Q1: Grouping and Pipes

In this question, you will add support for grouping and piping.

Recall that grouping allows for an entire regular expression to be treated as a single unit, and piping allows for a pattern to match an expression on either side. Combined, these will let us create patterns which match multiple strings!

Define the group and pipe expressions in your grammar.

Regular Expressions

Q1: Calculator Ops

Write a regular expression that parses strings written in the 61A Calculator language and returns any expressions which have two numeric operands, leaving out the parentheses around them.

写一个符合 (operand operator1 operator2) 格式的正则表达式. 这个是比较简单的, 因为这里的运算符只有 +, -, *, /. 我们用 [] 括起来就可以, 但是要注意**- 需要用 \ 转义**

Q2: Roman Numerals

Write a regular expression that finds any string of letters that resemble a Roman numeral and aren’t part of another word. A Roman numeral is made up of the letters I, V, X, L, C, D, M and is at least one letter long.

For the purposes of this problem, don’t worry about whether or not a Roman numeral is valid. For example, “VIIIII” is not a Roman numeral, but it is fine if your regex matches it.