中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

企業(yè)網(wǎng)站建設(shè)費(fèi)用深圳免費(fèi)外鏈生成器

企業(yè)網(wǎng)站建設(shè)費(fèi)用深圳,免費(fèi)外鏈生成器,個(gè)人公眾號可以用wordpress,開發(fā)網(wǎng)站監(jiān)控工具子序列類型問題 一、經(jīng)典動態(tài)規(guī)劃:編輯距離 基于labuladong的算法網(wǎng)站,經(jīng)典動態(tài)規(guī)劃:編輯距離; 總結(jié): 一般來說涉及到兩個(gè)字符串的問題,需要依賴上一次的各種操作,一般使用dp table&#xff…

子序列類型問題

一、經(jīng)典動態(tài)規(guī)劃:編輯距離

基于labuladong的算法網(wǎng)站,經(jīng)典動態(tài)規(guī)劃:編輯距離;

總結(jié):

  • 一般來說涉及到兩個(gè)字符串的問題,需要依賴上一次的各種操作,一般使用dp table;
  • dp數(shù)組和dp函數(shù):
    • 本質(zhì)上是一樣的;
    • 只不過dp數(shù)組是利用數(shù)組去體現(xiàn)結(jié)果值;
    • dp函數(shù)是在函數(shù)返回結(jié)果中體現(xiàn);
[72]編輯距離//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// 利用 dp table 進(jìn)行自下而上的求解public int minDistance(String word1, String word2) {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];// base casefor (int i = 1; i <= m; i++) {dp[i][0] = i;}for (int i = 1; i <= n; i++) {dp[0][i] = i;}// 開始遍歷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] = min(dp[i][j - 1] + 1,// 添加dp[i - 1][j] + 1,// 刪除dp[i - 1][j - 1] + 1// 替換);}}}return dp[m][n];}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));}
}
//leetcode submit region end(Prohibit modification and deletion)

二、動態(tài)規(guī)劃設(shè)計(jì):最大子數(shù)組

基于labuladong的算法網(wǎng)站,動態(tài)規(guī)劃設(shè)計(jì):最大子數(shù)組;

力扣第53題,最大子數(shù)組和;

[53]最大子數(shù)組和//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// dp tablepublic int maxSubArray(int[] nums) {int length = nums.length;// 需要明確dp數(shù)組的定義,dp[i]:以nums[i]為結(jié)尾時(shí),最大連續(xù)子數(shù)組的最大和int[] dp = new int[length];// base casedp[0] = nums[0];for (int i = 1; i < length; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);}// 遍歷得到最大值int res = Integer.MIN_VALUE;for (int i = 0; i < length; i++) {if (dp[i] > res) {res = dp[i];}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

三、經(jīng)典動態(tài)規(guī)劃:最長公共子序列

基于labuladong的算法網(wǎng)站,經(jīng)典動態(tài)規(guī)劃:最長公共子序列;

1、最長公共子序列

力扣第1143題,最長公共子序列;

[1143]最長公共子序列//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// dp tablepublic int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();// dp[i][j] 代表字符串 text1[0,i] 和 text2[0,j] 的最長公共子序列長度int[][] dp = new int[m + 1][n + 1];// base casefor (int i = 0; i <= m; i++) {dp[m][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][n] = 0;}// 開始遍歷子串for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}// 返回return dp[m][n];}int max(int a, int b, int c) {return Math.max(a, Math.max(b, c));}
}
//leetcode submit region end(Prohibit modification and deletion)

2、兩個(gè)字符串的刪除操作

力扣第583題,兩個(gè)字符串的刪除操作;

[583]兩個(gè)字符串的刪除操作//leetcode submit region begin(Prohibit modification and deletion)
class Solution {/*** @param word1* @param word2* @return 返回使得 word1 和 word2 相同所需的最小步數(shù)*/public int minDistance(String word1, String word2) {int length = get(word1, word2);return word1.length() + word2.length() - length - length;}// 求 word1 和 word2 的最長公共子序列int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[m][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][n] = 0;}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] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

3、兩個(gè)字符串的最小ASCII刪除和

力扣第712題,兩個(gè)字符串的最小ASCII刪除和;

[712]兩個(gè)字符串的最小ASCII刪除和//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minimumDeleteSum(String s1, String s2) {int m = s1.length();int n = s2.length();// dp[i][j] 使字符串 s1[0,i] 和 s2[0,j] 兩個(gè)相等所需要刪除的字符的 ASCII 值的最小和int[][] dp = new int[m + 1][n + 1];// base casefor (int i = 1; i <= m; i++) {dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);}for (int i = 1; i <= n; i++) {dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);}// 開始遍歷for (int i = 1; i <= m; i++) {int code1 = s1.charAt(i - 1);for (int j = 1; j <= n; j++) {int code2 = s2.charAt(j - 1);// 判斷此時(shí)兩個(gè)字母是否相等if (code1 == code2) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

四、動態(tài)規(guī)劃之子序列問題解題模板

基于labuladong的算法網(wǎng)站,動態(tài)規(guī)劃之子序列問題解題模板;

1、最長回文子序列

力扣第516題,最長回文子序列;

[516]最長回文子序列//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// 可以看成兩個(gè)字符串,找最長公共子序列的長度public int longestPalindromeSubseq(String s) {StringBuffer sb = new StringBuffer();int length = s.length();for (int i = length - 1; i >= 0; i--) {sb.append(s.charAt(i));}return get(s, sb.toString());}int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 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] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

2、讓字符串成為回文串的最少插入次數(shù)

力扣第1312題,讓字符串成為回文串的最少插入次數(shù);

[1312]讓字符串成為回文串的最少插入次數(shù)//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minInsertions(String s) {StringBuffer sb = new StringBuffer();int length = s.length();for (int i = length - 1; i >= 0; i--) {sb.append(s.charAt(i));}int max = get(s, sb.toString());return length - max;}int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 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] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)
http://www.risenshineclean.com/news/54811.html

相關(guān)文章:

  • 網(wǎng)站開發(fā)兼職接單平臺長沙關(guān)鍵詞優(yōu)化公司電話
  • 邯鄲外貿(mào)網(wǎng)站建設(shè)公司成都網(wǎng)站建設(shè)公司
  • 政府網(wǎng)站建設(shè)的存在問題網(wǎng)址查詢工具
  • 如何實(shí)現(xiàn)網(wǎng)站開發(fā)太原網(wǎng)站建設(shè)制作
  • 廣州建筑集團(tuán)股份有限公司杭州seo排名優(yōu)化外包
  • 如何提取網(wǎng)頁中的視頻seo主要做什么
  • 龍崗區(qū)住房建設(shè)局網(wǎng)站品牌營銷方案
  • 云盤做網(wǎng)站關(guān)鍵詞推廣營銷
  • 廈門網(wǎng)站建設(shè)哪家好優(yōu)化網(wǎng)絡(luò)的軟件
  • 企業(yè)網(wǎng)站建設(shè)webbj免費(fèi)網(wǎng)站優(yōu)化排名
  • 湛江疫情最新通報(bào)五年級上冊語文優(yōu)化設(shè)計(jì)答案
  • 什么是網(wǎng)站解決方案武漢網(wǎng)絡(luò)推廣有哪些公司
  • 網(wǎng)站留言評論功能深圳百度seo代理
  • 網(wǎng)站建設(shè)合同印花稅稅目外鏈?zhǔn)珍浘W(wǎng)站
  • vs2015網(wǎng)站開發(fā)教程seo搜索優(yōu)化待遇
  • 青島做網(wǎng)站的公司深圳市前十的互聯(lián)網(wǎng)推廣公司
  • asp網(wǎng)站后臺安全退出購物網(wǎng)站
  • 做網(wǎng)站哪家南京做網(wǎng)站網(wǎng)站關(guān)鍵詞挖掘
  • 網(wǎng)站建設(shè)市場前景體育新聞最新消息
  • 網(wǎng)站沒有被搜索引擎收錄東莞seo排名公司
  • 愛情動做網(wǎng)站推薦收錄批量查詢
  • 國內(nèi)做賭博網(wǎng)站代理怎么樣加快百度收錄的方法
  • 分布式移動網(wǎng)站開發(fā)技術(shù)一個(gè)品牌的策劃方案
  • 南昌哪里可以做電商網(wǎng)站seo收索引擎優(yōu)化
  • seo策略是什么青島seo推廣
  • 網(wǎng)站開發(fā)方向行業(yè)現(xiàn)狀青島網(wǎng)站建設(shè)制作公司
  • 建網(wǎng)站報(bào)價(jià) 優(yōu)幫云web免費(fèi)網(wǎng)站
  • 常州做沙灘旗的公司網(wǎng)站做網(wǎng)絡(luò)優(yōu)化的公司排名
  • 安裝網(wǎng)站系統(tǒng)個(gè)人網(wǎng)絡(luò)銷售平臺
  • 建設(shè)獨(dú)立服務(wù)器網(wǎng)站成人技能培訓(xùn)