正文索引 [隐藏]

传送门

t1 千位分隔数

给定一个整型数，给它每三位加上一个分隔符。

做法有很多，憨一点可以用取出每一位数字来做，但看这个范围估计是要炸的，所以我这里选择转成string来做。

转成string，计数，每三位加上一个”.”最后翻转一下就行了，记得处理一下前缀“.”。

class Solution {
public:
    string thousandSeparator(int n) {
        string str = to_string(n);
        
        if(n < 1000) return str;
        
        int m = str.size();
        string ans = "";
        
        int cnt = 0;
        for(int i = m-1; i >= 0; i--)
        {
            ans += str[i];
            if(cnt == 2) 
            {
                ans += ".";
                cnt = 0;
                continue;
            } 
            cnt++;
        }
        
        if(ans[ans.size()-1] == '.') ans.erase(ans.size()-1);
        
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

t2 可以到达所有点的最少点数目

给出一个DAG，找出最少能到达所有点的点集合。

赛时这题没做出来，看上去唬人得一匹，赛后看到了大佬的证明，直接跪了。

先说结论，答案就是集合A={node|其他任何节点都无法到达的node}，也等价于A={node|入度为零的点}。

下面放证明：

反证法：假设存在某节点node1， 且从以上集合中任意节点出发都不能到达node1。
由于node1肯定不包含在A中，因此必然有另外一个节点node2能够到达node1，而node2也不能存在于A中，因此必有node3能到达node2……
这样下去，必然有nodeN存在能够到达node(N-1)，当N大于节点个数时，就会存在矛盾（即必然会遍历到某个属于A中的元素）。另外一种情况是，图中有环，但题目明确说了无环图，所以完成了合理性证明。
再进行最优性证明：
显然，如果存在一个集合（记作B）元素个数少于A，那必定存在一个元素node1属于A但不属于B。根据A的性质，其它任意节点都不可到达node1，这样从B中的节点出发，不可能到达node1.因此不可能存在比它更少的元素个数的集合，满足条件。

epic-ramanujan

于是用两个set去找入度为0的点就可以了。

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        unordered_set<int> to, from;
        vector<int> ans;

        for(auto el: edges)
        {
            to.insert(el[1]);
            from.insert(el[0]);
        }

        for(auto p: from)
            if(!to.count(p)) ans.push_back(p);

        return ans;
    }
};

t3 得到目标数组的最少函数调用次数

给出一个func方法，有两种操作：

  1. 把序列中任意一项+1
  2. 将整个序列×2

给定一个目标序列，求使用以上方法将一个全零序列调整至目标序列所需要的最少调用次数。

首先贪心地思考，要让调用次数最少，那肯定尝试尽可能多地去使用操作2，那么我们就要找到操作2的执行次数是由什么来决定的。

遇事不决分析样例，写两组看看：

图源：Durant

可以看到，整个过程中操作2的执行次数与序列最大值有关(或者说就是序列最大值执行操作2的次数)，所以我们可以把思路放在这上面。

遍历nums数组，对每个数进行枚举。如果它是偶数，就循环除2直到无法再除，统计除2次数用以维护最大除2操作数；如果它是奇数，就-1，模拟操作1的过程，将这个次数累加到总操作数中，因为每个数+1的操作是独立的，应该直接累积到最后答案里。

最后的答案就是累计的+1操作数与维护得到的最大除2操作数之和。

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        int max_mal = -1;

        for(auto el: nums)
        {
            int tmp_mul = 0;
            while(el > 0)
            {
                if(!(el % 2))
                {
                    el /= 2;
                    tmp_mul++;
                }
                else el--,ans++;
            }
            max_mal = max(max_mal, tmp_mul);
        }
        ans += max_mal;
        
        return ans;
    }
};