面试经典150题【91-100】

文章目录

• 面试经典150题【91-100】
• • 70.爬楼梯
  • 198.打家劫舍
  • 139.单词拆分
  • 322.零钱兑换
  • 300.递增最长子序列
  • 77.组合
  • 46.全排列
  • 39.组合总和（※）
  • 22.括号生成
  • 79.单词搜索

    面试经典150题【91-100】

    五道一维dp题+五道回溯题。

    70.爬楼梯

    

    从递归到动态规划

        public int climbStairs(int n) {
            if(n==0) return 1;
            if(n==1) return 1;
            if(n==2) return 2;
            return climbStairs(n-1) + climbStairs(n-2);
        }
    

    这样会超时，然后把他放到数组里。

    public int climbStairs(int n) {
         int[]ans = new int[n+1];
         ans[0]=1;
         ans[1]=1;
         for(int i=2;i
             ans[i]=ans[i-1] + ans[i-2];
         }
         return ans[n];
     }
    
        public int rob(int[] nums) {
            if(nums.length == 0) return 0;
            int N=nums.length;
            int[] dp=new int[N+1];
            dp[0]=0;
            dp[1]=nums[0];
            for(int i=2;i
                // 第2家 dp[2], 不偷dp[1],  偷 dp[0]+nums[1]
                dp[i]=Math.max(nums[i-1]+dp[i-2],dp[i-1]);
            }
            return dp[N];
        }
    }
    
        public boolean wordBreak(String s, List
            Set
                maxLen = Math.max(maxLen,str.length());
            }
            boolean[] dp=new boolean[s.length() +1];
            dp[0]=true;
            for(int i=0;i
                for(int j=Math.max(0,i-maxLen);j
                    if(dp[j] && wordDictSet.contains(s.substring(j,i))){
                        dp[i]=true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }
    
        public int coinChange(int[] coins, int amount) {
            int[] dp=new int[amount+1];
            Arrays.fill(dp,amount+1);
            dp[0]=0;
            for(int i=0;i
                for(int j=0;j
                    if(i-coins[j]=0)
                    dp[i] = Math.min(dp[i],1+dp[i-coins[j]]);
                }
            }
            return dp[amount]amount? -1:dp[amount];
        }
    }
    
        public int lengthOfLIS(int[] nums) {
            //dp[i] 为必须包含第 i 个元素的最长递增子序列
            int[] dp=new int[nums.length];
            Arrays.fill(dp,1);
            for(int i=0;i
                for(int j=0;j
                    if(nums[i]nums[j]){
                        dp[i]=Math.max(dp[i],dp[j]+1);
                    }
                }
            }
            int ans=0;
            for(int i=0;i
                ans=Math.max(ans,dp[i]);
            }
            return ans;
        }
    }
    
        public List
             List
                return res;
            }
            // 从 1 开始是题目的设定
            Deque
            //终止条件是path的长度等于k
            if(path.size() == k){
                res.add(new ArrayList
                path.addLast(i);
                dfs(n,k,i+1,path,res);
                path.removeLast();
            }
        }
    }
    
        public List
             List
                return res;
            }
            // 从 1 开始是题目的设定
            Deque
            //终止条件是path的长度等于k
            if(path.size() == k){
                res.add(new ArrayList
                return ;
            }
            //不加新元素
            dfs(n,k,begin+1,path,res);
            //添加新元素
            path.addLast(begin);
            dfs(n,k,begin+1,path,res);
            path.removeLast();
        }
    }
    
        public List
            int len=nums.length;
            List
            if(depth == len){
                res.add(new ArrayList
                if(!used[i]){
                    path.add(nums[i]);
                    used[i]=true;
                    dfs(nums, len, depth + 1, path, used, res);
                    
                    used[i]=false;
                    path.remove(path.size()-1);
                }
            }
        }
    }
    
       public static List
            int len = candidates.length;
            List
                return res;
            }
            // 排序是剪枝的前提
            Arrays.sort(candidates);
            Deque
            if (target == 0) {
                res.add(new ArrayList
                if(target-candidates[i] 
        public static List
            List
            if (left  n || left