算法题（滑动窗口、动态规划）

一、题目1.无重复字符的最长子串LC 32.找到字符串中所有字母异位词LC 4383.爬楼梯LC 704.杨辉三角LC 1185.打家劫舍LC 198二、滑动窗口1.无重复字符的最长子串LC 31分析用两个指针表示一个窗口left和right保证窗口中永远是不重复的字符串right向右移动遇到重复的字符串就把left向右移动到新字符上一次出现位置的下一个。每次移动right都要记录此时的字符串长度最后取最大值。2解答class Solution { public int lengthOfLongestSubstring(String s) { int length s.length(); if(length0){return 0;} int maxLength 0; MapCharacter,Integer map new HashMap(); int left 0; for(int right 0; rightlength; right){ char ch s.charAt(right); if(map.containsKey(ch)){ left Math.max(left, map.get(ch)1); } map.put(ch,right); maxLength Math.max(maxLength,right-left1); } return maxLength; } }2.找到字符串中所有字母异位词LC 4381分析遍历字符串s中所有长度等于p的子串通过统计 26 个小写字母的出现次数判断是否为异位词。若子串与p的字母计数完全一致则将子串起始下标加入结果列表最后输出所有的异位词下标。2解答class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger list new ArrayList(); int slen s.length(); int plen p.length(); if (slen plen) { return list; } for (int i 0; i slen - plen 1; i) { String str s.substring(i, i plen); if (isAnagrams(str, p)) { list.add(i); } } return list; } public boolean isAnagrams(String str, String p) { if(str.length()!p.length()){return false;} int[] countStr new int[26]; int[] countP new int[26]; for (int i 0; i str.length(); i) { char ch str.charAt(i); countStr[ch - a]; } for (int i 0; i p.length(); i) { char ch p.charAt(i); countP[ch - a]; } return Arrays.equals(countStr,countP); } }三、动态规划1.爬楼梯LC 701分析定义dp[i]为爬到第i阶台阶的总方法数。根据每次可爬 1 阶或 2 阶得到递推式dp[i] dp[i-1] dp[i-2]。初始化dp[0] 1、dp[1] 1保证递推正常启动。循环计算至dp[n]最终返回该值即为答案。2解答class Solution { public int climbStairs(int n) { int[] dp new int[n1]; dp[1] 1; dp[0] 1; for(int i 2; in; i){ dp[i] dp[i-1]dp[i-2]; } return dp[n]; } }2.杨辉三角LC 1181分析每行第一个和最后一个数字都是 1;中间每个数字 上一行它左上方正上方 的和;递推公式c[i][j] c[i-1][j-1]c[i-1][j];这段代码先固定首尾为 1再用上层数字计算中间值逐行构建出完整的杨辉三角。2解答class Solution { public ListListInteger generate(int numRows) { ListListInteger c new ArrayList(numRows); c.add(List.of(1)); for(int i 1; inumRows; i ){ ListInteger row new ArrayList(i1); row.add(1); for(int j 1; ji; j){ row.add(c.get(i-1).get(j-1)c.get(i-1).get(j)); } row.add(1); c.add(row); } return c; } }3.打家劫舍LC 1981分析边界处理只有一间房屋时直接偷这间返回nums[0]。dp 数组定义dp[i]表示前i1间房屋能偷到的最大金额。初始化第一间直接偷第二间选金额更大的一间。递推公式对第i间要么不偷取前一间最大值要么偷取前两间最大值加当前金额取两者较大值。结果遍历完成后最后一位dp[nums.length-1]即为全局最大可偷金额。2解答class Solution { public int rob(int[] nums) { if(nums.length1){ return nums[0]; } int[] dp new int[nums.length]; dp[0] nums[0]; dp[1] Math.max(nums[0],nums[1]); for(int i 2; inums.length; i){ dp[i] Math.max(dp[i-1], dp[i-2]nums[i]); } return dp[nums.length-1]; } }