# 数据结构算法leetcode刷题练习(1)

2

3 4

6 5 7

4 1 8 3

  //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;
}

131. 分割回文串

  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()){
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();
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 个重复字符的最长子串

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();
}
}


|
5天前
|

【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

20 2
|
3天前
|

LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
15 6
|
3天前
|

LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
13 1
|
3天前
|

LeetCode经典算法题：预测赢家+香槟塔java解法
LeetCode经典算法题：预测赢家+香槟塔java解法
13 1
|
5天前
|

【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色

15 3
|
5天前
|
Python
【Leetcode刷题Python】50. Pow(x, n)

9 1
|
5天前
|
Python
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点

8 1
|
5天前
|

【Leetcode刷题Python】73. 矩阵置零

7 0
|
3天前
|

LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
6 0
|
3天前
|

LeetCode初级算法题：子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题：子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
10 0