2025高频面试算法总结篇【递归回溯动态规划】

文章目录

  • 递归&回溯
    • 131. 分割回文串
    • 面试题 08.12. 八皇后
  • 动态规划
    • 72编辑距离
    • 5. 最长回文子串
    • 279. 完全平方数
    • 300. 最长递增子序列
    • 139. 单词拆分


递归&回溯

131. 分割回文串

在这里插入图片描述
回溯思路:

临界条件:
if (start == s.length) => 保存
循环遍历这个字串
for (int i = start;i < s.length();i++)if (s[start:i] 是 回文串) => dfs(i+1)

回文串的判断:

  1. 可以直接判断。
  2. 可以采用动态规划的方式进行记录,dp[i][j]定义为s[i:j]字串是否是回文串,d[i][j] = s[i]==s[j] && d[i+1][j-1]
class Solution {List<List<String>> ans = new ArrayList<>();public List<List<String>> partition(String s) {if (s == null || s.length() == 0) {return ans;}dfs(s, 0, new ArrayList<>());return ans;}private void dfs (String s, int start, List<String> res) {if (start == s.length()) {ans.add(new ArrayList<>(res));return;}for (int i = start; i < s.length(); i++) {if (huiwen(s.substring(start, i+1))) {res.add(s.substring(start, i+1));dfs(s, i+1, res);res.remove(res.size() - 1);}}}private boolean huiwen(String substring) {int left = 0;int right = substring.length() -1;while (left < right) {if (substring.charAt(left) != substring.charAt(right)) {return false;}left++;right--;}return true;}}

面试题 08.12. 八皇后

在这里插入图片描述
回溯思路:定义一个一维数组即可cols[row] = x,第row行的皇后在第x列。

临界条件:
if (row == N) =》保存
递归&回溯:遍历当前这一行的数据
for (int col = 0; col < N; col++)if [row][col] 符合 题意 :=》下一行dfs(row+1)

[row][col] 符合 题意:

  1. 不同行已经确保了,需要判断不同列:cols[0:row] != col
  2. 对角线的判断:row - col == i - cols[i](左对角线冲突)& row + col == i + cols[i](右对角线冲突)【简单记忆:绝对值:行-遍历的行==列-遍历的列Math.abs(row - i) == Math.abs(col - cols[i])
class Solution {List<List<String>> ans = new ArrayList<>();public List<List<String>> solveNQueens(int n) {if (n == 0) return ans;dfs(0, n, new int[n]);return ans;}private void dfs(int row,int n, int[] cols) {if (row == n) {// 保存ans.add(board(cols));return;}for (int col = 0; col < n; col++) {if (helper(row, col, cols)) {cols[row] = col;dfs(row+1, n, cols);cols[row] = 0;}}}private boolean helper(int row,int col,int[] cols) {if (row == 0) return true;for (int i = 0; i < row; i++) {if (cols[i] == col|| Math.abs(row - i) == Math.abs(col - cols[i])) {return false;}}return true;}private List<String> board (int[] cols) {List<String> res = new ArrayList<>();char[] s = new char[cols.length];for (int i = 0; i < cols.length; i++) {Arrays.fill(s, '.');s[cols[i]] = 'Q';res.add(new String(s));}return res;} }

动态规划

72编辑距离

在这里插入图片描述
定义:dp[i][j]表示word1[0:i]编辑成word2[0:j]所使用的最少操作数 。
公式:初始 i=0 dp[0][j] = j , j=0, dp[i][j] = i if s[i] == s[j] dp[i][j] = dp[i-1][j-1] else dp[i][j] = 1+ Math.min(插入dp[i][j-1],删除dp[i-1][j], 替换 dp[i-1][j-1])

class Solution {// 定义// dp[i][j]:  word1[0:i] 转换成 word2[0:j] 所使用的最少操作数// 边界// d[0][0] = 0// d[i][0] = i d[0][j] = j// 状态转移// dp[i][j] =// if w1[i] == w2[j] => dp[i][j] = dp[i-1][j-1]// else 删插换 dp[i][j] = 1 + min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length() + 1][word2.length() + 1];for (int i = 0; i <= word1.length(); i++) {dp[i][0] = i;}for (int j = 0; j <= word2.length(); j++) {dp[0][j] = j;}for (int i = 1; i <= word1.length(); i++) {for (int j = 1; j <= word2.length(); j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else {dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i-1][j-1]) + 1;}}}return dp[word1.length()][word2.length()];}
}

5. 最长回文子串

在这里插入图片描述
定义:dp[i][j] 表示 s[i:j]是否是回文串
公式:dp[i][i] = true 单个字符一定是回文串,dp[i][j] = (s[i] == s[j]) && (len == 2 || dp[i + 1][j - 1])

class Solution {public String longestPalindrome(String s) {boolean[][] dp = new boolean[s.length()][s.length()];for (int i = 0; i < s.length(); i++) {dp[i][i] = true;}int start = 0;int maxLen = 1;for (int len = 2; len <= s.length(); len++) {for (int i = 0; i <= s.length() - len; i++) {int j = i + len - 1;if (s.charAt(i) == s.charAt(j)) {if (len == 2) {dp[i][j] = true;}else {dp[i][j] = dp[i + 1][j - 1];}}if (dp[i][j] && maxLen < len) {maxLen = len;start = i;}}}return s.substring(start, start + maxLen);}
}

279. 完全平方数

在这里插入图片描述
定义:dp[i] 和为 i 的完全平方数的最少数量 。
公式: dp[0]=0 dp[i]=Math.min(dp[i], dp[i-j*j]+1)

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j*j <= i;j++) {dp[i] = Math.min(dp[i], dp[i-j*j]+1);}}return dp[n];}
}

300. 最长递增子序列

在这里插入图片描述
定义:dp[i] 表示以nums[i]结尾的最长递增子序列的长度。
公式:dp[i]=max(dp[i],dp[j]+1)(其中 j<i 且 nums[j]<nums[i])

class Solution {public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}// dp[i] = dp[i-x] + 1int[] dp = new int[nums.length + 1];Arrays.fill(dp, 1);for (int i = 1; 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);}}if (dp[i] > dp[nums.length]) {dp[nums.length] = dp[i];}}return dp[nums.length];}
}

139. 单词拆分

在这里插入图片描述
状态定义dp[i] 表示 s[0:i] 是否可以拆分成 wordDict 里的单词组合。

转移方程dp[i]=dp[j]s[j:i]wordDictdp[i] = dp[j]

  • 遍历 j < i,如果 dp[j]true,且 s[j:i]wordDict 里的单词,则 dp[i] = true

初始化

  • dp[0] = true,表示空字符串可以被拆分。
import java.util.*;class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordSet = new HashSet<>(wordDict); // 用 HashSet 加速查找int n = s.length();boolean[] dp = new boolean[n + 1];dp[0] = true; // 空字符串可以拆分for (int i = 1; i <= n; i++) {for (int j = 0; j < i; j++) {if (dp[j] && wordSet.contains(s.substring(j, i))) {dp[i] = true;break; // 发现可拆分后立即终止,优化性能}}}return dp[n];}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ubuntu docker安装milvusdb

一、安装docker 1.更新软件包 sudo apt update sudo apt upgrade sudo apt-get install docker-ce docker-ce-cli containerd.io查看是否安装成功 docker -v二、使用国内的镜像下载 milvusdb Docker中国区官方镜像: https://registry.docker-cn.com milvusdb/milvus - Doc…

Redis如何实现持久化

Redis如何实现持久化 Redis默认将所有数据存储在内存中&#xff0c;虽然读写效率极高&#xff0c;但存在两大风险 数据易失性&#xff1a;进程重启或服务器宕机导致内存数据丢失。恢复成本高&#xff1a;无法直接通过内存重建大规模数据集。 Redis作为高性能的键值数据库&…

DeepSeek进阶应用(二):结合Kimi制作PPT(双AI协作教程)

&#x1f31f;引言&#xff1a; DeepSeek作为国产AI大模型&#xff0c;以强大的逻辑推理和结构化内容生成能力著称&#xff0c;擅长根据用户需求生成PPT大纲或Markdown文本&#xff1b;Kimi的PPT助手则能解析结构化内容并套用模板快速生成美观的PPT&#xff0c;两者结合实现“内…

查看分析日志文件、root密码不记得了,那应该怎么解决这些问题

下面我来讲解一下概念以及应该怎么做&#xff1a; 查看分析日志文件 一、主要日志文件 ♣ 内核及系统日志&#xff1a;这种日志数据由系统服务rsyslog统一管理&#xff0c;根据其主配置文件 /etc/rsyslog.conf 中的设置决定将内核消息及各种系统程序信息记录到什么位置。系统中…

mac电脑如何将wps接入deepseek (傻瓜式教学)

我的是mac pro m4 pro版本,版本不同页面或许有些许差异 首先将wps更新到最新的版本,并打开,点击 + 号 新建一个word文档 点击空白文档 点击开发工具,如果没有开发工具,可以先点击工具,在里面找到开发工具,然后点击宏安全性,设置为低,如下图所示

SpringMVC(五)拦截器

目录 拦截器基本概念 一 单个拦截器的执行 1 创建拦截器 2 SpringMVC配置&#xff0c;并指定拦截路径。 3 运行结果展示&#xff1a; 二 多个拦截器的执行顺序 三 拦截器与过滤器的区别 拦截器基本概念 SpringMVC内置拦截器机制&#xff0c;允许在请求被目标方法处理的…

3.17[A]CV

在计算机图形学中&#xff0c;反走样&#xff08;Antialiasing&#xff09; 是一种用于减少图像中锯齿状边缘&#xff08;aliasing artifacts&#xff09;的技术。当绘制曲线或图形时&#xff0c;由于像素的离散性&#xff0c;曲线边缘可能会出现锯齿状的失真。反走样通过考虑曲…

集成学习(上):Bagging集成方法

一、什么是集成学习&#xff1f; 在机器学习的世界里&#xff0c;没有哪个模型是完美无缺的。就像古希腊神话中的"盲人摸象"&#xff0c;单个模型往往只能捕捉到数据特征的某个侧面。但当我们把多个模型的智慧集合起来&#xff0c;就能像拼图一样还原出完整的真相&a…

【LangChain】理论及应用实战(5):Agent

文章目录 一、基本介绍1.1 Agent介绍1.2 Agent示例 二、几种主要的Agent类型2.1 ZERO_SHOT_REACT_DESCRIPTION2.2 CHAT_ZERO_SHOT_REACT_DESCRIPTION2.3 CONVERSATIONAL_REACT_DESCRIPTION2.4 CHAT_CONVERSATIONAL_REACT_DESCRIPTION2.5 OPENAI_FUNCTIONS 三、给Agent增加Memor…

口袋书签系统:AI 智能生成分类描述,省时又高效

口袋书签一键触达&#xff0c;免费使用&#xff1a;https://navfinder.cn/ 口袋书签系统新增了“根据收藏站点&#xff0c;AI自动生成分类描述”的功能&#xff0c;简要说明如下&#xff1a; 自动分析站点信息 系统会根据用户当前分类中的站点标题、标签等信息&#xff0c;结合…

AtCoder Beginner Contest 397 A - D题解

Tasks - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397) 本文为 AtCoder Beginner Contest 397 A - D题解 题目A: 代码(C): #include <bits/stdc.h>int main() {double n;std::cin >> n;if (n > 38.0) {std::cout << 1;}…

linux按照nginx

第一步先按照依赖gcc 一键安装上面四个依赖 Nginx的编译安装需要一些依赖库&#xff0c;如gcc、make、zlib、openssl等。可以使用yum命令安装这些依赖&#xff1a; yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel 创建目录 mkdir /usr/nginx 切换…

Muon: An optimizer for hidden layers in neural networks

引言 在深度学习领域&#xff0c;优化算法对模型训练效率和性能起着关键作用。从经典的随机梯度下降 (SGD) 及其动量法&#xff0c;到自适应优化方法 Adam/AdamW 等&#xff0c;一系列优化器大大加速了神经网络的收敛。然而&#xff0c;随着模型规模和数据量的爆炸式增长&…

数据结构与算法-图论-拓扑排序

前置芝士 概念 拓扑排序&#xff08;Topological Sorting&#xff09;是对有向无环图&#xff08;DAG&#xff0c;Directed Acyclic Graph&#xff09;的顶点进行排序的一种算法。它将图中的所有顶点排成一个线性序列&#xff0c;使得对于图中的任意一条有向边 (u, v)&#x…

市长海报/ Mayor‘s posters

AB 省 Bytetown 的市民无法忍受市长竞选活动的候选人随心所欲地将他们的选举海报贴在各个地方。市议会最终决定建造一面选举墙来放置海报&#xff0c;并引入以下规则&#xff1a; 每个候选人都可以在墙上放置一张海报。所有海报的高度都与墙壁的高度相同;海报的宽度可以是任意整…

LeetCode hot 100—验证二叉搜索树

题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 示例 1&#…

ccfcsp3402矩阵重塑(其二)

//矩阵重塑&#xff08;其二&#xff09; #include<iostream> using namespace std; int main(){int n,m,t;cin>>n>>m>>t;int c[10000][10000];int s0,sum0;int d[10000],k[100000];for(int i0;i<n;i){for(int j0;j<m;j){cin>>c[i][j];d[s…

MCP和Function Calling的区别

文章目录 1、什么是MCP1.1、定义和特点1.2、架构和工作原理3.3、MCP 的主要优势 2、什么是Function Calling3、MCP和Function Calling的区别4、总结 &#x1f343;作者介绍&#xff1a;双非本科大四网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;前三年专注于Java领域…

裂缝识别系统 Matlab GUI设计

使用说明 裂缝识别系统 Matlab GUI设计 &#xff0c;运行环境Matlab2023b及以上&#xff1b; 一种基于MATLAB图形用户界面&#xff08;GUI&#xff09;的裂缝自动识别系统&#xff0c;该系统利用数字图像处理技术实现裂缝图像的预处理&#xff0c;集成均衡化、噪声滤波、对比…

【源码分析】Nacos实例注册流程分析-事件驱动框架

【踩坑记录】 本人下载的Nacos 服务端版本是2.3.2&#xff0c;在开始进行源码编译便遇到问题&#xff0c;下面是各个问题记录 源码大量爆红 在最开始用Idea加载Maven项目的时候&#xff0c;发现项目中大量的代码爆红&#xff0c;提示其类或者包不存在&#xff0c;后来结果查…