昨天天气太好，睡过了
- 最小的 K 个数
可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字；
Partition 来源于快速排序思想.
观察快速排序是把全部数组排序，当前值需要前k个就行，所以加上对于index与k的判断，只要前k个
具体实现要观察注释里面写的坑
//40. 最小的 K 个数
public static int littk(int[] arr,int k) {
if(arr==null) return -1;
int index=0;
index = partion(arr,0,arr.length-1);
int start = 0;
int end = arr.length - 1;
while(index!=k-1) {
if(index>k-1){
//end及下面的start要给值，不然会浪费大量时间
end = index-1;
index=partion(arr,start,end);
}else{
start = index+1;
index=partion(arr,start,end);
}
}
return index;
}
public static int partion(int[] arr,int start,int end){
int res = arr[start];
while(start<end){
while(start<end&&arr[end]>=res) {
end--;
}
arr[start] = arr[end];
while(start<end&&arr[start]<res){
start++;
}
arr[end]=arr[start];
}
arr[start]=res;
return start;
}
//快速排序
public static void sort_fast(int[] arr,int left,int right) {
if(left>right) return;
int i= partion2(arr,left,right);
sort_fast(arr,left,i-1);
sort_fast(arr,i+1,right);
}
41.1 数据流中的中位数
后面再看
考虑将数据序列从中间开始分为两个部分，左边部分使用大根堆表示，右边部分使用小根堆存储。每遍历一个数据，计数器count增加1，当count是偶数时，将数据插入小根堆；当count是奇数时，将数据插入大根堆。当所有数据遍历插入完成后（时间复杂度为O(logn)O(logn)，如果count最后为偶数，则中位数为大根堆堆顶元素和小根堆堆顶元素和的一半；如果count最后为奇数，则中位数为小根堆堆顶元素。
public class Solution {
// 大顶堆，存储左半边元素
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 小顶堆，存储右半边元素，并且右半边元素都大于左半边
private PriorityQueue<Integer> right = new PriorityQueue<>();
// 当前数据流读入的元素个数
private int N = 0;
public void Insert(Integer val) {
// 插入要保证两个堆存于平衡状态
if (N % 2 == 0) {
// N 为偶数的情况下插入到右半边。
// 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
// 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
}
41.2 字符流中第一个不重复的字符
因为一个字符不会超过8位，所以创建一个大小为256的整形数组，创建一个List，存放只出现一次的字符。insert时先对该字符所在数组位置数量+1，再判断该位置的值是否为1，如果为1，就添加到List中，不为1，则表示该字符已出现不止1次，然后从List中移除，取出时先判断List的size是否为0，不为0直接List.get(0)，就可以得到结果，否则返回‘#’
方法不难想，主要是实现由坑，看注释
//41.2 字符流中第一个不重复的字符
private static int[] chacnt = new int[256];
private static ArrayList<Character> lst = new ArrayList<Character>();
public static void insert(char ch){
chacnt[ch]++;
if(chacnt[ch]==1){
lst.add(ch);
}else{
//注意這裡要強制轉換一下
lst.remove((Character)ch);
}
}
public static char findFist() {
if (lst.size() == 0) {
return '#';
} else {
return lst.get(0);
}
}
- 连续子数组的最大和
判断和是否大于0，大于0继续加，小于0重新开始
//42. 连续子数组的最大和
public static int maxsum(int[] arr) {
if (arr == null || arr.length == 0)
return -1;
int sum=0;
int res=0;
for(int val:arr){
if(sum>0) {
sum= val+sum;;
} else{
sum=val;
}
res=Math.max(sum, res);
}
return res;
}
Java虚拟机
1 在 Java 中 GC Roots 一般包含以下内容：
虚拟机栈中引用的对象
方法区中静态属性引用的对象
方法区中常量引用的对象
本地方法虚拟机栈中引用的对象
2 Java的引用类型
强引用 直接new一个对象；
软引用，使用SoftReference 当内存不够时被回收，主要用于缓存，比如网页缓存、图片缓存；
弱引用 使用WeakReference 存活时间在下一次垃圾回收前，也是用于缓存，Tomcat 中的 ConcurrentCache 就使用了 WeakHashMap 来实现缓存功能，不常使用的对象易于回收；
虚引用 使用PhantomReference 虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知；
虚引用必须和引用队列关联使用，当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会把这个虚引用加入到与之 关联的引用队列中。程序可以通过判断引用队列中是否已经加入了虚引用，来了解被引用的对象是否将要被垃圾回收。如果程序发现某个虚引用已经被加入到引用队列，那么就可以在所引用的对象的内存被回收之前采取必要的行动。
3 类的卸载条件
类的实例被回收
类对应的java.lang.Class对象没有任何对方被引用
加载该类的classloader被回收
网友评论