虽然很懒，开一个帖子监督自己刷LEETCODE吧

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

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

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


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

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;
        }
}

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;
    }
}

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;
    }
}

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;   
    }
}

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[i];               //把不一样的置于最后一个不一样之后
            }
            
        }
        return length;
    }
}[/i]

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;
   }
}

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;                              //返回左右子树的结果
    }
}

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是否相同，并且还要看左子树与另一个右子树，以及右子树与另一个左子树是否相同。
    }
}

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;
     }
   
}
}
  

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;
        }
    }
}