google电面+onsite+加面

lz sidewalk那道题用位运算可以吗？建立四个25位（2进制）的数，最终四个数字都应该是 1…1（25个1）

炸弹人的follow up楼主怎么答的？

mooc 发表于 2016-10-4 01:52
哦，是一维的是吗？

对。~~~~~~~

兰橘清檬 发表于 2016-10-4 03:28
lz sidewalk那道题用位运算可以吗？建立四个25位（2进制）的数，最终四个数字都应该是 1…1（25个1）

就是他不一定是下到 1 ~ 2 这样的位置，有可能是1.05 ~ 2.05，然后1.06 ~ 2.06这样。

virpro 发表于 2016-10-6 07:01
炸弹人的follow up楼主怎么答的？

我乱七八糟答的。

我就是说既然有很多空的，那我们就只存炸弹和墙，变成两个list。然后再算位置。

她说这是一种方法，还有别的方法吗？我说压缩，她说怎么压缩呢？我想啊想，我说是不是类似线段树？她说对。然后就没时间了。

第一题：

import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    OtherClass myObject = new OtherClass();
           System.out.println(myObject.get("google","algorithm"));
  }
}

// you can add other public classes to this editor in any order
public class OtherClass
{
  public String get(String original,String order){
          HashMap<Character,String> map=new HashMap<>();
   
    for(int i=0;i<order.length();i++){
      char c=order.charAt(i);
      map.put(c,"");
    }
   
    String tail="";
    for(int i=0;i<original.length();i++){
      char c=original.charAt(i);
      if(map.containsKey(c)){
              map.put(c,map.get(c)+c);
      }
      else
        tail+=c;
    }
   
    String result="";
    for(int i=0;i<order.length();i++){
      char c=order.charAt(i);
      result+=map.get(c);
    }
   
    result+=tail;
   
    return result;
  }
}

hcheng81 发表于 2016-10-6 08:52
就是他不一定是下到 1 ~ 2 这样的位置，有可能是1.05 ~ 2.05，然后1.06 ~ 2.06这样。

这样呀，感谢啦

楼主结果出来了吗？

感觉sparse的炸弹人可以用quad tree来存吧，解的话提供一个query方法，查这一行或者一列的炸弹，既然是sparse的，quad tree大多数分支都应该很浅，这样返回应该也是很快的

lld 发表于 2016-10-26 05:58
楼主结果出来了吗？

上周才ｔｅａｍ　ｍａｔｃｈ完毕。说这周ｆｉｎａｌ　ｒｅｖｉｅｗ了。