面试经典150题(114-118)

leetcode 150道题计划花两个月时候刷完之未完成后转，今天完成了5道(114-118)150

gap 了一周，以后就不记录时间了。。

114.(70. 爬楼梯) 题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

第一版（经典动态规划或者递归题目，只需要看他最后是跳一次还是跳二次，而且他最后跳一次前面的方案和他最后跳一次前面的方案是不冲突的所以是 fx=fx-1+fx-2 ）

class Solution {
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

115.(198. 打家劫舍) 题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

第一版（还是动态规划，但是这个里面是求最大的金额，fx 代表的就是一共 x 个房间可以获得的最大金额，也是有两种情况，x 这家偷和不偷所以 fx = max( x金额+fx-2 , fx-1) ）

class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        if(len==1){
            return nums[0];
        }
        int[] dp=new int[len+1];
        dp[0]=0;
        dp[1]=nums[0];
        for(int i=2;i<=len;i++){
            dp[i]=Math.max(nums[i-1]+dp[i-2],dp[i-1]);
        }
        return dp[len];

    }
}

116.(139. 单词拆分) 题目描述：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

第一版（这个没写出来，刚开始想着用递归就可以了，超时了）

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakCore(0,s.length(),s,wordDict);
    } 
    public boolean wordBreakCore(int start,int end,String s, List<String> wordDict) {
        if(start==end){
            return true;
        }
        if(start>end){
            return false;
        }
        for(int i=0;i<wordDict.size();i++){
            if(s.substring(start,end).indexOf(wordDict.get(i))!=-1){
                int left=s.substring(start,end).indexOf(wordDict.get(i))+start;
                int right=left+wordDict.get(i).length();
                boolean temp=wordBreakCore(start,left,s,wordDict)&&wordBreakCore(right,end,s,wordDict);
                if(temp){
                    return temp;
                }
            }
        }
        return false;
    }        
}

第二版（动态规划，思路是对的但是没写出来）

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict=new HashSet();
        for(String str:wordDict){
            dict.add(str);
        }
        int len=s.length();
        boolean[] dp=new boolean[len+1];
        dp[0]=true;
        for(int i=1;i<=len;i++){
            for(int j=i-1;j>=0;j--){
                if(dp[j]&&dict.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[len];

    }
}

117.（322. 零钱兑换）题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

第一版（动态规划，fx 代表 x 可以用多少硬币凑出来，这个里面有个坑（一看最少硬币我就想到排序但是有坑）就是如果 x=8 硬币为【1，4，6】应该最少的是 2 所以不能排序要把所有的走一遍求最小值, fx=f(x-coin)+1）

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            boolean flag=true;
            dp[i]=i;
            for(int j=0;j<coins.length;j++){
                if(i-coins[j]>=0&&dp[i-coins[j]]>=0){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                    flag=false;
                }
            }
            if(flag){
                dp[i]=-1;
            }
        }
        return dp[amount];
    }
}

118.(300. 最长递增子序列) 题目描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。

第一版（动态规划）

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if(len<=1){
            return len;
        }
        int[] dp=new int[len];
        int res=1;
        dp[0]=1;
        for(int i=1;i<len;i++){
            dp[i]=1;
            for(int j=i-1;j>=0;j--){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}