每周算法

面试题 16.17. 连续数列

难度简单83收藏分享切换为英文接收动态反馈

给定一个整数数组,找出总和最大的连续数列,并返回总和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        /*
            dp[j]  以j结束的最大连续数列
            我们只需要找到dp[0]到dp[i-1]中最大的一个
            dp[j] = dp[j-1] + j 
            dp[0] = nums[0]  
        */
        int max = nums[0] ;
        int dp_pre = nums[0];
        for(int i = 1 ; i < nums.size() ; i++){
            int tmp = dp_pre + nums[i];
            dp_pre = (tmp > nums[i])?tmp:nums[i];
            max = dp_pre > max ? dp_pre:max;
        } 
        return max;
    }
};

97. 交错字符串

难度中等468收藏分享切换为英文接收动态反馈

给定三个字符串 s1s2s3,请你帮忙验证 s3 是否是由 s1s2 交错 组成的。

两个字符串 st 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

提示:a + b 意味着字符串 ab 连接。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        /*
         f(i , j) 代表着 s1的前i个元素和s2的前j个元素是否能够交替构成s3  那么我们需要得到f(s1.size() , s2.size())
         f(i,j) = (f(i-1,j) && s1(i-1) == s3(i+j-1)) || (f(i,j-1) && s2(j-1) == s3(i+j-1))

         边界问题:
         f(0,0) = true  
         f(0,a) = false  (0 <= a <= s2.size())
         f(a,0) = false  (0 <= a <= s1.size())
        */
        // 这个二维数组为啥要设置的大一点   其实处理边界
        auto f = vector < vector <int> > (s1.size() + 1, vector <int> (s2.size() + 1, false));
        int n = s1.size(), m = s2.size(), t = s3.size();
        if (n + m != t)
            return false;
        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                // 处理边界
                if (i > 0) 
                    f[i][j] |= (f[i - 1][j] && s1[i - 1] == s3[p]);
                if (j > 0) 
                    f[i][j] |= (f[i][j - 1] && s2[j - 1] == s3[p]);
            }
        }
        return f[n][m];
    }
};
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        /*
         f(i , j) 代表着 s1的前i个元素和s2的前j个元素是否能够交替构成s3  那么我们需要得到f(s1.size() , s2.size())
         f(i,j) = (f(i-1,j) && s1(i-1) == s3(i+j-1)) || (f(i,j-1) && s2(j-1) == s3(i+j-1))
         以上状态的改变只和最近的一排有关 那么内存中如何做优化呢?
         f(j) 代表着 s2的前j个元素能够交替构成s3 那么我们需要得到f(s2.size())
         f(j) = (f(j) && s1(i-1) == s3(i+j-1)) || (f(j-1) && s2(j-1) == s3(i+j-1))
         边界问题:
         f(0,0) = true  
         f(0,a) = false  (0 <= a <= s2.size())
         f(a,0) = false  (0 <= a <= s1.size())
        */
        // 这个二维数组为啥要设置的大一点   其实处理边界
        auto f = vector <int> (s2.size() + 1, false);
        int n = s1.size(), m = s2.size(), t = s3.size();
        if (n + m != t) {
            return false;
        }
        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    // 这里为啥这么写  f(j) && s1(i-1) == s3(i+j-1) 其实这里的f[j] 就是上一行数据  也是就是 f[i-1][j]
                    f[j] &= (s1[i - 1] == s3[p]);
                }
                if (j > 0) {
                    f[j] |= (f[j - 1] && s2[j - 1] == s3[p]);
                }
            }
        }
        return f[m];
    }
};

每周论文阅读之博客学习

Mastering the Mempool: Your Intro to In-Flight Transactions (blocknative.com)

A Note On Nodes: Your Gateway To The Mempool (blocknative.com)

Why the Mempool Matters: The Hidden Competition for Confirmation (blocknative.com)

Mastering the Mempool

mempool是区块链的门户。在块上写入任何内容之前,它必须首先通过内存池。而Web3的这一重要部分常常被忽视。

由于mempool规定了如何将每个交易写入和确认到链上,因此了解mempool可以帮助您了解正在进行的交易的情况,并对区块链的工作方式进行深入了解。

在构建监控mempool的基础设施的过程中,我们学到了很多关于mempool的工作原理。我们想分享我们对以太坊生态系统这一迷人部分的见解。首先,让我们介绍什么是mempool,以及它对您、交易员、dapp和DeFi协议的重要性。

什么是mempool

区块链创建了一个永久性的交易分类账。一旦你写了,你就不能把它拆开。因此区块链需要一种机制来确定事务写入区块的顺序。mempool是区块链前面的动态暂存区域,它支持交易排序、交易费用优先排序和一般区块构建。

mempool这个词本身来自比特币。但在这篇文章中,我们将关注以太坊生态系统。mempool是指以太坊节点中的一组内存数据结构,它在挖掘候选事务之前存储这些事务。Geth称之为“transaction pool”;Parity 称之为“transaction queue”。不管名称如何,它都是内存中等待包含在块中的事务池。把它想象成一个“等待区”,让事务被接受到一个块中。

发送到以太坊节点的有效事务应进入mempool。但实际上没有一个内存池。相反,每个节点都有自己的mempool,它试图通过以太坊网络与其他节点(对等方)保持同步。由于网络通信并不总是可靠或及时的,每个节点都有一个稍微不同(有时明显不同)的mempool。此外,节点对于接受哪些事务有不同的规则(例如,最低gas价格和mempool大小限制)。

理想情况下,事务会离开节点的mempool,因为它们包含在块中。但是它们也可以离开,因为它们通过加速/取消被替换,或者由于节点的mempool配置而被丢弃。

Mempools 是区块链原语

mempool的概念是区块链本身的基础。而mempool的历史就是区块链的历史。

它是区块链如何将交易从用户的钱包转移到区块中的确认的核心组件。

不过,尽管mempool很重要,但在任何一家大型机构的白皮书中都没有提到它。维基百科上甚至都没有提到。

你还记得我们在这篇文章开头说的话吗?mempool经常被忽略。既然我们已经向您介绍了mempool的背景,那么让我们更详细地探讨一下它是如何成为典型事务流的一部分的。

Mempool如何适应典型的事务流?

典型的事务流包括以下步骤:

1. 首先,用户从Dapp或钱包发起交易,例如将资金发送到另一个帐户或合同
2. 然后用户用他们的钱包签署交易
3. 钱包将签名的交易发送到一个节点,通常称为网关节点,以进入以太坊网络(想想Infura或Pocket)
4. 该节点将验证事务是否有效,并将其添加到其mempool中
5. 由于节点连接到一组对等节点,因此它将事务广播到其他节点。
6. 这些对等节点将接收事务,对其进行验证,将其移动到自己的mempool中,并向其他对等节点广播,基本上是通过网络复制事务
7. 矿工作为一种特定的节点,也从对等方接收事务,对其进行验证,并尝试将其添加到块中
8. 最终,一个成功的矿工将一个带有事务的块添加到链中
9. 新的区块通过网络广播
10. 当所有节点从其对等节点接收到新的块时,它们会看到包含的事务并将其从mempool中删除

那是相当多的步骤。记住,这就是一切顺利的过程!在事情发生横向变化的情况下——正如它们不可避免地发生的那样——事务流会变得更加复杂。

节点:到Mempool的网关

每个Dapp都需要一个节点来连接到网络。签署事务时,该事务将通过节点发送到网络。在以太坊中,节点可以运行不同的软件——Geth和Parity是最常见的两种(请参阅ethernodes.org上的完整分类)。虽然Geth和Parity的工作方式有细微差别,但它们在今天的讨论中已经足够相似了。

当节点接收到您的事务时,该节点将执行一系列检查,以查看事务是否可以进入mempool,包括:

  • 签名是否有效(即交易未被篡改)?
  • 是否所有必需的元素(如To:和From:地址)都存在且有效?
  • 发件人地址是否为外部帐户(而不是合同帐户)?
  • 如果事务转移值,那么From:address余额是否包含该值?
  • 交易的Gas限额是否低于区块限额?
  • 事务是否适合本地mempool

如果事务通过了节点的检查,则该事务将添加到节点的mempool中。该节点还将向其他节点(称为对等节点)广播它。这些对等方中的每一个都将执行自己的检查—将有效的事务添加到其mempool中,然后将该事务广播给其对等方。此过程通常将事务传播到以太坊网络的整个网络。

进入mempool的有效事务然后进入两个池中的一个-挂起或排队。挂起池用于准备处理的事务。这些有资格开采,可能出现在下一个区块。排队池用于尚未准备好处理的事务,因为它们“无序”。

交易秩序

地址的交易顺序是区块链的关键安全特性。与传统的银行账户(通常使用集中的时间戳)一样,订单确保交易按预期顺序进行,同时防止重放攻击和重复支出。以太坊事务使用一个nonce,每个事务增加一个数字。

nonce保证了正确的交易顺序。临时顺序中的任何间隔(例如:31、32、33、35)表示节点可能尚未接收到事务。任何临时顺序有间隙的事务都会进入mempool的排队部分。

只要临时顺序中的间隔持续存在,排队池中的事务就会被卡住。这些卡住的交易可以锁定钱包,使其无法发送新的交易,将进入待定池,因此有资格得到确认。

nonce重用

一旦一个地址的nonce在一个块中被确认,它就不能被再次使用。这样可以确保事务不会重播。

但是,当事务位于mempool中时,它可以被具有相同nonce的新事务替换。这种替换功能可以加速和取消事务,实质上是用新事务覆盖mempool中的原始事务。

并非所有节点都相同

由于mempool可以使用大量的系统资源(特别是内存),因此节点操作员可以控制其mempool的配置方式。这反过来会影响哪些事务可以写入每个mempool以及它们的后续行为此外,以太坊生态系统中有不同类型的节点。这些节点都扮演着不同的角色:

完整节点-下载整个以太坊区块链和地址状态并验证新区块的任何计算机。矿工使用完整节点。

存档节点—一个完整的节点,它还保留事务和地址状态更改的所有历史记录。

轻节点-连接到完整节点作为区块链网关的计算机。光节点不验证块,也不维护整个区块链和地址状态。轻节点(客户端)没有mempool。

虽然您可以运行自己的节点来监控mempool,但许多交易员和构建者依赖Blocknative Advantage来获取以太坊、比特币、xDai和Binance的实时mempool数据。今天在mempool Explorer中了解更多信息并动手使用流式mempool数据。

为什么Mempool很重要:对确认的隐藏竞争

每一个待处理的以太坊事务都会在待确认的mempool中进行无形的竞争。

虽然mempool是区块链基础设施的一个关键部分,但许多人对mempool的工作原理,或者如何使用规则来对抗您的最佳利益,知之甚少。

  • 你在等你的交易确认吗?那是mempool。
  • 你是否被高昂的汽油费压垮了?那也是mempool。
  • 你是否对一笔阻塞了你钱包的交易感到沮丧?是的…mempool。
  • 你对自动机器人即时利用套利机会感到困惑吗?是 啊。你明白了。

幸运的是,在过去的几个月里,mempool已经开始走出阴影。 这些叙述说明了mempool是如何神秘、混乱,甚至完全危险的。直到最近,除了最老练、资金最雄厚的团队之外,所有人都无法动手使用mempool数据。

因此,Blocknative团队很高兴能够帮助这个无银行国家展示mempool的重要性。我们将介绍核心概念,然后探讨对交易者和建设者的影响,并总结一些新的、易于使用的工具,供您实际使用实时mempool数据。

Mempool:确认的竞争市场

mempool是一个竞争性的游戏,在这里,赢家可以以最低的费用尽快确认您的交易。当您批准并签署一个事务时,它会进入mempool,并加入成千上万的其他挂起的事务,这些事务正在争夺宝贵的块空间。

换言之,游戏正在进行中,您的交易将得到确认并进入链条。

但Gas价格是在你的交易进入mempool之前确定的。Gas价格越高,矿商将你的交易纳入下一区块的动机就越高,这使得mempool成为第一个价格拍卖。因此,mempool既不是一个静态的环境,也不是一个良性的环境,而是一个高度动态甚至混沌的系统。

这有效地使mempool成为链上确认和结算的实时市场。在这个市场上,你的交易与成千上万的其他交易并肩竞争,以引起矿工的注意。

了解竞争规则

为了帮助您参与竞争,以下是5个核心概念中的一些,它们共同构成了mempool市场的规则:

1.每个节点都有自己的版本

根据定义,mempool是预先达成共识的。这意味着网络中的每个节点都有自己独特的mempool版本。让你的手臂环绕整个mempool是几乎不可能的。

2.开放、公开

Mempool数据是开放的,可供整个网络公开使用。所以“每个人”都可以看到您的每个事务正在发生。但在其他人的交易进入链之前,你也可以看到他们的交易。

3.它是可变的

因为mempool是预先协商一致的,所以它是可变的。这意味着挂起的事务可以被替换事务覆盖,包括加速和取消。替换事务是赢得mempool竞争的关键工具,或者在条件变得不利时退出。

4.事务可能会被丢弃

网络拥塞会导致Gas价格快速上涨,使一些待处理的交易不再具有竞争力。考虑到网络上的许多节点具有有限的内存资源,特别是miner节点可能会丢弃没有竞争力的事务。如果事务被丢弃,它就会从mempool的大部分中消失。此外,如果没有复杂的基础设施,很难检测到事务已被丢弃。

5.交易可能会卡住

丢弃的事务可能会创建临时间隙,然后创建卡住的事务。卡住的交易将’冻结’任何进一步的交易,从您的钱包被确认,直到目前的差距得到解决。

正如您所见,mempool的规则异常复杂,而且经常以意想不到的方式相互作用。在这样的背景下,mempool现在经常被描绘成一片黑暗的森林,这并不奇怪。