概述
Leetcode刷题记录（主要用于自我记录）
前言
本人是计算机专业学渣一枚，因前面算法课上课神游太虚，因此现在亡羊补牢，本文主要是本人对于学习过程的记录，说的不对的地方欢迎指正。
Leetcode 77题–组合
说说做题时的想法吧，刚开始做这道题的时候第一时间想到的是用递归来解，因为是个求全解的问题，感觉用递归做要方便很多，但是卡在了如何进行递归这一步。当时有想到维护一个临时变量，通过递归来进行处理，但是因为没有考虑到回溯这一点，导致这个想法不了了之，后面又考虑过维护多个临时变量，当然也是不行。
想解这道题建议了解下回溯算法和深搜。
这里面最关键的地方在于回溯这个过程，也就是当你完成了某个节点的递归之后，应当回到这个节点的父节点，重新选择下一个子节点再进行递归。能想到这个这道题就很简单了。
代码如下：
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
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
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
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的代码：
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）：
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题也是可以用回溯加深搜解出来的，没什么难度，熟能生巧，缩短执行时间的关键还是在于剪枝，没什么特别的收获，代码如下：
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 二叉树的层平均值
我觉得这里只要是使用二叉树的遍历都可以解出来，比较简单，没有什么可以学习的点，不过代码应该可以更加精简。
/**
* 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每日一刷的题目Leetcode刷题记录（主要用于自我记录）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复