【刷题笔记】第九天

文章目录

[LCR 189. 设计机械累加器](https://leetcode.cn/problems/qiu-12n-lcof/)
[2007. 从双倍数组中还原原数组](https://leetcode.cn/problems/find-original-array-from-doubled-array/)

LCR 189. 设计机械累加器

c++专属解法：使用sizeof函数

1 + 2 + 3 + … + target = $\frac{(1 + target) target}{2}$

而 $s i zeo f (a) = (1 + t a r g e t) t a r g e t$

class Solution {
public:
    int mechanicalAccumulator(int target) {
        bool a[target][target + 1];
        return sizeof(a) >> 1;
    }
};

2007. 从双倍数组中还原原数组

方法1：哈希表

使用哈希表cnt标记2倍元素的次数

如果当前元素不存在于cnt中，说明不是某元素的2倍，所以应该是original中的元素，并在cnt中标记该元素的2倍 (cnt[changed[i] * 2]++)

如果当前元素存在于cnt中，说明是某元素的2倍，所以不是original中的元素，同时cnt中的次数-- (cnt[changed[i]]--)

如果changed是2倍数组，最后cnt的个数应该为0

class Solution {
    public int[] findOriginalArray(int[] changed) {
        Arrays.sort(changed);
        int n = changed.length;
        if (n == 0 || n % 2 != 0) return new int[0]; // 奇数个不存在original
        int[] ans = new int[n / 2];
        int index = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            if (!cnt.containsKey(changed[i])) {
                // 如果changed[i]不存在于cnt里，说明是original里的元素
                if (index >= n / 2) return new int[0];
                ans[index++] = changed[i];
                cnt.put(changed[i] * 2, cnt.getOrDefault(changed[i] * 2, 0) + 1); // 标记元素和个数
            } else {
                // 如果遇到标记的元素，说明不是original里的元素，同时个数--
                int tmp = cnt.get(changed[i]);
                if (tmp == 1) {
                    cnt.remove(changed[i]);
                } else {
                    cnt.put(changed[i], tmp - 1);
                }
            }
        }
        // 如果change 是双倍数组的话，cnt的元素应该为0
        return ans;

    }
}

方法2：队列

对方法1优化，由于哈希表的元素是按顺序从小到大插入的，所以用队列来替代哈希表

队列还是只放某元素的2倍，所以如果changed是2倍数组，最终队列应该是空。

如果队列为空，存入结果数组;

如果队列不为空：

队首元素等于当前元素，说明该元素是某元素的2倍，两两配对成功，弹出队列

队首元素小于当前元素，由于数组是从小到大排列的，后面的元素肯定也比队首元素大，因此不存在与队首元素配对的元素，所以直接返回空

队首元素大于当前元素，该元素存入结果数组，同时元素 * 2队列。

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n == 0 || n % 2 != 0) return new int[0];
        Arrays.sort(changed);
        
        Queue<Integer> q = new LinkedList<>();
        int[] ans = new int[n / 2];
        int index = 0;
        for (int i = 0; i < changed.length; ++i) {
            if (q.isEmpty()) {
                if (index >= n / 2) {
                    return new int[0];
                }
                ans[index++] = changed[i];
                q.add(changed[i] * 2);
            } else {
                if (q.peek() == changed[i]) {
                    // 配对成功
                    q.poll();
                } else if (q.peek() < changed[i]) {
                    // i后面的元素只会比q.peek()大，因为q.peek()配对失败
                    return new int[0];
                } else {
                    if (index >= n / 2) {
                        return new int[0];
                    }
                    ans[index++] = changed[i];
                    q.add(changed[i] * 2);
                }
            }
        }
        return ans;

    }
}