面经求玉米大米红薯土豆

用k+1的min heap怎么样？
像Sort a nearly sorted (or K sorted) array ,
http://www.geeksforgeeks.org/nearly-sorted-algorithm/

1. class charComparator implements Comparator<int[]> {
   
2.   
   
3.   int k = 0;
   
4.   
   
5.   public charComparator(int k){
   
6.     this.k = k;
   
7.   }
   
8. 
   
9.   @Override
   
10.   public int compare(int[] o1, int[] o2) {
    
11.     if(o1[k] != o2[k]){
    
12.       return o1[k] - o2[k];
    
13.     }
    
14.     return o1[1-k] - o2[1-k];
    
15.   }
    
16.   
    
17. }
    
18. 
    
19. public class Solution {
    
20.   
    
21.   public String smallest(String s, int k){
    
22.     StringBuffer sb = new StringBuffer();
    
23.     PriorityQueue<int[]> pqc = new PriorityQueue<>(k, new charComparator(0));
    
24.     PriorityQueue<int[]> pqi = new PriorityQueue<>(k, new charComparator(1));
    
25.     int i = 0;
    
26.     for(i = 0; i < Math.min(s.length(), k); ++i){
    
27.       int[] a = new int[]{(int)s.charAt(i), i};
    
28.       pqc.add(a);
    
29.       pqi.add(a);
    
30.     }
    
31.     for(int j = i; j < i + s.length(); ++j){
    
32.       if(j < s.length()){
    
33.         int[] a = new int[]{(int)s.charAt(j), j};
    
34.         pqc.add(a);
    
35.         pqi.add(a);
    
36.       }
    
37.       if(pqi.peek()[1] + k == j - i){
    
38.         sb.append(s.charAt(pqi.peek()[1]));
    
39.         pqc.remove(pqi.poll());
    
40.       }else{
    
41.         sb.append((char)pqc.peek()[0]);
    
42.         pqi.remove(pqc.poll());
    
43.       }
    
44.     }
    
45.     return sb.toString();
    
46.   }
    
47. }

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

学习了！第一次看到的pq和comparator这样用法，给大神跪了。

fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

好厉害的算法，学习了！
另外问一下，38行，pqi.peek()[1]是不是应该是pqi.peek()[0]?因为数组0元素代表的是字符，1代表的是下标

public String minPermutation(int k, String s){
        if(s == null || s.length() < k || k == 0 ) return "";
            char[] str = s.toCharArray();
            PriorityQueue<Character> minHeap = new PriorityQueue<Character>(k+1);
            int index = 0;
            for(int i = 0; i<s.length();i++){
                if(minHeap.size()<k+1){
                    minHeap.add(str[i]);
                }
                if(minHeap.size() == k+1){
                    str[index++] = minHeap.remove();
                }
            }
            while(index < s.length()){
                str[index++] = minHeap.remove();
            }
            return new String(str);
    }

fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

感谢分享思路！！

matieee 发表于 2015-11-7 00:19
public String minPermutation(int k, String s){
        if(s == null || s.length() < k || k == 0 ) r ...

你这里的代码和我在 “沙发” 的代码是一样的，犯了一个致命错误，看漏了那个条件, "每个字母只能换到距离k以内的地方".. 你可以试试

test case = "fdcbaabcdefadbcdaea", k = 2

正确：[c, b, a, a, b, c, d, e, f, a, d, b, c, d, a, e, a]
错误：[c, b, a, a, b, c, d, d, e, a, d, b, c, d, a, e, a, f, f]

第一个f应该被检查到out of range之后就扔掉的

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

我也上一个算法

1. public class Solution {
   
2. 
   
3.     public static void main(String[] args){
   
4.         String s = "bcdaea";
   
5.         int k = 2;
   
6.         System.out.println(new Solution().smallest(s, k));
   
7.     }
   
8. 
   
9. 
   
10.     public String smallest(String s, int k){
    
11.         StringBuffer sb = new StringBuffer();
    
12.         PriorityQueue<Element> pq = new PriorityQueue<Element>(k, new Comparator<Element>() {
    
13.             @Override
    
14.             public int compare(Element o1, Element o2) {
    
15.                 if(o1.c != o2.c){
    
16.                     return o1.c - o2.c;
    
17.                 }
    
18.                 return o1.index - o2.index;
    
19.             }
    
20.         });
    
21.         boolean[] visited = new boolean[s.length()];
    
22.         HashMap<Integer, Element> hm = new HashMap<Integer, Element>();
    
23.         int i = 0;
    
24.         for(i = 0; i < Math.min(s.length(), k); ++i){
    
25.             Element e = new Element(s.charAt(i), i);
    
26.             hm.put(i, e);
    
27.             pq.add(e);
    
28.         }
    
29.         for(int j = i; j < i + s.length(); ++j){
    
30.             if(j < s.length()){
    
31.                 Element e = new Element(s.charAt(j), j);
    
32.                 hm.put(j, e);
    
33.                 pq.add(e);
    
34.             }
    
35.             if(j - i - k >= 0 && !visited[j-i-k]){
    
36.                 sb.append(hm.get(j-i-k).c);
    
37.                 pq.remove(hm.get(j-i-k));
    
38.                 visited[j-i-k] = true;
    
39.             }else{
    
40.                 Element e = pq.poll();
    
41.                 visited[e.index] = true;
    
42.                 sb.append(e.c);
    
43.             }
    
44.         }
    
45.         return sb.toString();
    
46.     }
    
47. 
    
48.     static class Element{
    
49.         char c;
    
50.         int index;
    
51.         public Element(char c, int index){
    
52.             this.c = c;
    
53.             this.index = index;
    
54.         }
    
55.     }
    
56. }

复制代码

marthew777 发表于 2015-11-7 01:31
你这里的代码和我在 “沙发” 的代码是一样的，犯了一个致命错误，看漏了那个条件, "每个字母只能换到距 ...

的确:) 学习了。