假期无聊，不如一起刷《剑指offer》（第六天）

剑指 Offer 41. 数据流中的中位数

剑指 Offer 41. 数据流中的中位数
这道题是求数据流的中位数一般情况我们可以采用排序的方式很轻松的找出中位数。如果我们采用插入排序的话每次插入数字的时间复杂度大概是O(N)怎么能让这个时间更短呢？那么我们可以利用大小根堆的特点把单次查找的时间复杂度缩短到O(logN)。可以使用堆具体做法如下
我们把数据分为两部分一部分是小于中位数的大根堆另一部分是大于等于中位数的小根堆。我们控制两个堆的元素个数之差<=1这样的话如果两堆元素个数相同就各取堆顶元素均分得到中位数差1就取较多元素的堆顶。
具体如何插入我们分类讨论

class MedianFinder {
    private PriorityQueue<Integer> smallHeap;
    private PriorityQueue<Integer> bigHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        smallHeap=new PriorityQueue();//初始默认小根堆
        bigHeap=new PriorityQueue(new Comparator() {//转为大根堆
            @Override
            public int compare(Object o1, Object o2) {
                return (Integer)o2-(Integer)o1;
            }
        });
    }
    
    public void addNum(int num) {
        //保证size差值<=1
        if(smallHeap.size()>bigHeap.size()){//优先考虑往big插入
            if(num>smallHeap.peek()){//如果大于small的最小值从small拿一个到bignum插入small
                int tmp=smallHeap.poll();
                bigHeap.add(tmp);
                smallHeap.add(num);
            }else{
                bigHeap.add(num);
            }
        }else if(smallHeap.size()<bigHeap.size()){//优先考虑往small插入
            if(num<=bigHeap.peek()){//如果小于等于小根堆的最小值从big拿一个到smallnum插入big
                int tmp=bigHeap.poll();
                smallHeap.add(tmp);
                bigHeap.add(num);
            }else{
                smallHeap.add(num);
            }
        }else{
            if(bigHeap.size()!=0&&smallHeap.size()!=0&&num>bigHeap.peek()){
                smallHeap.add(num);
            }else{
                bigHeap.add(num);
            }
        }
    }
    
    public double findMedian() {
        // if(smallHeap.size()!=0){
        //     System.out.println("a:"+smallHeap.peek());
        // }
        // if(bigHeap.size()!=0){
        //     System.out.println("b:"+bigHeap.peek());
        // }
        if(smallHeap.size()>bigHeap.size()){
            return 1.0*smallHeap.peek();
        }else if(smallHeap.size()<bigHeap.size()){
            return 1.0*bigHeap.peek();
        }else{
            return 1.0*(smallHeap.peek()+bigHeap.peek())/2;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

剑指 Offer 43. 1～n 整数中 1 出现的次数

剑指 Offer 43. 1～n 整数中 1 出现的次数
我首先的想法是正常循环挨个数字判断但是很明显没有这么简单时间超限了

既然不能循环我觉得应该是有什么规律可循。练习了两个半小时的斯某人决定打开题解借鉴。
以下转自leetcode题解

得到了规律
根据当前位 cur值的不同分为以下三种情况
当cur=0 时 此位 1的出现次数只由高位 high决定计算公式为
high×digit
当cur=1 时 此位 1的出现次数由高位 high和低位决定计算公式为
high×digit+low-1
当cur=其他数字时 此位 1的出现次数只由高位 high决定计算公式为
（high+1×digit

class Solution {
    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

剑指 Offer 44. 数字序列中某一位的数字

剑指 Offer 44. 数字序列中某一位的数字

因为right很容易越界我们使用long类型

class Solution {
    public int findNthDigit(int n) {
        //先把范围缩小到0-9 或者10-99 或者100-999等等
        long k=1;
        long level=1;//1代表0-9  每+1代表范围扩大 例如2代表10-99
        long chars=0;//目前已占用的字符数
        long right=10;//每个范围所占字符数
        while(n>right){
            level++;//范围增大
            chars=(int)right;
            right=right+(level*90*k);
            k*=10;
        }
        n-=chars;
        //保存除数的结果
        long div=n/level;
        //保存取模的结果
        long mod=n%level;
        //将除数加上所在范围的基数u比如443 得到84要+100
        if(k!=1)
        div+=k;
        return Long.toString(div).charAt((int)mod)-'0';
    }
}

共勉