一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2205|回复: 17
收起左侧

一道google的题目,至今没看到正确答案。

[复制链接] |试试Instant~ |关注本帖
duduhaha 发表于 2016-4-3 13:07:01 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away-google 1point3acres

大家以上面关键字google 搜一下就会看见geeksforgeeks 的这道题目。
里面评论的人给了个反例,string "aaaabbbcc" and d=2. your algorithm give output "cannot be rarranged" by considering string as "abababacc", but there is a solution as "bababacac".



. 鍥磋鎴戜滑@1point 3 acres
这就意味着贪心 先放频率最多的字符是错误的,大家有什么好解法吗?这是google面经的常见题目。.鐣欏璁哄潧-涓浜-涓夊垎鍦
hanabeast 发表于 2016-4-3 13:42:15 | 显示全部楼层
public String reArrangeChar(String str, int k) {
                if (str == null || str.length() == 0) {
                        return str;
                }.1point3acres缃

                int len = str.length();

                //count the freq of every char
                Map<Character, Node> map = new HashMap<>();
                for (int i = 0; i < str.length(); i++) {
                        char c = str.charAt(i);-google 1point3acres
                        if (!map.containsKey(c)) {. 1point3acres.com/bbs
                                Node temp = new Node(c);
                                temp.freq++;
                                map.put(c, temp);
                        } else {
                                map.get(c).freq++;
                        }
                }. from: 1point3acres.com/bbs

                //Put them into Heap
                Queue<Node> heap = new PriorityQueue<Node>(10, new MyComparator());
                for (Node node : map.values()) {
                        heap.offer(node);
                }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                StringBuilder sb = new StringBuilder();
                Queue<Node> q = new LinkedList<>();
                for (int currIndex = 0; currIndex < len; currIndex++) {
                        if (!q.isEmpty() && q.peek().lastPos + k < currIndex) {
                                heap.offer(q.poll());
                        }. From 1point 3acres bbs
                       
                        if (heap.isEmpty()) {
                                return "Not Valid";
                        }
                       
                        Node curr = heap.poll();
                        curr.lastPos = currIndex;
                        curr.freq--;. 鍥磋鎴戜滑@1point 3 acres
                       
                        sb.append(curr.c);
                       
                        if (curr.freq != 0) q.offer(curr);
                }
                return sb.toString();.鐣欏璁哄潧-涓浜-涓夊垎鍦
               
        }
        class Node {
                char c;
. from: 1point3acres.com/bbs                 int freq;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                int lastPos;

                public Node(char c) {
                        this.c = c;
                }
        }

        class MyComparator implements Comparator<Node> {
                public int compare(Node one, Node two) {
                        if (one.freq != two.freq) {
                                return one.freq > two.freq ? -1 : 1;
                        }. Waral 鍗氬鏈夋洿澶氭枃绔,
                        return one.c - two.c;
                }
        }
回复 支持 2 反对 1

使用道具 举报

heroic 发表于 2016-9-12 01:25:46 | 显示全部楼层
直接用256大小数组表示string啊 每次找最大值也是O(1)的时间,其实对于所有有限的字母 字符串 直接开数组用下标计数会比hashmap或heap快很多。
回复 支持 0 反对 1

使用道具 举报

hanabeast 发表于 2016-4-3 13:42:05 | 显示全部楼层
public String reArrangeChar(String str, int k) {                 if (str == null || str.length() == 0) {                         return str;                 }                  int len = str.length();                  //count the freq of every char                 Map<Character, Node> map = new HashMap<>();                 for (int i = 0; i < str.length(); i++) {                         char c = str.charAt(i);                         if (!map.containsKey(c)) {                                 Node temp = new Node(c);                                 temp.freq++;                                 map.put(c, temp);                         } else {                                 map.get(c).freq++;                         }                 }                  //Put them into Heap                 Queue<Node> heap = new PriorityQueue<Node>(10, new MyComparator());                 for (Node node : map.values()) {                         heap.offer(node);                 }                  StringBuilder sb = new StringBuilder();                 Queue<Node> q = new LinkedList<>();                 for (int currIndex = 0; currIndex < len; currIndex++) {                         if (!q.isEmpty() && q.peek().lastPos + k < currIndex) {                                 heap.offer(q.poll());                         }                                                  if (heap.isEmpty()) {                                 return "Not Valid";                         }                                                  Node curr = heap.poll();                         curr.lastPos = currIndex;                         curr.freq--;                                                  sb.append(curr.c);                                                  if (curr.freq != 0) q.offer(curr);                 }                 return sb.toString();                          }         class Node {                 char c;                 int freq;                 int lastPos;                  public Node(char c) {                         this.c = c;                 }         }          class MyComparator implements Comparator<Node> {                 public int compare(Node one, Node two) {                         if (one.freq != two.freq) {                                 return one.freq > two.freq ? -1 : 1;                         }                         return one.c - two.c;                 }         }
回复 支持 1 反对 0

使用道具 举报

leolyq 发表于 2016-4-3 14:44:29 来自手机 | 显示全部楼层
用hashtable统计每个字符出现的次数,并按次数从大到小排序;然后分桶存放每个字符,具体做法是,分n个桶,每个桶长度为distance,按照第一步的顺序,按序将每个字符插入到每个桶里,注意最后一个桶大小可能小于distance的处理,应该就可以。
回复 支持 反对

使用道具 举报

 楼主| duduhaha 发表于 2016-4-3 15:51:27 | 显示全部楼层
hanabeast 发表于 2016-4-3 13:42. 鍥磋鎴戜滑@1point 3 acres
public String reArrangeChar(String str, int k) {
                if (str == null || str.length() == 0) {
                        retu ...

你这个答案应该是对的,厉害啊!
回复 支持 反对

使用道具 举报

牛仔很忙 发表于 2016-4-4 06:03:10 | 显示全部楼层
hanabeast 发表于 2016-4-3 13:42
public String reArrangeChar(String str, int k) {                 if (str == null || str.length() == 0) {                         return ...
-google 1point3acres
正解,真是厉害&#128077;
回复 支持 反对

使用道具 举报

raindreamer 发表于 2016-4-4 16:40:05 | 显示全部楼层
这代码是正解?. visit 1point3acres.com for more.
这不就是错误的贪心吗。。。能过LZ说的sample吗
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-4 22:58:15 | 显示全部楼层
是不是得backtracking ……… try所有情况……
回复 支持 反对

使用道具 举报

yalyka 发表于 2016-4-6 01:13:00 | 显示全部楼层
hanabeast 发表于 2016-4-3 00:42
public String reArrangeChar(String str, int k) {. visit 1point3acres.com for more.
                if (str == null || str.length() == 0) {
                        retu ...

仿佛看到了群里的小伙伴!
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-11 06:03:15 | 显示全部楼层
hanabeast 发表于 2016-4-3 13:42
public String reArrangeChar(String str, int k) {
                if (str == null || str.length() == 0) {
                        retu ...
. 1point 3acres 璁哄潧
这个代码并没有解决楼主所说的情况啊。。。
回复 支持 反对

使用道具 举报

Kimurate 发表于 2016-5-29 01:10:16 | 显示全部楼层
d=2的话就是隔一个吧?"aaaabbbcc" -> "ababacabc",可以用贪心啊。
回复 支持 反对

使用道具 举报

qinqinhao 发表于 2016-5-29 10:34:11 | 显示全部楼层
题目没有说清楚是at-least-d-distance还是exact-d-distance
. 1point 3acres 璁哄潧后者的话答案是bababacac
回复 支持 反对

使用道具 举报

Kimurate 发表于 2016-5-30 00:30:31 | 显示全部楼层
qinqinhao 发表于 2016-5-28 18:34
题目没有说清楚是at-least-d-distance还是exact-d-distance. visit 1point3acres.com for more.
后者的话答案是bababacac

题目的标题就是:rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away. from: 1point3acres.com/bbs
。。。
回复 支持 反对

使用道具 举报

qinqinhao 发表于 2016-5-30 04:45:07 | 显示全部楼层
请教exact如何做...
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-30 12:47:42 | 显示全部楼层
这是道FB题吧 当年面FB的时候做过。。贪心应该是可解的。。
  1. public static String taskScheduler(String tasks, int n) {-google 1point3acres
  2.                 StringBuilder sb = new StringBuilder();
  3.                 HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();
  4.                 for(char c : tasks.toCharArray()) countMap.put(c, countMap.containsKey(c) ? countMap.get(c) + 1 : 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 // sort the task by their occurence time (N/c * c *logk)
  6.                 PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>(){
  7.                         public int compare(Map.Entry<Character,Integer> e1, Map.Entry<Character,Integer> e2) {.1point3acres缃
  8.                                 return e2.getValue() - e1.getValue();
  9.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.                 });. visit 1point3acres.com for more.

  11.                 for(Map.Entry entry : countMap.entrySet()) queue.offer(entry);
  12.                
  13.                 while(!queue.isEmpty()) {. more info on 1point3acres.com
  14.                         List<Map.Entry> refill = new ArrayList<Map.Entry>();
  15.                         int i = 0;
  16.                         for(i = 0; i < n && !queue.isEmpty(); i++) {
  17.                                 Map.Entry e = queue.poll();
  18.                                 sb.append(e.getKey());
  19.                                 int count = (Integer)e.getValue();. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                                 if(count > 1) refill.add(new AbstractMap.SimpleEntry<Character, Integer>((Character)e.getKey(), count - 1));
  21.                         }
  22.                         while(i++ < n && refill.size() > 0) sb.append("_");
  23.                         // refill the task which hasn't finished yet
  24.                         for(Map.Entry e : refill) queue.offer(e);
  25.                 }
  26.                 return sb.toString();
  27.         }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

penggeqiang 发表于 2016-5-31 03:13:47 | 显示全部楼层
#include "stdio.h"
int findmax(int *m, int len)
{
        int i;. Waral 鍗氬鏈夋洿澶氭枃绔,
        int max = 0;
        for(i = 0; i < len; i++){
                if(m[i] > max){. 1point 3acres 璁哄潧
                        max = i;
                }-google 1point3acres
        }
        return max;
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

char *rearrange(char *a, int d)
{
        int m[128];
        char am[128];
        int i;
        for(i = 0; i < 128; i++){
                m[i] = 0;
        }
        char *r = malloc(strlen(a)+1);. Waral 鍗氬鏈夋洿澶氭枃绔,
        if(r == NULL){
                return NULL;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
        memset(r, 0, strlen(a)+1);
        char *p = a;
        while(*p){
                m[*p]++;
                p++;
        }
        int c = 0;
        int max = findmax(m, 128);.1point3acres缃
        int len = strlen(a);
        int curidx = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        int nd = 1;
        while(m[max] > 0){
                int j = m[max];-google 1point3acres
                m[max] = 0;
                int startpos = curidx;
                for(; j > 0; curidx+=d,j--){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        if(curidx >= len){
                                curidx = nd;
                                nd++;
                        }
                        r[curidx] = max;
                        int dx = curidx - startpos;
                        if(dx < 0){
                                dx = 0 - dx;
                        }
                        if(dx < d){
                                return NULL;
                        }
. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
                max = findmax(m, 128);
        }. from: 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
        return r;
}
int main(int argc, char**argv)
{. more info on 1point3acres.com
        char *a = "aaaabbbcc";
. From 1point 3acres bbs        char *ret = rearrange(a, 3);-google 1point3acres
        printf("ret=%s\n", ret);
}
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-12 00:29:45 | 显示全部楼层
除了maxheap, 同事维护一个size = d-1的queue就行,(d如果等于2就相当于另外一道题,不能连续,这种情况其实可以不用queue,直接check一下Peek的character是不是等于last string position的就行)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表