面试编程题 set

面试编程题 set

Posted by julyerr on February 13, 2018

Contains-Duplicate-III

解题思路
nums[i]和nums[j]之间的差距最大为t,i和j最大差距为k;通过维持最小和最大差距为2t的集合,必要时将下标差距大于k的元素移除,具体参见实现代码
实现代码

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//        check validation
    if (nums == null || nums.length < 2 || k < 1 || t < 0) {
        return false;
    }
    SortedSet<Long> set = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
//            截取一定范围内的subSet,左闭右开
        SortedSet<Long> subSet = set.subSet((long) nums[i] - t, (long) nums[i] + t + 1);
        if (!subSet.isEmpty()) {
            return true;
        }
//            下一次迭代的时候需要移除的元素
        if (i >= k) {
            set.remove((long) nums[i - k]);
        }
        set.add((long) nums[i]);
    }
    return false;
}

Subsets

解题思路
集合的幂次数判断,具体参见实现代码。
实现代码

public List<List<Integer>> subsets(int[] nums) {
    //        check validation
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }

    Set<List<Integer>> rt = new HashSet<>();

    int length = nums.length;
    Arrays.sort(nums);
    for (int i = 0; i < Math.pow(2, length); i++) {
        int tmp = i;
        List<Integer> list = new ArrayList<>();

        for (int j = 0; j < length; j++) {
            int bit = tmp & 0x01;
            tmp = tmp >> 1;
            if (bit == 1) {
                list.add(nums[j]);
            }
        }
        rt.add(list);
    }
    return new ArrayList<>(rt);
}

参考资料