1. 不同的平均值数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

模拟即可。

代码

class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        map<double,int> mp;
        sort(nums.begin(),nums.end());
        int ans=0;
        for (int i = 0, j = nums.size() - 1; i < j; ++i, --j) {
            if (mp[double(nums[i]+nums[j])/2.0]!=1) {
                mp[double(nums[i]+nums[j])/2.0]=1;
                ++ans;
            }
        }
        return ans;
    }
};

2. 统计构造好字符串的方案数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

先试了下暴力回溯，果然超时。

然后画了会儿草稿发现，这不就是背包问题吗！zero和one是物品，可以无限取用，字符串长度是容量，只要遍历0到high每个容量下装满背包的方案数，再把low到high区间的方案数累加，就得到答案。且这是一个完全背包求排列数的问题。于是使用 一维数组，先遍历背包容量，再遍历物品，且都是从前向后遍历。

看了题解才发现，准确来说这是个爬楼梯问题……一次遍历即可。

代码

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<long> dp(high+1, 0);
        vector<int> item(2);
        int MOD=1e9+7;
        item[0] = zero;
        item[1] = one;
        dp[zero] += 1;
        dp[one] += 1;
        for (int i = 1; i <= high; ++i) {
            for (int j = 0; j < 2; ++j) {
                if(i >= item[j]) {
                    dp[i] += dp[i-item[j]]%MOD;
                }
            }
        }
        int ans = 0;
        for (int i = low; i <= high; ++i) ans=(ans + dp[i])%MOD;
        return ans;
    }
};

3. 树上最大得分和路径

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

参考这篇

代码

class Solution {
private:
    bool findBob(vector<int>& bobInfo, vector<vector<int>>& pic, int cur, int before, int bobTime) {
        if (cur==0) {
            bobInfo[cur]=0;
            return true;
        }
        bool found=false;
        int n=pic.size();
        // 遍历图，找到bob到0的路径
        for (int i = 0; i < pic[cur].size(); ++i) {
            int index=pic[cur][i];
            if (index!=before&&findBob(bobInfo, pic, index, cur, bobTime+1)) {
                found=true;
                break;
            }
        }
        if (found) bobInfo[cur] = bobTime;
        return found;
    }

    void dfs(int cur, int before, int score, int& maxScore, vector<vector<int>>& pic, int aliceTime, vector<int>& bobInfo, vector<int>& amount) {
        if (bobInfo[cur]==aliceTime) {
            score += amount[cur] / 2;
        } else if (bobInfo[cur] > aliceTime) {
            score += amount[cur];
        }
        if (pic[cur].size() == 1) maxScore = max(maxScore, score);
        for (int i = 0; i < pic[cur].size(); ++i) {
            int index = pic[cur][i];
            if (index != before) {
                dfs(index, cur, score, maxScore, pic, aliceTime + 1, bobInfo, amount);
            }
        }
    }
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        vector<vector<int>> pic(amount.size());
        for (auto& edge:edges) {
            pic[edge[0]].push_back(edge[1]);
            pic[edge[1]].push_back(edge[0]);
        }

        vector<int> bobInfo(amount.size(),amount.size());
        findBob(bobInfo, pic, bob, -1, 0);

        pic[0].push_back(-1);
        int ans = INT_MIN;
        dfs(0, -1, 0, ans, pic, 0, bobInfo, amount);
        return ans;
    }
};

4. 矩阵中的局部最大值

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

前两层遍历是确定左上角元素的行列值，内部两层循环是遍历方才确定的33矩阵。

代码

class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        vector<vector<int>> ans;
        vector<int> row;
        int n = grid.size();
        for (int i = 0; i < n - 2; ++i) {
            row.clear();
            for (int j = 0; j < n - 2; ++j) {
                int maxNum=INT_MIN;
                for (int k = i; k < i + 3; ++k) {
                    for (int l = j; l < j + 3; ++l) {
                        maxNum=max(maxNum, grid[k][l]);
                    }
                }
                row.push_back(maxNum);
                maxNum=INT_MIN;
            }
            ans.push_back(row);
        }
        return ans;
    }
};

5. 边积分最高的节点

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

积分用LL防止溢出，实际难度应该是Easy。

代码

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        int n = edges.size();
        vector<long long> score(n,0);
        for (int i = 0; i < n; ++i) score[edges[i]] += i;
        int ans=-1;
        long long maxScore=LONG_LONG_MIN;
        for (int i = n - 1; i >= 0; --i) {
            if (score[i] >= maxScore) {
                maxScore = score[i];
                ans = i;
            }
        }
        return ans;
    }
};

6. 根据模式串构造最小数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

代码

class Solution {
public:
    string smallestNumber(string pattern) {
        int i = 0, n = pattern.length();
        char cur = '1';
        string ans(n + 1, 0);
        while (i < n) {
            if (i && pattern[i] == 'I') ++i;
            for (; i < n && pattern[i] == 'I'; ++i) ans[i] = cur++;
            int i0 = i;
            while (i < n && pattern[i] == 'D') ++i;
            for (int j = i; j >= i0; --j) ans[j] = cur++;
        }
        return ans;
    }
};

7. 算术三元组的数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

确定第一个元素之后，第二三个元素值就确定了，用map保存元素的存在情况。

代码

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        map<int,int> mp;
        for (auto& num : nums) mp[num] = 1;
        int ans = 0;
        for (auto& num : nums) if (mp[num + diff] == 1 && mp[num + diff*2] == 1) ++ans;
        return ans;
    }
};

8. 受限条件下可到达节点的数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

这类图的题目有基本的方法概念了。

代码

class Solution {
private:
    int ans=0;
    void dfs(vector<vector<int>>& pic, int cur, int before, map<int,int>& mp) {
        // 受限则直接返回
        if (mp[cur] == 1) return;
        // 不受限，说明可达，计数加一
        ++ans;
        // 如果是叶子结点，返回
        if (pic[cur].size() == 1) return;
        else {
            // 非叶子结点，遍历连接的其他结点
            for (int i = 0; i < pic[cur].size(); ++i) {
                int index = pic[cur][i];
                if (index != before) dfs(pic, index, cur, mp);
            }
        }
    }
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        // 建图
        vector<vector<int>> pic(n);
        for (auto& edge : edges) {
            pic[edge[0]].push_back(edge[1]);
            pic[edge[1]].push_back(edge[0]);
        }
        // 将受限结点存入map，便于查询
        map<int,int> mp;
        for (auto& elem : restricted) mp[elem] = 1;
        // 防止首结点被识别为叶子
        pic[0].push_back(-1);
        ans = 0;
        dfs(pic, 0, -1, mp);
        return ans;
    }
};

9. 检查数组是否存在有效划分

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

看到划分就想到子问题，于是想到DP。

代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp (n+1,false);
        dp[0] = true;

        for (int i = 1; i <= n; ++i) {
            if (i >= 2 && dp[i - 2] && nums[i - 1] == nums[i - 2]) dp[i] = true;
            if (i >= 3 && dp[i - 3] && ((nums[i - 1] == nums[i-2] && nums[i -2] == nums[i - 3])||(nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1))) dp[i] = true;
        }
        return dp[n];
    }
};

10. 最长理想子序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

一眼认出来是DP，但自己写的n的平方的DP超时了。看了这篇才知道，原来对于字符串的题目，有一个枚举套路。对于本题，可以将每个位置间递推，抽象成每个字母递推。即将DP数组设定为以下标为结尾的最长序列，变成以某字符为结尾的最长序列。前者依赖于字符串长，而后者是依据可取字符串的范围，即k。

代码

class Solution {
public:
    int longestIdealString(string s, int k) {
        // int n = s.size();
        // vector<int> dp(n, 1);
        // int ans = INT_MIN;
        // for (int i = 1; i < n; ++i) {
        //     for (int j = 0; j < i; ++j) {
        //         if (s[i] - s[j] <= k && s[i] - s[j] >= -k) dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
        //         ans = ans > dp[i] ? ans : dp[i];
        //     }
        // }
        // return ans;
        vector<int> dp(26);
        int ans = INT_MIN;
        for (char ch : s) {
            ch -= 'a';
            dp[ch] = 1 + *max_element(dp.begin() + max(ch - k, 0), dp.begin() + min(ch + k + 1, 26));
            ans = ans > dp[ch] ? ans : dp[ch];
        }
        return ans;

    }
};