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)
回文串的判断:
- 可以直接判断。
- 可以采用动态规划的方式进行记录,
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] 符合 题意
:
- 不同行已经确保了,需要判断不同列:
cols[0:row] != col
- 对角线的判断:
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] + 1
int[] 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];
}
}