2023‐07‐22 第 109 场双周赛 - ProgramTraveler/leetcode GitHub Wiki

检查数组是否是好的

  • 第一题感觉有点绕
  • 多花了点时间在思路上
class Solution {
public:
    bool isGood(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        int idx = 1;
        int len = nums.size();
        int n = len - 1;
        
        for (int i = 0; i < len - 1; i ++) {
            if (nums[i] != i + 1) return false;
        }
        
        if (n != nums[len - 1]) return false; 
        
        return true;
    }
};

将字符串中的元音字母排序

  • 这个也正常做就行
class Solution {
public:
    bool func(char c) {
        return c == 'A' || c == 'a' || c == 'E' || c == 'e' || c == 'I' || c == 'i' || c == 'O' || c == 'o' || c == 'U' || c == 'u';    
    }
    
    string sortVowels(string s) {
        string t;
        
        vector<int> cor; // 记录元音位置
            
        for (int i = 0; i < s.size(); i ++) {
            if (func(s[i])) {
                cor.emplace_back(i);
                
                t.push_back(s[i]);
            }
        }
        
        sort(t.begin(), t.end());
        
        for (int i = 0; i < cor.size(); i ++) s[cor[i]] = t[i];
        
        return s;
    }
};

访问数组中的位置使分数最大

  • 读题目感觉有点像组合问题
  • 就像用 dfs 来做
  • 然后就是 dfs 日常超时
  • 那只能是 dp 了
  • 后面得做点 dp 算法题了 太菜了
class Solution {
public:
    long long max(long long n1, long long n2) {
        return n1 > n2 ? n1 : n2;
    }
    
    long long maxScore(vector<int>& nums, int x) {
        // 有点随机组合的意思
        long long res = 0;
        
        int n = nums.size();
        
        vector<int> tem;
        
        function<void(int)> dfs = [&](int i) {
            if (i >= n) {
                long long sum = 0;
                
                for (int i = 0; i < tem.size(); i ++) {
                    if (i < tem.size() - 1 && tem[i] % 2 != tem[i + 1] % 2) sum -= x;
                    
                    sum += tem[i];
                }
                
                res = max(res, sum);
                
                return ;
            }
            
            // 不选
            dfs(i + 1);
            
            // 选
            tem.emplace_back(nums[i]);
            dfs (i + 1);
            tem.pop_back();
            
        };
        
        
        dfs(0);
        return res;
    }
};
正确思路
  • 思路看着挺简单的
  • 关键还是 状态转移方程
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();

        // 初始化 f[a_0 % 2]
        const long long INF = 1e18;
        long long f[2];
        f[0] = f[1] = -INF;
        f[nums[0] % 2] = nums[0];

        // 从左到右枚举访问的终点
        long long ans = nums[0];
        for (int i = 1; i < n; i++) {
            // 套用 dp 方程
            int p = nums[i] % 2;
            long long t = max(f[p] + nums[i], f[p ^ 1] + nums[i] - x);
            f[p] = max(f[p], t);
            ans = max(ans, t);
        }
        return ans;
    }
};
⚠️ **GitHub.com Fallback** ⚠️