Leetcode第218次周赛解题报告

真的绷不住了 每次都是动态规划做不出来 下面做几天动态规划题目

1678. 设计 Goal 解析器

根据题意，使用字符串替换替换即可

• () -> o
• (al) -> al

/**
 * @param {string} command
 * @return {string}
 */
var interpret = (command) => command.replaceAll("()","o").replaceAll("(al)","al")

1679. K 和数对的最大数目

可以把删除数对的过程抽象化为从一个集合中删除字符的过程
利用unordered_map记录出现次数，遍历每一个出现的数字i，对其对应的另一个数字：K-i进行删除（假如有的话）
最后使用ans维护删除次数，返回答案

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(auto x:nums)  mp[x]++;
        int ans = 0;
        for(auto x:nums) {
            if(mp[x]>0) {
                int left = k - x;
                mp[x]--;
                if(mp[left] > 0) {
                    mp[left]--;
                    ans++;
                }else mp[x]++;
            }
        }
        return ans;
    }
};

1680. 连接连续二进制数字

莫名其妙做对了，但是不知道为什么做对，硬说的话就是大模拟，配合上大数性质就解决了

class Solution {
public:
    int concatenatedBinary(int n) {
        int res=0, mo=1000000007,x=1;
        for(int i=n; i>=1;--i)
            for(int j=i;j>0;j/=2,x=x*2%mo)
                if(j%2) res=((res%mo)+(x%mo))%mo; 
        return res;
    }
};

1679. K 和数对的最大数目

顶不住了 我真不会 又是状态压缩DP 学会了回来更