面试经典150题【121-130】

面试经典150题【121-130】

4道堆，4道分治，2道Kadane算法。

215.数组中的第k大元素

这个有三种考察思路。一个是调用优先队列的API，一个是手写堆，一个是写快速选择。
法一：调用优先队列的API

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();

    }
}

法二：手写堆：
简化了一下，对于初始化直接用的快排。不写上浮操作了。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        MinHeap heap1=new MinHeap(nums,k);
        for(int i=k;i<nums.length;i++){
            heap1.add(nums[i]);
        }
        return heap1.heap[0];

    }
    class MinHeap{
        private int[]heap;
        public int size;
        MinHeap(int[] nums,int k){
            heap=new int[k];
            size = k;
            System.arraycopy(nums, 0, heap, 0, k);
            Arrays.sort(heap);
        }
        public void add(int num){
            if(num<=heap[0]) return;
            heap[0]=num;
            adjust();
        }
        public void adjust(){
            int i=0;
            while(true){
                if(2*i+1>size-1) return;
                if(2*i+2>size-1){
                    if(heap[i]>heap[2*i+1]){
                        swap(heap,i,2*i+1);
                    }
                    return;
                }
                int minIndex=2*i+2;
                if(heap[2*i+1]<heap[2*i+2]) minIndex=2*i+1;
                if(heap[i]<=heap[minIndex]) break; //不用再往下走了
                else{
                    swap(heap,i,minIndex);
                    i=minIndex;
                }
            }
        }
        private void swap(int[]nums,int a,int b){
            int temp=nums[a];
            nums[a]=nums[b];
            nums[b]=temp;
        }
    }
}

法三：快速排序选择，不建议。
原地的一直报错。开新数组还好一点。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        return quickSelect(numList, k);
    }
    private int quickSelect(List<Integer> nums, int k) {
        Random rand=new Random();
        int pivot = nums.get(rand.nextInt(nums.size()));
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot)
                big.add(num);
            else if (num < pivot)
                small.add(num);
            else
                equal.add(num);
        }
        if(big.size()>=k) return quickSelect(big,k);
        if(nums.size()-small.size()<k){
            return quickSelect(small,k- big.size()-equal.size());
        }
        //不在big里也不在small里
        return pivot;
    }
}

502.IPO

public class LC502 {
    public static void main(String[] args) {
        int k=2,w=0;
        int[] profits={1,2,3};
        int[] capital={0,1,1};
        System.out.println(findMaximizedCapital(k,w,profits,capital));


    }
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n=profits.length;
        List<int[]> list=new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(new int[]{capital[i],profits[i]});
        }
        //按照容量排序，从小到大
        Collections.sort(list,(a,b)-> a[0]-b[0]);
        //设置一个大根堆，每次只拿利润最大的一个
        PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        while(k-->0){
            //如果这个任务可以执行了，就把他放到大根堆里
            while(i<n && list.get(i)[0]<=w){
                q.add(list.get(i)[1]);
                i++;
            }
            //如果一个任务也执行不了，直接寄
            if(q.isEmpty()) break;
            // 取最大值加入累计利润
            w+=q.poll();
        }
        return w;

    }
}

堆一般都用现成的优先队列。

373.查找和最小的K对数字

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m= nums1.length,n= nums2.length;
        PriorityQueue<int[]> p=new PriorityQueue<>((a,b)->a[0]-b[0]);
        List<List<Integer>> ans=new ArrayList<>();
        for(int i=0;i<Math.min(m,k);i++){
            //求和，两个数组的索引
            p.add(new int[]{nums1[i]+nums2[0],i,0});
        }
        while(!p.isEmpty() && ans.size()<k){
            int[] temp=p.poll();
            int i=temp[1],j=temp[2];
            ans.add(List.of(nums1[i],nums2[j]));
            if(j+1< n) p.add(new int[]{nums1[i]+nums2[j+1],i,j+1});
        }
        return ans;

    }
}

比如nums1={1,2,3,4,5}. nums2={6,7,8,9,10}
先把[1,6],[2,6],[3,6],[4,6],[5,6]塞入到优先队列里。
每次出来一个就选择(i,j+1)塞入队列，比如[1,6]出来了就塞入[1,7]
如果不想提前塞入[2,6]这后面四个的话，可以选择当弹出 j=0的时候同时塞入（i,j+1）和(i+1,j)
本质上就是一个Nums1和nums2的矩阵，要不先把第一列塞入，每次塞入（弹出数据右边的）
要不只塞左上角一个，如果弹出的是第一列的，还要再多塞入一个下一行的最左边的。
在while代码添加下面一行即可：
if(j==0 && i+1<m) p.add(new int[]{nums1[i+1]+nums2[0],i+1,0});
总代码如下：

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m= nums1.length,n= nums2.length;
        PriorityQueue<int[]> p=new PriorityQueue<>((a,b)->a[0]-b[0]);
        List<List<Integer>> ans=new ArrayList<>();
        
        //求和，两个数组的索引
        p.add(new int[]{nums1[0]+nums2[0],0,0});
        
        while(!p.isEmpty() && ans.size()<k){
            int[] temp=p.poll();
            int i=temp[1],j=temp[2];
            ans.add(List.of(nums1[i],nums2[j]));
            if(j+1< n) p.add(new int[]{nums1[i]+nums2[j+1],i,j+1});
            if(j==0 && i+1<m) p.add(new int[]{nums1[i+1]+nums2[0],i+1,0});
        }
        return ans;

    }
}

295.数据流的中位数

左边维持一个大根堆，右边维持一个小根堆。保持两个堆的大小基本一样，相差不超过1

class MedianFinder {
    //我们尽量让A的元素多一个
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }

    public void addNum(int num) {
        if(A.size() !=B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;

    }
}

如果最终是A添加新的数字，这个数字要先在B里过一圈。反之亦然。

108.将有序数组转换为二叉搜索树

取中间节点当root,然后依次递归左右子树即可。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);

    }
    public TreeNode dfs(int[] nums,int l ,int r){
        if(l>r) return null;
        int mid=(l+r)/2;
        TreeNode cur=new TreeNode(nums[mid]);
        cur.left = dfs(nums,l,mid-1);
        cur.right=dfs(nums,mid+1,r);
        return cur;
    }
}

148.排序链表

用一个归并排序。时间复杂度O（NlogN）。
对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n)和递归函数调用 O(logn) 组成，而根据链表特性：

数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
递归额外空间：递归调用函数将带来 O(logn) 的空间复杂度，因此若希望达到 O(1) 空间复杂度，则不能使用递归。

    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        //一定要讲fast设置为head.next而不是head。不然slow.next=null这一步不好做
        ListNode slow=head,fast=head.next;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        ListNode temp=slow.next;
        //将其拆为左右两部分
        slow.next=null;
        //左右两部分分别排序
        ListNode left=sortList(head);
        ListNode right=sortList(temp);
        
        while(left!=null&& right!=null){
            if(left.val<right.val){
                cur.next=left;
                left=left.next;
            }else{
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        //最后肯定有一个为null，直接全部接收后续的
        cur.next = left!=null? left:right;
        return dummy.next;


    }

427.建立四叉树

什么勾八题，题干太长了。肯定不会被考面试。

23.合并K个升序链表

思考1：暴力，每次遍历k个求最小值。
但是下面的写法是错误的

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
         int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            //int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    
                }
            }
            if (minNode==null) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            minNode=minNode.next;
        }
        return dummyHead.next;
    }

}

因为minNode=minNode.next并不能让链表的头结点删除掉。还是要用索引
lists[minPointer]=lists[minPointer].next;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
         int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer=i;
                    
                }
            }
            if (minNode==null) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            lists[minPointer]=lists[minPointer].next;
        }
        return dummyHead.next;
    }

}

思考2：用一个大小为K的堆，代替每次遍历K次。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummyNode = new ListNode(0);
        ListNode tail = dummyNode;
        Queue<ListNode> q = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node : lists) {
            if (node != null) {
                q.add(node);
            }
        }
        while (!q.isEmpty()) {
            ListNode temp = q.poll();
            tail.next = temp;
            tail = tail.next;
            if (temp.next != null)
                q.add(temp.next);
        }
        return dummyNode.next;

    }

}

思考3：两两合并，经典分治.
用非递归的方法合并两个链表。用递归的方法合并N个链表。

class Solution {
   public ListNode merge2Lists(ListNode l1,ListNode l2){
        ListNode dummyNode =new ListNode(0);
        ListNode temp=dummyNode;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                temp.next=l1;
                l1=l1.next;
            }else{
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
        }
        temp.next= l1!=null? l1:l2;
        return dummyNode.next;

    }
    public ListNode mergeNLists(ListNode[] lists,int left,int right){
        if(left==right) return lists[left];
        int mid=(left+right)/2;
        ListNode leftMerge=mergeNLists(lists,left,mid);
        ListNode rightMerge=mergeNLists(lists,mid+1,right);
        return merge2Lists(leftMerge,rightMerge);

    }
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        return mergeNLists(lists,0,lists.length-1);
    }

}

53.最大子数组和

dp[i]含义，必须用Nums[i]的最大子数组和。截止到i
当然其实如果前面之和是负数，就不用管他。如果是正数，就是dp[i-1]+nums[i];

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int ans=dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(nums[i],nums[i]+dp[i-1]);
            ans=Math.max(ans,dp[i]);

        }
        return ans;

    }
}

918.环形子数组的最大和

对于{-1，-1，-1}这种，也要取一个数字。ans=-1
拼接成2倍长度，还要考虑滑动区间大小不能大于n，各种条件太复杂了。
还是直接Math.max(maxSum,sum-minSum);简单。
minSum就是中间的最小的一部分。
6,6，6， -5,-4,-3, 6，6,6

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxSum=nums[0],minSum=nums[0];
        int maxTemp=0,minTemp=0;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            maxTemp=Math.max(nums[i],maxTemp+nums[i]);
            maxSum=Math.max(maxSum,maxTemp);
            minTemp=Math.min(nums[i],minTemp+nums[i]);
            minSum=Math.min(minSum,minTemp);
            sum+=nums[i];
        }
        return sum==minSum? maxSum:Math.max(maxSum,sum-minSum);

    }
}

maxSum,截止到当前为止，最大的一段区间和
minSum,截止到当前为止，最小的一段区间和
如何sum==minSum。说明全是负数。则最大的一段区间和就是数组里最大的负数
maxTemp,必须用到nums[i]的最大区间和
minTemp,必须用到nums[i]的最小区间和