重拾刷题路01

2022-02-13

78.Subsets（Medium）

https://leetcode.com/problems/subsets/

给出不含重复数字的数组，返回所有不含重复元素的子集。

（1）级联（通过增加一个数字，生成新的集合）

class Solution {
    public List> subsets(int[] nums) {
        List> result = new ArrayList<>();
        result.add(new ArrayList<>());
        
        for (int num : nums) {
            List> subList =  new ArrayList<>();
            for (List list : result) {
                List newList = new ArrayList<>();
                newList.addAll(list); // 复制现有结果
                newList.add(num); // 把新的数字加进去
                subList.add(newList);
            }
            result.addAll(subList); // 把本次加完数字产生的集合加到结果中
        }
        
        return result;
    }
}

 （2）递归回溯法

使用回溯法，和人的解题思路类似，先固定第一个数字，然后选第二个数字，以此类推。

class Solution {
    public List> subsets(int[] nums) {
        List> result = new ArrayList<>();
        for (int size = 0; size <= nums.length; size++) {
            recursive(0, size, new ArrayList<>(), nums, result);
        }
        return result;
    }
    
    public void recursive(int startPos, int resSize, List list, int[] nums, List> result) {
        if (list.size() == resSize) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int pos = startPos; pos < nums.length; pos++) {
            list.add(nums[pos]);
            recursive(pos + 1, resSize, list, nums, result);
            list.remove(list.size() - 1);
        }
    }
}

 67.Add Binary（Easy）

https://leetcode.com/problems/add-binary/

注意补零，由于StringBuilder只能补在最后，所以要先reverse，再补零，再reverse回来。

注意进位的逻辑。

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int lengthA = a.length();
        int lengthB = b.length();
        int length = 0;
        // 把短的字符串前面补0
        if (lengthA > lengthB) {
            length = lengthA;
            StringBuilder sb = new StringBuilder(b).reverse();
            for (int i = 1; i <= (lengthA - lengthB); i++) {
                sb.append('0');
            }
            b = sb.reverse().toString();
        } else if (lengthB > lengthA) {
            length = lengthB;
            StringBuilder sb = new StringBuilder(a).reverse();
            for (int i = 1; i <= (lengthB - lengthA); i++) {
                sb.append('0');
            }
            a = sb.reverse().toString();
        } else {
            length = lengthA;
        }
        // 是否要进位
        boolean plus = false;
        for (int pos = length - 1; pos >= 0; pos--) {
            char charA = a.charAt(pos);
            char charB = b.charAt(pos);
            char charResult;
            if (charA == '0' && charB == '0') {
                charResult = plus ? '1' : '0';
                plus = false;
            } else if (charA == '1' && charB == '1') {
                charResult = plus ? '1' : '0';
                plus = true;
            } else {
                charResult = plus ? '0' : '1';
            }
            result.append(charResult);
            if (pos == 0 && plus) { // 最后还有进位需要加一位
                result.append('1');
            }
        }
        return result.reverse().toString();
    }
}

228. Summary Ranges（Easy）

https://leetcode.com/problems/summary-ranges/

fast和slow两个指针即可。这里用了两个while循环，但是实际的时间复杂度还是O(n)。

class Solution {
    public List summaryRanges(int[] nums) {
        List result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        int slow = 0;
        int fast = 0;
        while (slow < nums.length && fast < nums.length) {
            String str = String.valueOf(nums[slow]);
            while (fast < nums.length - 1 && nums[fast + 1] == nums[fast] + 1) {
                fast++;                
            }
            if (fast != slow) {
                str = str + "->" + nums[fast];
            }
            slow = fast + 1;
            fast = slow;
            result.add(str);
        }
        return result;
    }
}