11.14打卡

1. 最小覆盖字串（76）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        int tot = 0;
        int [] c1= new int[60],c2=new int[60];
        // c1 存储t中出现的字符及字数
        for(char x:t.toCharArray()){
            if (++c1[getId(x)]==1) //统计t中字母出现的次数，在对应字母索引位置
            tot++; //tot记录出现的字符种类数
        }
        String ans ="";
        //j 标识左边界，i标识右边界
        for(int i =0,j=0;i<n;i++){
            int idx1= getId(s.charAt(i)); //获取s的字符
            if(++c2[idx1]==c1[idx1]) //如果已经达到了该字母出现的总字数了，就相当于该字符已经可以不用搜索了，可以少搜查一个种类，表明一个字符已经匹配完成
            tot--; //总字符种类-1
            //每当往右移一位，就要判断左边界是可以右移并保证c2>c1，使得当前tot不增加
            while(j<i){
                int idx2=getId(s.charAt(j)); 
                if(c2[idx2]>c1[idx2]&&--c2[idx2]>=0)  
                j++;
                else break;
            }
            if(tot==0 && (ans.length()==0||ans.length()>i-j+1))  //如果长度为0 或者找到更短的就更新
            ans=s.substring(j,i+1);

        }
        return ans;
    }

    //返回字母所在的序号，比如A 就在0，小写也是一样
    public int getId(char x){
        return x>='A'&&x<='Z' ? x-'A' +26:x-'a';
    }
}

2.组合（77）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
          List<List<Integer>> res = new ArrayList<>();
        if(k<=0||n<k){
            return  res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfsconbime(n,k,1,path,res);
    return res;
    }

    private void dfsconbime(int n, int k, int begin,Deque<Integer> path, List<List<Integer>> res) {
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
         for (int i = begin; i <=n-(k-path.size())+1 ; i++){
            path.addLast(i);
            dfsconbime(n,k,i+1,path,res);
            path.removeLast();
        }      
    }
}

3. 子集（78）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
       List<List<Integer>> ans = new ArrayList<>();
        bfssubsets(0,nums,ans,new ArrayList<Integer>());
        return ans;
    }

    private void bfssubsets(int i, int[] nums, List<List<Integer>> ans, ArrayList<Integer> list) {
   
        ans.add(new ArrayList<>(list));
        
        for (int j = i; j <nums.length ; j++) {
            list.add(nums[j]);
            bfssubsets(j+1,nums,ans,list);
            list.remove(list.size()-1);
        }
       
    }
}

4. 单词搜索（79）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思想： 回溯

class Solution {
  
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfsexist(board, words, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    private boolean dfsexist(char[][] board,char[] words, int i, int j, int k) {
        if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=words[k])
            return false;
        if(k==words.length-1)
            return true;
        board[i][j]='\0';
        boolean res = dfsexist(board,words,i+1,j,k+1)||dfsexist(board,words,i,j+1,k+1)
                ||dfsexist(board,words,i-1,j,k+1)||dfsexist(board,words,i,j-1,k+1);
        board[i][j]=words[k];
        return res;
    }

}

5. 删除有序数组中的重复项（80）

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

思想： 快慢指针

class Solution {
    public int removeDuplicates(int[] nums) {
 int n = nums.length;
        if(n<=2)
            return n;
        int slow = 2,fast =2;
        while (fast<n){
            if(nums[slow-2]!=nums[fast]){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}