代码随想录算法训练营Day5、6 | Leetcode 242 有效字母的异位词 Leetcode 349 两个数组的交集 Leetcode 202 快乐数 Leetcode 1 两数之和

前言

因为昨天休息所以把两天合并成一天来写，昨天把上周的题又重写了一遍，发现一些细节还是要注意。今天的题目都是查找，也涉及到了最近正在学的STL。

Leetcode 242 有效字母的异位词 

题目链接：https://leetcode.cn/problems/valid-anagram/description/

代码随想录题解：代码随想录 (programmercarl.com) 

思路：异位词就是两个单词中出现相同字母的数量相同，运用桶排序统计第一个，然后第二个用来删，如果最后都删干净就是异位词。

代码：

class Solution {
public:
bool isAnagram(string s, string t) {
    int a[30];
    for(int i=0;i<26;i++)
    {
        a[i]=0;
    }
    for(int i=0;i<s.size();i++)//桶加
    {
        a[s[i]-'a']++;
    }
    for(int i=0;i<t.size();i++)//桶删
    {
        a[t[i]-'a']--;
    }
    for(int i=0;i<26;i++)
    {
        if(a[i]!=0)
        {
            return false;
        }
    }
    return true;
}
};

Leetcode 349 两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/

代码随想录题解：代码随想录 (programmercarl.com)

思路：将一个数组存入set中，将第二个数组的每个元素都进入set中查找，如果有就放入保存结果的set。这样第一个set过滤了第一个数组中重复的元素，第二个set过滤了第二个数组重复的元素。

代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> s;
    unordered_set<int> result(nums1.begin(),nums1.end());//第一个set
    for(int i:nums2) //遍历第二个数组
    {
        if(result.find(i)!=result.end())
        {
            s.insert(i); //第二个set
        }
    }
    return vector<int>(s.begin(),s.end());
    }
};

Leetcode 202 快乐数

题目链接：202. 快乐数 - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：根据题意描述，如果不是快乐数那么会无限循环，也就是会出现重复的和，因此我们的判断条件就是是否出现了重复的和，那么就需要将和保存进一个set里面。还需要注意的就是取各个位上的数字求平方和的算法怎么写，分解一下方便记忆，取各个位上的数，平方和。

代码：

class Solution {
public:
    int getsum(int a) //求各个位上的数的平方和
    {
        int sum=0;
        while(a)
        {
        sum=sum+(a%10)*(a%10);
        a=a/10; //记得写这一句
        }
    return sum;
    }
    bool isHappy(int n)
    {
      int sum=0;
      unordered_set<int> flag; //set保存出现过的和
      while(1)
      {
        sum=getsum(n); //求和
        if(sum==1)
        {
            return true;
        }
        if(flag.find(sum)!=flag.end())
        {
            return false;
        }
        flag.insert(sum);//如果都不是则存入
        n=sum;//换成下一个数
      }
    }
};

 Leetcode 1 两数之和 

题目链接：https://leetcode.cn/problems/two-sum/

代码随想录题解：代码随想录 (programmercarl.com)

思路：梦开始的地方，两层循环的语句是a[i]+a[j]==target，a[j]移动到等式右边a[i]==target+a[j]

这样将等式右边看成一个整体，那么就减少了一次循环。每次判断等式左端是否等于右端，如果不等于将左端存入一个新容器。因为要返回下标，所以采用的是map。

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
    unordered_map<int,int>a;
    for(int i=0;i<nums.size();i++)
    {
        auto iter = a.find(target - nums[i]); //a[i]==target-a[j]
        if(iter!=a.end()) //找到了
        {
            return {iter->second,i};//返回两个下标
        }
        a.insert(pair<int,int>(nums[i],i));//没找到就存入map
    }
    return {};
    }
};

C++ 多态

1.什么是多态

就是多种状态，不同对象在进行相同的行为时展现出不同的结果。一般出现在派生类继承一个有虚函数定义的基类后，被基类的指针或引用调用不同函数时发生。

2.多态的实现

涉及到虚函数以及虚函数表，虚函数是在基类中用virtual关键字修饰的函数，它可以被派生类重新实现，这个行为叫做重写。每个具有虚函数的类都有一个虚函数表，里面保存的是虚函数的地址，一般在编译阶段生成，存储在常量区。当我们初始化一个类的对象时，除了类中定义的变量，这个对象还会有一个虚函数表指针，然后我们在后续过程中用基类的引用或者指针调用虚函数时，程序会通过虚函数表指针访问虚函数表，根据对应的偏移量调用派生类的虚函数。

3.override和final

override：被这个关键字修饰的虚函数一定要在派生类中重写，如果不重写那么编译器会报错

final：被这个关键字修饰的虚函数不能再被重写，如果被重写那么编译器会报错

4.动态绑定与静态绑定

静态绑定：静态绑定是在编译阶段确定调用的函数和方法，编译器会根据函数或方法的类型，参数等信息确定。一般非虚函数，成员函数都是静态绑定，确定后就无法更改。

动态绑定：动态绑定是在运行阶段确定调用的函数和方法，编译器会根据函数的指针或引用确定，一般虚函数都是动态绑定。

5.纯虚函数和抽象类

一个基类中如果有某个虚函数被=0修饰，那么这个函数就为纯虚函数，含有纯虚函数的类被称为抽象类，他无法被实例化为对象，且派生类必须实现这个纯虚函数，否则派生类仍为抽象类。抽象类一般用于实现统一派生类的接口使用。

6.重写和重载

重载：对函数参数类型，数量的修改叫做函数的重载

重写：是指派生类重新实现基类中被virtual修饰函数的过程，其实就是虚函数的实现。

7.构造函数，析构函数与虚函数

构造函数不能被定义为虚函数，因为虚函数的调用需要虚指针，也就是需要访问对象的内存空间，但此时对象都还没构造出来，哪来的内存空间。

析构函数一般都要定义为虚函数，因为在析构一个对象的过程中，如果一切正常的话是先调用派生类的析构函数，再调用基类的析构函数。此时我们通过基类的指针或者引用来删除这个对象，如果基类的析构函数不是虚函数，那么在删除时就不会动态绑定，也就是这个指针或引用直接指向了父类的析构函数，没有调用子类的析构函数，如果在构造时设计了new，delete操作会导致内存泄漏

总结

终于把C++多态的总结写出来了，已经计划了好几天。今天的算法题难度不大，记下写法和细节就行。再花几天时间把STL学完就要尝试写一个mini STL，后续就是C++内存管理的部分了。