717. 1比特与2比特字符 / 18. 四数之和 / 22. 括号生成

717. 1比特与2比特字符【简单题】【每日一题】

思路：

1. 从前往后遍历bits数组，如果当前元素是1，那么由于第二种字符无论是10还是11，都是以1开头，所以可以肯定当前元素和它的下一个元素构成第二种字符，直接 i+= 2；bits数组只有0和1，不是1的话那必然是0，而只有第一种字符以0开头，且只占一位，所以此时如果当前元素已经是最后一位了，那么此时最后一位可以构成第一种字符，于是直接返回true，如果不是最后一位，那么i++。
2. 如果可以跳出for循环，说明此时最后一位无法构成字符，于是返回false。

代码：

class Solution {public boolean isOneBitCharacter(int[] bits) {int len = bits.length,i = 0;while (i<len){if (bits[i] == 1){i+=2;}else {if (i == len-1){return true;}else {i++;}}}return false;}
}

用时：

18. 四数之和【中等题】

思路：

1. 与三数之和类似，本题的四数之和先固定第一个数，再固定第二个数，然后双指针表示后两个数，实现思路就是，先排序，数组自左向右依次变大，于是，当前两个数固定之后，后两个数与前两个数这四数之和如果大于target，则右指针左移，如果小于target，则左指针右移，如果等于target，则说明这四个数就是我们要找的四个数，将其添加到ans列表中，同时题目中要求四元组不能相同，因此可以用hashset对其进行去重，做法是，将ans定义为hashset格式，然后返回new
   ArrayList（ans）。
2. 这个题重点不在解题思路，在如何剪枝，按照如上思路写出来的，用时 116ms，击败5%，我一看时间不对啊，这也太长了，我就去看题解，结果发现题解也是这个思路，但是它剪枝了，我就想，那我也去剪剪试试，此时还没看题解代码。
3. 第一次修改，增加了固定第一个数之后，如果前四个数大于target，则直接退出第一层for循环；如果前四个数等于target，则将这四个数添加到答案ans中，并继续下一次第一层for循环；如果第一个数和后三个数之和小于target，则继续下一次第一层for循环。增加了固定第二个数之后，如果前两个数与接下来数组中前两个数之和大于target，则直接退出第二层for循环；如果前两个数与接下来数组中后两个数之和小于target，则继续下一次第二层for循环。修改之后用时
   18ms ，还是没追上题解。
4. 第二次修改，在第一次修改的基础上，增加了在第一层for循环的开始，先判断当i大于0时，当前i位置数与前一个位置数是否相等，如果相等，说明四元组中第一个数重复了，而当后3个数不变的情况下，如果第一个数重复必然会导致整个四元组的重复，因此跳过这个重复的数字，即继续下一次第一层for循环；同理在第二层for循环的开始，先判断当j>i+1时，当前j位置数是否与前一个位置数相等，如果相等，则跳过这个重复的数字，继续下一次第二层for循环。修改之后用时
   5ms ，还是没追上题解。
5. 第三次修改，在第一次和第二次修改的基础上，增加了：对第三个和第四个数的去重，即在while循环中，如果遇到符合题意的四元组，则将其添加到ans中的同时，可以同时使用while循环对left和right位置的数进行去重，如果left位置和left+1位置的数相等，那么left++，如果right位置和right-1位置的数相等，那么right–；同时发现当四个数都进行去重之后，我就不用去hashset对四元组进行去重了，我现在的ans已经没有重复的四元组了，于是将ans修改为ArrayList形式的列表，最后返回ans；另外，在开头添加判断条件，当nums数组的长度小于4时，不可能有符合条件的四元组，此时直接返回空的ans。修改之后用时
   3ms ，还是没有追上题解。
6. 第四次修改，其实第3次修改就是看了题解的代码改的，结果发现还是比它差了1ms，经过我又一次的观察，发现题解添加四个数字进list的方式不一样，
   题解用的是，ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
   而我用的是
   ans.add(new ArrayList(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
   就事实来说，题解的肯定更好一点，是我太菜了我不知道还可以这么写。

代码：
直接放第4版的代码了。

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans = new ArrayList<>();int len = nums.length;if (len<4){return ans;}Arrays.sort(nums);for (int i = 0; i < len-3; i++) {if(i > 0 && nums[i] == nums[i-1]){continue;}long before4_1 = (long) nums[i]+nums[i+1]+nums[i+2]+nums[i+3];if (before4_1 > target){break;}else if (before4_1 == target){ans.add(Arrays.asList(nums[i],nums[i+1],nums[i+2],nums[i+3]));continue;}if ((long)nums[i]+nums[len-1]+nums[len-2]+nums[len-3] < target){continue;}for (int j = i+1; j < len-2; j++) {if(j > i+1 && nums[j] == nums[j-1]){continue;}int left = j+1,right = len-1;long pre = (long) nums[i]+nums[j],before4_2 = pre + nums[left]+nums[left+1];if (before4_2 > target){break;}if (pre +nums[right]+nums[right-1] < target){continue;}while (left<right){int cur = nums[left]+nums[right];if (pre+cur<target){left++;}else if (pre+cur>target){right--;}else {ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;}}}}return ans;}
}

用时：

22. 括号生成【中等题】

思路：

1. 我不知道这算动态规划还是算递归，但感觉跟青蛙跳台阶的题有相似之处。
2. 定义hashset类型ans用来存储去重的答案，初值默认为一对儿括号。从2开始for循环遍历，到n结束（可以取到n），定义一个hashset类型temp来存储括号对数为i时可以生成的括号；遍历ans中的每一个括号组合，设遍历到的括号组合为str，那么依次在str的每一个元素后边插入一对括号（可以在整个str的前方插入括号，也可以在整个str的后方插入括号）；将插入括号的新括号组合存入temp中；当ans中所有的括号组合都被遍历过之后，将ans更新为temp中的所有括号组合，并继续下一次关于
   i 的for循环。
3. 当遍历完n之后，for循环退出，此时将ans转为ArrayList类型列表返回。
4. 主要解题依据是，根据上一个n的括号组合，来求当前n的括号组合。

代码：

class Solution {public List<String> generateParenthesis(int n) {Set<String> ans = new HashSet<>();ans.add("()");for (int i = 2; i <= n; i++) {Set<String> temp = new HashSet<>();for (String str : ans){for (int j = 0; j < str.length(); j++) {temp.add(str.substring(0,j)+"()"+str.substring(j));}}ans = temp;}return new ArrayList<>(ans);}
}

用时：