給定一個(gè)三角形 triangle ，找出自頂向下的最小路徑和。
每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn) 在這里指的是 下標(biāo) 與 上一層結(jié)點(diǎn)下標(biāo) 相同或者等于 上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個(gè)結(jié)點(diǎn)。也就是說，如果正位于當(dāng)前行的下標(biāo) i ，那么下一步可以移動(dòng)到下一行的下標(biāo) i 或 i + 1 。
示例 1：
輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：如下面簡圖所示：
? ?2
? 3 4
?6 5 7
4 1 8 3
自頂向下的最小路徑和為?11（即，2?+?3?+?5?+?1?= 11）。
示例 2：輸入：triangle = [[-10]]
輸出：-10
?來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/triangle
動(dòng)態(tài)規(guī)劃解決
//dp[i][j]表示第i層第j列從上到下的最小和，i和j從0開始
public int minimumTotal(List<List<Integer>> triangle) {
int[][] dp=new int[triangle.size()][triangle.get(triangle.size()-1).size()];
dp[0][0]=triangle.get(0).get(0);
for(int i=1;i<dp.length;i++){
for(int j=0;j<triangle.get(i).size();j++){
if(j==0)
dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
else if(j==i)
dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
else
dp[i][j]=Math.min(dp[i-1][j]+triangle.get(i).get(j),dp[i-1][j-1]+triangle.get(i).get(j));
}
}
int min=Integer.MAX_VALUE;
for(int i=0;i<dp[dp.length-1].length;i++){
if(dp[dp.length-1][i]<min)
min=dp[dp.length-1][i];
}
return min;
}在一個(gè)由 '0' 和 '1' 組成的二維矩陣內(nèi)，找到只包含 '1' 的最大正方形，并返回其面積。
輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：4來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/maximal-square
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
此題粘貼官方題解
?代碼省略
131. 分割回文串
難度中等1469收藏分享切換為英文接收動(dòng)態(tài)反饋
給你一個(gè)字符串?
s，請你將?s?分割成一些子串，使每個(gè)子串都是?回文串?。返回?s?所有可能的分割方案。回文串?是正著讀和反著讀都一樣的字符串。
示例 1：
輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]示例 2：
輸入：s = "a" 輸出：[["a"]]
利用回溯算法解決
public List<List<String>> partition(String s) {
List<List<String>> lists=new ArrayList<>();
if(s==null||s.equals(""))
return lists;
ArrayList<String> list=new ArrayList<>();
backtreeing(s,0,list,lists);
return lists;
}
public static void backtreeing(String s,int start,List<String> list,List<List<String>> lists){
if(start==s.length()){
lists.add(new ArrayList<>(list));
return;
}
for(int i=start;i<s.length();i++){
String substring = s.substring(start, i + 1);
if(huiwen(substring)) {
StringBuilder stringBuilder = new StringBuilder();
String s1 = stringBuilder.append(substring).toString();
list.add(s1);
backtreeing(s,i+1,list,lists);
list.remove(list.size()-1);
}
}
}
public static boolean huiwen(String s){
StringBuilder stringBuilder=new StringBuilder(s);
if(s.equals(stringBuilder.reverse().toString()))
return true;
else
return false;
}?
395. 至少有 K 個(gè)重復(fù)字符的最長子串
難度中等811收藏分享切換為英文接收動(dòng)態(tài)反饋
給你一個(gè)字符串?
s?和一個(gè)整數(shù)?k?，請你找出?s?中的最長子串，?要求該子串中的每一字符出現(xiàn)次數(shù)都不少于?k?。返回這一子串的長度。示例 1：
輸入：s = "aaabb", k = 3 輸出：3 解釋：最長子串為 "aaa" ，其中 'a' 重復(fù)了 3 次。示例 2：文章來源：http://www.zghlxwxcb.cn/news/detail-423105.html
輸入：s = "ababbc", k = 2 輸出：5 解釋：最長子串為 "ababb" ，其中 'a' 重復(fù)了 2 次， 'b' 重復(fù)了 3 次。
?此題采用滑動(dòng)窗口未解決問題，故參考題解力扣文章來源地址http://www.zghlxwxcb.cn/news/detail-423105.html
class Solution {
public int longestSubstring(String s, int k) {
if (s.length() < k) return 0;
HashMap<Character, Integer> counter = new HashMap();
for (int i = 0; i < s.length(); i++) {
counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
}
for (char c : counter.keySet()) {
if (counter.get(c) < k) {
int res = 0;
for (String t : s.split(String.valueOf(c))) {
res = Math.max(res, longestSubstring(t, k));
}
return res;
}
}
return s.length();
}
}
作者：fuxuemingzhu
鏈接：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/solution/jie-ben-ti-bang-zhu-da-jia-li-jie-di-gui-obla/
來源：力扣（LeetCode）
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)算法leetcode刷題練習(xí)(1)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
