算法面试2-表格

算法2

查找问题

查找有无
-元素”a”是否存在？set 集合
查找对应关系(键值对应)
-元素”a”出现了几次？map 字典

set和map
通常语言的标准库都内置set和map
-容器类
-屏蔽实现细节
-了解语言中标准库常见容器类的使用

常见操作
-insert
-find
-erase
-change(map)

例题349:
给定两个数组nums，求两个数组的公共元素
-如nums1=[1,2,2,1],nums=[2，2]
-结果为[2]
-结果中每个元素只能出现一次
-出现的顺序可以是任意的

#include<iostream>
#include<vector>
#include<set>
using namespace std;
class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        for(int i =0;i<nums1.size();i++)
            record.insert(nums[i])
        set<int>resultSet
        for(int i =0;i<nums2.size();i++)
            if(record.find(nums2[i]) != record.end())
            //find查找元素，如果查找到record.end()为止发现元素，则存在。
            //如果=record.end()说明没有找到。说明nums2[i]存在
                resultSet.insert(nums2[i])
        vector<int>resultVector;
        for(set<int>::iterator iter = resultSet.begin();iter!=resultSet.end();iter++)
            resultVector.push_back(* iter);
        return resultVector;

    }
};
int main(){
    return 0;
}

可以使用容器类的构造方法

#include<iostream>
#include<vector>
#include<set>
using namespace std;
class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        set<int> record(nums1.begin(),nums1.end()); //简化
        set<int>resultSet;
        for(int i =0;i<nums2.size();i++)
            if(record.find(nums2[i]) != record.end())
            //find查找元素，如果查找到record.end()为止发现元素，则存在。
            //如果=record.end()说明没有找到。说明nums2[i]存在
                resultSet.insert(nums2[i])
        return vector<int>(resultSet.begin(),resultSet.end());//简化

    }
};
int main(){
    return 0;
}

例题350：
给定两个数组nums,求两个数组的交集
如nums1=[1,2,2,1],nums2=[2,2]
结果为[2,2]
出现的顺序可以是任意的

class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        map<int,int>record;
        for(int i =0;i<nums1.size();i++)
            record[nums1[i]]++; //记录频次
        vector<int>resultVector;
        for(int i =0;i<nums2.size();i++)
            if(record[nums2[i]]>0){
                resultVector.push_back(nums2[i]);
                    //nums2[i]);//如果发现在nums2中某以元素的频次也大于0，则记录下来
                    record[nums2[i]--];
            }
        return resultVector;
    }
};

C++中map的默认值为0
换种写法风格

class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        map<int,int>record;
        for(int i =0;i<nums1.size();i++)
            if(record.find(nums1[i])== record.end())
                record.insert(make_pair(nums1[i],1));//初始键值为1
            record[nums1[i]]++; //如果存在某一元素则记录频次
        vector<int>resultVector;
        for(int i =0;i<nums2.size();i++)
            if(record.find(nums2[i])!=record.end()&&record[nums2[i]]>0){
                resultVector.push_back(nums2[i]);
                    //nums2[i]);//如果发现在nums2中某以元素的频次也大于0，则记录下来
                    record[nums2[i]--];
                    if(record[nums2[i]]==0)
                        record.erase(nums2[i]);//每求一次交集将这个元素抹去
            }
        return resultVector;
    }
};

对于两个问题，如果数组有序？
set和map有不同的底层实现

哈希表

哈希表的缺点是失去了数据的顺序性
map和set的底层实现为平衡二叉树，时间复杂度为O(nlogn)
unordered_map 和 unordered_set 的底层实现为哈希表

数据的顺序性

-数据集中的最大值和最小值
-某个元素的前驱和后置
-某个元素的floor和ceil
-某个元素的排位rank
-选择某个排位的元素select

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
//时间复杂度O(n)
//空间复杂度O(n)
class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        unordered_set<int> record(nums1.begin(),nums1.end()); //简化
        unordered_set<int>resultSet;
        for(int i =0;i<nums2.size();i++)
            if(record.find(nums2[i]) != record.end())
            //find查找元素，如果查找到record.end()为止发现元素，则存在。
            //如果=record.end()说明没有找到。说明nums2[i]存在
                resultSet.insert(nums2[i])
        return vector<int>(resultSet.begin(),resultSet.end());//简化

    }
};
int main(){
    return 0;
}

unordered_map 哈希表底层实现为O(1)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution{
public:
    vector<int>intersection(vector<int>&nums1,vector<int>&nums2){
        unordered_map<int,int>record;
        for(int i =0;i<nums1.size();i++)
            record[nums1[i]]++; //记录频次
        vector<int>resultVector;
        for(int i =0;i<nums2.size();i++)
            if(record[nums2[i]]>0){
                resultVector.push_back(nums2[i]);
                    //nums2[i]);//如果发现在nums2中某以元素的频次也大于0，则记录下来
                    record[nums2[i]--];
            }
        return resultVector;
    }
};

例题：242 Valid Anagram
判断字符串t是否是字符串s变换字符顺序后得到的结果
如s = “anagram” ,t = “nagaram”，则返回true
如s = “rat”, t = “car” ，则返回false

例题： 202 Happy number
判断一个数是否为happy number。happy number是指，一个数，将其替换为其各位数字的平方和，重复这个过程，如果最终能得到1，这是happy number，如果这个过程陷入了一个不包含1的循环，则不是happy number
如：数字19：
1^2+9^2 = 82
8^2+2^2 = 68
6^2+8^2 = 100
1^2+0^2+0^2 = 1 Happy number!

例题： 290 word pattern
给定一个模式和一个字符串，判断字符串是否符合模式

例题: 205 Isomorphic Strings
判断两个字符串是否同构？

例题： 251
给定一个字符串，按照字母出现频率的倒序重组整个字符串

一个使用查找表的经典问题

例题： 1 Two Sum

给定一个整型数组nums。返回这个数组两个数字的索引值i和j
使得nums[i]+nums[j] = 一个给定的target
-索引从0开始
-没有解怎么办
-有多个解怎么办 ,保证有唯一解

class Solution{
public:
    vector<int>twoSum(vector<int>&nums,int target){
        unordered_map<int,int>record;
        for(int i = 0;i<num.size();i++)
            record[nums[i]] = i;
            int complement = target - nums[i];
            if(record.find(complement)!= record.end()){
                int res[2] = {i,record[complement]};
                return vector<int>(res,res+2);
            }
            record[nums[i]] = i;
    }
    throw invalid_arguement("the input has no solution")
}

例题： 219
给出一个整型数组nums和一个整数k，是否存在索引i和j，使得nums[i] == nums[j]
且i,j之间的差不超过k

这个问题也是使用滑动窗口查找表

//时间复杂度O(n)
//空间复杂度O(k)

class Solution{
    public:
        bool containsNearbyDuplicate(vector<int>& nums,int k){
            unordered_set<int>record;
            for (int i = 0;i<nums.size();i++){
                if(record.find(nums[i])!=record.end()) //如果新的元素在原窗口中找得到，返回true
                    return true;
                record.insert(nums[i]);
                //如果新的元素原窗口中不存在，则添加该元素
                if(record.size()==k+1)  //保持record最多k个元素
                    record.erase(nums[i-k]);
            }
            return false;
        }
};

例题：217 Contains Duplicate

例题：220
给出一个整型数组nums和一个整数k，是否存在索引i和j，使得nums[i]和nums[j]之间的差别不超过给定整数t，且i,j之间的差不超过整数k

//时间复杂度O(n)
//空间复杂度O(k)
#include<vector>
#include<set>
using namespace std;
class Solution{
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums,int k,int t){
            set<int>record;
            for (int i = 0;i<nums.size();i++){
                if(record.lower_bound(nums[i]-t)!=record.end() && *record.lower_bound(nums[i]-t)<=nums[i]+t)
                //确保寻找的元素在[v-t,v+t]的范围内
                    return true;

                record.insert(nums[i]);
                //如果新的元素原窗口中不存在，则添加该元素
                if(record.size()==k+1)  //保持record最多k个元素
                    record.erase(nums[i-k]);
            }
            return false;
        }
};