1. Algorithm: 每周至少做一个 LeetCode 的算法题

笔者的文章：

算法：单词匹配290. Word Pattern

LeetCode全集请参考：LeetCode Github 大全

题目

290. Word Pattern



Given a pattern and a string s, find if s follows the same pattern.



Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.



Example 1:



Input: pattern = "abba", s = "dog cat cat dog"
Output: true



Example 2:



Input: pattern = "abba", s = "dog cat cat fish"
Output: false



Example 3:



Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false



Example 4:



Input: pattern = "abba", s = "dog dog dog dog"
Output: false



Constraints:



• 1 <= pattern.length <= 300

• pattern contains only lower-case English letters.

• 1 <= s.length <= 3000

• s contains only lower-case English letters and spaces ' '.

• s does not contain any leading or trailing spaces.

• All the words in s are separated by a single space.



方法一

方法1：两个哈希图

错误的直觉：

开始思考此问题的最幼稚的方法是拥有一个哈希表，跟踪哪个字符（pattern）映射到哪个单词（s）。当您扫描每个字符-单词对时，请更新此哈希映射以查找映射中未包含的字符。如果看到已经是映射键之一的字符，请检查当前单词是否与该字符映射到的单词匹配。如果它们不匹配，则可以立即返回False，否则，请继续扫描直到结束。



这种检查对于以下情况将非常有效：



• “ abba”和“ dog cat cat dog”->返回True。

• “ abba”和“ dog cat cat fish”->返回False。



但这将失败：



• “ abba”和“ dog dog dog dog”->返回True（预期False）。



一个解决方法是有两个哈希映射，一个用于将字符映射到单词，另一个用于将单词映射到字符。在扫描每个字符-单词对时，



• 如果字符不在字符到单词的映射中，则还要检查该单词是否也在单词到字符的映射中。

如果该单词已存在于单词到字符的映射中，则您可以False立即返回，因为它之前已与其他字符映射过。

否则，更新两个映射。

• 如果字符到单词映射中的字符为IN，则只需要检查当前单词是否与字符到单词映射中该字符映射到的单词匹配。如果没有，您可以False立即返回。



public boolean wordPatternWithTwoMap(String pattern, String s) {
    // check edge
    if (pattern == null || s == null) {
      return pattern == s;
    }
    int len = pattern.length();
    String[] sarray = s.split(" ");
    if (len != sarray.length) {
      return false;
    }
    Map<Character, String> pmap = new HashMap<>();
    Map<String, Character> smap = new HashMap<>();
    for (int i = 0; i < len; i++) {
      char c = pattern.charAt(i);
      String word = sarray[i];
      if (!pmap.containsKey(c)) {
        // smap contain, return false
        if (smap.containsKey(word)) {
          return false;
        }
        pmap.put(c, word);
        smap.put(word, c);
      } else {
        String mapword = pmap.get(c);
        if (!word.equals(mapword)) {
          return false;
        }
      }
      // build two map
      pmap.put(c, word);
      smap.put(word, c);
    }
    return true;
  }

复杂度分析



时间复杂度： O(N)哪里 ññ表示中的字数s或中的字符数pattern。



空间复杂度： O(M) 哪里 中号中号代表中的唯一字数s。即使我们有两个哈希图，字符到单词哈希图的空间复杂度为O(1) 因为最多可以有26个键。



附录：我们不能保留两个哈希映射，而只能保留字符到单词的映射，并且只要我们发现不在映射中的字符，就可以检查当前字符-单词对中的单词是否已经是当前值中的一个。字符到单词的映射。但是，这是为了获得更好的空间而付出的时间，因为检查哈希映射中的值是O(M) 操作地点 中号中号是哈希图中的键值对的数量。因此，如果我们决定采用这种方式，我们的时间复杂度将是O(NM)哪里 ññ是中的唯一字符数pattern。



与方法1相似的另一种方法是使用哈希集来跟踪遇到的单词。无需检查单词是否已存在于单词到字符的映射中，只需检查单词是否在遇到的单词哈希集中。而且，您无需将单词更新为字符映射，只需将单词添加到遇到的单词哈希集即可。即使哈希集和哈希图的big-O空间复杂度相同，哈希集也将具有更好的实际空间复杂度。



方法2：单索引哈希图

直觉

而不是拥有两个哈希图，我们可以有一个索引哈希图，它跟踪中每个字符pattern和中每个单词的首次出现s。遍历每个字符-单词对时，我们插入看不见的字符pattern和看不见的词s。



目的是确保每个字符和单词的索引匹配。一旦发现不匹配，我们可以返回False。



让我们来看一些例子。



• pattern：'abba'

• s：'dog cat cat dog'



1. 'a'和'dog'-> map_index = {'a': 0, 'dog': 0}

索引“ a”和索引“ dog”相同。

1. 'b'和'cat'-> map_index = {'a': 0, 'dog': 0, 'b': 1, 'cat': 1}

索引“ b”和索引“ cat”相同。

1. 'b'和'cat'-> map_index = {'a': 0, 'dog': 0, 'b': 1, 'cat': 1}

“ b”已在映射中，无需更新。

“ cat”已经在映射中，无需更新。

索引“ b”和索引“ cat”相同。

1. 'a'和'dog'-> map_index = {'a': 0, 'dog': 0, 'b': 1, 'cat': 1}

“ a”已经在映射中，无需更新。

“ dog”已经在映射中，无需更新。

索引“ a”和索引“ dog”相同。



• pattern：'abba'

• s：'dog cat fish dog'

1. 'a'和'dog'-> map_index = {'a': 0, 'dog': 0}

索引“ a”和索引“ dog”相同。

1. 'b'和'cat'-> map_index = {'a': 0, 'dog': 0, 'b': 1, 'cat': 1}

索引“ b”和索引“ cat”相同。

1. 'b'和'fish'-> map_index = {'a': 0, 'dog': 0, 'b': 1, 'cat': 1, 'fish': 2}

“ b”已在映射中，无需更新。

“ b”的索引与“鱼”的索引不同。返回False。



实作



区分字符和字符串：在Python中没有单独的char类型。对于以下情况：

• pattern：'abba'

• s：'baab'



使用相同的哈希图将无法正常工作。一种解决方法是在每个字符前pattern添加“ char”，在每个单词前s添加“ word”。



这里需要注意：<font color='red'>遍历必须用Integer，而不是int. 因为Integer是对象，相同的int装箱为不同的Integer。</font>



public boolean wordPatternWithOneMap(String pattern, String s) {
    // check edge
    if (pattern == null || s == null) {
      return pattern == s;
    }
    int len = pattern.length();
    String[] sarray = s.split(" ");
    if (len != sarray.length) {
      return false;
    }
    Map<Object, Integer> map = new HashMap<>();
    for (Integer i = 0; i < len; i++) {
      char c = pattern.charAt(i);
      String word = sarray[i];
      if (!map.containsKey(c)) {
        map.put(c, i);
      }
      if (!map.containsKey(word)) {
        map.put(word, i);
      }
      if (map.get(c) != map.get(word)) {
        return false;
      }
    }
    return true;
  }



复杂度分析



时间复杂度： 上）O(N) 哪里 ññ代表中的字数s或中的字符数pattern。



空间复杂度： O(M)中号是中的唯一字符pattern和中的单词的数量s。



2. Review: 阅读并点评至少一篇英文技术文章

翻译：算法常见的模数1000000007 模数10 ^ 9 + 7



说明

在大多数编程比赛中，我们都需要以10 ^ 9 + 7模为模来回答结果。这背后的原因是，如果问题约束是大整数，则只有高效的算法才能在允许的有限时间内解决它们。



什么是模运算：

对两个操作数进行除法运算后得到的余数称为模运算。进行模运算的运算符为'％'。例如：a％b = c，这意味着，当a除以b时，它将得到余数c，7％2 = 1，17％3 =2。

为什么我们需要取模：

• 采用Mod的原因是为了防止整数溢出。C / C ++中最大的整数数据类型是64位无符号long long int，可以处理从0到（2 ^ 64 – 1）的整数。但是，在某些产出增长率很高的问题中，这种高范围的无符号长久可能不够。

假设在64位变量'A'中存储2 ^ 62，在另一个64位变量'B'中存储2 ^ 63。当我们将A和B相乘时，系统不会给出运行时错误或异常。它只是进行一些伪计算并存储伪结果，因为结果的位大小是在乘法溢出后得出的。

• 在某些问题中，需要计算结果取模逆，并且该数很有用，因为它是质数。同样，这个数字应该足够大，否则在某些情况下模块化逆技术可能会失败。



由于这些原因，问题解决者需要通过对一些数N取模来给出答案。

N的值取决于某些标准：

1. 它应该足够大以适合最大的整数数据类型，即确保没有结果溢出。

2. 它应该是质数，因为如果我们用质数来取数的mod，则结果通常是隔开的，即与非质数的mod数相比，结果是非常不同的结果，这就是为什么质数通常用于mod。



10 ^ 9 + 7满足两个条件。它是第一个10位数的质数，也适合int数据类型。实际上，任何小于2 ^ 30的素数都可以，以防止可能的溢出。



模数的使用方式：模数

的一些分布特性如下：

1.（a + b）％c =（（a％c）+（b％c））％c

1. （a b）％c =（（a％c）（b％c））％c

3.（a – b）％c =（（a％c）–（b％c））％c

4.<s>（a / b）％c =（（a％c）/（b％c））％c</s>

因此，模是分布在+，*和–上，而不是分布在/上。[有关详细信息，请参阅模数除法]

注意：（a％b）的结果将始终小于b。

在计算机程序的情况下，由于变量限制的大小，我们在每个中间阶段执行模M，这样就不会发生范围溢出。



>示例：

a = 145785635595363569532135132

b = 3151635135413512165131321321

c = 999874455222222200651351351

m = 1000000007

打印（a b c）％m。方法1：

首先，将所有数字相乘然后取模：

（a b c）％m =（459405448184212290290339339835148809

515332440033400818566717735644307024625348601572）％

1000000007

a b c即使在无符号long long

int中也不适合，这是由于系统下降它的一些最

重要的数字。因此，它给出了错误的答案。

（a b c）％m = 798848767方法2：

在每个中间步骤取模：

i = 1

i =（i * a）％m // i = 508086243

i =（i * b）％m // i = 144702857

i =（i * c）％m // i = 798848767

i = 798848767



方法2始终给出正确的答案。



使用模但在不同位置查找大量阶乘的函数。



语言举例

C ++



unsigned long long factorial(int n)
{
    const unsigned int M = 1000000007;
    unsigned long long f = 1;
 
    for (int i = 1; i <= n; i++)
        f = f * i;  // WRONG APPROACH as
                    // f may exceed (2^64 - 1)
 
    return f % M;
}



Python3



def factorial( n) :
    M = 1000000007
    f = 1
 
    for i in range(1, n + 1): 
        f = f * i # WRONG APPROACH as 
                  # f may exceed (2^64 - 1) 
 
    return f % M 
 # This code is contributed by Shubham Singh(SHUBHAMSINGH10)



C ++



unsigned long long factorial(int n)
{
    const unsigned int M = 1000000007;
 
    unsigned long long f = 1;
    for (int i = 1; i <= n; i++)
        f = (f*i) % M;  // Now f never can
                        // exceed 10^9+7
    return f;
}



Python3



def factorial( n) :
    M = 1000000007
    f = 1
 
    for i in range(1, n + 1): 
        f = (f * i) % M # Now f never can 
                        # exceed 10^9+7 
 
    return f 
# This code is contributed by Shubham Singh(SHUBHAMSINGH10)



可以遵循相同的步骤进行添加。

（a + b + c）％M与（（（（a + b）％M）+ c）

％M相同。每次加一个数字时都要执行％M，以避免溢出。



注意：在大多数编程语言中（例如C / C ++），当您使用负数执行模块化运算时，会给出负结果，例如-5％3 = -2，但是模块化运算后的结果应在范围内0到n-1表示-5％3 =1。因此将其转换为正模等效值。

C ++



int mod(int a, int m)
{
    return (a%m + m) % m;
}



Java



static int mod(int a, int m)
{
    return (a%m + m) % m;
}
// This code is contributed by 
//Shubham Singh(SHUBHAMSINGH10)



Python3



def mod(a, m):
    return (a%m + m) % m
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)



C＃

static int mod(int a, int m) 
{ 
    return (a % m + m) % m; 
} 



// This code is contributed by

//Shubham Singh(SHUBHAMSINGH10)



但是划分的规则不同。要在模算术中执行除法，我们首先需要了解模乘逆的概念。



参考

https://www.geeksforgeeks.org/modulo-1097-1000000007/



3. Tips: 学习至少一个技术技巧

笔者的文章：

Markdown stackoverflow 增加中划线

增加中划线的Markdown用法，line through, strike through



Like <strike>this</strike> or <s>this</s> or <del>this</del>



Like <strike>this</strike> or <s>this</s> or <del>this</del>



4. Share: 分享一篇有观点和思考的技术文章

Mock swift response， 通过依赖注入的方式，替换掉URLSession对象，使得单元测试得以进行。



参考：https://www.swiftbysundell.com/articles/mocking-in-swift/

https://itnext.io/partial-mocking-in-swift-backwards-e5036cf32a1b