蔚来的题，偏思维，有点意思！

ACM算法日常

发布于 2021-12-28 16:36:17

7500

发布于 2021-12-28 16:36:17

文章被收录于专栏：ACM算法日常

蔚来汽车联名力扣周赛的题目涉及的算法都很常见，但是都带了一点思维，作为头脑风暴是个不错的选择。

设计知识点：模拟、前缀和、双指针、贪心

5963. 反转两次的数字

给定一个正整数

，把它翻转两次，判断是否还等于

，每次反转要去除前导零

题解

可以直接模拟

//cpp 11
class Solution {
public:
    int rever(int num) {
        string s;
        int x = num;
        while (x) {
            s += x % 10 + '0'; x /= 10;
        }
        const char* str= s.c_str();
        return atoi(str);
    }
    bool isSameAfterReversals(int num) {
        return num == rever(rever(num));
    }
};

另一种办法，只要尾巴有

，反转的时候就会丢失，因此判断是否是

的倍数即可，特判一下

// cpp
class Solution {
public:
    bool isSameAfterReversals(int num) {
        return num == 0 || num % 10 != 0;
    }
};

5964. 执行所有后缀指令

给定一个网格，给定一个指令字符串，机器人按照指令行动，如果越界或者指令结束，机器人停止行动

现在机器人根据指令字符串的每一个后缀指令行动，计算机器人停止时执行的指令个数

题解

直接模拟，暴力梭哈

// cpp11
class Solution {
public:
    vector<int> executeInstructions(int n, vector<int>& st, string s) {
        vector<int> ans;
        for (int i = 0; i < s.length(); ++i) {
            int cnt = 0;
            int x = st[0], y = st[1];
            for (int j = i; j < s.length(); ++j) {
                if (s[j] == 'L') y--;
                else if (s[j] == 'R') y++;
                else if (s[j] == 'U') x--;
                else if (s[j] == 'D') x++;
                if (x >= 0 && x < n && y >= 0 && y < n) cnt++;
                else break;
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

5965. 相同元素的间隔之和

给定一个数组

，对于元素

a[i],\ a[j]

，我们定义他们的距离为

|j - i|

现在对每个位置

，我们先找出所有与

a[i]

相等的元素，然后计算他们到

a[i]

的距离之和

数据规定

1\leq n\leq 10^5

，其中

为数组

的长度

题解

比赛的时候想了个推式子的方法，思维量比较大

可以用哈希表划分等价类，以值为代表元，为每个集合维护一个

vector

考虑子问题，给定一个下标数组

vec

，如何计算距离之和

可以先利用差分数组

dif

计算出两两之间的距离

对于每个位置

，考虑距离出现的次数，于是可以列出如下式子

\begin{aligned} & \sum_{j = 0}^{i}j\cdot dif[j] + \sum_{j = i + 1}^{n - 1}(n - j)dif[j]\\ = & \sum_{j = 0}^{i}j\cdot dif[j] - \sum_{j = i + 1}^{n - 1}j\cdot dif[j] + n\sum_{j = i + 1}^{n - 1}dif[j]\\ \end{aligned}

考虑到

vec

是

dif

的前缀和，我们再用

pre

维护

j\cdot dif[j]

的前缀和，于是可以化简为

\begin{aligned} & pre[i] - (pre[n - 1] - pre[i]) + n\cdot (vec[n - 1] - vec[i])\\ = & (2\cdot pre[i] - pre[n - 1]) + n\cdot (vec[n - 1] - vec[i])\\ \end{aligned}

于是可以

\mathcal{O}(1)

计算每个位置的距离和，总的时间复杂度为

\mathcal{O}(n)

// cpp11
class Solution {
public:
    vector<long long> getDistances(vector<int>& a) {
        typedef long long LL;
        map<LL, vector<int>> mp;
        for (int i = 0; i < a.size(); ++i) {
            LL key = a[i];
            mp[key].push_back(i);
        }
        vector<LL> ans(a.size());
        for (auto& i: mp) {
            auto vec = i.second;
            int n = vec.size();
            vector<LL> dif(n), pre(n);
            dif[0] = vec[0];
            pre[0] = 0;
            for (int i = 1; i < n; ++i) {
                dif[i] = vec[i] - vec[i - 1];
            }
            for (int i = 1; i < n; ++i) {
                pre[i] = 1LL * i * dif[i] + pre[i - 1];
            }
            for (int i = 0; i < n; ++i) {
                ans[vec[i]] = 2LL * pre[i] - pre[n - 1] + 1LL * n * (vec[n - 1] - vec[i]);
            }
        }
        return ans;
    }
};

5966. 还原原数组

从前 alice 有一个数组 a，她任取了一个正整数 k

她对于每一个位置 i，都构造出了 a[i] - k, a[i] + k 两个元素，并放入了 l, h 数组的对应位置

现在 l, h 数组被合并成了一个新数组 arr，并随机做了一个排列，之前的数组 a，正整数 k 也消失了，希望你可以帮忙还原出原数组 a

数据规定

1\leq n\leq 1000

，其中

为数组

的长度

题解

将

arr

排序，那么

arr[0]

一定是

l[0]

我们从

1\sim 2n

枚举

arr

中所有位置，并判断该位置成为

h[0]

的可行性

不妨设

dif = h[0] - l[0]

，如果已经有

pair(i,\ j)

满足

arr[j] - arr[i] = dif,\ j > i

，那么之后满足

arr[j'] - arr[i'] = dif

的

pair(i',\ j')

一定满足

j' > j,\ i' > i

，这是由

arr

的单调性保证的

所以可以用两个单调指针去扫描

arr

，维护成立的

pair

个数，根据个数是否等于

来判断可行性

时间复杂度

\mathcal{O}(n)

// cpp11
class Solution {
public:
    vector<int> recoverArray(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (int i = 1; i < n; ++i) {
            int dif = nums[i] - nums[0];  // 可能的 dif
            if (dif == 0 || dif % 2) continue;  // dif 是正偶数
            int l = 0, r = 1;  // 双指针扫描
            vector<int> vis(n);
            while (r < n) {
                while (l < r && vis[l]) l++;  // 跳过重复的元素
                while (r < n && nums[r] != nums[l] + dif) r++;  // 右指针向右拓展
                if (r == n) break;
                // cout << l << ' ' << r << ' ' << dif << endl;
                ans.push_back((nums[r] + nums[l]) / 2);
                vis[r++] = true, vis[l++] = true;
            }
            if (ans.size() != n / 2) ans.clear();
            else break;
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除

机器人

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

机器人

编程算法

登录后参与评论

0 条评论

热度