重拾刷题路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; }}