c********l
发帖数: 8138 | 1 这题不难啊....
建一个ArrayList，代表所有的words，
ArrayList每一个成员都是一个String
巨简单 |
|
w****3
发帖数: 110 | 2 i表示计算的长度，j表示最后一切的位置，0放入index0，L放入最后一个index为编程
方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 2; i < a.size(); i++) {
dp[2][i] = a.get(i) - a.get(i-2);
}... 阅读全帖 |
|
w****3
发帖数: 110 | 3 是我想错了，dp的时候再加一层循环，最后return 20.复杂度似乎是n^3
其实和楼上几位的想法是一样的，先将切每段短的木料的cost算出来，每次新加一段的
时候，尝试第一刀切在这段之前的所有位置，切成两段以后的cost都已经知道了，所以
在这k个切法里找到最小的存下来即可。
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 1; i < a.size(); i++) {
dp[... 阅读全帖 |
|
r******g
发帖数: 138 | 4 对第四轮
public static String getDecimal(int a, int b){
if(a == 0)
return "0.0";
if(b == 0)
return "";
StringBuilder res = new StringBuilder();
res.append(a/b);
res.append(".");
int c = a;
HashMap mod = new HashMap();
ArrayList decimals = new ArrayList();
int index=0;
while(c%b !=0 && !mod.containsKey(c%b)){
... 阅读全帖 |
|
S******1
发帖数: 216 | 5 来自主题: JobHunting版 - FB 面筋
Minimum
写一个考虑顺序的inverted indexing做法
//7:10
//给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
int findMinWindow(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return -1;
if (p.isEmpty())
return 0;
Map> indexMap = new HashMap
Integer>>();
for (int i = 0; i < s.length(); i++) {
if (!indexMap.containsKey(s.charAt(i)))
indexMap.put(s.charAt(i), new Arra... 阅读全帖 |
|
z****e
发帖数: 54598 | 6 arraylist复杂度是o(n)那是最糟糕的情况
这个考官也是不懂
arraylist的insert明明是o(1) amortized
因为list本身有长度，如果超过了，需要扩充内存
但是平均起来是个常量
这个题目也不少太少见，见过几次 |
|
z****e
发帖数: 54598 | 7 arraylist这个类根本没有append和insert方法，只有一个add
java的list接口就只定义了add，没定义其他方法
看下面
我问楼主后的答覆
发信人: duck (五月飞花), 信区: JobHunting
标 题: Re: 问一个时间复杂度的问题，求教求教
发信站: BBS 未名空间站 (Sat May 31 11:44:06 2014, 美东)
我就是用了add 而已
他问我ArrayList的add是什么时间的
我张口就,常数阿
他表示很质疑 |
|
a**********0
发帖数: 422 | 8 继续consumer和producer的例子
package jc;
import java.util.*;
//what about there are two things to be synchronized?
public class ProCon2nd {
// a class object to store the strings
static List myListOne = new ArrayList();
static List myListTwo = new ArrayList();
// this is the thing getting synchronized
// it is static as it is the same for all instances
static Object myLock = new Object();
public void produce(){
... 阅读全帖 |
|
a**********0
发帖数: 422 | 9 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
a**********0
发帖数: 422 | 10 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
j**7
发帖数: 143 | 11 1.)
/*
* print all paths from root to leaf.
*/
public static void printPaths(TreeNode root) {
if (root == null) {
return;
}
ArrayList path = new ArrayList();
// post order tree traversal.
Stack st = new Stack();
st.add(root);
while (st.isEmpty() == false) {
TreeNode current = st.pop();
if (current == null) {
current = st.pop();
... 阅读全帖 |
|
f********c
发帖数: 147 | 12 这题试了好几个办法总是通不过，按说不难的，求帮忙看看，谢谢！
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阅读全帖 |
|
p****6
发帖数: 724 | 13 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后
建立一个HashMap, key是index, value是list
贴个java版本的
public List> printVertical1(TreeNode root){
List> res = new ArrayList>();
if(root == null)
return res;
Map> map = new HashMap
TreeNode>>();
getVertical(root, map, 0);
Set keys = new TreeSet(map.keySet());
... 阅读全帖 |
|
s********e
发帖数: 340 | 14 下面是一个简单的程序， add方法有错误，错误原因说是参数不对。请问能否解释一下
为什么？
如果使用泛型，该如何改才是正确？谢谢！
import java.util.ArrayList;
public class CollectionTest {
public static void addToString(ArrayListcollection,Object element){
collection.add(element);
}
} |
|
c******3
发帖数: 296 | 15 public static void addToString(ArrayListcollection,T element)
或者土一点：
public static void addToString(ArrayListcollection,Object
element) |
|
y**********a
发帖数: 824 | 16
static List anagram(List dict, String target){
int[] st=new int[256], ex=new int[256];
for (char c:target.toCharArray()) ++ex[c];
List rel=new ArrayList<>();
for (String s:dict) {
Arrays.fill(st, 0);
for (char c:s.toCharArray())++st[c];
if (Arrays.equals(st, ex)) rel.add(s);
}
return rel;
}
static List sortTickets(Listtickets) {
String[][] ts=new St... 阅读全帖 |
|
y**********a
发帖数: 824 | 17 除非具体知道奇数的次数，否则没法常数空间。
空间时间 : O(n) O(n)
static List timeEfficient(int[]A) {
Map m=new HashMap<>();
for (int a:A)
if (!m.containsKey(a)) m.put(a, 1);
else m.put(a, m.get(a)+1);
List rel=new ArrayList<>();
for (Map.Entry e:m.entrySet())
if (e.getValue()%2==0)
{rel.add(e.getKey());break;}
return rel;
}
空间时间： O(1) O(nlogn)
static List阅读全帖 |
|
y**********a
发帖数: 824 | 18
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
e... 阅读全帖 |
|
y**********a
发帖数: 824 | 19
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
e... 阅读全帖 |
|
o*********r
发帖数: 203 | 20 It's due to how Generics are designed:
- ArrayList继承List.
- ArrayList不是继承List. |
|
m*****k
发帖数: 731 | 21 List> l = new ArrayList>();
List> ll = new ArrayList<>(); |
|
j*********1
发帖数: 21 | 22 紧随大神步伐，下一步应该是behavior。
1. 时间节点：
学校CCO投的简历，大概是8月底的样子投的，9月8日收到回应。开始进入之后的环节。
如下是流程：
(1) Flex your coding skills
The first step in the interview process is a coding assignment, to be
completed in a 48-hour period. You can work on the assignment off-and-on
during the 48 hours. Depending on your familiarity with the material, it can
take some time to complete so be sure to plan accordingly.
(2) Phone interview
Following the coding assignment, we will schedule a set of phone interviews.
For these phone... 阅读全帖 |
|
g**********y
发帖数: 14569 | 23 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... 阅读全帖 |
|
x*********w
发帖数: 533 | 24 import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
public class EPI_15_1 {
static class Rect {
public int lft;
public int rgt;
public int height;
public Rect(int l, int r, int h) {
lft = l;
rgt = r;
height = h;
}
}
static class Point {
... 阅读全帖 |
|
s*********p
发帖数: 130 | 25
这题这么写可以吗？
分别把start array and end array排序，然后线性向下扫。
但是加入输入不把start 和 end 分开，而是向leetcode 那样建一个Interval class,
怎么保证start 和 end都有序呢？
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}
if (start.size() != end.size()) {
return 0;
}
Collections.sort(start);
Collections.sort(end);
... 阅读全帖 |
|
C*******a
发帖数: 448 | 26 List> A = new ArrayList>();
假设A已经赋值了，现在想改第m行第n列元素的值，怎么做？ |
|
s*********p
发帖数: 130 | 27 那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
merge sort 的merge 阶段。
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}
if (start.size() != end.size()) {
return 0;
}
Collections.sort(start);
Collections.sort(end);
int startP = 0;
int endP = 0;
int nu... 阅读全帖 |
|
s*********p
发帖数: 130 | 28 那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
merge sort 的merge 阶段。
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}
if (start.size() != end.size()) {
return 0;
}
Collections.sort(start);
Collections.sort(end);
int startP = 0;
int endP = 0;
int nu... 阅读全帖 |
|
w**********4
发帖数: 157 | 29 输入是 一个 String s， S中 可能含有 “*”. "*" 可以被替换成1 或者 0
For example ： "*" output "1", "0".
当时写了下面这个方法。
public static Collection getAllDecodes(String input) {
Collection list = new ArrayList();
list.add(input);
while (list.size() != 0) {
Collection res = new ArrayList();
for (String str : list) {
if (str.contains("*")) {
res.add(str.replaceFirst("\*", "1"));
res.add(str.replaceFirst("\*", "0"));
}
... 阅读全帖 |
|
r*******e
发帖数: 971 | 30 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 | 31 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;
//其实不需要记录层数 |
|
s*******z
发帖数: 14 | 32 dp？
1 按照先w后h的方式排序
2 存每一次放完以后能下一次可以放的地方，应该是个arraylist；如果新来的可以fit
前面的某一个，就update那一个成这个新来的。如果新来的无法fit，就上一层
arraylist加一个新来的。
3 dp初始是无限大空间。
感觉还要做一遍先h后w？ 菜鸟轻拍。。 |
|
g*****g
发帖数: 34805 | 33 这个取决于ArrayList的hashCode实现，如果实现是依赖Object.hashCode就会返回true.
但ArrayList的hashCode是基于elements的Hashcode. |
|
c******n
发帖数: 4965 | 34 你前头都做出来了， 为什么说后面的sort 难呢？
难道不是
ArrayList arr = new ArrayList();
arr.add(your_set)
Collections.sort(arr);
??
另外你说什么A-->0, C-->1 转换完全没有必要，即使你自己写sorting, 比较就用字符
比较就好了，就是alphabetical sorting 的定义。 不知道为什么你说要转换。 感觉
你想难了 |
|
a*********8
发帖数: 140 | 35 用recursion和post order的stack，做第一题：
class TreeNode2 {
char val;
TreeNode2 left;
TreeNode2 right;
TreeNode2(char val){
this.val = val;
}
}
public class Exercise2 {
public List pathRootToLeaf(TreeNode2 root){
List list = new ArrayList();
if (root == null){
return list;
}
List left = pathRootToLeaf(root.left);
List right = pathRootToLeaf(root.right);
i... 阅读全帖 |
|
w*****h
发帖数: 423 | 36 把0,1, 2, ...., n-1存在一个arraylist里，
然后用rand生成0 ~ n-1里的一个数，播放之，并在arraylist里删除对应位置的数
重复以上过程, 只是第二个循环需要产生0 ~ n- 2里的随机数，以此类推。 |
|
M**********g
发帖数: 59 | 37 其实再store的方法加个synchronized 就可以了，
每当有线程调用store方法的时候，这个对象就上锁了，其他线程就不能访问了。
下面是原题，和我写的实现
public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, ... 阅读全帖 |
|
S*******C
发帖数: 822 | 38 the weight of a tree = sum of weight of all node in the tree. Weight of node
= value of node * level of the node in the tree。
这里的代码能计算weight
public int findWeight(TreeNode root) {
int res = 0;
if (root == null)
return res;
List curLevel = new ArrayList();
curLevel.add(root);
int level = 1;
while (!curLevel.isEmpty()) {
for (TreeNode p : curLevel)
res += p.val * level;
level... 阅读全帖 |
|
j********l
发帖数: 325 | 39 没有想出优化的办法，就知道最普通的解法
class Dealer{
int DealerID;
List cars;
public Dealer(){}
public List getCars(int year) {
List res = new ArrayList();
for(Car c: cars) {
if(c.year == year) {
res.add(c);
}
}
return res;
}
public List getCars(String maker) {
}
public List getCars(String model) {
}
public List getCars(int year, String maker, String model) {
Li... 阅读全帖 |
|
H******7
发帖数: 1728 | 40 public List> fourSum(int[] num, int target) {
ArrayList> ans = new ArrayList<>();
if(num.length<4)return ans;
Arrays.sort(num);
for(int i=0; i
if(i>0&&num[i]==num[i-1])continue;
for(int j=i+1; j
if(j>i+1&&num[j]==num[j-1])continue;
int low=j+1, high=num.length-1;
while(low
int sum=num[i]+num[j]+n... 阅读全帖 |
|
D*******a
发帖数: 3688 | 41 when I interview people I allow them to use ArrayList |
|
T******7
发帖数: 1419 | 42 import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class ManhattanDistansIterator {
PriorityQueue pList = null;
int len;
int index;
public ManhattanDistansIterator(List points) {
len = points.size();
pList = new PriorityQueue<>(len, new Comparator() {
public int compare(Point p1, Point p2){
... 阅读全帖 |
|
k****r
发帖数: 807 | 43 kao，写了一个小时。。。。大致就是这样的代码，比较丑，不知道有没有更好的办法：
public class board88 {
public static List> findBoardPath(Point start, Point end,
int k) {
Map>> map = new HashMap<>();
boolean[][] visited = new boolean[8][8];
return findHelper(visited, start.row, start.col, k, end, map); //
return the path list from the point(i, j) to end in k steps.
}
public static List> findHelper(boolean[][] visited, int i,
int j, int k, Point end... 阅读全帖 |
|
y***i
发帖数: 414 | 44 public List getMaxNodePath(TreeNode node){
List max = new ArrayList();
max.add(node.val);
List res = new ArrayList();
res.add("");
findMaxPath(node, max, "", res);
return res;
}
public void findMaxPath(TreeNode node, List max, String path,
List res){
if(node == null){
return;
}
path = path.equals("") ? node.val + "" : path + "," + node.val;
... 阅读全帖 |
|
f**********e
发帖数: 288 | 45 给个book ArrayList pages = new ArrayList();
pages.add("The Taliban, the Sunni Islamist group that took over much of
Afghanistan in the 1990s, named Mansour its leader last month after
confirming its previous leader, Mullah Mohammed Omar, was dead.")
pages.add("A U.S.-led 2001 invasion booted the Taliban from power after it
offered safe haven to al Qaeda leader Osama bin Laden, leader, but a Taliban
insurgency continues in Afghanistan to this day.")
get the result of a word on which... 阅读全帖 |
|
J*********a
发帖数: 50 | 46 来献上本侠在此版第一道题：
public static int start = 0;
public static TreeNode deTree2(String s) {
//(A(B(C)(D))(E)(F))
while (s.charAt(start) == '(') start++;
TreeNode res = new TreeNode(s.charAt(start));
start++;
if (s.charAt(start) == ')') {
start++;
return res;
}
List list = new ArrayList<>();
while (s.charAt(start) == '(') {
list.add(deTree2(s));
}
res.children = list;
st... 阅读全帖 |
|
J*********a
发帖数: 50 | 47 lz是不是面的时候紧张啊。。。
紧张的时候思路容易混乱，这题可以用stack加个list吧：
public static void printTreeNodeLeafToRoot(TreeNode root) {
if (root == null) return;
Deque stk = new LinkedList<>();
stk.push(root);
List list = new ArrayList<>();
list.add(root);
while (!list.isEmpty()) {
List curr = new ArrayList<>();
for (TreeNode tn : list) {
if (tn.right != null) {
stk.push(tn.right);
... 阅读全帖 |
|
b******b
发帖数: 713 | 48 Assuming the numbers is in a list, e.g. ArrayList, below method
generate the next number in the list:
void next(ArrayList current)
{
int carryOver = 0;
current.set(current.size()-1, current.get(current.size()-1) + 1);
for (int i = current.size() - 1; i >= 0; i--)
{
int val = current.get(i);
int newVal = (val + carryOver) % 3;
carryOver = (val + carryOver) / 3;
current.set(i, newVal);
if (carryOver == 0) break;
}
if (carryOver > 0)... 阅读全帖 |
|
j*****8
发帖数: 3635 | 49 题目如下：
Given a string that contains only digits 0-9 and a target value, return all
possibilities to add binary operators (not unary) +, -, or * between the
digits so they evaluate to the target value.
给的几个例子：
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
下面是我的java code，有个test case一直超时，求大牛指点优化。我的思路很简单，
先生成所有可能的计算式，然后对每个计算式求值与target比较。
public List addOperators(String num, int target) {
... 阅读全帖 |
|
C****p
发帖数: 6 | 50 我的java代码，暴力两层dfs，672ms竟然过了。。。
第一层遍历所有数字组合，第二层遍历所有运算符组合，calculate的时候用了deque来
处理乘法优先的情况
不得不说这题有点变态，好像是G家的面试题？
public class Solution {
public List addOperators(String num, int target) {
List ans = new ArrayList();
if (num == null || num.length() == 0) {
return ans;
}
char[] digits = num.toCharArray();
List numbers = new ArrayList();
dfs(ans, target, numbers, digits, 0);
return ans;
}
... 阅读全帖 |
|
