5.7LeetCode

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] canGo=new boolean[nums.length];
        canGo[0]=true;
        for(int i=0;i<nums.length;i++){
            if(canGo[i]){
                int j=i+1;
                while(j<nums.length&&j<=i+nums[i]){
                    canGo[j]=true;
                    j++;
                }   
            }
            if(canGo[nums.length-1]) return true;
        }
        return canGo[nums.length-1];
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int maxlength=nums[0];
        for(int i=0;i<=maxlength;i++){
            if(maxlength>=nums.length-1) return true;
            if(nums[i]+i>maxlength) maxlength=nums[i]+i;
        }
        return false;
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<n;i++) 
            dp[0][i]=1;
        for(int i=0;i<m;i++)
            dp[i][0]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m-1][n-1];
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        int[] dp=new int[amount+1];
        for(int i=0;i<amount+1;i++)
            dp[i]=Integer.MAX_VALUE;
        for(int i:coins)
            if(i<=amount)
                dp[i]=1;  
        for(int i=1;i<amount+1;i++)
            for(int j:coins){
                if(i-j>0&&dp[i-j]!=Integer.MAX_VALUE&&dp[i-j]+1<dp[i])
                    dp[i]=dp[i-j]+1;
            }
        //return dp[amount];
        return dp[amount]==Integer.MAX_VALUE? -1:dp[amount];
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            dp[i]=1;
        for(int i=1;i<nums.length;i++)
            for(int j=i-1;j>=0;j--)
                if(nums[i]>nums[j]&&dp[j]+1>dp[i])
                    dp[i]=dp[j]+1;
        int max=0;
        for(int i:dp){
            //System.out.println(i);
            if(i>max)
                max=i;
            
        }
            
        return max;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        StringBuffer res=new StringBuffer();
        if(root==null) return res.toString();
        res.append(String.valueOf(root.val));
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode t=queue.poll();
                if(t==null){
                    res.append(",null");
                }
                else{
                    res.append(",");
                    res.append(String.valueOf(t.val));
                    queue.offer(t.left);
                    queue.offer(t.right);
                }
            }
        }
        //System.out.println(res);
        return res.toString();
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] s=data.split(",");
        int n=s.length;
        for(int i=s.length-1;i>=0;i--)
            if(s[i].equals("null"))
                n--;
            else break;
        // for(int i=0;i<n;i++)
        //     System.out.println(s[i]);

        TreeNode[] node=new TreeNode[n];
        int j=1;
        for(int i=0;i<n;i++)
            if(!s[i].equals("null"))
                node[i]=new TreeNode(0);
            else node[i]=null;
        for(int i=0;i<n;i++)      
           if(!s[i].equals("null")){
               node[i].val=Integer.parseInt(s[i]);
               if(j<n&&!s[j].equals("null")) node[i].left=node[j];
               j++;
               if(j<n&&!s[j].equals("null")) node[i].right=node[j];
               j++;
               
            }
            else node[i]=null; 
         
        return node[0];
           
    }
}

class Solution {
    public int trailingZeroes(int n) {
        int max=0; int t=n;
        while(t!=0){
            t=t/5;
            max++;
        }
        int res=0;
        for(int i=1;i<max;i++)
            res+=n/Math.pow(5,i);
        return res;
    }
}