当前位置: 首页 > article >正文

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] + 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];
    }
}


http://www.kler.cn/a/589046.html

相关文章:

  • windows 下用docker 部署nginx
  • unity基础——Navigation导航系统
  • 网络安全设备系统集成方案 系统集成和网络安全
  • 命令行参数和环境变量【Linux操作系统】
  • 【论文笔记】Best Practices and Lessons Learned on Synthetic Data for Language Models
  • BigEvent项目后端学习笔记(一)用户管理模块 | 注册登录与用户信息全流程解析(含优化)
  • 数据增强常见问题与解决方案:提升AI模型性能的关键技巧
  • PyCharm如何有效地添加源与库?
  • CSS中固定定位
  • 错误记录: git 无法连接到github
  • Apache Pol (excel)
  • 算法——图论——关键活动
  • Python的那些事第四十五篇:继承自Nose的测试框架Nose2
  • 区间预测 | Matlab实现QRBiTCN分位数回归双向时间卷积神经网络注意力机制时序区间预测
  • Ubuntu 一站式初始化笔记
  • 【sql靶场】第13、14、17关-post提交报错注入保姆级教程
  • JVM常用概念之超态虚拟调用
  • 解析GNGGA数据,C语言单片机
  • AI是如何实现屏幕触控防水? 实测华为畅享70X
  • Redis监控:从睁眼瞎到千里眼的进化史