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

骑猪看日落 2023-09-25 23:32 106阅读 0赞

> 给定一个三角形 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  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

此题粘贴官方题解

![b5a74cd889b240d6bba3c3b19d524975.png][]

代码省略

> [131. 分割回文串][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 个重复字符的最长子串][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 次。

此题采用滑动窗口未解决问题，故参考题解[力扣][Link 1]

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）

[b5a74cd889b240d6bba3c3b19d524975.png]: https://img-blog.csdnimg.cn/b5a74cd889b240d6bba3c3b19d524975.png
[131.]: https://leetcode.cn/problems/palindrome-partitioning/
[395. _ K]: https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
[Link 1]: 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/