1.最小覆盖子串
class Solution { public String minWindow(String s, String t) { HashMap<Character, Integer> map1 = new HashMap<>(); HashMap<Character, Integer> map2 = new HashMap<>(); int m = s.length(), n = t.length(); boolean flag = false; for(int i = 0;i<n;i++){ map1.put(t.charAt(i), map1.getOrDefault(t.charAt(i), 0)+1); } Deque<Character> queue = new LinkedList<>(); int cnt = 0; String res = s; for(int i = 0, j = 0;j<m;j++){ char temp = s.charAt(j); queue.addLast(temp); if(map1.containsKey(temp)){ int a = map1.get(temp); if(map2.containsKey(temp)){ int b = map2.get(temp); if(a>b){ map2.put(temp,b+1); cnt++; }else{ map2.put(temp,b+1); } }else{ map2.put(temp,1); cnt++; } } while(i<j){ char temp1 = s.charAt(i); if(!map2.containsKey(temp1)){ queue.removeFirst(); i++; }else{ int p = map1.get(temp1), q = map2.get(temp1); if(q>p){ map2.put(temp1,q-1); queue.removeFirst(); i++; }else{ break; } } } //System.out.println(cnt); if(cnt == n){ if(queue.size()<=res.length()){ flag = true; StringBuilder string = new StringBuilder(); for(char cur : queue){ string.append(cur); } res = string.toString(); //System.out.println(res); } } } if(flag == false){ return ""; } return res; } }
2.找到字符串中所有字母异位词
class Solution { //滑动窗口算法+哈希表存储 public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new LinkedList<>(); //这个哈希表存储子串的结构 HashMap<Character, Integer> map1 = new HashMap<>(); //这个哈希表存储当前滑动窗口的元素。 HashMap<Character, Integer> map2 = new HashMap<>(); int m = s.length(), n = p.length(); for(int i = 0;i<n;i++){ map1.put(p.charAt(i), map1.getOrDefault(p.charAt(i),0)+1); } //cnt代表了滑动窗口中所需的元素个数 int cnt = 0; for(int i = 0, j = 0;j<m;j++){ //遍历当前元素 char temp = s.charAt(j); //如果该元素值存在于子串中 if(map1.containsKey(temp)){ int a = map1.get(temp); //判断滑动窗口中概元素值的个数与总个数 if(map2.containsKey(temp)){ int b = map2.get(temp); //如果不够,则加入该元素 if(a>b){ map2.put(temp,b+1); cnt++; //如果超出则遍历左断点,一次出来滑动窗口的值,直到遇到该元素(因为这里要求连续) }else{ while(s.charAt(i)!=temp&&i<j){ if(map2.containsKey(s.charAt(i))){ map2.put(s.charAt(i), map2.getOrDefault(s.charAt(i),0)-1); cnt--; } i++; } i++; } //如果滑动窗口不存在该元素,但该元素属于子川,则加一 }else{ map2.put(temp,1); cnt++; } //如果该元素不属于子川,因为要求连续存储,所以这里会将滑动窗口清空 }else{ for(char tt : map2.keySet()){ map2.put(tt,0); } cnt = 0; i = j+1; }//滑动窗口元素满足要求,则加入左端点 if(cnt == n){ res.add(i); } } return res; } }
3.正则表达式匹配
class Solution { public boolean isMatch(String s, String p) { int m = s.length() + 1, n = p.length() + 1; boolean[][] dp = new boolean[m][n]; dp[0][0] = true; for(int j = 2; j < n; j += 2) dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*'; for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = p.charAt(j - 1) == '*' ? dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') : dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1)); } } return dp[m - 1][n - 1]; } }
4.路径总和3
class Solution { public HashMap<Long, Integer> map; public long temp,target; public int res; public int pathSum(TreeNode root, int targetSum) { map = new HashMap<>(); map.put(0L,1); target = (long)targetSum; temp = 0L;res = 0; dfs(root); return res; } public void dfs(TreeNode root){ if(root == null){ return; } temp += root.val; long t = temp - target; if(map.containsKey(t)){ res += map.get(t); } map.put(temp,map.getOrDefault(temp,0)+1); dfs(root.left); if(root.left!=null){ map.put(temp,map.get(temp)-1); temp-=root.left.val; } dfs(root.right); if(root.right!=null){ map.put(temp,map.get(temp)-1); temp-=root.right.val; } } }
标签:map,HashMap,temp,int,2023.2,算法,root,dp From: https://www.cnblogs.com/lyjps/p/17091030.html