![image.png](/static/img/7551a468ac3ce83435782ea9fade1b71.image.webp)

> 1 ^ 3 = 2
> 
> 2 ^ 3 = 1
> 



```cpp
class Solution {
public:
    int magicalString(int n) {
        int res = 0;
        int tag = 2;
        string s1 = "";
        string s2 = "12";
        for (int i = 0; i < n; i++) {
            if (i >= s2.size()) s2 = s1;
            if (s2[i] == '1') res++;
            for (int j = 0; j < s2[i] - '0'; j++) {
                s1 += (tag^3) + '0';
            }
            tag ^= 3;
        }
        return res;
    }
};
```

双指针3

Merkle Tree是一种用于完整性校验的数据结构，也被称为哈希树。它由计算机科学家Ralph Merkle提出，并以他的名字命名。Merkle Tree在点对点网络、Git版本控制系统、IPFS协议以及比特币和以太坊等项目中得到广泛应用。



哈希（Hash）是Merkle Tree的基础概念。哈希是一种将数据转换为固定长度字符串的算法。通过对数据进行哈希运算，可以得到一个唯一的哈希值。即使数据发生微小变化，其哈希值也会完全不同。因此，通过比较哈希值，可以检查数据是否被损坏或篡改。

在点对点网络中，数据通常被分割成多个小块进行下载，并且存在不稳定或不可信的机器。为了解决这个问题，可以使用哈希列表（Hash List）。哈希列表是由多个数据块的哈希值组成的列表，这些哈希值之间存在兄弟关系。通过下载种子文件（包含哈希列表），可以从任意机器上下载数据块，并通过根哈希来验证每个哈希的正确性。

Merkle Tree是在哈希列表的基础上引入了树形结构，以获得更高的灵活性。在Merkle Tree中，数据被分成小块，并计算每个块的哈希值。然后，将相邻的两个哈希值合并成一个字符串，并计算该字符串的哈希值，得到一个新的哈希值。这个过程不断重复，直到最终形成一棵倒挂的树，树根被称为Merkle Root。Merkle Tree可以用于验证大型数据的完整性。

---
Learn more:
1. [Merkle Tree - 知乎](https://zhuanlan.zhihu.com/p/103372259)
2. [区块链技术与应用-note - 知乎](https://zhuanlan.zhihu.com/p/635292249)
3. [https://zhuanlan.zhihu.com/p/22642813？ - 知乎](https://www.zhihu.com/question/51062163)

merkle树

![image.png](/static/img/85c71013771317487b1f1f93b81ba747.image.webp)



```cpp
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
  sort(g.begin(), g.end());
  sort(s.begin(), s.end());
  
  int i = 0, j = 0, ans = 0;
  
  while(i < g.size() && j < s.size()) {
    if(g[i] <= s[j]) {
      ans++;
      i++;
      j++;
    } else {
      j++;
    }
  }
  
  return ans;
}
};
```

双指针2

![image.png](/static/img/5e3a08cba6b8d017457ec191ac6d06e5.image.webp)



```cpp
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        while(i < s.size() && j < t.size()) {
          if(s[i] == t[j]) i++;
          j++;
        }
        return i == s.size();
    }
};
```

双指针（1）

![image.png](/static/img/fc75023f30e205a5dd327e259ed1352c.image.webp)



```cpp
class Solution {
public:
    int maxProduct(vector<string>& words) {

          int n = words.size();
          vector<int> masks(n);

          for(int i=0; i<n; i++) {
            int mask = 0;
            for(char c: words[i]) {
              mask |= 1<<(c-'a'); 
            }
            masks[i] = mask; 
          }

          int ans = 0;

          for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
              if((masks[i]&masks[j])==0) {
                ans = max(ans, int(words[i].size()*words[j].size()));
              }
            }
          }

          return ans;
    }
};
```