感谢你一路上的陪伴

1
class Solution {
2
public:
3
    int minMirrorPairDistance(vector<int>& nums) {
4
        unordered_map<int, vector<int>> mp; //这里放一个哈希表，用来存相同数值下的角标
5
        for(int i=1;i<nums.size();i++) {
6
            mp[nums[i]].push_back(i); //先把j放进去
7
        }
8
        int min = INT_MAX/2;
9
        for (int i=0;i<nums.size()-1;i++) {
10
            int temp = reverse(nums[i]); //再去找反转的i
11
            if (mp.contains(temp)) {
12
                for (auto j:mp[temp]) {
13
                    if (i<j&&j-i<min) { //匹配以后因为题中i<j,所以去做了个匹配
14
                        min = j-i;
15
                        if (min==1)return 1; //这里还笨拙的做了一个优化，即已经找到最优解了就不用往下找了
16
                    }
17
                }
18
            }
19
        }
20
        if (min == INT_MAX/2) return -1;
21
        return min;
22
    }
23
    int reverse(int x) { //反转的代码，非常朴实无华
24
        int rev = 0;
25
        while (x != 0) {
26
            rev = rev * 10 + (x % 10);
27
            x /= 10;
28
        }
29
        return rev;
30
    }
31
};

1
class Solution {
2
public:
3
    int minMirrorPairDistance(vector<int>& nums) {
4
        unordered_map<int, int> last_index; //同样创建一个哈希表，但是不需要是数组了，目的只保留当前最靠右侧的反转值
5
        int n = nums.size(), ans = n;
6

7
        for (int j = 0; j < n; j++) { //向右枚举数组里的值
8
            int x = nums[j];
9
            auto it = last_index.find(x); //去找一下哈希表里面是否存在相同值
10
            if (it != last_index.end()) {
11
                ans = min(ans, j - it->second); //有就看一下是否需要更新最小值
12
            }
13

14
            // 计算 reverse(x)，不用字符串
15
            int rev = 0;
16
            for (; x > 0; x /= 10) {
17
                rev = rev * 10 + x % 10;
18
            }
19
            last_index[rev] = j; //然后强制替换当前哈希表对应值保留的角标，因为如果之前有更小的就已经记录了ans
20
        }
21

22
        return ans < n ? ans : -1; //返回
23
    }
24
};
25

26
//作者：灵茶山艾府
27
//链接：https://leetcode.cn/problems/minimum-absolute-distance-between-mirror-pairs/solutions/3845358/mei-ju-you-wei-hu-zuo-pythonjavacgo-by-e-wlzl/
28
//来源：力扣（LeetCode）
29
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。