g**********y
发帖数: 14569 | 1 赞！
试试G的题：
1. 二分找左右边界。
2. 常见题
3. 用一个collector收集结果，最底层的function:
isOverlapping(Rectangle a, Rectangle b)
collectCommon(ArrayList collector, Rectangle a, Rectangle b)
递归比较子节点，如果overlap, 进一步比较子节点，直到叶子，最后计算结果存入
collector。
4. 5.
6. DP
7. DFS
8. 计算P(i) = score(i)/sum(score[1..n]), 然后随机生成
9. 这个写起来最繁，45分钟内把头绪理清楚而且写清楚，我觉得很难，这是个大致框
架：
public class FindVertex {
ArrayList findVertices(Rectangle[] r) {
ArrayList collector = new ArrayList();
HashMap阅读全帖 |
|
y*********e
发帖数: 518 | 2 分层遍历，也可以用 vector 。
void levelTraverse(Tree root) {
Vector thisLevel = new Vector();
Vector nextLevel = new Vector();
thisLevel.add(root);
while (!thisLevel.isEmpty()) {
foreach (Tree tree in thisLevel) {
print(tree);
nextLevel.addAll(tree.children());
}
thisLevel.clear();
thisLevel.addAll(nextLevel);
nextLevel.clear();
println();
}
} |
|
g**********y
发帖数: 14569 | 3 换了种结构，ListArray + HashMap, code还是ugly, 稍
好点。
public class LiarLiar {
public int[] divide(String[] line) {
ArrayList list = new ArrayList();
HashMap pairs = new HashMap();
int N = Integer.parseInt(line[0].trim());
for (int i=0, j=1; i
String[] s = line[j].split(" ");
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim(... 阅读全帖 |
|
g**********y
发帖数: 14569 | 4 再换了种结构，这个快一些，100000人，每个人accuse 1~3个，1.3秒左右算出来。
public class LiarLiar {
public int[] divide(String[] line) {
int N = Integer.parseInt(line[0].trim());
HashMap map = new HashMap();
for (int i=0, j=1; i
String[] s = line[j].split(" ");
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
add(map, name, line[j].trim());
add(map, line[j].trim(), name);
}
}
HashSet a = new HashSet();
HashSet阅读全帖 |
|
A**u
发帖数: 2458 | 5 career cup 上的题目
Write a method that returns all subsets of a set.
想请教一下，递归的怎么写呢
这是career cup的java写法，我不懂java,完全看不懂， 请大家给个算法思路
ArrayList> getSubsets(ArrayList set,
2 int index) {
3 ArrayList> allsubsets;
4 if (set.size() == index) {
5 allsubsets = new ArrayList>();
6 allsubsets.add(new ArrayList()); // Empty set
7 } else {
8 allsubsets = getSubsets(set, index + 1);
9 int item = set.get(index);
10 ArrayList阅读全帖 |
|
m***n
发帖数: 2154 | 6 带返回路径的
public int miniSum(Node tree, ArrayList pre) {
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) {
pre.add(tree);
return tree.value;
}
ArrayList storeresult = new ArrayList();
int left= miniSum(tree.left, storeresult);
ArrayList storeresultright = new ArrayList();
int right = miniSum(tree.right,storeresultright);
pre.add(tree);
... 阅读全帖 |
|
e******x
发帖数: 184 | 7 非名校CS Master new grad~ 本科zju数学的
之前一心准备google，还是挂了
对machine learning，data mining比较感兴趣，不过这些组master好难进。
但自我感觉算法不错，求ms，fb大牛们的内推呢~~
把onsite的题抓上来~
1. Three coke machines. Each one has two values min & max, which means if
you get coke from this machine it will load you a random volume in the range
[min, max]. Given a cup size n and minimum soda volume m, show if it's
possible to make it from these machines.
比如三台machine(50, 100), (100, 200), (500, 1000). n=110, m=40, yes. n=90, m
=40, no. n=100, m=60, n... 阅读全帖 |
|
c*****r
发帖数: 108 | 8 题目是path sum||
过了小测试。但是没有过大测试。 fail的testcase 是一个堆非常复杂的+/-1 的树。
下面是我的code。 麻烦大家来抠一下吧。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
ArrayList> paths = new ArrayList
Integer>>();
pathSum_r(root, sum, new ArrayList(), paths);
ret... 阅读全帖 |
|
Y**3
发帖数: 21 | 9 我看你的代码逻辑和我的一样，本想改成像C++一样简洁的版本，后发现对java不熟
arraylist和vector还不一样，就放弃了，直接给去了几个没必要的if就过了large
case，八百多毫秒,看来java太慢啊。。。
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
ArrayList> paths = new ArrayList
Integer>>();
pathSum_r(root, sum, new ArrayList(), paths);
return paths;
}
private void pathSum_r(TreeNode root, int sum, ArrayList path,
ArrayList> paths... 阅读全帖 |
|
b****z
发帖数: 176 | 10 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
b****z
发帖数: 176 | 11 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
m***2
发帖数: 595 | 12 贴块砖，感觉是我见到的最容易理解好记的版本了
而且能够过最新的test （好多解法之前能过，最新的容易Memory超，感觉leetcode的
判断更严格了）
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> result = new ArrayList>();
if (start == null || end == null || start.length() != end.length() |
| dict.size() == 0) {
return result;
}
HashMap> visited = new HashMap
HashSet>();
... 阅读全帖 |
|
a*********4
发帖数: 7 | 13 来自主题: JobHunting版 - 一道面试题 a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}
public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set ... 阅读全帖 |
|
a*********4
发帖数: 7 | 14 来自主题: JobHunting版 - 一道面试题 a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}
public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set ... 阅读全帖 |
|
z****e
发帖数: 54598 | 15 import java.util.*;
public static List RemoveDup(List list){
if(list == null)
return null;
Set set = new HashSet();
set.addAll(list);
list.clear();
list.addAll(set);
return list;
} |
|
z****e
发帖数: 54598 | 16 import java.util.*;
public static List RemoveDup(List list){
if(list == null)
return null;
Set set = new HashSet();
set.addAll(list);
list.clear();
list.addAll(set);
return list;
} |
|
r******r
发帖数: 700 | 17 再问个与 Vector deprecated 相关的问题。如果不用 Vector, 就用 Collections.
synchronizedCollection(...). 因为它返回一个 “a synchronized (thread-safe)
collection backed by the specified collection. ”。
public static Collection synchronizedCollection(Collection c) {
return new SynchronizedCollection(c);
}
但是，在使用的时候，为何还要对返回的 collection c 再次 synchronized(c),如下
。不是已经安全了吗？
Collection c = Collections.synchronizedCollection(myCollection);
...
synchronized(c) {
Iterator i = c.iterator(); // Must ... 阅读全帖 |
|
f**********5
发帖数: 1073 | 18 Addall.com为你免费查价格，特别适合教科书
★ 发自iPhone App: ChineseWeb 7.3 |
|
b******g
发帖数: 1721 | 19 我随便说说啊，期待大牛。
包含的方法：就是一般的List class 的方法：get(index), add(object),
addAll(Collection), remove(object)， 还有就是相关的Iterator类的定义。
测试的话,
1. 这个是abstract 类，所以就还是需要一个具体类，extend class。
2. 测试的时候有个criteria: statement coverage, branch coverage or state
coverage over the design state chart, all methods or different use
cases.
3. 测试的方法： fuzz testing (random generate different input, here the
input is a set of different/same objects)
4.具体的工具，junit
欢迎补充。 |
|
g***s
发帖数: 3811 | 20 It is very quick even for n = Integer.MAX_VALUE;
public static void main(String arg[]){
preprocess();
int n=Integer.MAX_VALUE;
System.out.println("squares sum of " + n + " : ");
for (int num : getSquaresSum(n)){
System.out.print(" " + num);
}
System.out.println("\ntotal callCount= " + callCount);
}
public static Collection getSquaresSum(int n){
Stack cur = new Stack();
Stack阅读全帖 |
|
g***s
发帖数: 3811 | 21 1. sort all points (begin and end)
2. for (point x: all points smallest to largest)
3. if (x is a begin point)
add the segment of x into NonePointSet
4. else { // x is a end point
5 if (x is in the NonePointSet) {
6 set two events on day x;
7 clear NonePointSet & OnePointSet;
8 } else { x is in the OnePointSet) {
9 set one event on day x;
10 OnePointSet.addAll(NonePointSet);
11 clear NonePointSet
12 } // else the segment ... 阅读全帖 |
|
H***e
发帖数: 476 | 22 这题跟dp啥关系啊？
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
... 阅读全帖 |
|
s*******e
发帖数: 35 | 23 用HASHMAP 找出每个WORD 所在的位置 occurrence map，在做一个反向的由所在位置(
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List L = new LinkedList();
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap<... 阅读全帖 |
|
s*******e
发帖数: 35 | 24 用HASHMAP 找出每个WORD 所在的位置 occurrence map，在做一个反向的由所在位置(
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List L = new LinkedList();
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap<... 阅读全帖 |
|
e****e
发帖数: 418 | 25 public class LineReader {
private int pos = 0;
private List chars = null;
public Character[] readLine() {
if ( chars == null || chars.size() == 0 )
chars = Arrays.asList( read4096() );
List line = new ArrayList();
int i = pos;
while ( i < chars.size() && chars.get(i) != '\n' && chars.get(i) !=
'\0' )
line.add( chars.get(i++) );
if ( chars.get(i) == '\n' ) {
... 阅读全帖 |
|
D********g
发帖数: 650 | 26 加上了backtracking:
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
f... 阅读全帖 |
|
h*******n
发帖数: 614 | 27 来自主题: JobHunting版 - FB面经~ 我用的就是你的算法
public void printBinaryWithLength(int n){
System.out.print(getBinaryWithLength("", n));
}
private ArrayList getBinaryWithLength(String prefix, int n) {
ArrayList result = new ArrayList();
if(n==0){
result.add(prefix);
return result;
}
ArrayList list1 = getBinaryWithLength(prefix+"0", n-1);
ArrayList list2 = getBinaryWithLength(prefix+"1", n-1);
result.ad... 阅读全帖 |
|
e******x
发帖数: 184 | 28 牛逼！就是先排序，奇数取中间点，偶数中间两点以及他们间任意点都可以~
如果它的addAll没有call add呢，这样那个count也要加n~ 可能我题没说清楚，大概是
这个list每次insert一次count就加一吧。。
add |
|
s*****9
发帖数: 93 | 29 用了DP，同时用了HashSet防止重复结果，运行时间无法通过Large Test. HashSet的查
找不是应该O(1)时间吗？怎样才能更快呢？请帮忙看一下：
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
HashSet> final_set = new HashSet
Integer>>();
ArrayList current_list = new ArrayList();
threeSumRecur(num, 0, current_list, final_set);
ArrayList> final_lists = new ArrayList
Integer>>();
... 阅读全帖 |
|
l**********1
发帖数: 415 | 30 Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
the given api is
public ArrayList> combine(int n, int k)
the solution I got is as follows which is really slow O(n!) and time out at
10,7. So please provide any idea of higher efficiency algorithm for this
one. Thanks in advance
public void combination(ArrayList> r... 阅读全帖 |
|
c********r
发帖数: 286 | 31 Java的reference type like arraylist 也有个比较麻烦的地方就是要经常addall一下
，C++的vector就不需要
just my 2 cents |
|
h********0
发帖数: 74 | 32 public ArrayList> combine_iterative(int n, int k) {
ArrayList> result = new ArrayList>
();
ArrayList list;
int end = n-k+1;
for(int i=1; i<= end; i++){
list = new ArrayList();
list.add(i);
result.add(list);
}
ArrayList listTmp;
for(int i = 1; i< k; i++){
//int len = result.size();
for(int j = result.size(); j>0; j-- ){
list = ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 33 Methods inherited from class java.util.AbstractCollection
addAll, containsAll, retainAll, toArray, toArray, toString
toArray是从一个abstract class里继承下来的，跟set interface无关 |
|
z****e
发帖数: 54598 | 34 leetcode 不超过两秒就可以过大oj
我用了800毫秒，还有1200毫秒富余
把你的code贴上来看看
Run Status: Accepted!
Program Runtime: 864 milli secs
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> list = new ArrayList
>>();
Set set = new HashSet>();
Arrays.sort(num);
for(int i=0;i
... 阅读全帖 |
|
b**m
发帖数: 1466 | 35 我的理解就是个DFS， 我写的有啥问题吗？
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results = new ArrayList();
if(root==null){
return results;
}
... 阅读全帖 |
|
t**********r
发帖数: 2153 | 36 这个是过了OJ的code.为了不超时,加了点tweak.看起来没有以前那么好看了.
public static ArrayList> threeSum(int[] inputs) {
if (inputs == null || inputs.length <= 2) {
// throw new IllegalArgumentException("Invalid inputs");
return new ArrayList>();
}
Arrays.sort(inputs);
Set> matchedTriplets = new HashSet
Integer>>();
for (int i = 0; i < inputs.length - 2; i++) {
if (inputs[i] > 0... 阅读全帖 |
|
l*******A
发帖数: 209 | 37 啊，你说的第二点很对.大意了,忘了检查一下...
你说的第一点我不太理解,用HashSet是为了避免加入同样的ArrayList,返回一
个set,然后可以用set的API来读任何一个元素啊
大不了再造一个ArrayList> result,然后result.addAll(set),
return result.
hashset |
|
l*****n
发帖数: 52 | 38 leetcode subset 我用eclipse调试
import java.util.*;
public class subSets {
public static HashSet> subsets(int[] s){
HashSet> result = new HashSet
>();
if(s.length == 0|| s== null) return null;
//Arrays.sort(s);
ArrayList list = new ArrayList();
recursion(result,list,s,0);
return result;
}
public static void recursion(HashSet> result,
Array... 阅读全帖 |
|
z****e
发帖数: 54598 | 39 public void printPrimeNum(int num) {
List list = new ArrayList();
//1
int sqrt = (int) Math.round(Math.sqrt(num));
//2
for (int i = 2; i <= sqrt; i++) {
boolean isPrime = true;
for (int j : list) {
if (i % j == 0) isPrime = false;
}
if (isPrime) list.add(i);
}
//3
List temp = new ArrayList();
for (int i = sqrt + 1; i <= nu... 阅读全帖 |
|
m*******1
发帖数: 77 | 40 写了一个平方复杂度的，但是一直超时。请大家帮忙看看。
public ArrayList> fourSum(int[] num, int target) {
Map cache = new HashMap();
Map> previous = new HashMap
Integer>>();
ArrayList> result = new ArrayList
Integer>>();
Set nima = new HashSet();
if (num.length < 4) {
return result;
}
Arrays.sort(num);
for (int i = ... 阅读全帖 |
|
n*******s
发帖数: 482 | 41 Given four number a0, a1, a2, a3,..., ak
Find all possible expression to using + - * / with any '(',')' to generate a
result equals to target X.
上来就想了
1. 数字permutation （k！种）
2. 然后在数字之间插operator ： +-*/ （k-1 spaces， total possibility 4^(k-1
))
3. 加括号，就是生成所有叶子数为k的树，简单起见就是用binary tree了
List GenTree(oprand[s..e])
{
List allTress = new List();
if(s==e)
allTrees.add(new Node(s));
return allTrees.
for i=s to e-1:
... 阅读全帖 |
|
D***0
发帖数: 138 | 42 网上申请的，回复的挺快，安排了code challenge，一道题，不限时，半个小时写完了
，发过去，第二天收到了thank you but 88.不知道哪里的问题。
* Write a function that takes two parameters:
* (1) a String representing a text document and
* (2) an integer providing the number of items to return.
* Implement the function such that it returns a list of Strings ordered by
word frequency,
* the most frequently occurring word first.
* Use your best judgement to decide how words are separated.
* Your solution should run in O(n) time where n is the number of cha... 阅读全帖 |
|
f********c
发帖数: 147 | 43 这题试了好几个办法总是通不过，按说不难的，求帮忙看看，谢谢！
public class Solution {
public List> levelOrder(TreeNode root) {
List> result = new ArrayList>();
if(root == null) return result;
Queue current = new LinkedList(); //store
current level TreeNode
current.add(root);
List levelValue = new ArrayList(); //store
elements in current level
while(!current.isEmpty()) {
Queue阅读全帖 |
|
|
|
T******g
发帖数: 790 | 46 不自己写Node->LinkedList了，直接import java.util.*;?
可以不可以？比如这个切割链表的代码:package chapter2;
import java.util.*;
public class CC2_4{
public static LinkedList partition(LinkedList list,int k){
if(list==null)
return null;
LinkedList less=new LinkedList();
LinkedList noLess=new LinkedList();
for(int i=0;i
if(list.get(i)
less.add(list.get(i));
}else{
noLess.add(list.get(i));
}
}
less.addAll(noLess);
return less;
}
public static void mai... 阅读全帖 |
|
r*******e
发帖数: 971 | 47 List next=new ArrayList<>();
int prev=0,sum=0;
while(curr!=null&&!curr.isEmpty()){
for (NestedInteger ni:curr){
if (ni.isInteger())
prev+=ni.getInteger();
else
next.addAll(ni.getList());
}
curr=next;
next=new ArrayList<>();
sum+=prev;
}
return sum;
//其实不需要记录层数 |
|
r*******e
发帖数: 971 | 48 List next=new ArrayList<>();
int prev=0,sum=0;
while(curr!=null&&!curr.isEmpty()){
for (NestedInteger ni:curr){
if (ni.isInteger())
prev+=ni.getInteger();
else
next.addAll(ni.getList());
}
curr=next;
next=new ArrayList<>();
sum+=prev;
}
return sum;
//其实不需要记录层数 |
|
c*****e
发帖数: 3226 | 49 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.len... 阅读全帖 |
|
g*******e
发帖数: 107 | 50 public zero_one_multiple(int N){
HashMap> map=new HashMap
Integer>> ();
int jj=0;
ArrayList remain=new ArrayList();
remain.add(0);
long resD=1;
while (resD
int residue=(int) (resD%N);
if (residue==0) return resD;
jj++;
int size=remain.size();
for (int i=0; i
int tmp=remain.get(i)+residue;
if ((tmp%N)==0) {
ArrayList res... 阅读全帖 |
|
