1. 首页
  2. 文章中心
  3. 算法

Leetcode每日一刷的题目Leetcode刷题记录（主要用于自我记录）

81 阅读 0 评论
我是靠谱客的博主 幸福毛衣，这篇文章主要介绍Leetcode每日一刷的题目Leetcode刷题记录（主要用于自我记录），现在分享给大家，希望可以做个参考。

Leetcode刷题记录（主要用于自我记录）

前言

本人是计算机专业学渣一枚，因前面算法课上课神游太虚，因此现在亡羊补牢，本文主要是本人对于学习过程的记录，说的不对的地方欢迎指正。

Leetcode 77题–组合

说说做题时的想法吧，刚开始做这道题的时候第一时间想到的是用递归来解，因为是个求全解的问题，感觉用递归做要方便很多，但是卡在了如何进行递归这一步。当时有想到维护一个临时变量，通过递归来进行处理，但是因为没有考虑到回溯这一点，导致这个想法不了了之，后面又考虑过维护多个临时变量，当然也是不行。

想解这道题建议了解下回溯算法和深搜。

这里面最关键的地方在于回溯这个过程，也就是当你完成了某个节点的递归之后，应当回到这个节点的父节点，重新选择下一个子节点再进行递归。能想到这个这道题就很简单了。

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        add(1,n,k);
        return result;
    }

    public void add(int start,int n, int k){
        if(temp.size() + n-start+1 < k)
            return;
        if(temp.size() == k){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        temp.add(start);
        add(start+1,n,k);
        temp.remove(Integer.valueOf(start));
        add(start+1,n,k);
    }
}

add的第一个if主要是为了优化，大量减少遍历次数。

上面的代码中的
result.add(new ArrayList(temp));
一行是比较容易出错的，如果没有拷贝temp，而是直接add的话，因为整个递归结束之后，temp是空的，而result里面存的都是temp的引用，返回的结果就会全是空的。

9.8完成该题
9.9review

Leetcode 39题–组合总和

好像leetcode连续一段时间的每日一题都是相似内容的？好像最近是回溯算法。我刚开始的做法和上面77题的做法差不多，同样是深搜+回溯。

不过刚开始剪枝做的不好，时间上效率很差。以及一开始写了一个for循环的函数来计算arraylist的总和，导致耗时很多，后面通过维护一个临时变脸代替了这个函数，时间从25ms缩短到了6ms，不过官方解法写的更加简洁（目前的代码能力还是做不到官方解法的那种程度，官方解法没有维护任何临时变量，而是在递归当中不断的修改target的值，确实是很聪明的做法）。通过不断的摸索和尝试，像类似这种全遍历+回溯的题目，能否尽量多地剪枝是影响执行时间最重要的因素。

反思：
1、对递归+回溯的写法还是不那么熟练，写错了好几回
2、代码能够进一步简化，代码能力有待提高
3、在如何剪枝方面想的过于复杂，有时候简单地剪枝也会有相当不错的结果。

这里附上我自己写的三种解法（执行时间：25ms–>6ms–>3ms）：

25ms

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        add(candidates,target,0);
        return result;
    }

    public void add(int[] candidates, int target,int index){
        if(index >= candidates.length)
            return;
        if(calculate() == target){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        if(calculate() > target){
            return;
        }
        temp.add(candidates[index]);
        add(candidates,target,index);
        temp.remove(temp.size()-1);
        add(candidates,target,index+1);
    }

    public int calculate(){
        int x=0;
        for(int y:temp){
            x+=y;
        }
        return x;
    }
}

上面这段代码最主要的问题就在于calculate这个函数过于耗时了，如果temp很长，效率就会比较差

6ms

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    int temp_all = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        add(candidates,target,0);
        return result;
    }

    public void add(int[] candidates, int target,int index){
        if(index >= candidates.length)
            return;
        if(temp_all == target){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        if(temp_all > target){
            return;
        }
        temp.add(candidates[index]);
        temp_all += candidates[index];
        add(candidates,target,index);
        temp_all -= temp.get(temp.size()-1);
        temp.remove(temp.size()-1);
        add(candidates,target,index+1);
    }
}

相比于第一段代码，这里移除了calculus函数，而是通过维护一个临时变量temp_all来实现对总和的记录，大大减少了代码执行时间。但是这种写法有些过于冗杂了，可以看看官方的解法，会简洁很多。

3ms

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    int temp_all = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        add(candidates,target,0);
        return result;
    }

    public void add(int[] candidates, int target,int index){
        if(index >= candidates.length)
            return;
        if(temp_all == target){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        if(temp_all > target){
            return;
        }
        if(candidates[index] + temp_all > target){
            add(candidates,target,index+1);
        }else{
            temp.add(candidates[index]);
            temp_all += candidates[index];
            add(candidates,target,index);
            temp_all -= temp.get(temp.size()-1);
            temp.remove(temp.size()-1);
            add(candidates,target,index+1);
        }
    }
}

这里比6ms的代码做的更好的地方在于添加了一条剪枝规则，即一个if else判断，这里如果被选择的节点的值加上当前temp的总和已经超过了target，那么这条路径就不需要接着走下去了，可以直接考虑下一个节点。就是这么简单的一个剪枝，整个效率就提升了一倍。

更简洁的3ms的代码：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        add(candidates,target,0);
        return result;
    }

    public void add(int[] candidates, int target,int begin){
        if(target == 0){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = begin ; i < candidates.length; i++){
            if(target - candidates[i] < 0){
                continue;
            }
            temp.add(candidates[i]);
            add(candidates,target-candidates[i],i);
            temp.remove(temp.size()-1);
        }
    }
}

在写40题的时候意识到在递归内部用for循环的话逻辑会更清晰一些。

9.9完成

Leetcode 40题–组合总和2

40题和39题不同的地方在于candidate里面是有重复元素的，这就使得我们在处理的时候不得不考虑重复元素这一点。

如果希望考虑重复元素，就得判断这一轮这个值是否已经出现过了。如果直接判断这一点，相对是比较复杂的，因为不知道这个值在前面的那个地方出现过，如果candidate本身是排好序的，那么就只需要判断这个值的前一个值就可以了。

总的来说40题和39题还是差不多的，代码如下（3ms）：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        List<Integer> temp = new ArrayList<Integer>();
        Arrays.sort(candidates);

        add(candidates,0,result,temp,target);

        return result;
    }

    public void add(int[] candidates, int begin, List<List<Integer>> result, List<Integer> temp, int target){
        if(target == 0){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = begin ; i < candidates.length ; i++){
            if(target- candidates[i] < 0 ){
                break;
            }
            if(i > begin && candidates[i] == candidates[i-1]){
                continue;
            }
            temp.add(candidates[i]);
            add(candidates,i+1,result,temp,target-candidates[i]);
            temp.remove(temp.size()-1);
        }
    }
}

9.10完成

Leetcode 216题–组合总和3

216题也是可以用回溯加深搜解出来的，没什么难度，熟能生巧，缩短执行时间的关键还是在于剪枝，没什么特别的收获，代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();

        add(result,temp,n,k,1);
        return result;
    }

    public void add(List<List<Integer>> result,List<Integer> temp,int target,int target_num,int begin){
        if(target_num > target)
            return;
        if(target_num == 1 && target >= begin && target <= 9){
            temp.add(target);
            result.add(new ArrayList<Integer>(temp));
            temp.remove(temp.size() - 1);
            return;
        }
        if(target_num == 0 && target == 0){
            result.add(new ArrayList<Integer>(temp));
        }else if(target_num == 0)
            return;
        
        for(int i = begin ; i <= Math.min(target-target_num+1,9) ; i++){
            if(target - i < 0)
                continue;
            
            temp.add(i);
            add(result,temp,target-i,target_num-1,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

9.11完成

Leetcode 637 二叉树的层平均值

我觉得这里只要是使用二叉树的遍历都可以解出来，比较简单，没有什么可以学习的点，不过代码应该可以更加精简。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> total = new ArrayList<Double>();
        List<Integer> total_num = new ArrayList<Integer>();
        List<Double> result = new ArrayList<Double>();

        add(total,total_num,result,root,0);
        return result;
    }

    public void add(List<Double> total,List<Integer> total_num,List<Double> result,TreeNode node,int idx){
        if(node == null)
            return;
        if(total.size() == idx){
            total.add(Double.valueOf(node.val));
        }else
            total.set(idx,total.get(idx)+Double.valueOf(node.val));
        if(total_num.size() == idx)
            total_num.add(1);
        else
            total_num.set(idx,total_num.get(idx)+1);
        if(result.size() == idx)
            result.add(total.get(idx)/total_num.get(idx));
        else
            result.set(idx,total.get(idx)/total_num.get(idx));

        add(total,total_num,result,node.left,idx+1);
        add(total,total_num,result,node.right,idx+1);
    }
}

9.12完成

持续更新ing。。。

最后

以上就是幸福毛衣最近收集整理的关于Leetcode每日一刷的题目Leetcode刷题记录（主要用于自我记录）的全部内容，更多相关Leetcode每日一刷内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(54)

相关文章

每日一刷-leetcode
每日一刷-leetcode
开始刷Leetcode，启程的注意事项
开始刷Leetcode，启程的注意事项
leetcode刷题记录（中等4.26）1011.在D天内送达包裹的能力-二分法（中等4.27）377.组合总和Ⅳ-动态规划（中等4.28）633.平方数之和-双指针（困难4.29）403.青蛙过河-动态规划（中等4.30）137.只出现一次的数字II-位运算
leetcode刷题记录（中等4.26）1011.在D天内送达包裹的能力-二分法（中等4.27）377.组合总和Ⅳ-动态规划（中等4.28）633.平方数之和-双指针（困难4.29）403.青蛙过河-动态规划（中等4.30）137.只出现一次的数字II-位运算
leetcode统计记录
leetcode统计记录
Leetcode每日一刷的题目Leetcode刷题记录（主要用于自我记录）
Leetcode每日一刷的题目Leetcode刷题记录（主要用于自我记录）
刷leetcode的第一天
刷leetcode的第一天
每天坚持刷 LeetCode 的人，究竟会变得有多强... 学习技巧都藏在这几个公众号里面了......
每天坚持刷 LeetCode 的人，究竟会变得有多强... 学习技巧都藏在这几个公众号里面了......
每天刷LeetCode——D3【简单题】题目描述算法思路算法实现
每天刷LeetCode——D3【简单题】题目描述算法思路算法实现

评论列表共有 0 条评论

立即
投稿
返回
顶部