算法--2023.2.2

1.力扣72--编辑距离

class Solution {
    //典型动态对话问题
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        //这里需要初始化边界，代表如果另一个字符串未空，我们需要修改多少个字符串才能一致
        for(int i = 0;i<=m;i++){
            dp[i][0] = i;
        }
        for(int i = 0;i<=n;i++){
            dp[0][i] = i;
        }
        //动态规划的遍历
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                //如果当前两个字符相等，则从两者前一个、删除+1，插入+1中选一个最小的
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j]+1,dp[i][j-1]+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[m][n];

    }
}

2.力扣112--路径总和

class Solution {
    public int temp = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        temp += root.val;
        if(temp == targetSum&&root.left==null&&root.right==null){
            return true;
        }
        boolean left = hasPathSum(root.left,targetSum);
        if(root.left!=null){
            temp -= root.left.val;
        }
        boolean right = hasPathSum(root.right,targetSum);
        if(root.right!=null){
            temp -= root.right.val;
        }

        return left||right;

    }
}

3.力扣113--路径总和2

class Solution {
    public Deque<Integer> path;
    public List<List<Integer>> res;
    public int temp;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        path = new LinkedList<>();
        res = new LinkedList<>();
        temp = 0;
        dfs(root,targetSum);
        return res;
    }
    public void dfs(TreeNode root, int targetSum){
        if(root == null){
            return;
        }
        temp += root.val;
        path.addLast(root.val);
        if(temp == targetSum&&root.left == null&&root.right == null){
            res.add(new LinkedList<>(path));
        }
        dfs(root.left,targetSum);
        if(root.left!=null){
            temp -= root.left.val;
            path.removeLast();
        }
        dfs(root.right,targetSum);
        if(root.right!=null){
            temp -= root.right.val;
            path.removeLast();
        }
    }
}