面试经典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<n+1;i++){
         ans[i]=ans[i-1] + ans[i-2];
     }
     return ans[n];

 }

然后你也可以将数组再简化为两个变量。因为只与前两个变量有关。

198.打家劫舍

在这里插入图片描述

class Solution {
    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<N+1;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];

    }
}

一维dp的子问题，基本就是与dp[i-1]和dp[i-2]有关系。

139.单词拆分

在这里插入图片描述

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

    }
}

dp[i]代表从0到i这个字符串成不成。

322.零钱兑换

在这里插入图片描述
做一个长度为amount +1 的数组，每个位置代表着i能不能被硬币拼凑。
要注意初始化dp[0]=0

class Solution {
    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<amount+1;i++){
            for(int j=0;j<coins.length;j++){
                if(i-coins[j]>=0)
                dp[i] = Math.min(dp[i],1+dp[i-coins[j]]);
            }
        }
        return dp[amount]>amount? -1:dp[amount];

    }
}

300.递增最长子序列

在这里插入图片描述

class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp[i] 为必须包含第 i 个元素的最长递增子序列
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=0;i<nums.length;i++){
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}

77.组合

在这里插入图片描述
画一个递归的树图
在这里插入图片描述

class Solution {
    public List<List<Integer>> combine(int n, int k) {
         List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }
    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        //终止条件是path的长度等于k
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return ;
        }
        //以i开头，n结尾
        for(int i=begin;i<=n;i++){
            path.addLast(i);
            dfs(n,k,i+1,path,res);
            path.removeLast();
        }
    }

}

或者换一个树的类型，选与不选。只修改dfs即可
在这里插入图片描述

class Solution {
    public List<List<Integer>> combine(int n, int k) {
         List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }
    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        //终止条件是path的长度等于k
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return ;
        }
        if(begin == n+1){
            return ;
        }
        //不加新元素
        dfs(n,k,begin+1,path,res);
        //添加新元素
        path.addLast(begin);
        dfs(n,k,begin+1,path,res);

        path.removeLast();
    }

}

要对begin也做限制。
总体的板子还是。做一个helper函数，终止条件，dfs,这一步要加的，dfs,减去这一步加的。

46.全排列

在这里插入图片描述

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        if(len == 0) return res;
        boolean[] used=new boolean[len];
        List<Integer> path=new ArrayList<>();
        dfs(nums,len,0,path,used,res);
        return res;
    }
    private void dfs(int[] nums, int len, int depth,List<Integer> path, boolean[] used,List<List<Integer>> res) {
        if(depth == len){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<len;i++){
            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);
            }
        }
    }
}

要用一个used数组记录哪个位置被使用。

39.组合总和（※）

在这里插入图片描述
在这里插入图片描述

class Solution {
   public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }
    public static void dfs(int[] candidates,int begin,int len,int target,Deque<Integer>path,List<List<Integer>> res){
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=begin;i<len;i++){
            if(target-candidates[i] <0) break;
            path.addLast(candidates[i]);
            dfs(candidates,i,len,target-candidates[i],path,res);
            path.removeLast();
        }
    }
}

注意dfs中的i , 从begin到len , 并且也要传递到下一个dfs中去。

  • 排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；

  • 组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

22.括号生成

在这里插入图片描述

class Solution {
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        String cur = "";
        int left = 0, right = 0;
        dfs(res, cur, n, left, right);
        return res;

    }

    public static void dfs(List<String> res, String cur, int n, int left, int right) {
        if (left > n || left < right)
            return;
        if (cur.length() == 2 * n) {
            res.add(cur);
        }
        if (left < n)
            dfs(res, cur + "(", n, left + 1, right);
        if (right < n)
            dfs(res, cur + ")", n, left, right + 1);

    }
}

这种是直接将修改的新字符串传递给函数。

public class LC22 {
    public static List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        StringBuilder sb=new StringBuilder();
        int left=0,right=0;
        dfs(res,sb,n,left,right);
        return res;

    }
    public static void dfs(List<String> res,StringBuilder sb,int n,int left,int right){
        if(left >n || left<right) return;
        if(sb.length()== 2*n && left ==n){
            res.add(sb.toString());
            return;
        }
        if(left<n){
            sb.append("(");
            dfs(res,sb,n,left+1,right);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right<n){
            sb.append(")");
            dfs(res,sb,n,left,right+1);
            sb.deleteCharAt(sb.length()-1);
        }

    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}

这种就是很典型的回溯了，增加了再删除。

79.单词搜索

在这里插入图片描述
以每一个字母为开头进行搜索。搜索过程就是dfs的上下左右。
遍历到成功后要置为’\0’,这样可以防止第二次遍历到，结束了要改回来。
k代表遍历到word字符串的哪个变量了

public class LC79 {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean ans = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j - 1, k + 1) || dfs(board, word, i, j + 1, k + 1);
        board[i][j] = word[k];
        return ans;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/489414.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

详解Java 中的 Lambda 表达式

详解Java 中的 Lambda 表达式

引言&#xff1a; Lambda 表达式是 Java 8 中引入的一个重要特性&#xff0c;它可以使代码更加简洁、易读&#xff0c;并且更加具有函数式编程风格。Lambda 表达式本质上是一个匿名函数&#xff0c;它可以作为方法参数传递&#xff0c;也可以直接赋值给一个变量。 一、Lambda 表…
阅读更多...
Day20:LeedCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

Day20:LeedCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654. 最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums …
阅读更多...
【Rust】——提取函数消除重复代码和泛型

【Rust】——提取函数消除重复代码和泛型

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…
阅读更多...
Java项目：75 springboot房产销售系统

Java项目：75 springboot房产销售系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 使用房产销售系统分为管理员和用户、销售经理三个角色的权限子模块。 管理员所能使用的功能主要有&#xff1a;首页、个人中心、用户管理、销售经理管…
阅读更多...
OpenCV4.9在iOS中安装

OpenCV4.9在iOS中安装

返回&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;使用CUDA 为Tegra构建OpenCV-CSDN博客 下一篇&#xff1a; 警告&#xff01; 本教程可以包含过时的信息。 所需软件包 CMake 2.8.8 或更高版本Xcode 4.2 或更高版本 从 G…
阅读更多...
品牌出海必读：深入解析成功背后的5大底层逻辑

品牌出海必读：深入解析成功背后的5大底层逻辑

品牌出海是当今全球化时代中企业发展的重要策略之一。无论是传统制造业还是新兴科技公司&#xff0c;都在不同程度上关注着海外市场的拓展。然而&#xff0c;品牌出海并非仅仅是一个简单的营销策略&#xff0c;其背后蕴含着复杂的底层逻辑。本文Nox聚星将和大家探讨品牌出海的底…
阅读更多...
电脑桌面便签软件，好用的电脑桌面便签软件

电脑桌面便签软件，好用的电脑桌面便签软件

在数字化时代&#xff0c;我们的工作方式正在发生深刻的变革。作为现代办公一族&#xff0c;提升工作效率&#xff0c;管理好的灵感和待办事项变得尤为重要。而在众多的办公辅助工具中&#xff0c;电脑桌面便签软件以其便捷、实用的特点&#xff0c;深受广大办公族的喜爱。今天…
阅读更多...
C语言例4-17：从键盘输入一个年份year（4位十进制数），判断其是否是闰年

C语言例4-17：从键盘输入一个年份year（4位十进制数），判断其是否是闰年

算法分析&#xff1a; 如果X能被Y整除&#xff0c;则余数为0&#xff0c;即如果X%Y的值等于0&#xff0c;则表示X能被Y整除。首先将是否是闰年的标志leap初始值设置为0&#xff08;非闰年&#xff09;&#xff0c;仅当year为闰年时将leap的位置为1。 初始代码如下&#xff1a…
阅读更多...
踏入IOT安全世界：DIR-815路由器多次溢出漏洞分析复现

踏入IOT安全世界：DIR-815路由器多次溢出漏洞分析复现

前言 在进行IOT安全领域的学习和实践中&#xff0c;经典漏洞的复现是必不可少的一环。本文将介绍一个经典漏洞&#xff0c;涉及到Binwalk、firmware-mod-kit、FirmAE等工具的使用&#xff0c;以及对DIR-815路由器中多次溢出漏洞的复现过程。 固件下载地址&#xff1a;https:/…
阅读更多...
安捷伦Agilent 34401A数字万用表

安捷伦Agilent 34401A数字万用表

181/2461/8938产品概述&#xff1a; Agilent34401A 万用表将准确性、速度、测量简便性和多功能性结合到坚固的 6 1/2 位数字万用表中&#xff0c;无论在工作台上还是在系统中都同样适用。您可以以 5 1/2 位数的价格获得 6 1/2 位数的性能。除了直流和交流电压、直流和交流电流…
阅读更多...
golang+vue微服务电商系统

golang+vue微服务电商系统

golangvue微服务电商系统 文章目录 golangvue微服务电商系统一、项目前置准备二、项目简介三、代码GItee地址 golang、vue redis、mysql、gin、nacos、es、kibana、jwt 一、项目前置准备 环境的搭建 官方go开发工程师参考地址&#xff1a;https://blog.csdn.net/qq23001186/cat…
阅读更多...
【数据结构与算法】直接插入排序和希尔排序

【数据结构与算法】直接插入排序和希尔排序

引言 进入了初阶数据结构的一个新的主题——排序。所谓排序&#xff0c;就是一串记录&#xff0c;按照其中的某几个或某些关键字的大小&#xff08;一定的规则&#xff09;&#xff0c;递增或递减排列起来的操作。 排序的稳定性&#xff1a;在一定的规则下&#xff0c;两个值…
阅读更多...
Web3 游戏周报（3.17-3.23）

Web3 游戏周报（3.17-3.23）

【3.17-3.23】Web3 游戏行业动态&#xff1a; Saga 宣布成立 Web3 游戏发行部门 Saga Origins Web3 游戏平台 Portal 宣布将于周四开放质押功能 STP 推出基于 Base 的 AI 增强游戏 Layer3 Clique Merlin 生态游戏项目 BitRealms 完成 Pre-Seed 轮融资 Telos 在游戏侧链发布…
阅读更多...
Open CASCADE学习|显示文本

Open CASCADE学习|显示文本

目录 1、修改代码 Viewer.h&#xff1a; Viewer.cpp&#xff1a; 2、显示文本 OpenCasCade 你好啊 霜吹花落 1、修改代码 在文章《Open CASCADE学习|显示模型》基础上&#xff0c;增加部分代码&#xff0c;实现对文本显示的支持&#xff0c;具体如下&#xff1a; Viewer…
阅读更多...
入门编程，一定要从C语言开始吗？

入门编程，一定要从C语言开始吗？

对于编程入门学习者&#xff0c;C语言肯定不是首选。建议先确定自己的发展方向&#xff0c; 如果打算做Web 开发&#xff0c;可以先从学习HTML,CSS,Javascript开始&#xff0c;后台使用Node.JS&#xff0c;也是用Javascript 来编程, 可降低入门门槛。 在开始前我有一些资料…
阅读更多...
MySQL索引优化、SQL优化-持续更新

MySQL索引优化、SQL优化-持续更新

背景 成本最低的优化手段&#xff0c;面试常问的面试题。 下面主要是讲InnoDB存储引擎的索引&#xff0c;InnoDB也是实际项目用的最多的存储引擎。 优势 提高数据查询效率。 缺点 占用空间、降低了增、删、改速度&#xff0c;因为要维护索引 原理 底层是B树数据结构。 …
阅读更多...
关于Web APP 促进临床预测模型进入临床实践的讨论

关于Web APP 促进临床预测模型进入临床实践的讨论

关于Web APP 促进临床预测模型进入临床实践的讨论 关键词&#xff1a; 临床预测模型、Web APP、实践、标准、讨论、分享 近年来&#xff0c;随着机器学习技术的快速发展&#xff0c;临床预测模型在辅助诊断、预后评估、治疗方案选择等方面展现出巨大潜力。然而&#xff0c;将…
阅读更多...
工时表软件：项目管理的效率利器

工时表软件：项目管理的效率利器

在当今的项目管理实践中&#xff0c;时间是最宝贵的资产之一。精准地追踪和管理项目工时对于项目的成功至关重要。工时表软件作为一种现代管理工具&#xff0c;其应用不仅简化了项目管理流程&#xff0c;还提高了工作效率&#xff0c;已成为现代企业管理不可或缺的一项利器。 …
阅读更多...
[Vue warn]: Invalid vnode type when creating vnode: false

[Vue warn]: Invalid vnode type when creating vnode: false

如题&#xff0c;意思是创建vnode时&#xff0c;vnode类型无效:false。 根据右边的索引点进去&#xff0c;发现定位的是组件loading。搜索loading发现声明了变量loading&#xff0c;更改后问题消失。
阅读更多...
MySQL数据库高阶语句①

MySQL数据库高阶语句①

目录 一.按关键字排序 1.单字段排序 &#xff08;1&#xff09;按分数排序 &#xff08;2&#xff09;结合where进行条件筛选 2.多字段排序 &#xff08;1&#xff09;查询学生信息先按兴趣id升序排序&#xff0c;再按id升序排序 &#xff08;2&#xff09;查询信息按兴…
阅读更多...
最新文章

Copyright @ 2022~2023