day11

[0242.有效的字母异位词]

• 我完全没思路 以前只是在书上学过 哈希查找相关的 哈希函数构造方法、哈希冲突处理方法、哈希表上查找删除伪代码，没有真正用哈希方法实现代码解决问题------简而言之：知道 不会用

• 看了思路 我定义已知长度数组基本语句不会，26个字母映射到自己定义的长度为26的数组的方法不知道，就没有下文了。。。全程抄代码。。。。。

C++ 代码如下：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

• int a[26] = {0}; //定义数组的基本语句：长度26 元素初值为0
vector<int> a(26 , 0);

  • vector定义动态数组及访问形式：
    C++标准提供被封装的动态数组——vector。vector是一个封装动态大小数组的顺序容器（Sequence Container），这种被封装的数组可以具有各种类型。vector不是一个类，而是一个类模板。

    跟普通数组相比，使用vector定义的数组对象元素都会被初始化。若是数组元素为基本类型则元素初始化为0；若数组元素为类类型，则会调用类的默认构造函数初始化（需要保证该类具有默认的构造函数）。

    注意，vector数组对象不是数组，而是封装了数组的对象，vector数组名字表示的就是一个数组对象，而非数组的首地址。

  • vector定义动态数组的形式为：vector<元素类型> 数组对象名（数组长度）;

  • vector动态数组也可以自定义初值，形式为 vector<元素类型> 数组对象名（数组长度，元素初值）;

  • 对vector数组对象元素访问与普通数组相同：数组对象名[下标表达式]

  • vector定义数组对象成员函数如下，其中size（）返回数组长度，比较重要：

1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

• 回答了数组定义问题，那么现在回答哈希映射是怎么处理的这个问题

  • 首先 通过待映射元素的特性来判断应该映射到哪个数据结构中---是数组中、set中、还是map中? 一个简单的选择标准是:

    • 当元素类型单一、连续，尤其是范围可控，则用数组，并且能用数组就尽量用数组，因为数组简单，结构不复杂；
    • 当元素范围不可控则用set：当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的；如果需要集合是有序的，那么就用set；如果要求不仅有序还要有重复数据的话，那么就用multiset；
    • 当涉及key值-value值则用map：map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
    • 当然，严格的判断标准见下面对常见三种哈希结构的详细描述：

    集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
    std::set	红黑树	有序	否	否	O(log n)	O(log n)
    std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
    std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

    std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

    虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

    映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
    std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
    std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
    std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

    std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

  • 从本题待映射元素是字母a-z，单一、连续、范围可控，那么我们就选数组作为哈希结构。

  • 选定了数组，呢么记下来定义数组就好了：int record[26] = {0};

  • 那么怎么实现映射呢？record[s[i] - 'a']随着i的递增，s[i]取s中每一个字母，关键来了：让取到的每一个元素（字母a-z随机一个）跟标准元素（字母'a')做运算（差），运算的结果值 就是你定义的 哈希结构（数组）的下标值-----------实现了元素从绝对位置到相对位置的转变，即哈希映射。

  • 至于record[s[i] - 'a']++与映射没有关系了，就涉及到本题具体情况，让对应位置++ 或-- 来判断两串相同字母是否相同。

• 一口不能吃成大胖子，一道题是需要多次反复消化的。