Java List 拆解 - l00jj/algorithm GitHub Wiki

拆解 List

通过拆解 List 提速不一定需要完全拆解。 如 15. 三数之和 中，方法快慢并重要，方法 30ms 和 9ms 的解法都可以通过一重拆解达到 0ms 的目的；

所以重点在于尝试把计算环节放入size()中，在 2901. 最长相邻不相等子序列 II - 第 115 场双周赛 这题甚至只能放在 size() ，如果外置计算过程只能 $12ms$ ，置于 size() 能加速至 $0ms$；

单层拆解

import java.util.AbstractList;

class Solution {
    List<List<Integer>> _ans = null;
    public List<List<Integer>> threeSum(int[] nums) {
        
        return new AbstractList<List<Integer>>(){
            
            public List<Integer> get(int index){
                return _ans.get(index);
            }

            public int size(){
                init(); 
                return _ans.size();
            }
            
            private void init(){
                if(_ans != null) return;

                final int n = nums.length;
                _ans = new ArrayList<List<Integer>>();

                int max = nums[0], min = nums[0];
                for (int num : nums) {
                    if (max < num) max = num;
                    if (min > num) min = num;
                }
                int[] map = new int[max - min + 1];
                int length = 0;
                for (int num : nums) {
                    if (map[num-min]++ == 0) length++;
                }
                int[] list = new int[length];
                int tail = 0;
                for (int i = 0; i < map.length; i++) {
                    if (map[i] == 0) continue;
                    list[tail++] = i + min;
                }

                if (min > 0 || max < 0) return;

                if (min <= 0 && map[-min] >= 3) {
                    List<Integer> res = new ArrayList(3);
                    res.add(0);
                    res.add(0);
                    res.add(0);
                    _ans.add(res);
                }

                
                for (int i = 0; i < length; i++) {
                    int num = list[i];
                    if (num >= 0) break;
                    if (map[num - min] > 1) {
                        int diff = -(num * 2);
                        if (diff - min < map.length) {
                            if (map[diff - min] > 0) {
                                List<Integer> res = new ArrayList(3);
                                res.add(num);
                                res.add(num);
                                res.add(diff);
                                _ans.add(res);
                            }
                        }
                    }

                    for (int j = i + 1; j < length; j++) {
                        int diff = -(num + list[j]);
                        if (diff - min >= map.length) continue;
                        if (diff < list[j]) break;
                        
                        if (diff == list[j]) {
                            if (map[diff - min] > 1) {
                                List<Integer> res = new ArrayList(3);
                                res.add(num);
                                res.add(list[j]);
                                res.add(diff);
                                _ans.add(res);
                            }
                        } else {
                            if (map[diff - min] > 0) {
                                List<Integer> res = new ArrayList(3);
                                res.add(num);
                                res.add(list[j]);
                                res.add(diff);
                                _ans.add(res);
                            }
                        }
                    }
                }
            
            }
        };
    }
}

完全拆解

class Solution extends java.util.AbstractList<List<Integer>> {

    private static final AnsElement ANS_ELEMENT = new AnsElement();
    private static final int[] EMPTY_TMPL = new int[1000];
    private static final int[] CONTAINER = new int[1001];
    private static int size;

    private int[][] items1, items2;
    private int pos = 1;

    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        if (items1.length > items2.length) {
            this.items1 = items1;
            this.items2 = items2;
        } else {
            this.items1 = items2;
            this.items2 = items1;
        }
        return this;
    }

    @Override
    public List<Integer> get(int index) {
        while (CONTAINER[pos] == 0) {
            ++pos;
        }
        ANS_ELEMENT.value = pos;
        ANS_ELEMENT.weight = CONTAINER[pos];
        CONTAINER[pos] = 0;
        return ANS_ELEMENT;
    }

    @Override
    public int size() {
        if (items2 != null) {
            if (size != 0) {
                // 不是第一次调用，清空容器
                System.arraycopy(EMPTY_TMPL, 0, CONTAINER, 0, size);
            }
            size = items1.length;
            for (int[] item : items1) {
                CONTAINER[item[0]] = item[1];
            }
            items1 = null;
            for (int[] item : items2) {
                if (CONTAINER[item[0]] == 0) {
                    // 初次记录
                    ++size;
                    CONTAINER[item[0]] = item[1];
                } else {
                    // 再次记录
                    CONTAINER[item[0]] += item[1];
                }
            }
            items2 = null;
        }
        return size;
    }

    /** 答案元素 */
    private static class AnsElement extends java.util.AbstractList<Integer> {

        private int value, weight;

        @Override
        public Integer get(int index) {
            return index == 0 ? value : weight;
        }

        @Override
        public int size() {
            return 2;
        }
    }
}

3213

⚠️ **GitHub.com Fallback** ⚠️