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