[数据结构与算法]LeetCode——Weekly Contest 312

LeetCode周赛第312场记录

6188. 按身高排序(读题写代码)

这道题纯按照题意写代码，没有难度，此处从略。

6189. 按位与最大的最长子数组(脑筋急转弯)

这道题是一个脑筋急转弯问题，重要的就是看到一个结论：按位与只会使得运算结果越来越小，而没有逐渐增大的可能。（我在比赛时脑子抽抽了，脑子里一直想着是XOR运算）所以这道题的最终被规约为：找出这个数组中的连续最大元素的序列长度。

所以只需要执行两次遍历即可，第一次在于找出数组中的最大元素，第二次对最大元素的连续序列长度进行计数，返回最大长度即可。

int longestSubarray(vector<int>& nums) 
{
        int Max = nums[0];
        for(int Each : nums)        // 1.search for largest element
            Max = max(Max, Each);

        int Ans = 0, Cur = 0;
        for(int Each : nums)        // 2.count the number of contigious max element
            if(Each == Max)
            {
                ++Cur;
                Ans = max(Ans, Cur);
            }
            else
                Cur = 0;
        return Ans;
}

这种题出在竞赛里，想出来就可以立刻AC，没有成功地将题意进行转化就会很费时间。

6190. 找到所有好下标(动态规划)

一个数满足好下标必须保证它的左边连续k个元素是非递增的，右边连续k个元素是非递减的。

那么一个朴素的想法就是遍历这个数组，并在其中挨个记录其左边和右边分别满足要求的元素个数，如果两者都满足，那么这个位置就是一个好下标，因为要求是连续的元素，所以这里需要记录之前的状态，因而可以使用动态规划的的思路来求解。

完整的AC代码如下：

vector<int> goodIndices(vector<int>& nums, int k) 
{
        int n = nums.size();
        vector<int> left(n, 1);		// 统计某一位置左边有多少个连续不递增元素
        vector<int> right(n, 1);	// 统计某一位置右边有多少个连续不递减元素
        for (int i = 1; i < n; i++) 
        {
            if (nums[i] <= nums[i - 1]) 
                left[i] = left[i - 1] + 1;
            if (nums[n - i - 1] <= nums[n - i]) 
                right[n - i - 1] = right[n - i] + 1;
        }

        vector<int> ans;
        for (int i = k; i < n - k; i++) 
            if (left[i - 1] >= k && right[i + 1] >= k) // 如果左右都符合要求，那么是一个好下标
                ans.emplace_back(i);
                
        return ans;
}

2421. 好路径的数目（并查集）

这里的代码参考的是灵茶山艾府大佬的题解，首先在此做版权声明。

这里就是从大佬的代码里学习一些思路和技巧了，首先给出完整的AC代码：

int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) 
{
        /* set up graph */
        int Size = vals.size();
        vector<vector<int>> Graph(Size);
        for(auto& Each : edges)
        {
            int From = Each[0], To = Each[1];
            Graph[From].push_back(To);
            Graph[To].push_back(From);
        }

        int Father[Size], ID[Size], UnionSize[Size];
        iota(Father, Father + Size, 0);
        iota(ID, ID + Size, 0);
        fill(UnionSize, UnionSize + Size, 1);
        /* using lambda expr to declare a function object */
        function<int(int)> findFather = [&](int x)->int {return x == Father[x] ? x : (Father[x] = findFather(Father[x]));};

        int Ans = Size;                                 // the minimum number of good path is Size
        sort(ID, ID + Size, [&](int x, int y)->bool{ return vals[x] < vals[y];});
        for(auto x : ID)
        {
            int ValueX = vals[x], FatherX = findFather(x);
            for(auto y : Graph[x])
            {
                y = findFather(y);                      // search the father of y
                if(y == FatherX || vals[y] > ValueX)
                    continue;
                if(vals[y] == ValueX)
                {
                    Ans += UnionSize[y] * UnionSize[FatherX];
                    UnionSize[FatherX] += UnionSize[y];
                }
                Father[y] = FatherX;		// merge the set into one set
            }
        }
        return Ans;
}

思路上不再赘述，对于我这样的算法小白来说还是过于高超了，我根本想不到会使用并查集来解这道题。这道题中并查集中每个集合以数值最大的节点作为父亲节点，值从小到大地遍历所有节点。另外一个相对费解的点就是，UnionSize[x]记录的是当前集合中值为val[x]的个数，当从小到大遍历时记录的也就是当前集合中最大节点值的数量。因为一条好路径，它的两个端点一定是当前集合中的最大元素，否则不能满足中间所有节点数值都小于等于端节点的要求。

这段代码还有以下的学习点：

1.注意lambda表达式的使用和线段树的模板以及function函数对象，写的非常好。

2.注意函数iota用于使用连续递增序列值初始化连续空间。

3.在排序vals时，没有直接对vals进行排序，这是因为不能破坏vals的原始序列。这份代码中将各个元素的索引下标提取出来形成ID，对ID进行sort然后去索引原数组，这种做法非常聪明。