丢了么网站,信用中国 网站截图怎么做,小米网站推广方案,室内设计效果图app文章目录 面试经典150题【121-130】215.数组中的第k大元素502.IPO373.查找和最小的K对数字295.数据流的中位数108.将有序数组转换为二叉搜索树148.排序链表427.建立四叉树23.合并K个升序链表53.最大子数组和918.环形子数组的最大和 面试经典150题【121-130】
4道堆#xff0c… 文章目录 面试经典150题【121-130】215.数组中的第k大元素502.IPO373.查找和最小的K对数字295.数据流的中位数108.将有序数组转换为二叉搜索树148.排序链表427.建立四叉树23.合并K个升序链表53.最大子数组和918.环形子数组的最大和 面试经典150题【121-130】
4道堆4道分治2道Kadane算法。
215.数组中的第k大元素 这个有三种考察思路。一个是调用优先队列的API一个是手写堆一个是写快速选择。 法一调用优先队列的API
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger 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 heap1new MinHeap(nums,k);for(int ik;inums.length;i){heap1.add(nums[i]);}return heap1.heap[0];}class MinHeap{private int[]heap;public int size;MinHeap(int[] nums,int k){heapnew int[k];size k;System.arraycopy(nums, 0, heap, 0, k);Arrays.sort(heap);}public void add(int num){if(numheap[0]) return;heap[0]num;adjust();}public void adjust(){int i0;while(true){if(2*i1size-1) return;if(2*i2size-1){if(heap[i]heap[2*i1]){swap(heap,i,2*i1);}return;}int minIndex2*i2;if(heap[2*i1]heap[2*i2]) minIndex2*i1;if(heap[i]heap[minIndex]) break; //不用再往下走了else{swap(heap,i,minIndex);iminIndex;}}}private void swap(int[]nums,int a,int b){int tempnums[a];nums[a]nums[b];nums[b]temp;}}
}法三快速排序选择不建议。 原地的一直报错。开新数组还好一点。
class Solution {public int findKthLargest(int[] nums, int k) {ListInteger numList new ArrayList();for (int num : nums) {numList.add(num);}return quickSelect(numList, k);}private int quickSelect(ListInteger nums, int k) {Random randnew Random();int pivot nums.get(rand.nextInt(nums.size()));ListInteger big new ArrayList();ListInteger equal new ArrayList();ListInteger small new ArrayList();for (int num : nums) {if (num pivot)big.add(num);else if (num pivot)small.add(num);elseequal.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 k2,w0;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 nprofits.length;Listint[] listnew ArrayList();for(int i0;in;i){list.add(new int[]{capital[i],profits[i]});}//按照容量排序从小到大Collections.sort(list,(a,b)- a[0]-b[0]);//设置一个大根堆每次只拿利润最大的一个PriorityQueueInteger qnew PriorityQueue((a,b)-b-a);int i0;while(k--0){//如果这个任务可以执行了就把他放到大根堆里while(in list.get(i)[0]w){q.add(list.get(i)[1]);i;}//如果一个任务也执行不了直接寄if(q.isEmpty()) break;// 取最大值加入累计利润wq.poll();}return w;}
}堆一般都用现成的优先队列。
373.查找和最小的K对数字 class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {int m nums1.length,n nums2.length;PriorityQueueint[] pnew PriorityQueue((a,b)-a[0]-b[0]);ListListInteger ansnew ArrayList();for(int i0;iMath.min(m,k);i){//求和两个数组的索引p.add(new int[]{nums1[i]nums2[0],i,0});}while(!p.isEmpty() ans.size()k){int[] tempp.poll();int itemp[1],jtemp[2];ans.add(List.of(nums1[i],nums2[j]));if(j1 n) p.add(new int[]{nums1[i]nums2[j1],i,j1});}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,j1)塞入队列比如[1,6]出来了就塞入[1,7] 如果不想提前塞入[2,6]这后面四个的话可以选择当弹出 j0的时候同时塞入i,j1和(i1,j) 本质上就是一个Nums1和nums2的矩阵要不先把第一列塞入每次塞入弹出数据右边的 要不只塞左上角一个如果弹出的是第一列的还要再多塞入一个下一行的最左边的。 在while代码添加下面一行即可 if(j0 i1m) p.add(new int[]{nums1[i1]nums2[0],i1,0}); 总代码如下
class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {int m nums1.length,n nums2.length;PriorityQueueint[] pnew PriorityQueue((a,b)-a[0]-b[0]);ListListInteger ansnew ArrayList();//求和两个数组的索引p.add(new int[]{nums1[0]nums2[0],0,0});while(!p.isEmpty() ans.size()k){int[] tempp.poll();int itemp[1],jtemp[2];ans.add(List.of(nums1[i],nums2[j]));if(j1 n) p.add(new int[]{nums1[i]nums2[j1],i,j1});if(j0 i1m) p.add(new int[]{nums1[i1]nums2[0],i1,0});}return ans;}
}
295.数据流的中位数 左边维持一个大根堆右边维持一个小根堆。保持两个堆的大小基本一样相差不超过1
class MedianFinder {//我们尽量让A的元素多一个QueueInteger 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(lr) return null;int mid(lr)/2;TreeNode curnew TreeNode(nums[mid]);cur.left dfs(nums,l,mid-1);cur.rightdfs(nums,mid1,r);return cur;}
}148.排序链表 用一个归并排序。时间复杂度ONlogN。 对数组做归并排序的空间复杂度为 O(n)分别由新开辟数组 O(n)和递归函数调用 O(logn) 组成而根据链表特性
数组额外空间链表可以通过修改引用来更改节点顺序无需像数组一样开辟额外空间 递归额外空间递归调用函数将带来 O(logn) 的空间复杂度因此若希望达到 O(1) 空间复杂度则不能使用递归。 public ListNode sortList(ListNode head) {if(headnull || head.nextnull) return head;//一定要讲fast设置为head.next而不是head。不然slow.nextnull这一步不好做ListNode slowhead,fasthead.next;while(fast!null fast.next!null){slowslow.next;fastfast.next.next;}ListNode dummynew ListNode(0);ListNode curdummy;ListNode tempslow.next;//将其拆为左右两部分slow.nextnull;//左右两部分分别排序ListNode leftsortList(head);ListNode rightsortList(temp);while(left!null right!null){if(left.valright.val){cur.nextleft;leftleft.next;}else{cur.nextright;rightright.next;}curcur.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 (minNodenull) {break;}tail.next minNode;tail tail.next;minNodeminNode.next;}return dummyHead.next;}}因为minNodeminNode.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];minPointeri;}}if (minNodenull) {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;QueueListNode 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 tempdummyNode;while(l1!null l2!null){if(l1.vall2.val){temp.nextl1;l1l1.next;}else{temp.nextl2;l2l2.next;}temptemp.next;}temp.next l1!null? l1:l2;return dummyNode.next;}public ListNode mergeNLists(ListNode[] lists,int left,int right){if(leftright) return lists[left];int mid(leftright)/2;ListNode leftMergemergeNLists(lists,left,mid);ListNode rightMergemergeNLists(lists,mid1,right);return merge2Lists(leftMerge,rightMerge);}public ListNode mergeKLists(ListNode[] lists) {if(lists.length0) 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[] dpnew int[nums.length];dp[0]nums[0];int ansdp[0];for(int i1;inums.length;i){dp[i]Math.max(nums[i],nums[i]dp[i-1]);ansMath.max(ans,dp[i]);}return ans;}
}918.环形子数组的最大和 对于{-1-1-1}这种也要取一个数字。ans-1 拼接成2倍长度还要考虑滑动区间大小不能大于n各种条件太复杂了。 还是直接Math.max(maxSum,sum-minSum);简单。 minSum就是中间的最小的一部分。 6,66 -5,-4,-3, 66,6
class Solution {public int maxSubarraySumCircular(int[] nums) {int maxSumnums[0],minSumnums[0];int maxTemp0,minTemp0;int sum0;for(int i0;inums.length;i){maxTempMath.max(nums[i],maxTempnums[i]);maxSumMath.max(maxSum,maxTemp);minTempMath.min(nums[i],minTempnums[i]);minSumMath.min(minSum,minTemp);sumnums[i];}return summinSum? maxSum:Math.max(maxSum,sum-minSum);}
}maxSum,截止到当前为止最大的一段区间和 minSum,截止到当前为止最小的一段区间和 如何summinSum。说明全是负数。则最大的一段区间和就是数组里最大的负数 maxTemp,必须用到nums[i]的最大区间和 minTemp,必须用到nums[i]的最小区间和
