owenzhang的博客

Leetcode 第138场周赛解题报告

字数统计: 1.8k阅读时长: 7 min
2019/04/21
loading

今天的比赛的题目难度没有区分开，考察的不是很全面。题目描述也有些晦涩，考察的点却很简单。

例如第1题题目描述的让人看不清，看懂后发现就是考察个排序，真不知道这种题目出来有什么用途。面试中肯定不会出这种题。

第3题的用例也是错的，为了过掉题目，还要按照「错误的解」来修改程序。

做题的时候还有个插曲，外面下雨了，出去收了会衣服。回来还有时间把所有题目都AC掉。建议后面的比赛要难易结合，考点尽量宽泛些。

不过站在leetcode的角度来说，众口难调，组织这么多次比赛，偶尔出现几次问题也正常，希望后面的比赛越办越好。

下面是详细的题解和思考。

比赛的地址 Weekly Contest 138

https://leetcode-cn.com/contest/weekly-contest-138

1. 高度检查器

题目：

高度检查器(Height Checker)

地址：

https://leetcode-cn.com/contest/weekly-contest-138/problems/height-checker/

题意：

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。

思路：
本质就是求一个数组，排序后，要有多少个位置的数字不在从前的位置上。

排序后比较即可，代码很简单。

这题在做的时候以为是最少移动次数呢，例如输入[5,1,2,3,4]，可以把5直接放到最后。如果是这样的话题目难度就增加了，有兴趣可以再想想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int ans = 0;
        vector<int> v(heights);
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); ++i)
        {
            if(v[i]!=heights[i])
                ans++;
        }
        return ans;
    }
};

2. 爱生气的书店老板

题目：

爱生气的书店老板(Grumpy Bookstore Owner)

地址：

https://leetcode-cn.com/contest/weekly-contest-138/problems/grumpy-bookstore-owner/

题意：

给出两个长度都为n的数组customers和grumpy，grumpy每个元素只能是0或1，最后求和sum为

sum=customers[i]*（1-grumpy[i] ） (0 <= i < n)

然后给定一个数X（1<=X<=n）,可以把grumpy数组中连续X长度的元素的值从1变为0。问在确定X值后sum的最大值是多少？

思路：

上面的题意是我翻译的，实际上原题用的老板和顾客，还有生气值。有点和生活脱节，不是很好理解。

如果理解了题意，题目的做法就大概知道了。

先计算出来没有X时的原始sum值。然后使用一个长度X的区间，在customers数组从前到后扫描n-X次。更新每个扫描区间增加的值，增加的最大值和sum的原始值相加，就是结果。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int sum = 0;
        for(int i = 0; i < customers.size(); ++i)
            sum += customers[i]*(1-grumpy[i]);
        int delt = 0;
        for(int i = 0; i < X; ++i)
            delt += customers[i]*grumpy[i];
        int dt = delt;
        for(int i = X; i < customers.size(); ++i)
        {
            dt += customers[i]*grumpy[i] - customers[i-X]*grumpy[i-X];
            delt = max(dt, delt);
        }
        return sum + delt;
    }
};

3. 交换一次的先前排列

题目：

交换一次的先前排列(Previous Permutation With One Swap)

地址：

https://leetcode-cn.com/contest/weekly-contest-138/problems/previous-permutation-with-one-swap/

题意：

给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。

如果无法这么操作，就请返回原数组。

示例 4：

1
2
输入：[3,1,1,3]
输出：[1,1,3,3]

思路：

题目简单直白，题意也比较好理解。直交换两个数值，得到小于当前字典序的集合中，最大的那个字典序排列。

简直是把题目又复述了一遍。

处理方式为：

第一步：从当前序列的后往前找，找到第一个降序的位置（A[i]>A[i+1]），则必存在能构造比当前小的序列。

第二步：把A[i]后面的数字中，小于A[i]且最接近A[i]的值的数字找出来，和A[i]交换。

为什么第一步不再往前找，因为往前找更换，会让小的值出现在高位，导致不是最大字典序。

为什么第二步要找最接近的且小的，因为大的更换就超过当前序列，只能找小的。从小的里面找个最大值更换才能字典序最大，且不会超过当前序。

题目中的示例4是有问题的，答案应该是比[3,1,1,3]小的最大字典序是[1,3,1,3]，而不是[1,1,3,3]。

但是为了把题目过了，只能把18行改为if(A[i]>=A[t] && A[i]<A[f])，多加个等号。

因为可能是官方生成用例的时候也多加个等号，做题还要考虑官方的思路。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size();
        int f = 0;
        int t = 0;
        for(int i = n-2; i>=0; --i)
        {
            if(A[i]>A[i+1])
            {
                f = i;
                t = f+1;
                break;
            }
        }
        for(int i = f+2; i<n; ++i)
        {
            if(A[i]>=A[t] && A[i]<A[f])//如果题目修改了，把>=换成>即可
            {
                t = i;
            }
        }
        swap(A[f],A[t]);
        return A;
    }
};

4. 距离相等的条形码

题目：

距离相等的条形码(Distant Barcodes)

地址：

https://leetcode-cn.com/contest/weekly-contest-138/problems/distant-barcodes/

题意：

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

思路：

数组的已有元素重新排列，保证相邻元素不相同。由于题目保证存在答案，直接用贪心的方法就可以实现。

先统计出每个元素的个数，按照个数排序分配。按元素个数多少，从头到尾间隔放到数组的偶数下标位置中。然后第二轮把剩余元素放到奇数下标，构造出最后答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    const int MAXN = 10001;
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size();
        vector<int> ans(n);
        int cnt[MAXN] = {0};
        for(int m : barcodes)
            cnt[m]++;
        vector<pair<int, int>> v;
        for(int i = 0; i < MAXN; ++i)
        {
            if(cnt[i]>0)
                v.push_back({cnt[i], i});
        }
        sort(v.begin(), v.end());
        int i = 0;
        int j = v.size()-1;
        int k = 0;
        while(k<2)
        {
            for( i=k ; i < n; i+=2)
            {
                if(v[j].first == 0)
                    --j;
                ans[i] = v[j].second;
                --v[j].first;
            }
            ++k;
        }
        return ans;
    }
};

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC138%E5%9C%BA%E5%91%A8%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

发表日期：April 21st 2019, 10:00:03 am

更新日期：April 21st 2019, 10:00:03 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1. 高度检查器
  2. 2. 2. 爱生气的书店老板
  3. 3. 3. 交换一次的先前排列
  4. 4. 4. 距离相等的条形码
Total : 150
2024
2020
2019
2018
2017
2016
2014
2013
2012
2011
技术 读书 思考 技巧 学习 跑步