Leetcode第273场周赛总结

反转两次的数字

https://leetcode-cn.com/problems/a-number-after-a-double-reversal/

题目描述

反转一个整数意味着倒置它的所有位。
例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零。
给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。如果 reversed2 等于 num ，返回 true ；否则，返回 false 。
示例 1：
输入：num = 526
输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。
示例 2：
输入：num = 1800
输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。
示例 3：
输入：num = 0
输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。
$提示：0 <= num <= 10^6$

My Original Solution

class Solution {
public:
    void Reverse(string& s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
        int index = 0;
        while (s[index] == '0') {
            s.erase(s.begin());
        }
    }
    bool isSameAfterReversals(int num) {
        if (num < 0) num = (-1)*num;
        if (num == 0) return true;
        string s_0, s;
        s_0 = s = to_string(num);
        Reverse(s);
        Reverse(s);
        if (s_0 == s)
            return true;
        else 
            return false;
    }
};

评价：将num转成字符串来做没有必要。

Elegant Solution

class Solution {
public:
    bool isSameAfterReversals(int num) {
        if (num == 0) return true;
        if (num % 10 == 0) return false;
        return true;
    }
};

执行所有后缀命令

https://leetcode-cn.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/

题目描述

现有一个 n x n 大小的网格，左上角单元格坐标 (0, 0) ，右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos ，其中 startPos = [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。

另给你一个长度为 m 、下标从 0 开始的字符串 s ，其中 s[i] 是对机器人的第 i 条指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。

机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满足下述条件之一时，机器人将会停止：

下一条指令将会导致机器人移动到网格外。
没有指令可以执行。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是机器人从第 i 条指令开始，可以执行的指令数目。

My Original Solution

class Solution {
private:
    bool MoveLeft(int n, vector<int>& startPos) {
        startPos[1]--;
        if (startPos[1] < 0)
            return false;
        else 
            return true;
    }
    bool MoveRight(int n, vector<int>& startPos) {
        startPos[1]++;
        if (startPos[1] > n - 1)
            return false;
        else
            return true;
    }
    bool MoveUp(int n, vector<int>& startPos) {
        startPos[0]--;
        if (startPos[0] < 0)
            return false;
        else 
            return true;
    }
    bool MoveDown(int n, vector<int>& startPos) {
        startPos[0]++;
        if (startPos[0] > n - 1)
            return false;
        else
            return true;
    }
public:
    vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
        int num = s.size();
        vector<int> answer(num, 0);
        if (startPos[0] < 0 || startPos[0] > n - 1 || startPos[1] < 0 || startPos[1] > n - 1)
            return answer;
        vector<int> startPosTemp = startPos;
        for (int i = 0; i < num; i++) { // 每次计算answer[i]的结果
            int flag = false;
            startPos = startPosTemp;
            for (int j = i; j < num; j++) {
                char instructor = s[j];
                switch(instructor) {
                    case 'L':
                        if (!MoveLeft(n, startPos))
                            flag = true;
                        else
                            answer[i]++;
                        break;
                    case 'R':
                        if (!MoveRight(n, startPos))
                            flag = true;
                        else
                            answer[i]++;
                        break;
                    case 'U':
                        if (!MoveUp(n, startPos))
                            flag = true;
                        else
                            answer[i]++;
                        break;
                    case 'D':
                        if (!MoveDown(n, startPos))
                            flag = true;
                        else
                            answer[i]++;
                        break;
                    default:
                        break;
                }
                if (flag)
                    break;
            }     
        }
        return answer;
    }
};

评价：太冗长了！

Elegant Solution

class Solution {
public:
    vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
        int m = s.size();
        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            int x = startPos[0], y = startPos[1];
            int cnt = m - i;
            for (int j = i; j < m; ++j) {
                char ch = s[j];
                if (ch == 'L') {
                    --y;
                }
                else if (ch == 'R') {
                    ++y;
                }
                else if (ch == 'U') {
                    --x;
                }
                else {
                    ++x;
                }
                if (x < 0 || x >= n || y < 0 || y >= n) {
                    cnt = j - i;
                    break;
                }
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

相同元素的间隔之和

https://leetcode-cn.com/problems/intervals-between-identical-elements/

题目描述

给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。

arr 中两个元素的间隔定义为它们下标之间的绝对差。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。

返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与 arr[i] 的值相同）的间隔之和。

注意：|x| 是 x 的绝对值。

示例 1：
输入：arr = [2,1,3,1,2,3,3]
输出：[4,2,7,2,4,4,5]
解释：

下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4
下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2
下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7
下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2
下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4
下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4
下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5

示例 2：
输入：arr = [10,5,10,10]
输出：[5,0,3,4]
解释：

下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5
下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0
下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3
下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4

提示：

n == arr.length
1 <= n <= 105
1 <= arr[i] <= 105

题解

class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        unordered_map<int, pair<int, int>> hash;
        int n = arr.size();

        // 前缀
        vector<long long> res1(n, 0);
        for (int i = 0; i < n; i++) {
            auto iter = &hash[arr[i]];
            if (iter->second != 0) {
                res1[i] = res1[iter->first] + (i - iter->first) * iter->second;
            }
            iter->first = i;
            iter->second++;
        }

        hash.clear();

        // 后缀
        vector<long long> res2(n, 0);
        for (int i = n - 1; i >= 0; i--) {
            auto iter = &hash[arr[i]];
            if (iter->second != 0) {
                res2[i] = res2[iter->first] + (iter->first - i) * iter->second;
            }
            iter->first = i;
            iter->second++;
        }
        vector<long long> res(n, 0);
        for (int i = 0; i < n; i++) res[i] = res1[i] + res2[i];
        return res;
    }
};

直接使用哈希会超时。因此，要在此处使用前缀和。核心公式为res1[i] = res1[pre] + (i - pre) * 个数其中res1数组为前缀和数组。要理解该公式画个图就OK了。

还原原数组

https://leetcode-cn.com/problems/recover-the-original-array/

题目描述

Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：

对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
给你一个由 2n 个整数组成的整数数组 nums ，其中恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回原数组 arr 。如果出现答案不唯一的情况，返回任一有效数组。

注意：生成的测试用例保证存在至少一个有效数组 arr 。

示例 1：
输入：nums = [2,10,6,4,8,12]
输出：[3,7,11]
解释：
如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。
示例 2：
输入：nums = [1,1,3,3]
输出：[2,2]
解释：
如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。
示例 3：
输入：nums = [5,435]
输出：[220]
解释：
唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。

提示：

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 109
生成的测试用例保证存在至少一个有效数组 arr

题解

class Solution{
public:
    vector<int> recoverArray(vector<int>& nums) {
        int n = nums.size() / 2;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < 2 * n; i++) {
            for (int j = i + 1; j < 2 * n; j++) {
                if (nums[j] > nums[i] && ((nums[j] - nums[i]) % 2 == 0)) {
                    int k = (nums[j] - nums[i]) / 2;
                    vector<int> v(2 * n), ans; // v数组用来标记是否访问过

                    for (int x = 0, y = 0; x < 2 * n; x++) {
                        if (!v[x]) {
                            while (y < 2 * n && (v[y] || nums[y] != nums[x] + 2 * k)) y++;
                            if (y == 2 * n) break;
                            v[y] = 1;
                            y += 1;
                            ans.push_back(nums[x] + k);
                        }
                    }
                    if (ans.size() == n) return ans;
                }
            }
        }
        return {};
    }
};

暴力+双指针

Leetcode第273场周赛总结