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;
}
- 从 1 到 n 整数中 1 出现的次数
很绕
不直观的算法 参考 https://blog.csdn.net/yi_afly/article/details/52012593 没太理解，今天再想想
若weight为0，则1出现次数为roundbase
若weight为1，则1出现次数为roundbase+former+1
若weight大于1，则1出现次数为rount*base+base
public static int count(int n) {
if(n<1) return 0;
int round = n;
int base =1;
int cnt=0;
while(round>0) {
int weight = round%10;
round/=10;
cnt+= cnt*base;
if(weight==1)
cnt+=(n%base)+1;
else if(weight>1)
cnt+=base;
base*=10;
}
return cnt;
}
