一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 535|回复: 11
收起左侧

[Leetcode] 虽然很懒,开一个帖子监督自己刷LEETCODE吧

[复制链接] |试试Instant~ |关注本帖
caffery24 发表于 2015-6-4 17:36:40 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 caffery24 于 2015-6-4 20:48 编辑

今天开始从最最最简单的题开始刷,刷一道传一道吧。希望大家一起来。

希望大家能给我的拙劣思路提提意见。谢谢大家。

现在大四。。。只是刚刚跟了两门课。。。所以第一次刷,从最简单的开始,希望坚持下去


补充内容 (2015-6-6 17:19):
...才第三天,感觉还是很多东西掌握不住。但是还是坚持,第一遍,哪怕不如别人写得好,有些知识没顾及到,得看别人的思路,就当是看了一遍算法书吧。做题中学算法、

评分

2

查看全部评分

 楼主| caffery24 发表于 2015-6-4 17:38:18 | 显示全部楼层
1.  第六题Remove Duplicates from Sorted Array没有更简单的题了吧。。。但是还是第一次写,交了两遍,第一遍count没想清楚,每次遇到不一样的多减了1

程序:
public class Solution {
    public int removeDuplicates(int[] nums) {
        int count=0;int length=nums.length;
        for(int i=1;i<nums.length;i++)
        {
            if(nums[i]==nums[i-1])
            {
                count++;
                length--;
            }
            else
            {
                int tep=nums[i];
                nums[i-count]=tep;

            }
        }
     return length;   
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-4 17:49:45 | 显示全部楼层
本帖最后由 caffery24 于 2015-6-4 17:57 编辑

2.第27题Remove Element 我的思路和26题一样,区别仅仅是把val当成26题中相同的数字。其它基本一样

程序:
public class Solution {
    public int removeElement(int[] nums, int val) {
        int length=nums.length;int count=0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums==val)
            {   count++;                    //碰到一样的,就累积
                length--;
            }
            else
            {
                nums[i-count]=nums;               //把不一样的置于最后一个不一样之后
            }
            
        }
        return length;
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-4 18:24:46 | 显示全部楼层
3. 58题Length of Last Word
交了三次:主要三种特殊情况:(1)  “ ”;(2)“a b      ”;(3) "a";

程序:
public class Solution {
    public int lengthOfLastWord(String s) {
        int length=0;
     for(int i=s.length()-1;i>=0;i--)
    {
        char c=s.charAt(i);
        if(c!=' ')
        {
            length++;
        }
        else if(length!=0)         //此条件是针对第二种情况,即最后部分是空格;如果全是空格,会通过for循
                                         // 环跳出,没有影响
        break;
    }
    return length;
   }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-4 19:08:28 | 显示全部楼层
4. 66题Plus One
这个题个人感觉唯一需要考虑的就是9+1的情况;以及如果最高位发生进位的情况,但是没想出来In place的方法,不知道有谁能做到in place?

程序:
public class Solution {
    public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--)
        {
            if(digits[i]<9)                              //没有进位的情况,直接加1返回
            {
                digits[i]++;
                return digits;
            }
            else
            {   
                digits[i]=0;
            }
        }
        int[] result=new int[digits.length+1];         //最高位发生进位,使用新数组保存。
        if(digits[0]==0)
        {
        result[0]=1;
         for(int j=1;j<result.length;j++)
            {
           result[j]=0;
            }
         
        }
         return result;
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-4 19:40:51 | 显示全部楼层
本帖最后由 caffery24 于 2015-6-4 19:45 编辑

5. 83题Remove Duplicates from Sorted List
这一个题第一次的做法时间复杂度worst case n^2,原因是每次遇到一个重复就改一次node.next。然后从这个node在判别一次
随后进行了改进,一直到与node不同的node.val才改node.next=node.next.next。这样是一个线性的。

程序:
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node=head;
        while(node!=null)
        {while(node.next!=null&&node.val==node.next.val)  //如果到了不是最后一个Node,并且与下一个
                                                                                  node.val相同,skip过这一个Node.next,比较                           
                                                                                    下一个node.val,until 下一个node.val不一样           个人觉得这一步类似于数组删除中count的作用。,都是为了找下一个的正确位置
        {
            node.next=node.next.next;                              
        }
                    
            node=node.next;           //如果与下一个Node.val相同,则继续比较
        }
        return head;
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-4 20:47:18 | 显示全部楼层
6. 第100题 Same Tree
这一题采用了pre-order的recursively来判断。。。程序写的有点臃肿,但是思路应该是比较简单的一种把,毕竟题也是最简单的1级。

程序:
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public boolean same;
    public boolean isSameTree(TreeNode p, TreeNode q) {
       if(p==null||q==null)        //判断两个是否都是null
        return p==q;
        else if(p.val==q.val)       //如果两个val相等,看它的左右两个子树
       { same= isSameTree(p.left,q.left);
       if(same==false)                             //如果左子树不同,无需比较右子树,直接返回false
       return false;
        same=isSameTree(p.right,q.right);
       }
        else                                         //如果两个node的val不同,返回false
        return false;
        return same;                              //返回左右子树的结果
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-5 15:19:32 | 显示全部楼层
101题  Symmetric Tree
这个题和100题基本类似,再看了100题的别人的高端解法后,感觉自己对递归有了深层次理解,即主要需要抓住每一个Node都得完成的判断事情,这也构成了递归的主体

程序:
public class Solution {
    public boolean isSymmetric(TreeNode root) {
      if(root==null)
      return true;
      else
       return check(root.left,root.right);                          
    }
    public boolean check(TreeNode node1,TreeNode node2)
    {  if(node1==null||node2==null)
    return node1==node2;
    else
    return node1.val==node2.val&&check(node1.left,node2.right)&&check(node1.right,node2.left);
//每一次check想返回true必须check两个Node的val是否相同,并且还要看左子树与另一个右子树,以及右子树与另一个左子树是否相同。
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-5 16:09:20 | 显示全部楼层
104题Maximum Depth of Binary Tree
采用了一个模板算法

程序:
public class Solution {
    public int maxDepth(TreeNode root) {
     if(root==null)
     return 0;
     else
     {
         int left=maxDepth(root.left);
         int right=maxDepth(root.right);
         return Math.max(left,right)+1;
     }
   
}
}
  
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-5 22:23:00 | 显示全部楼层
110题Balanced Binary Tree
是depth问题一个延伸
程序:
public class Solution {
   
    public boolean isBalanced(TreeNode root) {
    return check(root)!=-1;
        
    }
    public int check(TreeNode root)
    {
        if(root==null)
        return 0;
        else
        {
            int left=check(root.left);
            int right=check(root.right);
            if(left==-1||right==-1||Math.abs(left-right)>1)
            return -1;
            else
            return Math.max(left,right)+1;
        }
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-5 22:24:58 | 显示全部楼层
111        Minimum Depth of Binary Tree
就是在上一个maxdepth上的一点改动,需要加两个判别条件,来区分null的节点带来的0

程序:
public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
        return 0;
        else
        {
            int left=minDepth(root.left);
            int right=minDepth(root.right);
            if(left==0&&right!=0) return right+1;
            else if(right==0&&left!=0) return left+1;
            return Math.min(left,right)+1;
        }
    }
}
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-6-5 22:26:29 | 显示全部楼层
112 PATH SUM
自己的写法简直惨不忍睹。。。采用了一个个加,最后看是不是的写法

程序:
public class Solution {
    private int total=0;private int flag=0;
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)
        return false;
        else
        {
            visited(root,sum);
        }
        if(flag==-1)
        return true;
        else
        return false;
        
    }
    public void visited(TreeNode node,int sum)
    {  total=total+node.val;
        if(node.left!=null&&flag!=-1)
        {
             visited(node.left,sum);
        }
        if(node.right!=null&&flag!=-1)
        {
            visited(node.right,sum);
        }
        if(sum==total&&node.left==null&&node.right==null)
        {
            flag=-1;
        }
        else if(flag!=-1)
        total=total-node.val;
        
        
    }
}

然后看了看大神们简介的写法:
//九章DFS模板  dfs的结束条件是root没有子节点(root是叶子)
//然后 不用写for循环 因为是二叉树 只要分别递归左右子节点当新root即可。
//记得 (不管这个递归方法是怎么结束的 因为 只有一个onePath作为单条path的缓存
//                所以递归方法啊结束时候都要 onePath.remove(onePath.size()-1);
public class PathSum {
        public boolean hasPathSum(TreeNode root, int sum) {

                if (root == null) {
                        return false;
                }

                sum = sum - root.val;
                // 结束条件 当 到叶子节点时候sum==0
                if (root.left == null && root.right == null) {
                        if (sum == 0) {
                                return true;
                        }
                }
     if(hasPathSum(root.left,sum)){return true;}
     if( hasPathSum(root.right, sum)){return true;}
     return false;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 00:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表