ARTS打卡44-在对赌游戏中如何套利

Algorithm做算法题，Review点评英文文章，Tip总结技术技巧，Share做技术分享。每周打卡一次，这就是ARTS打卡。

1. 做算法题

LeetCode题678. 有效的括号字符串^[1]

题目描述：

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。任何右括号 ) 必须有相应的左括号 ( 。左括号 ( 必须在对应的右括号之前 )。

*
可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。一个空字符串也被视为有效字符串。

示例 1:输入: "()" 输出: True 示例 2:输入: "()" 输出: True 示例 3:输入: "())" 输出: True

解题思路：利用两个栈，一个保存字符串中(
的序号（左括号栈），一个保存字符串中*
的序号（星号栈）。出现)
时查看左括号栈，如果有元素就弹出，如果没有就查看星号栈，如果有元素就弹出，如果没有直接返回False。遍历完字符串后，如果左括号栈清空，返回True，如果未清空，则与星号栈依次比较栈顶元素，如果左括号栈元素值更大则返回False，更小则两个栈都弹出栈顶，继续比较新的栈顶，直到左括号清空了返回True。

解题代码：

class Solution:
    def checkValidString(self, s: str) -> bool:
        if len(s) == 0: return True
        branket_stack = []
        star_stack = []
        for i in range(len(s)):
            if s[i] is '(':
                branket_stack.append(i)
            elif s[i] is '*':
                star_stack.append(i)
            else:
                if len(branket_stack) > 0:
                    branket_stack.pop()
                elif len(star_stack) > 0:
                    star_stack.pop()
                else:
                    return False
        if len(branket_stack) == 0:
            return True
        elif len(branket_stack) > len(star_stack):
            return False
        else:
            while len(branket_stack) != 0:
                if branket_stack[-1] > star_stack[-1]:
                    return False
                else:
                    branket_stack.pop()
                    star_stack.pop()
            return True

2. 点评英文文章

文章How to Create a Telegram Chatbot^[2]介绍了如何用Python写一个Telegram聊天机器人。代码中需要应用Telegram的库PyTelegramBotAPI ，应该是封装了与Telegram交互的底层细节。机器人代码实现比较简单，最后的效果类似于微信公众号的消息自动回复。

3. 技术技巧

如果自己写正则表达式容易遗漏一些情况，有一个正则表达式搜索引擎^[3]，收入了各类正则表达式，不妨作为参考。

4. 技术分享

该网站^[4]通过概率分析得出什么条件下可以在两个下注平台之间套利，与押注大小无关，只需要平台A下注赢的概率+平台B下注败的概率小于1即可。

引用链接

[1]
 LeetCode题678. 有效的括号字符串: https://leetcode-cn.com/problems/valid-parenthesis-string/
[2]
 How to Create a Telegram Chatbot: https://hackernoon.com/how-to-create-a-telegram-chatbot-nb3g34x6
[3]
 正则表达式搜索引擎: https://regexlib.com/
[4]
 该网站: http://morefreeze.github.io/2020/12/president-arbitrage.html