leetCode每日十题---堆（难度：中等）二

题目描述1

笔者解答1.1

class Solution { public int getKthMagicNumber(int k) { HashSet<Integer> set=new HashSet<>(); int[] params=new int[]{3,5,7}; PriorityQueue<Integer> queue=new PriorityQueue<>(); queue.offer(1); set.add(1); int count=0; int temp=0; do { temp=queue.poll(); count++; if(count==k)System.out.println(queue.poll()); for(int i:params){ if(set.add(i*temp)) queue.offer(i*temp);; } set.remove(temp); }while(count<k); return temp; } }

笔者分析1.2

刚开始看到这题，发现和上次也的丑数那题几乎一样，所以很顺利的写了出来，但是有些问题，当k比较大的时候，输出结果过大会越界，不对，不是输出结果，是在存储的时候会偶数值越界。有想过用Long才存储，但返回是Int类型，也没啥效果，归根结底还是方法不对。评论区的解法真的是神仙打架啊，太秀了，看看下面这个。

class Solution { public int getKthMagicNumber(int k) { int i3=0,i5=0,i7=0; int dp[]=new int[k]; dp[0]=1; for(int i=1;i<k;i++){ dp[i]=Math.min(Math.min(3*dp[i3],5*dp[i5]),7*dp[i7]); if(dp[i]==3*dp[i3]) i3++; if(dp[i]==5*dp[i5]) i5++; if(dp[i]==7*dp[i7]) i7++; } return dp[k-1]; } }

题目描述2

笔者解答2.1

class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { List<List<Integer>> list=new ArrayList<List<Integer>>(); int index_1=0; int index_2=0; int length_1=nums1.length; int length_2=nums2.length; int[] nums=new int[length_1]; int i,j; for(i=0;i<length_1;i++)nums[i]=-1; int x=0; int y=0; HashSet<String> set=new HashSet<String>(); int count=1; List<Integer> list_temp=new ArrayList<Integer>(); if(length_1==0||length_2==0) return list; int min=length_1*length_2>k?k:length_1*length_2; while(count<min) { int temp1=0; String str=""; int temp_x=x; int temp_y=y; do{ if(temp_x==length_1){ temp1=-1;break; } temp1=nums1[temp_x]+nums2[y]; str="x"+temp_x+"y"+y; temp_x++; }while(set.contains(str)); int temp2=0; do{ if(temp_y==length_2){ temp2=-1;break; } temp2=nums1[x]+nums2[temp_y]; str="x"+x+"y"+temp_y; temp_y++; }while(set.contains(str)); if((temp1>temp2&&temp2!=-1)||temp1==-1){ //存入list list_temp=new ArrayList<Integer>(); list_temp.add(nums1[x]); temp_y--; list_temp.add(nums2[temp_y]); list.add(list_temp); set.add("x"+x+"y"+temp_y); System.out.println("("+x+","+temp_y+")"); count++; if(x==length_1){ x=0; y++; if(y==length_2)y--; } } else if((temp1<=temp2&&temp1!=-1)||temp2==-1){ //存入list list_temp=new ArrayList<Integer>(); temp_x--; list_temp.add(nums1[temp_x]); list_temp.add(nums2[y]); list.add(list_temp); set.add("x"+temp_x+"y"+y); System.out.println("("+temp_x+","+y+")"); count++; if(y==length_1) { y=0; x++; if(x==length_1)x--; } } } list_temp=new ArrayList<Integer>(); list_temp.add(nums1[x]); list_temp.add(nums2[y]); list.add(list_temp); return list; } }

笔者分析2.2

这题思路其实不难，我开始也是说铁着心要把它写出来，结果改了两小时BUG，还有些用例通过不了。。。菜了菜了！求助评论区。优先队列还能这样用也是爱了。

class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> compare(o2, o1)); for (int i : nums1) { for (int j : nums2) { int[] arr = new int[]{i, j}; if (queue.size() < k) { queue.offer(arr); } else if (!queue.isEmpty() && compare(queue.peek(), arr) > 0) { queue.poll(); queue.offer(arr); } } } List<List<Integer>> res = new ArrayList<>(); while (!queue.isEmpty()) { int[] poll = queue.poll(); res.add(Arrays.asList(poll[0], poll[1])); } return res; } private int compare(int[] arr1, int[] arr2) { return (arr1[0] + arr1[1]) - (arr2[0] + arr2[1]); } }

题目描述3

笔者解答3.1

class Solution { public int[] rearrangeBarcodes(int[] barcodes) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); int i; for(i=0;i<barcodes.length;i++){ map.put(barcodes[i],map.getOrDefault(barcodes[i],0)+1); } int[] str=new int[barcodes.length]; if(barcodes.length==1)return barcodes; circle(-1,map,str.length,str); return str; } public static boolean circle(int last_num,Map<Integer,Integer> map,int n,int[] str){ if(n==1){ if(map.get(last_num)==0){ for(int key:map.keySet()){ if(map.get(key)==1){ str[str.length-n]=key;break; } } return true; } else return false; } else{ for(int key:map.keySet()){ if(map.get(key)>=1&&key!=last_num){ map.put(key,map.getOrDefault(key,0)-1); if(circle(key,map,n-1,str)) { str[str.length-n]=key; return true; } map.put(key,map.getOrDefault(key,0)+1); } } } return false; } }

笔者分析3.2

我真以为我写出来了的，用哈希表和递归，以为会很漂亮的通过，结果竟然是时间超时。。。再次求助于评论区：挺简单的贪心题，按照数量从大到小放就好了，大的放在前面，如果出现相同的值则先放下一个。

public int[] rearrangeBarcodes(int[] barcodes) { int[] res = new int[barcodes.length]; Map<Integer, Integer> map = new HashMap<>(); for (int barcode : barcodes) map.put(barcode, map.getOrDefault(barcode, 0) + 1); int index = 0; Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]); for (Integer integer : map.keySet()) pq.add(new int[]{map.get(integer), integer}); int[] p = pq.poll(); res[index++] = p[1]; p[0] -= 1; pq.add(p); while (index < res.length) { int[] cp = pq.poll(); if (cp[1]!=res[index-1]){ res[index++]=cp[1]; cp[0]-=1; }else { int[] poll = pq.poll(); res[index++]=poll[1]; poll[0]-=1; pq.add(poll); } pq.add(cp); } return res; }

题目描述4

笔者解答4.1

class Solution { public boolean isPossible(int[] nums) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i:nums){ map.put(i,map.getOrDefault(i,0)+1); } for(int i:nums){ int subNum=0; int p=1; int next=i; while(map.getOrDefault(next,0)>=p){ p=map.get(next); map.put(next,p-1); ++subNum; ++next; } if(subNum>0&&subNum<3){ return false; } } return true; } }

笔者分析4.2

反思了一下下，这些看似没有头绪很复杂的题目，实现的代码其实没有想象的那么可怕，相反它可能很简洁，但这取决于你思考问题的角度，以及该问题的核心突破口。比较简单的难题并不是使用的数据结构又有多复杂，而是这个突破口不太好把握和运用。

题目描述5

笔者分析5.1

虽然我再上一题分析中写道哪些看似难的题，其实真正的代码并不复杂。但我看到这题，又是一头雾水，心想这得多复杂啊，直到我看到评论区大佬的解法，我佛了。

class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { int[][] dp = new int[n][K+2]; for(int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE); for(int k = 0; k <= K+1; ++k) dp[src][k] = 0; for(int k = 1; k <= K+1; ++k) { for(int[] flight : flights) { if(dp[flight[0]][k-1] != Integer.MAX_VALUE) dp[flight[1]][k] = Math.min(dp[flight[1]][k], dp[flight[0]][k-1] + flight[2]); } } return dp[dst][K+1] == Integer.MAX_VALUE ? -1 : dp[dst][K+1]; } }

题目描述6

笔者解答6.1

class MedianFinder { PriorityQueue<Integer> queue; int Num; /** initialize your data structure here. */ public MedianFinder() { queue=new PriorityQueue<Integer>(); Num=0; } public void addNum(int num) { queue.offer(num); Num++; } public double findMedian() { PriorityQueue<Integer> temp_queue=new PriorityQueue<Integer>(); double result=0; int num=Num; if(num%2==1){ num=num/2+1; int count=1; while(!queue.isEmpty()){ int number=queue.poll(); temp_queue.offer(number); if(count==num) result=(double)number; count++; } }else{ num=num/2; int count=1; while(!queue.isEmpty()){ int number=queue.poll(); temp_queue.offer(number); if(count==num||count==num+1) result+=(double)number; count++; } result/=2; } queue=temp_queue; return result; } }

笔者分析6.2

个人认为，虽然这题的定位困难，但感觉比前几题要好理解多了。思路很简单，就是很容易超时，就比如我上面写的代码，超时了。观摩了下评论区大佬的想法，大小顶堆结合求中位数的方法实在太惊艳了。 大顶堆+小顶堆：可以看作大顶堆是普通版，小顶堆是实验班。数量上时刻保持小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。新学生先入普通班（大顶堆），此时可能会失去平衡了，于是取大顶堆的第一个（班里最好的学生）加入实验班（小顶堆），判断若数量过多（不是等于或多一个），取第一个（实验班里最差的学生）到普通班（大顶堆）里。取中位数的时候，若两堆数量相等，则各取堆顶取平均，若小顶比大顶多一，则多的那一个就是中位数。

题目描述7

笔者分析7.1

原来写过一个二维的，不是很难，现在三维的，感觉难度不是一个层次的，主要是这个墙太难找了，看了题解，将围墙由外向内缩减，牛！

public int trapRainWater(int[][] heights){ if(heights==null||heights.length==0)return 0; int n=heights.length; int m=heights[0].length; //用一个vis数组来标记这个位置有没有被访问过 boolean[][] vis=new boolean[n][m]; //优先队列中存放三元组[x,y,h]坐标和高度 PriorityQueue<int[]> pq=new PriorityQueue<>((o1,o2)->o1[2]-o2[2]); //先把最外一圈放进去 for(int i=0;i<n;i++){ for(int j=0;j<m;j++) { if(i==0||i==n-1||j==0||j==m-1){ pq.offer(new int[]{i,j,heights[i][j]); vis[i][j]=true; } } } int res=0; //方向数组，把dx和dy压缩成一维来做 int[] dirs={-1,0,1,0,-1};//很强 while(!pq.isEmpty()){ int[] poll=pq.poll(); //看一下周围四个方向，没访问过的话能不能往里灌水 for(int k=0;k<4;k++) { int nx=poll[0]+dirs[k]; int ny=poll[1]+dirs[k+1]; //如果位置合法且没访问过 if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]){ //如果外围这一圈中最小的比当前这个还高，那就说明能往里面灌水啊 if(poll[2]>heights[nx][ny]){ res+=poll[2]-heights[nx][ny]; } //如果灌水高度得是你灌水后的高度了，如果没灌水也要取高的 pq.offer(new int[]{nx,ny,Math.max(heights[nx][ny],poll[2])}); vis[nx][ny]=true; } } } return res; } }

题目描述8

笔者解答8.1

class Solution { public List<List<Integer>> getSkyline(int[][] buildings) { List<List<Integer>> List=new ArrayList<List<Integer>>(); int n=buildings.length; if(n==0)return List; int maxlength=buildings[n-1][1]; int[] str=new int[maxlength+1]; PriorityQueue<int[]> queue=new PriorityQueue<>((o1,o2)->{ return o2[2]-o1[2]; }); int i,j; for(i=0;i<n;i++)queue.offer(buildings[i]); for(i=0;i<=maxlength;i++)str[i]=0; while(!queue.isEmpty()){ int[] temp=queue.poll(); int k,q; for(k=temp[0];k<temp[1];k++){ if(temp[2]>str[k]) str[k]=temp[2]; } } int last=0; for(i=0;i<maxlength+1;i++) { int temp=str[i]; if(temp!=last){ List<Integer> list=new ArrayList<Integer>(); list.add(i); list.add(temp); List.add(list); last=temp; } } return List; } }

笔者分析8.2

自我感觉还是挺好的，思路清晰，代码简洁，但就是内存超出限制。。。。下面这个方法和我写的类似，通过的原因在于它用单个点的存储取代了我的长数组。

public List<List<Integer>> getSkyline(int[][] buildings) { List<List<Integer>> resList = new ArrayList<>(); if (buildings == null || buildings.length == 0 || buildings[0] == null || buildings[0].length == 0) { return resList; } //定义比较器，先按pos从小到大排序，pos相等，按height从小到大排 PriorityQueue<Point> queue = new PriorityQueue<>((o1, o2) -> { if (o1.pos != o2.pos) { return o1.pos - o2.pos; } if (o1.height != o2.height) { return o1.height - o2.height; } return 0; }); //生成queue，<第一个位置，负高度>，<第二个位置，正高度> for (int i = 0; i < buildings.length; i++) { queue.offer(new Point(buildings[i][0], -buildings[i][2])); queue.offer(new Point(buildings[i][1], buildings[i][2])); } PriorityQueue<Integer> maxHeightQueue = new PriorityQueue<>(Comparator.reverseOrder()); maxHeightQueue.offer(0); int prePeak = maxHeightQueue.peek(); while (!queue.isEmpty()) { //当当前高度是负数，说明是上升的，加到maxHeightQueue，反之移除掉 Point point = queue.poll(); if (point.height < 0) { maxHeightQueue.offer(-point.height); } else { maxHeightQueue.remove(point.height); } int curPeak = maxHeightQueue.peek(); if (curPeak != prePeak) { resList.add(Arrays.asList(point.pos, curPeak)); prePeak = curPeak; } } return resList; } class Point { int pos, height; public Point(int pos, int height) { this.pos = pos; this.height = height; } }

总结

原来N皇后问题是自己吓自己呀，就一个回溯算法，大小顶堆也是秀了我一脸，优先队列也可以花里胡哨的用。每日打卡第七天，以下图为证。