力扣题目训练（5）

2024年1月29日力扣题目训练

• 2024年1月29日力扣题目训练
• • 345. 反转字符串中的元音字母
  • 349. 两个数组的交集
  • 350. 两个数组的交集 II
  • 96. 不同的二叉搜索树
  • 97. 交错字符串
  • 44. 通配符匹配

2024年1月29日力扣题目训练

2024年1月29日第五天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道，今天总算把进度赶上了，虽然有很多不会的，但是总体还是有进步的。

345. 反转字符串中的元音字母

链接: 反转元音字母

难度： 简单

题目：

运行示例：

思路：

与之前的反转字符串类似，无非是这里需要先记录下元音字母位置再反转。

代码：

class Solution {
public:
    string reverseVowels(string s) {
        vector res;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'||
            s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U'){
                res.push_back(i);
            }
        }
        int n = res.size();
        for(int i = 0; i <  n/ 2; i++){
            char c = s[res[i]];
            s[res[i]] = s[res[n-i-1]];
            s[res[n-i-1]] = c;
        }
        return s;
    }
};

349. 两个数组的交集

链接: 数组交集

难度： 简单

题目：

运行示例：

思路：

利用哈希表存储在第一个数组中出现的数字，然后和第二个数组中的元素进行判断。

代码：

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        unordered_map map;
        vector ans;
        for(int i = 0; i < nums1.size(); i++){
            if(map[nums1[i]] == 0)  map[nums1[i]] = 1;
        }
        for(int i = 0; i < nums2.size(); i++){
            if(map[nums2[i]] == 1 && !(std::find(ans.begin(), ans.end(), nums2[i]) != ans.end()))   ans.push_back(nums2[i]);
        }
        return ans;
    }
};

350. 两个数组的交集 II

链接: 数组的交集出现次数

难度： 简单

题目：

运行示例：

思路：

这道题与上一道题有相似之处，我都是用的哈希表，但是这道题题目我用了两个哈希表分别记录两个数组中元素出现的次数，然后进行对比得到结果。

官方的方法是用一个哈希表，通过改变哈希表中元素出现的次数的值来得到结果。

代码：

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        unordered_map map1,map2;
        vector ans;
        for(int i = 0; i < nums1.size(); i++){
            map1[nums1[i]]++;
        }
        for(int i = 0; i < nums2.size(); i++){
            map2[nums2[i]]++;
        }
        for(auto p:map1){
            int key = p.first;
            int count = p.second;
            if(map2[key] != 0){
                int n = count > map2[key]?map2[key]:count;
                cout<<n<<endl;
                for(int i = 0; i < n; i++){
                    ans.push_back(key);
                }
            }
        }
        return ans;
    }
};

官方代码

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        unordered_map  map;
        for(int num: nums1){
            map[num]++;
        }
        vector intersection;
        for(int num:nums2){
            if(map[num]){
                intersection.push_back(num);
                map[num]--;
                if(map[num] == 0){
                    map.erase(num);
                }
            }
        }
        return intersection;
    }
};

96. 不同的二叉搜索树

链接: 二叉搜索树

难度： 中等

题目：

运行示例：

思路：

这道题与昨天的训练题类似，但是这道题只用求种类数相对简单，我们可以利用动态规划求当前节点左右自述的种类数再相乘即可得到结果。

代码：

class Solution {
public:
    int numTrees(int n) {
        vector dp(n+1,0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
};

97. 交错字符串

链接: 交错字符串

难度： 中等

题目：

运行示例：

思路：

我本来用的是回溯的但是时间超过了，看了官方发现这是一道比较典型的动态规划问题，dp[i][j]表示s1的前i个字符与s2的前j个字符组成的字符串与s3的前i+j-1个字符之间的状态。

代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        if(n1+n2 != n3) return false;
        vector<vector > dp(n1+1,vector(n2+1,false));  
        dp[0][0] = true;
        for(int i = 0; i <= n1; i++){
            for(int j = 0; j <= n2; j++){
                int k = i + j -1;
                if(i > 0) dp[i][j] = dp[i][j] || dp[i-1][j] && s1[i-1] == s3[k];
                if(j > 0) dp[i][j] = dp[i][j] || dp[i][j-1] && s2[j-1] == s3[k];
            }
        }
        return dp[n1][n2];
    }
};

44. 通配符匹配

链接: 通配符匹配

难度： 困难

题目：

运行示例：

思路：

这个题与上一道题交错字符串类似，都是求匹配所以使用动态规划算法。

代码：

置换：

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] -1 ] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
            } 
        }
        for(int i = 0; i < n; i++){
            if(nums[i] != i+1){
                return i + 1;
            }
        }
        return n + 1;
    }
};