给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 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
动态规划解决
//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; }
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
此题粘贴官方题解
代码省略
131. 分割回文串
难度中等1469收藏分享切换为英文接收动态反馈
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 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 个重复字符的最长子串
难度中等811收藏分享切换为英文接收动态反馈
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1：
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
此题采用滑动窗口未解决问题，故参考题解力扣
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(); } }
