[LeetCode-周赛]273

Rank : 301/4367
Solved : 4/4

竞赛链接

反转两次的数字

思路

模拟题意. cpp可以使用to_string和stoi函数方便的进行字符串和int之间的转换.

Code

class Solution {
public:
    bool isSameAfterReversals(int num) {
        string nums = to_string(num);
        reverse(nums.begin(), nums.end());
        int r1 = stoi(nums);
        string r2 = to_string(r1);
        reverse(r2.begin(), r2.end());
        if (num == stoi(r2))
            return true;
        return false;
    }
};

复杂度分析

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

---

执行所有后缀指令

思路

由于数据范围很小, 因此直接按照题意模拟.

Code

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

复杂度分析

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

---

相同元素的间隔之和

思路

首先可以将问题一分为二: 分别统计左边和右边, 最后两者相加即可.
以左边为例. 我们可以使用前缀和的思想完成统计. 具体思路为:

• 记left[i]为nums[i]左边与其的间隔之和. cnt[nums[i]]为i极其左边与nums[i]值相等的个数.
• 若当前枚举到下标i, 其值为nums[i], 若其左边最后一个与其值相同的下标为j, 则有:
  $$sum[i] = sum[j] + cnt[nums[i]] * (i - j) $$
• 上式表示所有所有与nums[i]相同的下标, 先考虑其到j处的距离距离之和(由sum的定义可知为sum[j]); 然后再统计j到i处的距离之和, 其为(i - j) * cnt[nums[i]]. 主要思想是利用历史信息, 分两步部分统计(先到j, 再到i), 其中使用前缀和进行优化.

最后将left和right相加即可.

Code

using LL = long long;
class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        int n = arr.size();
        vector<LL> sum(n + 1, 0L);
        unordered_map<int, int> mp;  // 记录每个数最后一次出现的位置
        unordered_map<int, int> cnt;
        // Left
        for (int i = 1; i <= n; i ++ ) {
            int cur = arr[i - 1];
            if (mp.count(cur) == 0) {
                mp[cur] = i;
                cnt[cur] ++ ;
                continue;                
            }
            int idx = mp[cur], num = cnt[cur];
            sum[i] = sum[idx] + 1ll * num * (i - idx);
            mp[cur] = i;
            cnt[cur] ++ ;
        }
        // Right
        mp.clear();
        cnt.clear();
        vector<LL> ans(n, 0L);
        // 先把左边的加到答案里, 然后算右边的
        for (int i = 0; i < n; i ++ )
            ans[i] += sum[i + 1];
        sum = vector<LL>(n + 1, 0L);
        for (int i = n; i >= 1; i -- ) {
            int cur = arr[i - 1];
            if (mp.count(cur) == 0) {
                mp[cur] = i;
                cnt[cur] ++ ;
                continue;                
            }
            int idx = mp[cur], num = cnt[cur];
            sum[i] = sum[idx] + 1ll * num * (idx - i);
            mp[cur] = i;
            cnt[cur] ++ ;
        }
        for (int i = 0; i < n; i ++ )
            ans[i] += sum[i + 1];
        return ans;
    }
};

复杂度分析

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

---

还原原数组

思路

首先观察数据范围可知, 可以使用$O(N^2)$的算法解决.
由于将原数组左右k和右移k后, 对应位置的数差值固定为2k.
因此如果我们知道k的具体值的话, 问题就转化成: 给定k值的情况下, 判断数组能否还原出原数组.

• 判断可以从贪心的小到大考虑: 若考虑到x了, 则将x放入lower数组, 将x + 2k放入higher数组, 若无x + 2k则失败。使用map或者multiset判断的时间复杂度为$O(NlogN)$
• 对于k值, 可以考虑枚举所有可能的k值. 由于数组的最大值必定为higher的最大值, 最小值必定为lower的最小值. 因此可以枚举higher的最小值或者lower的最大值, 从而计算出k. 时间复杂度$O(N)$.

最后算法整体时间复杂度为$O(N^2logN)$.

Code

class Solution {
public:
    vector<int> recoverArray(vector<int>& nums) {
        int n = nums.size();
        n /= 2;
        // Max -> higher, Min -> lower
        int HMx = *max_element(nums.begin(), nums.end());
        int LMn = *min_element(nums.begin(), nums.end());
        
        if (n == 1)
            return {LMn + (HMx - LMn) / 2};
        
        set<int> st(nums.begin(), nums.end());
        
        map<int, int> cnt;
        for (auto& num : nums)
            cnt[num] ++ ;

        // 从大到小枚举LMx, 计算k
        for (auto it = st.rbegin(); it != st.rend(); it ++ ) {
            int LMx = *it;
            if (LMx == HMx)
                continue;
            int d = HMx - LMx;
            if (d % 2 or cnt[HMx] > cnt[LMx])
                continue;
            int k = d / 2;
            bool flag = true;
            // lower
            map<int, int> exist;
            // map<int, int> cur = cnt;
            for (auto& [_k, _v] : cnt) {
                if (_v == 0)
                    continue;
                if (cnt.count(_k + 2 * k) == 0 or cnt[_k + 2 * k] < _v) {
                    flag = false;
                    break;  
                } else {
                    cnt[_k + 2 * k] -= _v;
                    exist[_k] = _v;                     
                }
            }
            // 复原全局的cnt
            for (auto& [_k, _v] : exist)
                cnt[_k + 2 * k] += _v;
            
            if (flag) {
                // cout << "find " << k << ' ' <<  HMx << ' ' << LMx << endl;
                vector<int> ans;
                // lower
                exist[LMn] = cnt[LMn];
                for (auto& [l, time] : exist)
                    ans.insert(ans.end(), time, l + k);
                return ans;
            }
        }
        return {};
    }
};

• 实现的过程中使用exist来存储lower数组, 如果没有找到答案, 则将exist的内容复原到原来的mapcnt中, 这样可以减少cnt的重复拷贝, 将运行时间从超时边缘(1972ms)优化成28ms.

复杂度分析

• 时间复杂度$O(N^2logN)$
• 空间复杂度$O(N^2)$

---

欢迎讨论指正