leetCode进阶算法题+解析（十一）
公司最新消息，2月10-21在家办公，哎，还是学习吧。学习使我快乐~~
组合
题目：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
思路：乍一看就又是回溯。不知道是力扣上题目分堆了还是咋的，怎么最近做的都是回溯的题目呢。反正这个题的思路就是回溯。没啥可多说的，我直接去实现了。
好了，用回溯实现了，运行没问题，性能不可说。我先直接贴代码：
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<List<Integer>>();
int[] nums = new int[n];
for(int i = 0;i<n;i++){
nums[i] = i+1;
}
back(new ArrayList<Integer>(),nums,0,k);
return res;
}
public void back(List<Integer> list,int[] nums,int start,int k){
if(list.size()==k){
res.add(new ArrayList<Integer>(list));
}else{
for(int i = start;i<nums.length;i++){
list.add(nums[i]);
back(list,nums,i+1,k);
list.remove(list.size()-1);
}
}
}
}
我觉得可能是我这个数组有问题？不用数组能不能好点？我去试试。
事实证明数组换了也依然性能不行，但是既然改版了还是要贴一次代码的。
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<List<Integer>>();
back(new ArrayList<Integer>(),n,1,k);
return res;
}
public void back(List<Integer> list,int n,int start,int k){
if(list.size()==k){
res.add(new ArrayList<Integer>(list));
}else{
for(int i = start;i<=n;i++){
list.add(i);
back(list,n,i+1,k);
list.remove(list.size()-1);
}
}
}
}
我直接去看看性能第一的代码吧。我也很懵，感觉代码差不多，但是人家2ms。而我二十多ms。。。先贴上来吧：
class Solution {
private static List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<List<Integer>>();
if (n < 1 || n < k || k < 1) {
return res;
}
List<Integer> selectNum = new ArrayList<Integer>();
dfs(1, n, k, selectNum);
return res;
}
public static void dfs(int min, int max, int k, List<Integer> selectNum) {
if(0 == k) {
res.add(new ArrayList<Integer>(selectNum));
return;
}
for(int i = min; i <= max - k + 1; i++) {
selectNum.add(i);
dfs(i + 1, max, k - 1,selectNum);
selectNum.remove(selectNum.size() - 1);
}
}
}
然后这道题就这样吧。下一题了。
子集
题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路：这个题乍一看我以为是回溯问题，但是现在发现别的方法也能实现。。。我还是按照我的思路先做一遍再说。
好了，第一版本出来了，如果用回溯就条理很清晰。回溯三部曲：添加，递归，返回上一步。然后之前的回溯是到某点（比如list长度多少然后添加到结果集），但是这个的条件是要变一下的，就是每当list有变化就都要添加到结果集种，说了这么多我直接贴代码:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
不过这个题目我刚刚就说了，应该不用回溯也能完成的。类似于双层for循环？反正是可以解决的，我去考虑好了用常规解法实现。
咳咳，遇到点小挫折。就是我想得太简单了，不过现在好了，是看了一句评论的话豁然开朗做出来的，
逐个枚举，空集的幂集只有空集，每增加一个元素，让之前幂集中的每个集合，追加这个元素，就是新增的子集。
我先贴代码;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<Integer>());
for(int i = 0;i<nums.length;i++){
int len = res.size();
for(int j = 0;j<len;j++){
List<Integer> list = new ArrayList<Integer>(res.get(j));
list.add(nums[i]);
res.add(list);
}
}
return res;
}
}
单词搜索
题目：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
思路：这个题我第一思路就是标记。首先找到第一个字母，然后上下左右找第二个字母。找到了作为一个分支开始继续，因为每个单词只能用一次，所以选择过的单词还要标记已用。最后如果能找到整个单词返回true。找不到返回false。暂时就是这个思路，但是具体怎么实现还是要慢慢琢磨的。对了，每一个选点都可是用回溯实现，不行就退回上一步。我去代码实现了。
我用最笨的办法勉强实现了，但是超出时间限制了，87个测试案例，我过了85个。所以这个题只能说思路是对的，但是肯定还要做一些额外的限制或者优化啥的。我去好好想想这个题要怎么实现。
看了下解析，发现我真的是对了百分之九十，就剩下的百分之十是代码不够精简优雅，我决定还是把我自己的代码贴出来分享下（一方面也是我不断调整的，另一方面很直观）
class Solution {
boolean flag;
public boolean exist(char[][] board, String word) {
if(board.length*board[0].length<word.length()) return false;
for(int i = 0 ;i < board.length;i++){
for(int j = 0; j< board[0].length;j++){
if(board[i][j] == word.charAt(0)){
char temp = board[i][j];
board[i][j] = '0';
back(board,word,1,i,j);
board[i][j] = temp;
}
}
}
return flag;
}
public void back(char[][] board, String word,int start,int r,int l){
if(start == word.length()) {
flag = true;
return;
}else{
if(r>0 && board[r-1][l] == word.charAt(start)){
char temp = board[r-1][l];
board[r-1][l] = '0';
back(board,word,start+1,r-1,l);
board[r-1][l] = temp;
}
if(r<board.length-1 && board[r+1][l] == word.charAt(start)){
char temp = board[r+1][l];
board[r+1][l] = '0';
back(board,word,start+1,r+1,l);
board[r+1][l] = temp;
}
if(l>0 && board[r][l-1] == word.charAt(start)){
char temp = board[r][l-1];
board[r][l-1] = '0';
back(board,word,start+1,r,l-1);
board[r][l-1] = temp;
}
if(l<board[0].length-1 && board[r][l+1] == word.charAt(start)){
char temp = board[r][l+1];
board[r][l+1] = '0';
back(board,word,start+1,r,l+1);
board[r][l+1] = temp;
}
}
}
}
然后优化版本的：
class Solution {
public boolean exist(char[][] board, String word) {
if(board.length*board[0].length<word.length()) return false;
for(int i = 0 ;i < board.length;i++){
for(int j = 0; j< board[0].length;j++){
if(back(board,word,0,i,j)) return true;
}
}
return false;
}
public boolean back(char[][] board, String word,int k,int i,int j){
if(k >= word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) return false;
board[i][j] += 100;
boolean result = back(board, word, k + 1, i - 1, j) || back(board, word, k + 1, i + 1, j)
|| back(board, word, k + 1, i, j - 1) || back(board, word, k + 1, i, j + 1);
board[i][j] -= 100;
return result;
}
}
首先一个优化点，我这想差了，是保留原值，然后赋值，回溯，然后恢复值。其实这块人家的处理直接加减值更好。然后还有就是我是先去确定当前值，然后再去四周找下一个值。而人家是直接判断这个值是不是需要的。反正我是觉得思路是一样的，然后这个题就这样吧，直接下一题。
删除排序数组的重复项2
题目：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路：敲黑板划重点！题目的主要两点：1.原地删除。2.不使用额外空间。这个题其实我做过。好像这个删除排序数组的重复项1的进阶条件就是这个。我当时好像直接按照进阶要求自己的，哈哈。就是双指针，一个是当前元素摆放，一个是判断是否是重复元素。说起来不太好说，我直接写代码一看就明白了。
回来了，这个题简单的出奇，就是一个思路的问题。我直接上代码:
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
for(int n : nums){
if(i<2 || n>nums[i-2]){
nums[i] = n;
i++;
}
}
return i;
}
}
我这里i是当前摆放元素。然后遍历的n是用来判断是否是相同元素重复两次以上。这里因为已经是排序的了，所以只要不大于就是重复元素。
反正这道题就这样了，我直接下一题。
搜索旋转排序数组2
题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
思路：这个题感觉和旋转排序数组1是一样的，我记得当时还有要求时间复杂度要多少。这个题可能是懒得写了。我记得是一个二分法，但是区别是要判断当前点是前半段的还是后半段的，反正挺麻烦但是不难。这个题是可以有重复元素，我但是我感觉重复元素应该也不影响啊，不知道是不是我没想到，我去尝试写着代码试试。
回来了，找到这个题的坑点了。 0 1 0 0 0 0 0 . target = 1用二分法无法解决。所以这个题就是单纯的遍历？？？
反正我没别的好办法了。是我想的太少了，浪费n多时间，简直日狗了。这个题刷的我心态炸了。
直接上最无脑的代码:
class Solution {
public boolean search(int[] nums, int target) {
for(int i:nums){
if(target = i) return true;
}
return false;
}
}
我顺便附上官方题解的代码,简直就是自己骗自己：
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[start] == nums[mid]) {
start++;
continue;
}
//前半部分有序
if (nums[start] < nums[mid]) {
//target在前半部分
if (nums[mid] > target && nums[start] <= target) {
end = mid - 1;
} else { //否则，去后半部分找
start = mid + 1;
}
} else {
//后半部分有序
//target在后半部分
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else { //否则，去后半部分找
end = mid - 1;
}
}
}
//一直没找到，返回false
return false;
}
今天的笔记就记到这里，如果稍微帮到你了记得点喜欢和关注。也祝大家工作顺顺利利！（然而我还没工作，还在家里蹲，哎）
