目录

1.最小覆盖子串

2.二叉树展开为链表

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

1.最小覆盖子串

 

java">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.二叉树展开为链表

先序遍历的写法。

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

java">/*** 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然后输出，但时间复杂度较高。

 

 

java">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: 

升序的优先队列。