B*****7
发帖数: 137 | 1 自己写了一个code，和大多数网上的code一样，基本思路就是bfs。但要过大oj还真不
容易。我refactor了半天也只能有大概一半的概率过。过的时候时间都是800 ms 以下
（～750 ms），只有一次到过800 ms. 所以强烈怀疑这道题的时间上限是800 ms. LOL
我附了code，用java写的。大牛们帮忙看看该怎么改进？先谢谢啦。
public class Solution {
public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
int m = board.length;
if( m == 0 ) return;
int n = board[0].length;
// special cases
if( m < 3 || n < 3 ) return;
// p... 阅读全帖 |
|
g**********y
发帖数: 14569 | 2 就是简单的BFS, 运行很快，对N=25, 16ms。f(19)=299, f(25)=899
public class MonkeyWalk {
public final static void main(String[] args) {
new MonkeyWalk().run(25);
}
private void run(int N) {
ArrayDeque queue = new ArrayDeque();
queue.add(new Point(0, 0));
HashSet visited = new HashSet();
visited.add("0 0");
while (!queue.isEmpty()) {
Point p = queue.pop();
visit(p.x+1, p.y, queue, visite... 阅读全帖 |
|
g**********y
发帖数: 14569 | 3 public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];
ArrayDeque q = new ArrayDeque();
for (int i=0; i
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}
b[0] = a[q.peekFirst()];
for (int i=w; i
while (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[... 阅读全帖 |
|
g**********y
发帖数: 14569 | 4 public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];
ArrayDeque q = new ArrayDeque();
for (int i=0; i
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}
b[0] = a[q.peekFirst()];
for (int i=w; i
while (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[... 阅读全帖 |
|
g**********y
发帖数: 14569 | 5 把HashSet换成boolean的话，对N=25, 速度可以从2.8秒提到0.2秒。
对N=25, x/y = +/-899 就是边界，所以二维数组[2000][2000]就足够存储所有访问过的点。
程序：
public class MonkeyWalk {
public final static void main(String[] args) {
long t0 = System.currentTimeMillis();
new MonkeyWalk().run(25);
long t1 = System.currentTimeMillis();
System.out.println(t1 - t0);
}
private ArrayDeque queue;
private boolean[][] visited;
private int count = 0;
private void run(int N) {
... 阅读全帖 |
|
l****1
发帖数: 19 | 6 上一个自己写的第三题的Java实现。请求大神门指教。。
顺便为明天G电面intern攒点人品。。
import java.util.*;
public class MaxWindow{
public LinkedList findMax(int[] in, int k){
ArrayDeque deque=new ArrayDeque();
LinkedList result=new LinkedList();
for(int i=0;i
if(!deque.isEmpty() && deque.getFirst().index<=i-k)
deque.pollFirst();
while(!deque.isE... 阅读全帖 |
|
l****1
发帖数: 19 | 7 上一个自己写的第三题的Java实现。请求大神门指教。。
顺便为明天G电面intern攒点人品。。
import java.util.*;
public class MaxWindow{
public LinkedList findMax(int[] in, int k){
ArrayDeque deque=new ArrayDeque();
LinkedList result=new LinkedList();
for(int i=0;i
if(!deque.isEmpty() && deque.getFirst().index<=i-k)
deque.pollFirst();
while(!deque.isE... 阅读全帖 |
|
s**********e
发帖数: 326 | 8 昨天面的，面试官首先迟到了将近五分钟，上来面试官简单介绍了他自己，然后就直接
进入主题，也没有让我做自我介绍啥的，上来问我有没有用过java iterator pattern,
我给听成intepreter, 回答没用过，他不相信，又问了一遍，恍然大悟，赶紧说用过
用过，用过很多，然后他还说用java的人不可能没用过
然后问为什么用iterator, 有啥好处
答了之后接着问java里面有几种list, 答arraylist和linkedlist
又问实现这两种不同list的iterator有什么不同，到此为止都是对答如流，问他我答的
是不是他想要的答案，他说exactly
答完以后开始出题，先是写个data structure, 让我guess这是什么data structure,
class N {
private N l; // can be null
private N r; // can be null
private String data;
}
一紧张说成linkedlist, 赶紧改口说是tree,
然后就是描述问题，要求写一个Iterator, 每... 阅读全帖 |
|
x******0
发帖数: 178 | 9 虽然是老题，但是写起来还是很费劲，唉。。
public static ArrayList SlidingWindowMax(int[] arr, int windowSize){
//edge case
ArrayList res = new ArrayList();
ArrayDeque indexQ = new ArrayDeque();
for (int i = 0; i < windowSize; i++){
while (!indexQ.isEmpty() && arr[i] > indexQ.getLast()){
indexQ.pollLast();//only keep possible max
}
indexQ.add(i);
}
for (int i... 阅读全帖 |
|
h****3
发帖数: 89 | 10 请各位指点一下，java如果用ArrayDeque来代替双向链表，哪一步是bottleneck导致速
度太慢？
感觉用ArrayDeque的写法code简单很多，思路也很好想 |
|
g**********y
发帖数: 14569 | 11 写了个9的Java ->
public class SimplifyPath {
public String simplify(String path) {
String[] segs = path.split("/");
Deque d = new ArrayDeque();
for (String seg : segs) {
if (".".equals(seg) || "".equals(seg)) {
continue;
}
else if ("..".equals(seg)) {
if (!d.isEmpty()) d.removeLast();
}
else {
d.addLast(seg);
}
}
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 12 写了个9的Java ->
public class SimplifyPath {
public String simplify(String path) {
String[] segs = path.split("/");
Deque d = new ArrayDeque();
for (String seg : segs) {
if (".".equals(seg) || "".equals(seg)) {
continue;
}
else if ("..".equals(seg)) {
if (!d.isEmpty()) d.removeLast();
}
else {
d.addLast(seg);
}
}
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 13 这个题不好写的是状态保存和转换。
最多5个peg, 8个disc, 所以可以用long(64-bit)来保存状态，转换需要位操作。
这是我的写法，欢迎改进：
public class KPeg {
public void move(int N, int K, int[] begin, int[] end) {
long s0 = stateToLong(begin);
long sn = stateToLong(end);
ArrayList visited = new ArrayList();
visited.add(new Node(s0, 0, 0, -1));
Deque dq = new ArrayDeque();
dq.add(0);
while (!dq.isEmpty()) {
int current = dq.remov... 阅读全帖 |
|
S**I
发帖数: 15689 | 14 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
b********6
发帖数: 97 | 15 贴个我刚通过的解法 608ms
public class LRUCache {
static public class Pair {
int key;
int val;
Pair before;
Pair next;
public Pair(int k, int v){
key = k;
val = v;
before = null;
next = null;
}
}
//private LinkedList< Pair > item_list ;
//private ArrayDeque item_list;
private Pair head;
private Pair tail;
private HashMap item_map;
private int cap;
... 阅读全帖 |
|
p*******2
发帖数: 50 | 16 这个circular array可以直接用ArrayDeque？
StringBuilder |
|
l*n
发帖数: 529 | 17 good point, java arraydeque就是现成的circular array。 |
|
A****L
发帖数: 138 | 18 public class WordLadderII {
public class Ladder { //Define Ladder class it's important
public Ladder parent;
public String word;
public Ladder(Ladder prev,String w) {parent=prev;word=w;}
}
public ArrayList> findLadders(String start, String end
, HashSet dict) {
ArrayList> ladders = new ArrayList
String>>();
Ladder ladder = new Ladder(null,end); //Here we look from end to
start ... 阅读全帖 |
|
A****L
发帖数: 138 | 19 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String sta... 阅读全帖 |
|
A****L
发帖数: 138 | 20 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String sta... 阅读全帖 |
|
y**********a
发帖数: 824 | 21 遍历所有的可能性，计算。
public int maxResult(int[]A) {
int[]rel=new int[1];rel[0]=Integer.MIN_VALUE;
dfs(A, new int[A.length-1], 0, rel);
return rel[0];
}
void dfs(int[]A, int[]op, int i, int[] max) {
if (i==op.length) {
StringBuilder s=new StringBuilder();
s.append(Integer.toString(A[0]));
char[] opc=new char[4];
opc[0]='+';opc[1]='-';opc[2]='*';opc[3]='/';
for (int j=0;j
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 22 1. 拉格朗日定理：任何一个整数都可以分解成4个整数的平方和。
2. a_i <= sqrt(T)
3. BFS, search one square sum (0 ~ sqrt(T)), then two square sum, ... it
will end at most level 4.
程序可能可以更高效 －－
public List split(int N) {
int n = (int) Math.sqrt(N);
int[] square = new int[n];
for (int i=0; i
List[] res = new List[N];
res[0] = new ArrayList();
Queue queue = new ArrayDeque();
q... 阅读全帖 |
|
o******h
发帖数: 1142 | 23 public class Solution {
List> results;
List list;
Map> map;
public List> findLadders(String start, String end, Set<
String> dict) {
results= new ArrayList>();
if (dict.size() == 0)
return results;
int curr=1,next=0;
boolean found=false;
list = new LinkedList();
map = new HashMap阅读全帖 |
|
c********t
发帖数: 5706 | 24 你说得对，因为只需要唤醒一个。但是为什么要用循环数组，直接用LinkedList或
ArrayDeque不行吗？
|
|
c********t
发帖数: 5706 | 25 原谅我再执着问一次。synchronized 等待状态是block，不需要唤醒, 和wait是有区别
的。notify是唤醒wait状态的。到底会不
会有enque, deque同时wait的时候呢？如果没有，那notify只会wake对方的莫个thread
, 我写了一个最简单的，没用
notifyAll, 用的notify. 这个也是每次只唤醒一个线程。但如果有enque,
deque同时wait，这代码会有应该有deadlock，但是测试了很多次，上百线程，也没有
发生deadlock. 请大牛们帮看看下面代码有问题吗？
public class BlockingQueue3 {
private Deque queue;
private int limit = 10;
public BlockingQueue3(int pLimit) {
limit = pLimit;
queue = new ArrayDeque<>();
}
public synchronized void put(T ite... 阅读全帖 |
|
