算法面试题

名企笔试 + 算法题

---

优先级队列

实质就是堆排序(二叉堆排序)

和TopK一样

优先级队列（头条面试题）

leetcode

class Solution {
    //方案2: 使用最大堆
    public int findKthLargest(int[] nums, int k) {

        int[] arr=new int[nums.length];
        for(int i=0;i<nums.length;i++){//构建最大堆
            insert(arr,i-1,nums[i]);
        }

        // print(arr);

        //第K大值
        int r=arr[0];
        for(int i=arr.length-1;i>(arr.length-1-k);i--){//弹出第K个，就是第K大值
            r=delete(arr,i);
            // System.out.print(","+r);
        }
        return r;
    }

    //从最大堆删除元素
    //last: nums[last]有值
    //返回值：为删除的元素
    private int delete(int[] nums, int last){
        //步骤：
        //1. 头、尾互换，将尾部元素删除
        //2. 头部元素下沉

        if(last==0){
            return nums[last];
        }

        swap(nums, 0, last);
        last--;  //将尾部元素删除

        int cur=0;
        while(cur<=last && findLeft(cur)<=last && findRight(cur)<=last
            && nums[cur] < Math.max(nums[findLeft(cur)],nums[findRight(cur)])){//头部元素下沉
            if(nums[findLeft(cur)]<nums[findRight(cur)]){//和右节点交换
                swap(nums,cur,findRight(cur));
                cur=findRight(cur);
            }else{//和左节点交换
                swap(nums,cur,findLeft(cur));
                cur=findLeft(cur);
            }
        }

        if(cur<=last && findLeft(cur)<=last
            && nums[cur] < nums[findLeft(cur)]){//头部元素下沉
            swap(nums,cur,findLeft(cur));
            cur=findLeft(cur);
        }

        if(cur<=last && findRight(cur)<=last
            && nums[cur] < nums[findRight(cur)]){//头部元素下沉
            swap(nums,cur,findRight(cur));
            cur=findRight(cur);
        }

        return nums[last+1];
    }

    //插入元素：最大堆
    //last: 当前数组的最后一个元素索引（nums[last]已经插入数据）
    //v: 待插入的值
    //返回最后一个元素的索引
    private int insert(int[] nums, int last, int v){
        nums[++last]=v;  //先插入到最后
        if(last==0){//只有1个元素
            return last;
        }

        int cur=last;
        while(nums[findParent(cur)]<nums[cur]){//从底层往上冒
            swap(nums, cur, findParent(cur));
            cur=findParent(cur);
        }
        return last;
    }

    private void swap(int[] nums, int a,int b){
        int t=nums[a];
        nums[a]=nums[b];
        nums[b]=t;
    }

    private int findParent(int i){
        return (i-1)/2;
    }

    private int findLeft(int i){
        return 2*i+1;
    }

    private int findRight(int i){
        return 2*i+2;
    }

    private void print(int[] nums){
        for(int i:nums){
            System.out.println(i);
        }
     System.out.println("--------------------------");
    }
}

---

先递增后递减的数组中找最值

百度面试题之求数组最大值

---

先递增后递减的数组中找目标值的索引（智加科技）

---

蛇形螺旋矩阵的生成和遍历

按照4个方向分别去做