LeetCode第319周赛题解

一如既往的一题选手

第一题

6233. 温度转换

难度： 简单

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案。

注意：

开氏度 = 摄氏度 + 273.15

华氏度 = 摄氏度 * 1.80 + 32.00

不需要任何思路 直接就能写 

class Solution {
public:
    vector<double> convertTemperature(double celsius) {
        
        //开氏度 = 摄氏度 + 273.15
        //华氏度 = 摄氏度 * 1.80 + 32.00
        vector<double> res;
        double val1=celsius+273.15;
        double val2=celsius*1.8+32.00;
        res.push_back(val1);
        res.push_back(val2);
        return res;
    }
};
           

第二题

6234. 最小公倍数为 K 的子数组数目

难度：中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

思路 ：

#1 暴力尝试

套用2层循环 调用 c++自带的lcm函数  依次去判断k是不是公倍数 如果是 res++ 最后返回res

代码如下：

class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(nums[i] == k) ans++;
            int t = nums[i];
            for(int j = i + 1; j < n; j++) {
                t = lcm(nums[j], t);
                if(t == k) ans++;
            }
        }
        return ans;
    }
};
           

#2动态规划 

首先先来确定几个值的含义 loc：上一个无效地点的下标(很重要)  pre：判定这个点 和k的最小公倍数 是不是k 如果不是 直接就break掉  cur：用来不断的判断一个点的左边界点  

过程如下 来到一个点 调用lcm函数 判断它是否和k的最小公倍数为k

1不是 则这个点就废掉了 相当于 所以集合都不包括这个点 我们又是从左到右依次计算每一个合格的子数组的 所以 如果判定到了 某一个点 他和k的最小公倍数 不是k 则可以直接 利用 loc 变量 将其接住 表明 之后的子树组 无法在跨越到这个点 或者这个点之前的任何下标 

2是 则开始判断 nums[j]  与 cur的最小公倍数 是不是k  是k则跳出循环 不是就一直向前寻找 直到找到合理数组的左边界 然后 res+=j-loc 

解释一下这一大段 并用一些例子来辅助说明    nums=[9,9,9,9,1,2,3,6,5]   k=6  下标从0开始 我们可以知道 道下标为3 依旧是无法让 lcm(k,nums[i])为 k  所以loc来到了 3 位置  然后 来到下标为4 的位置 发现 lem(nums[i],k 为 k 进入 循环 然后开始 判断 cur是不是 k 然后  如果是 则跳出循环  否则就会一直跳到 loc位置 * 这句是重点 他跳到loc位置  然后 res+=j-loc 会发现 此时 j==loc 即 res不会加 如果他中途跳了出来  例如从 下标为6开始 cur=lcm(cur,nums[j]) 发现 来到 下标为5的时候 2 3的最小公倍数 刚刚好是 6 所以跳出循环 res+=j-loc 代表什么？ 代表以i位置结尾 这个子数组至少需要推几个位置才能使得 公倍数为k  为什么是j-loc 就那刚刚的例子来说 来到了 j在 5 位置跳出了循环 现在有2个子数组 是符合条件的 [2,3] 以及[1,2,3] 所以是什么意思呢 因为他是一个连续子数组 所以只能在判断连续的位置 所以每次从j位置向前移动一个 只要他大于loc位置 就说明有一个新的数组一定合格 因为loc已经帮我们排除掉了  

代码如下：

​
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int ret = 0, i, j, pre = 1, loc = -1, cur = 1;
        for (i = 0; i < nums.size(); i ++){
            pre = lcm(pre, nums[i]) ;
            if (k % pre == 0){
                j = i ;
                cur = lcm(nums[j], 1);
             while(j > loc && k != cur){
                    j -- ;
                    if (j <= loc) break ;
                    cur = lcm(nums[j], cur) ;
                }
                res += j - loc ;
            }else {
                loc = i ;
                pre = 1 ;
            }
        }
        return res ;
    }
};

​
           

第三题

6235. 逐层排序二叉树所需的最少操作数目

难度：中等

给你一个 值互不相同 的二叉树的根节点 root 。

在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。

返回每一层按 严格递增顺序 排序所需的最少操作数目。

节点的 层数 是该节点和根节点之间的路径的边数。

思路

 层序遍历+置换环

根据题目描述 我们知道了他需要来一层一层的比较 所以需要利用队列来实现层序遍历 并且在遍历每层的节点的时候 需要让他实现一个 最小交换次数 的函数 最后用res变量来记住他 最后返回res每层最小的交换次数函数实现 本题是可以交换任意位置的元素，可以通过找环来做。对于数组nums，它排序之后为sortedNums，我们可以通过sortedNums知道原数组中每个数nums[i]应该排在哪个位置，当某个元素不在自己正确的位置 i 上时，若把它排到 i 上，就会把位置 i 上的数字怼出来；再把这个数字往它应该在的位置上怼，就这样下标连续怼可以完成一个小范围（也有可能整个数组都排好序）数字的归位，这个范围内的数形成了一个“环”。在能交换任意位置的两个元素的情况下，使数组升序的最小交换次数就是数组元素总个数减去环的个数。

代码如下：

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while(!q.empty()) {
            vector<int> layer;
            int qs = q.size();
            for(int i = 0; i < qs; i++) {
                TreeNode* node = q.front();
                q.pop();
                layer.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            int d = getMinSwaps(layer);
            ans += d;
        }
        return ans;
    }
    
    int getMinSwaps(vector<int>& v){
        vector<int> v1(v);
        sort(v1.begin(), v1.end());
        map<int, int> m;
        int len = v.size();
        for(int i = 0; i < len; i++) {
            m[v1[i]] = i;
        }
        int loops = 0;
        vector<bool> flag(len, false);
        for(int i = 0; i < len; i++) {
            if(!flag[i]) {
                int j = i;
                while(!flag[j]) {
                    flag[j] = true;
                    j = m[v[j]];
                }
                loops++;
            }
        }
        return len - loops;
    }
};
           

第四题

6236. 不重叠回文子字符串的最大数目

难度：困难

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

每个子字符串的长度 至少 为 k 。

每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

 思路：

做法，求出每个子串是不是回文子串。记 g(l,r) 表示第 l 到 r 个字符构成的子串是不是回文子串。

之后维护 f(i)f(i) 表示长度为 ii 的前缀中能选出多少个长度大等于 k 且不重叠的子串，转移方程为 

                f[i]=max(f[i-1],f[j]+1)      其中 i-j>=k 并且 j+1到i是回文串

上面的转移表示不选择以第 i 个字符为结尾的子串；下面的转移表示选择以第 (j + 1)个字符为开始，第 ii 个字符为结束的回文子串。

初值 f(0) = 0，答案就是 f(n)，复杂度 O(n^2)；

代码如下：

class Solution {
public:
    int maxPalindromes(string s, int K) {
        int n = s.size();
        bool flag[n][n];
        memset(flag, 0, sizeof(flag));
        for (int i = 0; i < n; i++) 
            {
                for (int l = i, r = i; l >= 0 && r < n && s[l] == s[r]; l--, r++) 
                {
                    flag[l][r] = true;
                }
            }
        for (int i = 0; i + 1 < n; i++) {
             for (int l = i, r = i + 1; l >= 0 && r < n && s[l] == s[r]; l--, r++)  
                    {
                        flag[l][r] = true;
                    }    
            }    

        int f[n + 1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            for (int j = i - K; j >= 0; j--) {
                if (flag[j][i - 1]) f[i] = max(f[i], f[j] + 1);
            }
        }
        return f[n];
    }
};