day15-算法每日4题

64. 最小路径和

class Solution {   /     * 给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。     * 说明：每次只能向下或者向右移动一步。     * 动态规划     * 从左上角(0,0)->(i,j)的最小路径和     * dp(grid,i,j) = Math.min( dp(grid,i - 1 ,j) , dp(grip,i,j-1 ) ) + grid[i][j];     */    // 备忘录    int[][] memo;    public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0) return 0; /// 列长 int m = grid.length; // 行长 int n = grid[0].length; // 记录到每一个坐标时的路径和 memo = new int[m][n]; // 先给出默认值 for (int[] row : memo) {     Arrays.fill(row, 0); } return dp(grid, m - 1, n - 1);    }    private int dp(int[][] grid, int i, int j) { // 如果只有一个元素 if (i == 0 && j == 0) return grid[0][0]; if (i < 0 || j < 0) return Integer.MAX_VALUE; // 避免重复计算 if (memo[i][j] != 0) {     return memo[i][j]; } // 将计算记过记录备忘录 memo[i][j] = Math.min(dp(grid, i - 1, j), dp(grid, i, j - 1)) + grid[i][j]; return memo[i][j];    }}

658. 找到 K 个最接近的元素

class Solution {    /     * 给定一个 排序好 的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。     * 
     * 整数 a 比整数 b 更接近 x 需要满足：     * 
     * |a - x| < |b - x| 或者     * |a - x| == |b - x| 且 a < b     * 我们可以将数组中的元素按照与目标 x 的差的绝对值排序，排好序后前 k 个元素就是我们需要的答案。     */    public List<Integer> findClosestElements(int[] arr, int k, int x) { if (arr == null || arr.length == 0) return null; // 自动装箱进行初始化 List<Integer> res = Arrays.stream(arr).boxed()  .sorted((a, b) -> Objects.equals(a, b) ? 0 : Math.abs(a - x) - Math.abs(b - x))  .collect(Collectors.toList()); // |a - x| - |b - x | 升序 // 截取k个 res = res.subList(0, k); Collections.sort(res); return res;    }}

3. 无重复字符的最长子串

class Solution {  /     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。     * 滑动窗口     */    public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; // 用来存储每个字母出现的次数 // 每次循环窗口里面的内容有没有重复来进行左边界和右边界来移动 Set<Character> set = new HashSet<>(); // 窗口的左边界和右边界 int l = 0, r = 0; int maxWin = 0; // 左右两边不能超过字符串的长度 while (l < s.length() && r < s.length()) {     // 判断当前扩张边界的字符是否已经在set中存在了     if (set.contains(s.charAt(r))) {  // 将set中左边界元素移除,并且左边界往前移动  set.remove(s.charAt(l));  l++;     } else {  // 将右边界的元素添加到set中,并且右边界往前移动  set.add(s.charAt(r));  r++;  // 计算最大窗口,右边界 - 左边界  maxWin = Math.max(maxWin, r - l);     } } return maxWin;    }}

824. 山羊拉丁文

class Solution {  /     * 给你一个由若干单词组成的句子sentence ，单词间由空格分隔。每个单词仅由大写和小写英文字母组成。     * 请你将句子转换为 “山羊拉丁文（Goat Latin）”（一种类似于 猪拉丁文- Pig Latin 的虚构语言）。山羊拉丁文的规则如下：     * 如果单词以元音开头（'a', 'e', 'i', 'o', 'u'），在单词后添加"ma"。     * 例如，单词 "apple" 变为 "applema" 。     * 如果单词以辅音字母开头（即，非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。     * 例如，单词 "goat" 变为 "oatgma" 。     * 根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从 1 开始。     * 例如，在第一个单词后添加 "a" ，在第二个单词后添加 "aa" ，以此类推。     * 返回将 sentence 转换为山羊拉丁文后的句子。     */      Set<Character> vowels = new HashSet<Character>() { {     add('a');     add('e');     add('i');     add('o');     add('u');     add('A');     add('E');     add('I');     add('O');     add('U'); }    };    String suffix = "ma";    public String toGoatLatin(String sentence) { if (sentence == null || sentence.length() == 0) return ""; StringBuilder res = new StringBuilder(); String[] words = sentence.split(" "); for (int i = 0; i < words.length; i++) {     // 处理单个单词     StringBuilder generatedWord = generateSingle(words[i]).append("a".repeat(Math.max(0, i + 1))).append(" ");     res.append(generatedWord); } return res.toString().trim();    }    private StringBuilder generateSingle(String word) { StringBuilder res = new StringBuilder(); // 判断第一个字母是不是元音字母 if (vowels.contains(word.charAt(0))) res = new StringBuilder(word + suffix); else res.append(word.substring(1)).append(word.charAt(0)).append(suffix); return res;    }}