后20题

394. 字符串解码*

Stack<Integer>numStack=new Stack<>();
Stack<StringBuilder> opeStack=new Stack<>();
StringBuilder builder=new StringBuilder();
int count=0;
for (char c : s.toCharArray()) {
  if(c>='0'&&c<='9'){
    count=10*count+c-'0';
  }else if(c=='['){
    numStack.push(count);
    opeStack.push(builder);
    builder=new StringBuilder();
    count=0;
  }else if(c==']'){
    int num=numStack.pop();
    StringBuilder temp = opeStack.pop();
    for(int i=0;i<num;i++){
      temp.append(builder);
    }
    builder=temp;
  }else{//如果是字符
    builder.append(c);
  }
}
return builder.toString();

438. 找到字符串中所有字母异位词*

//使用int数组+滑动窗口来判断
List<Integer>res=new ArrayList<>();
if(s.length()<p.length()){
  return res;
}
int[]sMap=new int[26];
int[]pMap=new int[26];
for(int i=0;i<p.length();i++){
  sMap[s.charAt(i)-'a']++;
  pMap[p.charAt(i)-'a']++;
}
if(Arrays.equals(sMap,pMap)){
  res.add(0);
}
for(int i=0;i<s.length()-p.length();i++){
  sMap[s.charAt(i)-'a']--;
  sMap[s.charAt(i+p.length())-'a']++;
  if(Arrays.equals(sMap,pMap)){
    res.add(i+1);
  }
}
return res;

448. 找到所有数组中消失的数字*

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int left=0;
        int right=nums.length;
        while (left<right){
            if(nums[left]!=left+1&&nums[nums[left]-1]!=nums[left]){
                swap(nums,left,nums[left]-1);
            }else if(nums[left]!=left+1&&nums[nums[left]-1]==nums[left]){
                left++;
            }else if(nums[left]==left+1){
                left++;
            }
        }
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i+1){
            res.add(i+1);
        }
    }
        return res;
    }
    private void swap(int[]nums,int left,int right){
        int temp=nums[right];
        nums[right]=nums[left];
        nums[left]=temp;
        return;
    }
}

461. 汉明距离

int num=x^y;
int res=0;
while (num!=0){
  num&=num-1;
  res++;
}
return res;

543. 二叉树的直径

if(root==null){
  return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
res=Math.max(res,left+right);
return Math.max(left,right)+1;

560. 和为 K 的子数组

if(nums.length==1&&k!=nums[0]){
  return 0;
}
Map<Integer,Integer> map=new HashMap<>();
map.put(0,1);
int sum=0;
int res=0;
for(int i=0;i<nums.length;i++){
  sum+=nums[i];
  map.put(sum,map.getOrDefault(sum,0)+1);
  if(map.containsKey(sum-k)){
    res+=map.get(sum-k);
  }
}
return res;

581. 最短无序连续子数组

int right=-1;
int rightNums=nums[0];
for(int i=1;i<nums.length;i++){
  if(nums[i]<rightNums){
    right=i;
  }else{
    rightNums=nums[i];
  }
}
int left=0;
int leftNums=nums[nums.length-1];
for(int i=nums.length-2;i>=0;i--){
  if(nums[i]>leftNums){
    left=i;
  }else{
    leftNums=nums[i];
  }
}
return right-left+1;

621. 任务调度器

if(n==0){
  return tasks.length;
}
int[]map=new int[26];
for(int i=0;i<tasks.length;i++){
  map[tasks[i]-'A']++;
}
Arrays.sort(map);
int maxTask=map[25];
int maxCount=1;
for(int i=25;i>=1;i--){
  if(map[i]==map[i-1]){
    maxCount++;
  }else{
    break;
  }
}
int res=maxTask*(n+1)+maxCount;
return Math.max(tasks.length,res);

1044. 最长重复子串*

class Solution {
    public String longestDupSubstring(String s) {
        String res="";
        int left=0;
        int right=s.length()-1;
        while (left<=right){
            int mid=(left+right+1)/2;
            String result = check(s, mid);
            if(!result.equals("")){
                res=result;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return res;
    }
    private String check(String s,int len){
        String res="";
        Set<Integer>set=new HashSet<>();
        for(int i=0;i<=s.length()-len;i++){
            String substring = s.substring(i, i + len);
            int hashCode=substring.hashCode();
            if(set.contains(hashCode)&&s.indexOf(substring)!=i){
                res=s.substring(i,i+len);
                return res;
            }
            set.add(hashCode);
        }
        return res;
    }
}