2022/4/4 大作业做题心得 Anagram Clusters ，Area Codes ， Word Ladder ， Rising Tides

运行环境：QT 6.0.2

Problem 1　　Anagram Clusters　　相同字母异序词

尽管老师讲了一遍，但我还是没弄懂，后来才理解了老师的思路。

 1 /**
 2  * Given a word, returns a string formed by sorting the letters
 3  * in that word.
 4  *
 5  * @param word The input word
 6  * @return A sorted version of the word
 7  */
 8 string sortedVersionOf(const string& input) {
 9     /* This algorithm is an implementation of an algorithm called
10      * "Counting Sort." It's described in the slides 05 for Lecture.
11      */
12 
13     /* Build a frequency table of the letters in the word.
14      */
15     Map<char, int> sort;    //Map not map!
16     for(char ch: input){
17         sort[ch]++;
18     }
19 
20     string result;
21     /* Iterate over the frequency table and build the result
22      * string from the information it contains.
23      */
24     for(char ch: sort){
25         for(int i = 0; i < sort[ch]; i++){
26             result += ch;
27         }
28     }
29     return result;
30 }

首先这个函数是将单词的每个字母放进map里，再按照顺序重新组合成排列方式相同的字符串

 1 Lexicon english("EnglishWords.txt");
 2 
 3     Map<string, Lexicon> anagramClusters;
 4 
 5     /* Distribute words into their anagram clusters by using
 6      * the handy map autoinsertion feature.
 7      */
 8     for(const string& word: english){
 9         anagramClusters[sortedVersionOf(word)].add(word);
10     }

接下来在main函数里，首先把文件中的所有单词用上面的函数重新排序后作为键放进map里，然后往值（Lexicon类型）里面添加这个单词，这样就可以把相同字母异序词联系到一起。

后面就直接将输入的单词转化，然后寻找对应的值再输出就行了。

Problem 2 　　AreaCodes

我学到了：

1. atoi() 是c里面的，所以不支持string类型，而是要用char* 相关类型的。
2. c_str() 的作用是将string转化为 char const* 类型。
3. 直接用stoi() 就可以将string 转为int（碰到第一个非数字的字符停止）。不过看不懂源码的我又去网上搜了搜，发现stoi好像本来的作用不是这个，而是将n进制的字符串转化为10进制。其中用到了strtol，我试了试，发现strtol也可以达到类似的效果，返回的是一个long类型的整数 。试验如下：

   1 string str = "123is432";
   2     //stoi("123444");
   3     cout << stoi(str) << "\n" << "stoi类型：" << typeid(stoi(str)).name() << endl;
   4     cout << "c_str类型： " << typeid(str.c_str()).name() << endl;
   5 
   6     char* ptr;
   7     cout << strtol(str.c_str(), &ptr, 10) << "\nstrtol类型：";
   8     cout << typeid(strtol(str.c_str(), &ptr, 10)).name() << endl;
   9 }

   结果：

   1 123
   2 stoi类型：int
   3 c_str类型： char const * __ptr64
   4 123
   5 strtol类型：long

   注意，stoi不会改变原有的字符串，而是返回一个新的整数！

走的弯路：

　　最开始，我把c_str的作用理解为“只拷贝开头数字”了，但是后来做试验来看它的作用时发现不是这样，所以还是要多敲。

　　后来，直接用cin输入了，忽略了cin是通过空格分开的，不能直接读取整行，所以最后换成了getline(cin, input)

Problem 3　　WordLadder

 说实话，这道题难住我了，到网上找了一圈，还没弄懂广度优先算法该怎么实现。好在同学从老师那里弄来了答案，无奈之下，只能迷迷糊糊地照着打了一遍，把看懂的地方修改成我自己的风格。

不过，还算有点收获。

我学到了：

1. 将字符串全部转化为小写的函数。需要带上algorithm头文件，strtwl( str.begin(), str.end(), str.begin(), ::tolower); 注意最后没有括号！

Problem 4　　RisingTides