[数据结构与算法]leetcode第311场周赛

感受：这次周赛难度不大，比较基础

6180. 最小偶倍数 - 力扣（LeetCode）

?这题签到题没什么好说的直接枚举

class Solution {
public:
    int smallestEvenMultiple(int n) {
        if(n%2==0)return n;
        for(int i=1;;i++)
        {
            if((i*n)%2==0)return i*n;
        }
        return 0;
    }
};

6181. 最长的字母序连续子字符串的长度 - 力扣（LeetCode）

?这题只要遍历一遍就可以，看后一个元素减一是不是等于当前元素，然后取一个max

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int maxv=0,cnt=1;
        if(s.size()==1)return 1;
        
        for(int i=0;i<s.size()-1;i++)
        {
            if(s[i+1]-1!=s[i])cnt=1;
            if(s[i+1]-1==s[i])cnt++;
            maxv=max(cnt,maxv);
            
        }
        
        return maxv;
    }
};

6182. 反转二叉树的奇数层 - 力扣（LeetCode）

这题直接dfs搜索每一层，但是值得注意的是如果将两个节点进行交换的话那整棵树都会进行交换

所以我们只要交换节点之间的值就好

class Solution {
public:

    void dfs(int d,TreeNode*left,TreeNode*right)
    {
        if(left&&right)
        {
            if(d%2==0&&left->left&&right->right)
            {
                  swap(left->left->val,right->right->val);
            }
            dfs(d+1,left->left,right->right),dfs(d+1,left->right,right->left);

        }
    }
    TreeNode* reverseOddLevels(TreeNode* root) {
     dfs(0,root,root);   

        return root;
    }
};

?6183. 字符串的前缀分数和 - 力扣（LeetCode）

这题暴力思路很简单，将每一个字符串的前缀统计在map里然后再遍历每个字符串的前缀即可

但是时间复杂度是O（n ^2logn)?，大概是1e7的复杂度，但是由于力扣的评测机过于垃圾

1e7会TLE尤其是c++，但是神奇的是python不会TLE所以这里用python来写

先来个c++代码

#pragma GCC optimize(2)//O2优化
class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        map<string,int>mp;
        for(int i=0;i<words.size();i++)
        {
            int j=0;
            string s;
            while(j<words[i].size())
            {
                s+=words[i][j];
                mp[s]++;
                j++;
            }
        }
        vector<int>res;
        
        
        int cnt=0;
        for(int i=0;i<words.size();i++)
        {           
            string s;
            int j=0;
            while(j<words[i].size())
            {
                s+=words[i][j];
                cnt+=mp[s];
                j++;
            }
            res.push_back(cnt);
            cnt=0;
        }
        return res;
    }
};

python代码?

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        cnt=defaultdict(int)
        for word in words:
            prefix=''
            for i in word:
                prefix+=i
                cnt[prefix]+=1
        ans=[]
        for word in words:
            prefix=''
            sumx=0
            for char in word:
                prefix+=char
                sumx+=cnt[prefix]
            ans.append(sumx)
        return ans;