c++ for循环在这里做什么?

gk7wooem  于 2023-01-15  发布在  其他
关注(0)|答案(2)|浏览(155)

我在试着理解这个代码块,我在课堂上看到过,但我还是不明白。
我知道map是什么和如何工作的,它是一个键对值对象,在这个例子中,我只是不明白发生了什么,我看到我们有一个char和int,但我不明白他们在这个例子中是如何交互的。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, int> mapS;
        map<char, int> mapT;

        for(int i = 0; i < s.length(); i++)
        {
            if(mapS[s[i]] != mapT[t[i]]) return false;
            
            mapS[s[i]] = i+1;
            mapT[t[i]] = i+1;
        }
        return true;
    }
};

我试着打印出每个for的结果,我得到了0和1(不是二进制意义上的)。我还知道我们在'i'+1处取一个字符并将其放置在maps索引中。我遗漏了什么?
谢谢!
抱歉,我还是不习惯在这里提出好的问题。
我试图首先理解解决方案,所以,就像有人建议的那样,我将用我的推理来解决它。
首先,我们启动两个贴图(mapS和mapT)。
第二步,迭代字符串s的长度(我想我们可以假设字符串t的长度是相同的,这一点还不清楚)。
我们检查s [i]处的字符是否等于t [i],并且它也必须存在于Map中(这就是我的问题所在)。
我把那条线当作向前看的线,并把它加到Map上。
如果没有问题,我们还会回来。
现在,如果我错了,请原谅,但是根据文档,我们不应该比较这里的键吗?或者我完全错过了一些东西。
另外,有人提到我是否理解同构。我不完全理解。我有一个大概的想法。

6za6bjd0

6za6bjd01#

首先,我将检查一下你提供的解释。
首先,我们启动两个贴图(mapS和mapT)。
教育性地,我们 * 初始化 * 两个Map。
第二步,迭代字符串s的长度(我想我们可以假设字符串t的长度是相同的,这一点还不清楚)。
为了解决这个问题,我们可以假设t至少和s一样长。
我们检查s [i]处的字符是否等于t [i],
不,那是s[i] == t[i].
而这也必须存在于Map中。(这就是它对我来说分崩离析的地方)
不,如果我们没有在mapS中存储s[i]的值,mapS[s[i]]就是0。
下面是if条件的实际作用:

  • 它在mapS中查找s[i],返回一些int--或者是我们最近为键s[i]存储的int,或者是0,如果我们从未为键s[i]存储过int
  • 它在mapT中查找t[i],返回一些int--或者是我们最近为键t[i]存储的int,或者是0,如果我们从未为键t[i]存储过int
  • 如果两个int不同,则函数提前返回值false

我把那条线当作向前看的线,并把它加到Map上。
它不会向前看,向前看的内容类似于s[i+1]t[i+1],它确实在两个Map中都存储了i+1,但它不会"向前看"。
如果没有问题,我们还会回来。
如果我们退出循环体,则返回true,因为i达到了s的长度,而没有提前返回。
现在,如果我错了,请原谅,但是根据文档,我们不应该在这里比较键吗?
什么文件?
另外,有人提到我是否理解同构,我不完全理解,我有一个大概的想法。
"同构"在这里的意思并不明显,但我们会弄清楚的。
现在我来分析一下这个函数。
理解循环功能的一种方法是从简单输入开始,然后"手动"遍历循环,根据需要遍历多次(从简单输入开始,这样就不必遍历太多次!)
让我们关注mapS变量,看看循环对它做了什么。因为mapS是使用s中的元素索引的,所以我们需要为s选择一些字符串。让我们使用"abcab"
程序仅在一条语句中更新mapS

mapS[s[i]] = i+1;

现在让我们遍历循环,看看mapS是如何演化的,我们假设if条件总是false。
| i|s[i]|循环体之前的mapS|循环体后mapS|
| - ------|- ------|- ------|- ------|
| 无|'a'|(空)|* * 一米四二米一x**|
| 1个|'b'|['a']=1|一米四十五英寸一x一米四十六英寸一x|
| 第二章|'c'|x一米四十八英寸x一米四十九英寸|x 1米50英寸x 1米51英寸xx 1米52英寸x|
| 三个|'a'|x 1米54英寸1 x 1米55英寸1 x 1米56英寸1|* * 1米57英寸1 x1米58英寸1 x 1米59英寸1 x|
| 四个|x1米60英寸1x|x1米61英寸1x x 1米62英寸1x 1米63英寸1x|一个米64个一个
一个米65个一个一个米66个一个|
所以在循环体的开头,我们可以说:对于s.substr(0, i)中的每个字符cs的第一个i字符),mapS[c]s.substr(0, i)中的c的最后一个索引大
一 *。
注意,当i == 0为空字符串时,s.substr(0, i)为空字符串。
如前所述,mapS对任何未存储在map中的键返回0,因此我们将0视为"s.substr(0, i)不包含c"。
根据0的这个含义,我们可以说,在循环体的开始,对于everycmapS[c]编码cs.substr(0, i)中的最后一个索引如下:

  • mapS[c] == 0编码含义"c不在s.substr(0, i)中"。
  • mapS[c] == x编码含义"x - 1 < is[x - 1] == c以及s.substr(0, i)在任何大于x - 1的索引处不包含c"。

由于mapT的更新方式与mapS完全相同,只是使用了t中的字符,因此我们可以说它编码了与mapS相同的含义,只是相对于t而不是s
现在我们可以分析if语句的条件了:mapS[s[i]] != mapT[t[i]].
请记住,s.substr(0, i)到达s[i];它恰好在s[i]之前停止,即"abcab"[2]'c',并且"abcab".substr(0, 2)"ab";子字符串'c'结尾。
因此,在if条件下:

  • mapS[s[i]]s.substr(0, i)中的s[i]的编码的最后一个索引。(记住"编码的最后一个索引"可以编码含义"没有这样的索引"。)
  • mapT[t[i]]t[i]t.substr(0, i)中的编码的最后索引。

因此,如果这些编码的最后索引不同,则if语句使函数提前返回值false

现在假设循环一直进行到i == s.length()if条件never为真,然后循环正常退出,并且程序已经证明,每当它在s中看到某个字符c,以及在t中相同索引处看到某个对应的字符d时,先前在st中的相同的较早(编码)索引处看到cd
从这一点到更全面地理解isIsomorphic,这是一个小小的飞跃,但isIsomorphic(s, t)的含义如下:
是否有方法将s中出现的每个字符c统一Map到t中出现的唯一字符d?反之亦然?如果有,isIsomorphic(s, t)返回true。否则,返回false。
请看这个例子:isIsomorphic("abcab", "zyxzy")。它返回true,因为s中出现的字符与t中出现的字符之间存在统一的双向Map:
| S的|t|
| - ------|- ------|
| 项目a|z|
| b.人口基金|Y型|
| (c)秘书长的报告|x|
但是isIsomorphic("abcab", "zyzzy")是假的。s中的'a''c'都必须Map到t中的'z'-但是t中的'z'只能Map回一个字符,而不能同时Map到'a''c'
这种统一、唯一、双向的Map称为bijection
一个isomorphism总是一个双射,但通常有额外的要求,这取决于它定义的结构类型。例如,在图论中,你可以定义两个图的节点之间的双射,但同构也必须定义这两个图的边之间的双射。
此函数更好的名称可能是bijectionExistssamePattern

chhqkbe1

chhqkbe12#

从理解代码开始首先需要理解它试图解决的问题。
两个字符串同构是指每个字符串A都可以Map到字符串B中的每个字符。
例如,ACABXCXY同构。

A -> X
C -> C
B -> Y

另外,ACABXCZY同构的。

A -> X, Z  # 'A' cannot map to multiple characters
C -> C
B -> Y

那么,代码是如何解决这个问题的呢?我们将看看函数体的各个部分。

std::map<char, int> mapS;
std::map<char, int> mapT;

声明两个Map,每个Map对应一个字符串。它们都是空的。

for(int i = 0; i < s.length(); i++)

这个循环只关心s的长度,我们已经遇到了一个障碍,如果我们想检查s -> tt !-> s的单向Map,这个函数不能正确地完成,我会进一步说,如果st的长度不同,这个函数应该立即返回false,因为我们保证如果t.length() < s.length()的话会读取越界。
继续:

{
    if(mapS[s[i]] != mapT[t[i]]) return false;

    mapS[s[i]] = i+1;
    mapT[t[i]] = i+1;
}

我们必须将它们放在一起。if检查只是想知道对应的map元素是否具有相同的值。如果它们不具有相同的值,则在Map中存在不匹配,并且可以立即返回false。如果值确实匹配,则一起更新两个map。使用i + 1是因为operator[]处理map的方式。如果键不存在,尝试使用该键进行索引将在Map中创建一个条目,并将int值初始化为0。添加1是避免误报的一种廉价方法。
最后,如果您完成了循环而没有返回false,则假定字符串是同构的,并返回true。
但是这个函数是假的,几乎可以说它检查的是"单向"同构,当ts长时,但是如果s更长,它仍然可以返回true,并在这样做的同时调用未定义的行为。
对我来说,更好的解决方案是存储 * actual character * Map,还需要跟踪第二个字符串中的唯一字符,并且第一次检查应该是等长。

#include <iostream>
#include <set>
#include <string>
#include <unordered_map>

class Solution {
 public:
  bool isIsomorphic(const std::string& s, const std::string& t) {
    if (s.length() != t.length()) return false;

    // The map stores the character mapping from s to t. Characters in s
    // are the key, and the value is the corresponding character in t.
    std::unordered_map<char, char> map;

    // The set stores the **unique** characters of t. This allows us to know
    // if we already have a mapping to a character in t, if it exists in
    // the set.
    std::set<char> trackedChars;

    for (std::size_t i = 0; i < s.length(); ++i) {
      char sChar = s[i];
      char tChar = t[i];

      // Have I mapped this character yet?
      if (map.find(sChar) != map.end()) {  // Yes
        // Is the mapping still correct?
        if (map[sChar] != tChar) {  // Map mismatch found
          return false;
        }
      } else {  // No
        // Has the corresponding character been mapped already?
        if (trackedChars.find(tChar) != trackedChars.end()) {
          // tChar is already mapped
          return false;
        } else {  // tChar is also not yet mapped
          map[sChar] = tChar;
          trackedChars.insert(tChar);
        }
      }
    }

    // Making it out of the loop implies every character mapped correctly.
    return true;
  }
};

int main() {
  std::string one{"ACAB"};
  std::string two{"XCXY"};

  Solution s;
  std::cout << std::boolalpha << s.isIsomorphic(one, two) << '\n';
}

输出:

true

我不想重复前面说过的话,但是对于一个类来说,这种代码结构是垃圾。它应该只是一个自由函数,或者 * 可能 * 插入到一个名称空间中。但是这超出了这个问题的范围。

相关问题