LeteCode第319场周赛

温度转换

1.对应OJ链接：

温度转换

2.题目描述

3.解题思路

本题解题思路非常的简单直接返回即可。非常的有手就行

4.对应代码

class Solution {
public:
    vector<double> convertTemperature(double celsius) {
        return {celsius+273.15,celsius*1.8+32};
    }
};
1
2
3
4
5
6

最小公倍数数为k的子数组数目

1.对应oj链接
数组的数目

2.题目描述

3.解题思路

本题的解决思路也非常的简单，我们一看这个数据量的范围非常的小。此时我们直接枚举所有的子数组即可，直接求这个最小公倍数。再这里有一个小小的优化就是如果这个子数组的最小公倍数大于k了此时可以break跳出循环。不用再继续遍历了具体请看代码如何书写

4.对应代码

class Solution {
public:
    int gcd(int a,int b){
        return !b?a:gcd(b,a%b);
    }

    int subarrayLCM(vector<int>& nums, int k) {
            int ans=0;
         
            int N=nums.size();
            //根据数据量猜解法
            for(int L=0;L<N;L++){
                 int start=nums[L];
                for(int R=L;R<N;R++){
                    //枚举所有子数组
                    int g=gcd(nums[R],start);//求最小公倍数
                    start=(nums[R]*start)/g;//最小公倍数

                    if(start==k){
                        ans++;
                    }
                    if(start>k){//最小公倍数已经大于k了没有枚举的必要了
                        break;//后面没有这个枚举的必要了
                    }

                     
                }

            }
            return ans;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最少的操作此时

1.对应Oj链接
最少的操作次数
2.题目描述

3.解题思路

解题思路本题，我们可以使用这个层序遍历拿到没一层的数据，然后我们求每一层需要多少次。这个问题不就解决了吗？那么现在的难点就在于这个如何求每一层的到底需要多少次交换了？再这里用到了一个技巧就是这个离散化。什么意思了就是我们拿到的每一层的值有可能很大但是我们可以将其转换为再这个数组中的排名。下面我们通过一张图来说明一下

这样我们就将这个很大的数组转换成为了这个再排序好的对应的下标，有了这个就好办了。那么我们此时3应该去3位置，1应该去1位置。我们就可以写一个循环直到每个数都在它正确的位置上。不在就和对应的位置进行交换并累加到答案当中来。

4.对应代码

class Solution {
public:
    //变成有序数组最少需要交换几次
    int Need(vector<int>&nums)
    {
        if(nums.size()<=1){
            return 0;
        }
        int N=nums.size();
        map<int,int>TreeMap;
        for(int i=0;i<N;i++)
        {
            TreeMap.insert({nums[i],i});
        }
        sort(nums.begin(),nums.end());
        vector<int>tmp;
        //进行离散化也就是nums[i]对应的位置就是这个i位置如果不在需要交换一次
        for(auto&ch:nums)
        {
            tmp.push_back(TreeMap[ch]);
           
        }
     
        int ans=0;
        for(int i=0;i<N;i++)
        {
             while(tmp[i]!=i){
                 swap(tmp[i],tmp[tmp[i]]);
                 ans++;
             }
        }
        return ans;

    }
    int minimumOperations(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        queue<TreeNode*>q;
        q.push(root);
        int ans=0;
        while(!q.empty())
        {
            vector<int>tmp;
            int len=q.size();
            //层序遍历拿到没一层
            for(int i=0;i<len;i++){
                auto node=q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }

            }
           //每一层需要的数目
            ans+=Need(tmp);
        }
        return ans;
        
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

不重叠回文的最大数目

1.对应OJ
不重叠回文的最大数目
2.题目描述

3.解题思路

本题的解题思路需要用到之前一个经典的问题最长回文字串，我们需要生成一张dp表表示[L…R]范围内是否是回文。那么接下来我们需要定义一个动态规划f[i]表示这个[0…i]范围内满足条件的最大回文数目。下面我们来分析一下这个可能性：
可能性1： i位置不再回文区域里面那么此时f[i]=f[i-1].这个容易
可能性2:i位置再回文区域里面我们此时就可以从[0…i-1] 当中选择一个点和i组成一个范围看是否满足条件，加锁这个点为j。如果是符合条件的那么f[i]=f[j-1]+1。

4.对应代码

class Solution {
public:
    int maxPalindromes(string s, int k) {
           int N=s.size();
           vector<vector<bool>>dp(N,vector<bool>(N));
           dp[N-1][N-1]=true;
           for(int i=0;i<N-1;i++){
               dp[i][i]=true;
               dp[i][i+1]=s[i]==s[i+1]?true:false;
           }
           for(int L=N-2;L>=0;L--)
           {
               for(int R=L+2;R<N;R++){
                   if(s[L]==s[R]){
                       dp[L][R]=dp[L+1][R-1];
                   }else{
                       dp[L][R]=false;
                   }
               }
           }
           //
           vector<int>f(N+1);//0到i范围内符合条件的有多少个注意再这里为了处理方便我们0位置不用
           
           for(int i=1;i<=N;i++)
           {
               f[i]=f[i-1];//不在这个回文区域里面
               for(int j=1;j<=i;j++)
               {
                   //在枚举区间但是需要满足条件在拼起来即可
                   if(i-j+1>=k&&dp[j-1][i-1]){
                        f[i]=max(f[i],f[j-1]+1);
                   }
               }
           }
           return f[N];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38