On the shoulders of giants.

weekly-contest-194

数组异或操作

给你两个整数,nstart

数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)且 n == nums.length

请返回 nums 中所有元素按位异或(XOR)后得到的结果。

示例 1:

输入:n = 5, start = 0
输出:8
解释:数组 nums 为 [0, 2, 4, 6, 8],其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

示例 2:

输入:n = 4, start = 3
输出:8
解释:数组 nums 为 [3, 5, 7, 9],其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3:

输入:n = 1, start = 7
输出:7

示例 4:

输入:n = 10, start = 5
输出:2

提示:

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length
题解

直接模拟计算即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    int xorOperation(int n, int start) {
        int result = 0;
        for(int i = 0; i < n; i++) {
            result ^= start + 2 * i;
        }
        return result;
    }
};

保证文件名唯一

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹:在第 i 分钟,新建名为 names[i] 的文件夹。

由于两个文件 不能 共享相同的文件名,因此如果新建文件夹使用的文件名已经被占用,系统会以 (k) 的形式为新文件夹的文件名添加后缀,其中 k 是能保证文件名唯一的 最小正整数

返回长度为 n 的字符串数组,其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。

示例 1:

输入:names = ["pes","fifa","gta","pes(2019)"]
输出:["pes","fifa","gta","pes(2019)"]
解释:文件系统将会这样创建文件名:
"pes" --> 之前未分配,仍为 "pes"
"fifa" --> 之前未分配,仍为 "fifa"
"gta" --> 之前未分配,仍为 "gta"
"pes(2019)" --> 之前未分配,仍为 "pes(2019)"

示例 2:

输入:names = ["gta","gta(1)","gta","avalon"]
输出:["gta","gta(1)","gta(2)","avalon"]
解释:文件系统将会这样创建文件名:
"gta" --> 之前未分配,仍为 "gta"
"gta(1)" --> 之前未分配,仍为 "gta(1)"
"gta" --> 文件名被占用,系统为该名称添加后缀 (k),由于 "gta(1)" 也被占用,所以 k = 2 。实际创建的文件名为 "gta(2)" 。
"avalon" --> 之前未分配,仍为 "avalon"

示例 3:

输入:names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出:["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释:当创建最后一个文件夹时,最小的正有效 k 为 4 ,文件名变为 "onepiece(4)"。

示例 4:

输入:names = ["wano","wano","wano","wano"]
输出:["wano","wano(1)","wano(2)","wano(3)"]
解释:每次创建文件夹 "wano" 时,只需增加后缀中 k 的值即可。

示例 5:

输入:names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出:["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释:注意,如果含后缀文件名被占用,那么系统也会按规则在名称后添加新的后缀 (k) 。

提示:

  • 1 <= names.length <= 5 * 10^4
  • 1 <= names[i].length <= 20
  • names[i] 由小写英文字母、数字和/或圆括号组成。
题解

把存在的文件加入 map 中,判断一个文件名是否出现过,就在 map 中找存不存在。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        map<string, int> count;
        vector<string> result;
        for(auto name : names) {
            if(count.find(name) == count.end()) {
                count[name] = 0;
                result.push_back(name);
            } else {
                string k;
                do {
                    count[name]++;
                    k = "(" + to_string(count[name]) + ")";
                } while(count.find(name + k) != count.end());
                count[name + k] = 0;
                result.push_back(name + k);
            }
        }
        return result;
    }
};

避免洪水泛滥

你的国家有无数个湖泊,所有湖泊一开始都是空的。当第 n 个湖泊下雨的时候,如果第 n 个湖泊是空的,那么它就会装满水,否则这个湖泊会发生洪水。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ,其中:

  • rains[i] > 0 表示第 i 天时,第 rains[i] 个湖泊会下雨。
  • rains[i] == 0 表示第 i 天没有湖泊会下雨,你可以选择 一个 湖泊并 抽干 这个湖泊的水。

请返回一个数组ans ,满足:

  • ans.length == rains.length
  • 如果 rains[i] > 0 ,那么ans[i] == -1 。
  • 如果 rains[i] == 0 ,ans[i] 是你第 i 天选择抽干的湖泊。

如果有多种可行解,请返回它们中的 任意一个 。如果没办法阻止洪水,请返回一个 空的数组 。

请注意,如果你选择抽干一个装满水的湖泊,它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊,那么将无事发生(详情请看示例 4)。

示例 1:

输入:rains = [1,2,3,4]
输出:[-1,-1,-1,-1]
解释:第一天后,装满水的湖泊包括 [1]
第二天后,装满水的湖泊包括 [1,2]
第三天后,装满水的湖泊包括 [1,2,3]
第四天后,装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水,也没有湖泊会发生洪水。

示例 2:

输入:rains = [1,2,0,0,2,1]
输出:[-1,-1,2,1,-1,-1]
解释:第一天后,装满水的湖泊包括 [1]
第二天后,装满水的湖泊包括 [1,2]
第三天后,我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后,我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后,装满水的湖泊包括 [2]。
第六天后,装满水的湖泊包括 [1,2]。
可以看出,这个方案下不会有洪水发生。同时, [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3:

输入:rains = [1,2,0,1,2]
输出:[]
解释:第二天后,装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后,湖泊 1 和 2 都会再次下雨,所以不管我们第三天抽干哪个湖泊的水,另一个湖泊都会发生洪水。

示例 4:

输入:rains = [69,0,0,0,69]
输出:[-1,69,1,1,-1]
解释:任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解,其中 1 <= x,y <= 10^9

示例 5:

输入:rains = [10,20,20]
输出:[]
解释:由于湖泊 20 会连续下 2 天的雨,所以没有没有办法阻止洪水。

提示:

  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9
题解

贪心、二分。依次遍历数组,保存可以抽水的天数,当遇到某个湖泊要溢出的情况时,二分查找最小能抽水的那一天(在两次下雨之间),并抽出湖泊的水。

时间复杂度:\(O(n\log m)\)

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> result(n, 1);
        set<int> tmp;
        unordered_map<int, int> h;
        for(int i = 0; i < n; i++) {
            int rain = rains[i];
            if(rain != 0) {
                if(h.count(rain) != 0) {
                    auto it = tmp.lower_bound(h[rain]);
                    if(it == tmp.end()) 
                        return vector<int> {};
                    result[*it] = rain;
                    tmp.erase(it);
                } 
                h[rain] = i;
                result[i] = -1;
            } else tmp.insert(i);
        }
        return result;
    }
};

找到最小生成树里的关键边和伪关键边

给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1 ,同时还有一个数组 edges ,其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集,它连接了所有节点且没有环,而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边,会导致最小生成树的权值和增加,那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意,你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1:

输入:n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出:[[0,1],[2,3,4,5]]
解释:上图描述了给定图。
下图是所有的最小生成树。

注意到第 0 条边和第 1 条边出现在了所有最小生成树中,所以它们是关键边,我们将这两个下标作为输出的第一个列表。
边 2,3,4 和 5 是所有 MST 的剩余边,所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 :

输入:n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出:[[],[0,1,2,3]]
解释:可以观察到 4 条边都有相同的权值,任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示:

  • 2 <= n <= 100
  • 1 <= edges.length <= min(200, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= fromi < toi < n
  • 1 <= weighti <= 1000
  • 所有 (fromi, toi) 数对都是互不相同的。
题解

先跑一次最小生成树,记结果为 min_result

删除每条边 edge ,再跑最小生成树:

  • 如果结果与 min_result 不同,那么该边 edge 为关键路径
  • 如果结果与 min_result 相同,那么再跑一次最小生成树并强行把该边 edge 加入,如果结果还与 min_result 相同,那么该边 edge 为伪关键路径

时间复杂度:\(O(m\log m + mn)\)

class Solution {
private:
    struct Edge {
        int from, to, id, value;
        bool operator < (const Edge& tmp) const {
            return value < tmp.value;
        }
    };
public:
    vector<int> father;
    vector<Edge> graph;
    int getFather(int x) {
        return father[x] == x ? x : father[x] = getFather(father[x]);
    }
    int kruskal(int n, int erase_edge, int flag) {
        int result = 0, total = 0;
        for(int i = 0; i < n; i++) father[i] = i;
        if(flag == 1) {
            int u_parent = getFather(graph[erase_edge].from);
            int v_parent = getFather(graph[erase_edge].to);
            result += graph[erase_edge].value;
            father[u_parent] = v_parent;
            total++;
        }
        for(int i = 0; i < graph.size(); i++) {
            if(i == erase_edge) continue;
            int u_parent = getFather(graph[i].from);
            int v_parent = getFather(graph[i].to);
            if(u_parent != v_parent) {
                result += graph[i].value;
                father[u_parent] = v_parent;
                if(++total == n - 1) return result;
            }
        }
        return -1;
    }
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        graph = vector<Edge> ();
        for(int i = 0; i < edges.size(); i++) {
            vector<int> edge = edges[i];
            graph.push_back((Edge){edge[0], edge[1], i, edge[2]});
        }
        sort(graph.begin(), graph.end());
        father = vector<int> (n);
        int min_sum = kruskal(n, -1, 0);
        vector<vector<int>> result(2, vector<int> ());
        for(int i = 0; i < edges.size(); i++) {
            int sum = kruskal(n, i, 0);
            if(sum != min_sum) {
                result[0].push_back(graph[i].id);
            } else if(min_sum == kruskal(n, i, 1)){
                result[1].push_back(graph[i].id);
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注