1. 重排字符形成目标字符串

难度

• Easy
• Medium
• Hard

完成情况

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

思路

显然副本数与目标字符串分别在两个字符串中的数目有关，而与顺序无关。用两个数组分别存储两个字符串中每个字符的数量，其商为当前字符的副本数，显然字符串的副本数取决于副本数最少的字符。

代码

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> targetNum(26, 0);
        for (auto& ch : target) targetNum[ch - 'a']++;
        vector<int> sNum(26, 0);
        for (auto& ch : s) sNum[ch - 'a']++;
        int ans = INT_MAX;
        for (int i = 0; i < 26; ++i) {
            if (targetNum[i]) {
                ans = min((sNum[i] / targetNum[i]), ans);
            }
        }
        return ans;
    }
};

2. 价格减免

难度

• Easy
• Medium
• Hard

完成情况

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

思路

本身不难，但是细节很多，比如考虑dollar符号位置，处理溢出等。

代码

class Solution {
public:
    string discountPrices(string sentence, int discount) {
        string ans = "";
        auto newPrice = [&](long price, int discount)->string {
            double p = price * (100 - discount) * 0.01;
            stringstream ss;
            ss << setiosflags(ios::fixed) << setprecision(2) << p;
            string s = "$" + ss.str();
            return s;
        };
        int n = sentence.size();
        for (int i = 0; i < n;) {
            if (sentence[i] == '$' && (i == 0 || sentence[i - 1] == ' ') && i < n - 1 && (sentence[i + 1] - '0' >= 0 && sentence[i + 1] - '0' < 10) ) {
                ++i;
                long sum = 0;
                string temp = "$";
                bool isTrue = true;
                while (sentence[i] != ' ' && i < n) {
                    if (sentence[i] - '0' >= 0 && sentence[i] - '0' < 10) {
                        temp += sentence[i];
                        sum = sum * 10 + (sentence[i] - '0');
                        ++i;
                    }
                    else {
                        isTrue = false;
                        break;
                    }
                }
                if (isTrue) ans += newPrice(sum, discount);
                else ans += temp;
            }
            else {
                ans += sentence[i];
                ++i;
            }
        }
        return ans;
    }
};

3. 回环句

难度

• Easy
• Medium
• Hard

完成情况

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

思路

题目保证了给出的字符串一定是个正常的句子，那就没有什么难度了，直接遍历判断即可。

代码

class Solution {
public:
    bool isCircularSentence(string sentence) {
        int n = sentence.size();
        if (sentence[0] != sentence[n - 1]) return false;
        for (int i = 0; i < n; ++i) {
            if (sentence[i] == ' ') {
                if (sentence[i - 1] != sentence[i + 1]) return false;
            }
        }
        return true;
    }
};

4. [划分技能点相等的团队]

难度

• Easy
• Medium
• Hard

完成情况

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

思路

看似很难，其实很简单。

确定技能点总和与团队人数后，每个团队的技能点总和是确定的（如果总技能点不能被团队数整除，就返回-1）。那么剩下的工作就是看看数组中是不是每个数都恰好能匹配到团队技能点和减去自身的数。用map也行，查找也行。

代码

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        int n = skill.size();
        int sum = 0;
        unordered_map<int, int> mp;
        for(auto& num : skill) {
            mp[num]++;
            sum += num;
        }
        if (sum % (n >> 1) != 0) return -1;

        int teamSum = sum / (n >> 1);
        long long ans = 0LL;
        for (int i = 0; i < n; ++i) {
            int s1 = skill[i], s2 = teamSum - s1;
            if (mp[s1]) {
                --mp[s1];
                if(!mp[s2]) return -1;
                else {
                    --mp[s2];
                    ans += s1 * s2;
                }
            }
        }
        return ans;
    }
};

5. 两个城市间路径的最小分数

难度

• Easy
• Medium
• Hard

完成情况

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

思路

今天最开心的是能做出这道Medium的图论题。

根据题目描述不难发现，因为每条边只要可达，便能重复使用，那么只要在一个连通子图内，就能把所有边走一遍，再到目标点去。所以我们的工作就是找到包含起始点和目标点的连通子图内的最短边。

用一个数组 access 记录顶点的访问情况来区分连通子图。

代码

class Solution {
private:
    void dfs(int pre, int cur, vector<vector<int>>& pic, unordered_set<int>& access) {
        if (access.count(cur)) return;
        access.emplace(cur);
        for (auto& next : pic[cur]) {
            if (cur != pre) {
                dfs(cur, next, pic, access);
            }
        }
    }
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<int>> pic(n + 1, vector<int>());
        for (auto& road : roads) {
            pic[road[0]].push_back(road[1]);
            pic[road[1]].push_back(road[0]);
        }
        unordered_set<int> access;

        dfs(-1, 1, pic, access);

        int ans = INT_MAX;
        for (auto& road : roads) {
            if (access.count(road[0]) && access.count(road[1])) ans = ans < road[2] ? ans : road[2];
        }
        return ans;
    }
};

6. 将节点分成尽可能多的组

难度

• Easy
• Medium
• Hard

完成情况

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

思路

这题其实有点遗憾，有比较清晰的思路，但是实现方面有困难。对于单个连通子图，应当从度最小的顶点出发，做广度遍历，或者说层序遍历，层数就是这个连通子图能达到的最多分组。每个连通子图的分组数加起来，就是答案。要注意一个情况，就是连通子图是一个完全的环时，不存在分组。我在实现步骤卡在这里了。

代码