【二刷hot-100】day 3

目录

1.最小覆盖子串

2.二叉树展开为链表

3.面试题 17.14. 最小K个数

1.最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
           char [] s1=s.toCharArray();
           int m=s1.length;
           int retleft=-1;
           int retright=m;
           int [] cnts=new int[128];
           int [] cntt=new int[128];
           for(char c: t.toCharArray()){
             cntt[c]++;
           }

           int left=0;
           for(int right=0;right<m;right++){
            cnts[s1[right]]++;
            while(isCovered(cnts,cntt)){
                if(right-left<retright-retleft){
                    retleft=left;
                    retright=right;
                }
                cnts[s1[left]]--;
                left++;
            }
           }
           return retleft<0?"":s.substring(retleft,retright+1);
    }

    private boolean isCovered(int [] cnts,int [] cntt ){
        for(int i='A';i<='Z';i++){
            if(cnts[i]<cntt[i]){
                return false;
            }
        }

        for(int i='a';i<='z';i++){
            if(cnts[i]<cntt[i]){
                return false;
            }
        }
        return true;
    }
}

2.二叉树展开为链表

先序遍历的写法。

 就是找出左子树最右边的节点以便把右子树接过来。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
         while(root!=null){
             //如果左子树为null，直接考虑下一个节点
             if(root.left==null){
                root=root.right;
             }else{
                //查找左子树的最右节点
                TreeNode pre=root.left;
                while(pre.right!=null){
                    pre=pre.right;
                }
                //拼接右子树
                pre.right=root.right;
                //root的右子树换上左子树
                root.right=root.left;
                //root的左子树置空
                root.left=null;
                //下一个节点
                root=root.right;
             }
         }
    }
}

3.面试题 17.14. 最小K个数

可以直接sort然后输出，但时间复杂度较高。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        //升序的优先队列，小根堆排序
        PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->a-b);
        for (int i:arr) q.add(i);
        int [] ret=new int[k];
        for(int i=0;i<k;i++) ret[i]=q.poll();
        return ret;
    }
}

ps: 

升序的优先队列。