首页 > 其他分享 >LeetCode三则

LeetCode三则

时间:2024-04-26 21:45:51浏览次数:14  
标签:三则 删除 示例 int word1 word2 LeetCode dp

72. 编辑距离
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:
输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
public class Solution {
    public int minDistance(String word1, String word2) {
        /**
         * @author XiSoil
         * @date 2024/4/25 11:56
         *执行分布用时4ms,击败的85.49%Java用户
         *消耗内存分布43.76MB,击败的88.12%Java用户
         **/
        int m = word1.length();
        int n = word2.length();
        //dp[i][j]从word1的第0~i个字符变成word2的第0~j个字符,需要的最少操作次数
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        //如果word1[i-1] == word2[j-1],则不需要操作,否则需要操作
        //dp[i][j] = dp[i-1][j-1]
        // 如果word1[i-1]!= word2[j-1],则需要操作,需要选择三个操作中的最小值加1
        // dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
Solution
516. 最长回文子序列
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

回文序列定义为:从左往右读和从右往左读都是一样的序列。

示例 1:
输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:
输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

提示:
1 <= s.length <= 1000
s 仅由小写英文字母组成
class Solution {
    /**
     * @author XiSoil
     * @date 2024/04/25 11:54
     *执行分布用时24ms,击败的82.79%Java用户
     *消耗内存分布40.72MB,击败的96.87%Java用户
     **/
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n];

        //从后向前遍历还可以避免在状态转移过程中出现对同一行中未更新的状态进行访问的情况
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = prev + 2;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }

        return dp[n - 1];
    }
}
Solution
712. 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:
输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时,两个字符串相等,115 + 116 = 231 就是符合条件的最小和。

示例 2:
输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let",
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时,两个字符串都等于 "let",结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet",我们会得到 433 或 417 的结果,比答案更大。
public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        /**
         * @author XiSoil
         * @date 2024/4/25 12:09
         *执行分布用时20ms,击败的37.52%Java用户
         *消耗内存分布43.82MB,击败的39.97%Java用户
         **/
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
            }
        }
        return dp[m][n];
    }
}
Solution

 

标签:三则,删除,示例,int,word1,word2,LeetCode,dp
From: https://www.cnblogs.com/xxaxf/p/18160924

相关文章

  • 56. 合并区间(leetcode)
    https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked合并区间练习题typedefpair<int,int>PII;vector<PII>segs;classSolution{public:vector<vector<int>>merge(vector<vector<int>>......
  • LeetCode三则
    5.最长回文子串给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s仅由数字和英文字母组成cl......
  • 72. 编辑距离(leetcode)
    https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked这是一个难题,关于序列DP的,官方的题解较为难懂,这里有一位前辈解释的很好这里的状态定义是:dp[i][j]表示word1的前i个字母,转换成word2的前j个字母的最小步数classS......
  • LeetCode 1331. Rank Transform of an Array
    原题链接在这里:https://leetcode.com/problems/rank-transform-of-an-array/description/题目:Givenanarrayofintegers arr,replaceeachelementwithitsrank.Therankrepresentshowlargetheelementis.Therankhasthefollowingrules:Rankisanintegers......
  • [leetcode 周赛] 100276. 最短路径中的边
    solution使用dijkstra算法求出顶点0到每个顶点的最小距离dp[i]然后再从n-1开始遍历,如果dp[to]+w==dp[from],这条边符合条件importjava.util.*;classSolution{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();......
  • LeetCode 2326. Spiral Matrix IV
    原题链接在这里:https://leetcode.com/problems/spiral-matrix-iv/description/题目:Youaregiventwointegers m and n,whichrepresentthedimensionsofamatrix.Youarealsogiventhe head ofalinkedlistofintegers.Generatean mxn matrixthatconta......
  • LeetCode 1424. Diagonal Traverse II
    原题链接在这里:https://leetcode.com/problems/diagonal-traverse-ii/description/题目:Givena2Dintegerarray nums,return allelementsof nums indiagonalorderasshowninthebelowimages.Example1:Input:nums=[[1,2,3],[4,5,6],[7,8,9]]Output:[1,4,......
  • LeetCode三则
    63.不同路径II一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网格中的障碍物和空......
  • leetcode回文数
    给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,为121-。因此......
  • LeetCode三则
    三道动态规划62.不同路径一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?输入:m=3,n=7输出:28输入:m=3,n=2输出:3解释:......