c***2
发帖数: 838 | 1 int binary_search_rotation(int a[], int l, int u, int x)
{
int m;
while (l <= u) {
m = (l + u) / 2;
if (x == a[m]) {
return m;
}
else if (a[l] <= a[m]) {
if (x > a[m]) {
l = m+1;
}
else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m - 1;... 阅读全帖 |
|
j*****g
发帖数: 223 | 2 // txt -> text
// p -> pattern (include . and *)
void pattern_match(const char *txt, const char *p)
{
int **d = NULL;
int len_txt = 0, len_p = 0;
int i, j, k;
if (!txt || !p) goto exit;
len_txt = strlen(txt);
len_p = strlen(p);
if (len_txt == 0 || len_p == 0) goto exit;
printf("text : %s\n", txt);
printf("pattern: %s\n", p);
d = new int*[len_p];
if (!d) goto exit;
memset(d, NULL, sizeof(int*) * len_p);
for (i = 0; i < len_p; i++)
{
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 3 这是我的代码，虽然没有那么漂亮简洁，但是比较容易懂。
我可以尝试把代码缩短，但是缩短之后就很难理解了。
void post_order_traversal_iterative(BinaryTree* root) {
bool down = true;
BinaryTree *prev;
stack s;
s.push(root);
while (!s.empty()) {
BinaryTree *curr = s.top();
if (down) {
if (curr->left) {
s.push(curr->left);
} else {
if (curr->right) {
s.push(curr->right);
} else {
down = false;
cout << curr->data << " ";
s.pop();
prev = cu... 阅读全帖 |
|
k*****7
发帖数: 72 | 4 很好。是我之前想歪，分了3个一组去递归所以判断不完。。。。
代码贴下来抛砖了：
int MNCS(int a[]){
if(a==null)
return 0;
else if(a.length>2)
return
Math.max((a[0]>0?a[0]:0)+MNCS_helper(a,2), MNCS_helper(a,1));
else if(a.length == 2)
return Math.max(0, Math.max(a[0], a[1]));
else if(a.length == 1 && a[0]>0)
return a[0];
else
return 0;
}
int MNCS_helper(int[] a, int i) {
if(i == a.length-1)
return a[i]>0?a[i]:0;
el... 阅读全帖 |
|
f****4
发帖数: 1359 | 5 来自主题: JobHunting版 - 问个面试题 void printspiral(char *a, int colsize, int m, int n, int x0, int y0)
{
// a is the matrix, colsize is its original column size
// m is #rows, n is #cols in the submatrix
// x0 and y0 are the offsets of the first element of the submatrix
// check if m and n are positive
if (m<=0 || n<=0) {
cout << "zero or negative dimensions" << endl;
return;
}
int i;
if(m>=2&&n>=2) {
// print the outer circle
for(i=0; i<=n-2; i++)
cout << a[x0*c... 阅读全帖 |
|
r******n
发帖数: 170 | 6 Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = ... 阅读全帖 |
|
r******n
发帖数: 170 | 7 多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成binary
search；不在递增区域，就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x
{
u = m-1;
}
else
... 阅读全帖 |
|
r******n
发帖数: 170 | 8 Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = ... 阅读全帖 |
|
r******n
发帖数: 170 | 9 多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成binary
search；不在递增区域，就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x
{
u = m-1;
}
else
... 阅读全帖 |
|
y***m
发帖数: 7027 | 10 这个简单java的，有更简洁明了完善高效结构化的么,thx!
class BinaryTree {
private int data;
private int minNode = Integer.MAX_VALUE;
private BinaryTree leftpoiter;
private BinaryTree rightpoiter;
public BinaryTree() {
}
public BinaryTree(int data) {
this.data = data;
leftpoiter = null;
rightpoiter = null;
}
public void getMinNode(int key) {
getMinNode(this, key);
}
public void getMinNode(BinaryTree root, int key) {
if (root != null) {
i... 阅读全帖 |
|
y***m
发帖数: 7027 | 11
处理 -1 就行了吧
这样省了些代码，但b=1时多执行了 1/2的取整操作，b=2时多执行了2-3步代码吧...
nod
public static double pow(double a, int b) {
if (b == 0)
return 1;
else if (b == -1)
return 1/a;
else if (b == 1)
return a;
else if (b == 2)
return a*a;
else if (b == -2)
return 1/(a*a);
else if (b % 2 == 0) {
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 12 我刚写的，至少例子都能通过。话说我没觉得递归哪里不好啊。。。
bool is_match(const char* s, const char* p)
{
// invalid input
if(s == NULL || p == NULL || p[0] == '*')
return false;
// both string and pattern terminate synchronously
if(s[0] == 0 && p[0] == 0)
{
return true;
}
// pattern has been used up but string does not reach the end
if(p[0] == 0 && s[0] != 0)
{
return false;
}
// test if there is a '*' after current character
bool anyOccur ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 13 我刚写的，至少例子都能通过。话说我没觉得递归哪里不好啊。。。
bool is_match(const char* s, const char* p)
{
// invalid input
if(s == NULL || p == NULL || p[0] == '*')
return false;
// both string and pattern terminate synchronously
if(s[0] == 0 && p[0] == 0)
{
return true;
}
// pattern has been used up but string does not reach the end
if(p[0] == 0 && s[0] != 0)
{
return false;
}
// test if there is a '*' after current character
bool anyOccur ... 阅读全帖 |
|
c**********e
发帖数: 2007 | 14 Quick Selection:
选target个最小的。最终目的是，使a[0], …, a[target-1]为最小的。因为是递归调用子函数，子函数对数组的一部分a[low], …, a[high]操作。
#include
using namespace std;
#define swap(x,y) { int z=x; x=y; y=z; }
int low_n(int a[], int low, int high, int target) {
int pivot; int mid=(low+high)/2;
if(a[low]<=a[mid])
{
if(a[high]<=a[low]) pivot=a[low];
else if(a[high]<=a[mid]) pivot=a[high];
else pivot=a[mid];
} else
{
if(a[high]<=a[mid]) pivot=a[mid];
else if(a[high]<=a[low]) pivot=a[high];
... 阅读全帖 |
|
e********e
发帖数: 12 | 15 用merge的方法写了下。
template
T findKthOf2SortedArray1(T P[], int s, T Q[], int t, int k)
{
// assume: 1 <= k <= (s+t)
int i=0, j=0;
for (int l = 0; l < k; l++){
if (i == s) j++;
else if (j == t) i++;
else {
if (P[i] < Q[j]) i++;
else j++;
}
}
if (i == 0) return Q[j-1];
else if (j == 0) return P[i-1];
else return max(P[i-1], Q[j-1]);
}
template
T medianOfTwoSortedArray3(T P[], int s, T Q[], int... 阅读全帖 |
|
s*******f
发帖数: 1114 | 16 // 给一个字符串，例如"30*(5+10)",输出计算结果。
double GetValue(double b1, double b2, char op){
switch(op){
case '+':
return b1 + b2;
case '-':
return b1 - b2;
case '*':
return b1 * b2;
case '/':
if (b2 < 0.00000001)
return 0;
return b1 / b2;
default:
return 0;
}
}
bool OpPriority(char op1, char op2){
if (op1 == '*' || op1 == '/'){
return true;
}else if ((op1 ==... 阅读全帖 |
|
a******9
发帖数: 12 | 17 public class Circle_Print {
public static void print(int[][] A){
int m = A[0].length;
int n = A.length - 1;
int i = 0;
int j = 0;
boolean forwardDownward = true;
while(true){
if(m == 0) break;
else{
for (int p = 0; p < m-1; p++) {
System.out.print(A[i][j]+",");
if(forwardDownward) j++;
else j--;
}
System.out.print(A[i][j]+",");
... 阅读全帖 |
|
w***y
发帖数: 6251 | 18 我就是自己做了一个main部分测试了一下, 其他部分都是copy书上的
import java.util.Comparator;
import java.util.PriorityQueue;
public class heap {
/*
* careercup里答案部分
*/
private Comparator maxHeapComparator, minHeapComparator;
private static PriorityQueue maxHeap;
private static PriorityQueue minHeap;
public static void addNewNumber(int randomNumber) {
if (maxHeap.size() == minHeap.size()) {
if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {... 阅读全帖 |
|
S****h
发帖数: 115 | 19 贴下自己的代码供参考，大家有兴趣的话给挑挑ug,thanks！
import java.util.List;
class Solution {
List groups;
int score;
public Solution() {
groups = new ArrayList();
}
}
public class StringNumberGroup {
public Solution getOptimalGroup(String phone) {
if (phone.length() <= 3) {
Solution s = new Solution();
s.groups.add(phone);
s.score = getScore(phone);
... 阅读全帖 |
|
g*********e
发帖数: 14401 | 20 class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(*s=='\0'){
if(*p=='\0')
return true;
else if(*p=='*')
return isMatch(s, p+1);
else
return false;
}
else{
if(*p=='\0')
return false;
else if(*p=='?' || *p==*s)
return... 阅读全帖 |
|
j********e
发帖数: 1192 | 21 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
s*******f
发帖数: 1114 | 22 //回报本版，码遍本版
//Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
//and a a number e.g. 69.
//You need to tell if it is in the input, e.g. 69=>true.
//strlen is O(n), don't use C style string for O(log n), suppose
//the string is friendly without lots of blank.
void GetWordPos(const char *mid, const char *left, const char *right, const
char **pstart, const char **pend){
while (isspace(*mid))
++mid;
*pstart = mid;
while (*pstart >= left && !isspace(**pstart))
... 阅读全帖 |
|
d****o
发帖数: 1055 | 23 /*
curInt
curStr
flag=1
*/
Answer; time. O(n) space O(1)
bool findInput(string in, int target){
string s = intToString(target);
int i=0;
int flag=1;
int curInt=0;
while(i
if(in[i]!=' '&&flag==1){
curInt = curInt*10+(in[i]-'0');
} else if(in[i]!=' '&&flag==0){
curInt= in[i]-'0';
i++;
} else if(in[i]==' '&&flag==1){
if(curInt==target) return true;
... 阅读全帖 |
|
l******9
发帖数: 26 | 24 做了第一道题，然后才看到那个python 版本的 比较max_so_far, min_ending_her 和
max_ending_her
http://ideone.com/BiLUP
public int search(int A[]) {
int max = 0;
int i = 0;
int count = 0; // the count of negative numbers between
zeros
int p = 1; // the product of all number between zeros
int first = 0; // the product of positive numbers before the
first negative number between zeros
int firstNegative = 0; // the value... 阅读全帖 |
|
r*****a
发帖数: 421 | 25 用recursive brutal force的算法leetcode通过了small data test，
但是在large data test的时候超时了。
尤其是以下这个例子，自己电脑上都算不出来。
s="bbbababbbbabbbbababbaaabbaababbbaabbbaaaabbbaaaabb"
p="*b********bb*b*bbbbb*ba"
有没有更优化的算法？
贴个java的
public boolean wildcardMatch(String s, String p, int sPos, int pPos) {
if (sPos == s.length()) {
if (pPos == p.length()) // p also used up
return true;
} else if (pPos < p.length() && p.charAt(pPos) == '*') { // current p
is *, rest should all be *
return wild... 阅读全帖 |
|
l*******b
发帖数: 2586 | 26 写成state machine得有7种状态，5种字符，还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val t... 阅读全帖 |
|
l*******b
发帖数: 2586 | 27 经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
... 阅读全帖 |
|
l*******b
发帖数: 2586 | 28 写成state machine得有7种状态，5种字符，还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val t... 阅读全帖 |
|
l*******b
发帖数: 2586 | 29 经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
... 阅读全帖 |
|
s***5
发帖数: 2136 | 30 第一题用Perl regular expression可以一行搞定。
if(str =~ /[+|-]?[0|[1-9]\d*](\.[0-9]+)*/ || str =~ /[+|-]?\.\d+/)
return true;
else
return false;
如果不能用regular expression，下面有个C＋＋的code。
bool isNumeric(string str)
{
// assume there are no leading or ending spaces in the string
int i = 0, end = str.size()-1;
if(str[i] == '+' || str[i] == '-') i++; // check the sign symbol
if(str[i] == '.') { // if the first non-sign char is '.', e.g. .56
if(i == end) return false;... 阅读全帖 |
|
p****e
发帖数: 3548 | 31 搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
... 阅读全帖 |
|
p****e
发帖数: 3548 | 32 搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
... 阅读全帖 |
|
j*****y
发帖数: 1071 | 33 bless
一条龙是什么阿 ? tic tac toe ?
double atof(char *s)
{
int i = 0;
while(s[i] && s[i] == ' ')
{
++i;
}
double num = 0;
bool flag_signal = false;
bool negative = false;
bool flag_dot = false;
vector afterDot;
while(s[i])
{
if(s[i] == '+' || s[i] == '-')
{
if(flag_dot)
{
break;
... 阅读全帖 |
|
p*****p
发帖数: 379 | 34 刚写了个，上个部分代码
private enum Direction {LEFT, RIGHT, UP, DOWN};
private static float getCurrentPathMax(int currentRow, int currentCol, int[]
[] maze, int[][] visited, Direction lastStep) {
int rows = maze.length, cols = maze[0].length;
if (currentRow < 0 || currentRow >= rows || currentCol < 0 || currentCol
>= cols) {
return -1;
}
if (maze[currentRow][currentCol] == 0) {
// blank
if (visited[currentRow][currentCol] == 3) {
return 0;
... 阅读全帖 |
|
d****n
发帖数: 1241 | 35 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheC... 阅读全帖 |
|
d****n
发帖数: 1241 | 36 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheC... 阅读全帖 |
|
d**e
发帖数: 6098 | 37 ☆─────────────────────────────────────☆
oneid (Mobius) 于 (Fri Dec 28 19:12:49 2012, 美东) 提到:
比如careercup,glassdoor上每个公司那么多题,难道大家都做完了?
还是leetcode has OJ?比较容易发现code的问题?
但是大家觉得leetcode的题被问得几率比careercup上针对性的公司的题概率高么?不可
能把?
☆─────────────────────────────────────☆
luckynoob (菜鸟) 于 (Fri Dec 28 19:20:06 2012, 美东) 提到:
题目肯定是做不完的，重要的是实现一下一些重要方法吧，书还是要看的
☆─────────────────────────────────────☆
lolhaha (人生如棋，棋如人生) 于 (Fri Dec 28 19:21:35 2012, 美东) 提到:
careecup上的题你做得完吗？
那上面的很多回帖都有问题，没有正确答案
☆─────... 阅读全帖 |
|
s*******s
发帖数: 1031 | 38 来自主题: JobHunting版 - 一个小面筋 做了一下，不知道对不对。
void PostVisit(TreeNode *tree) {
if(!tree)
return;
PostVisit(tree->left);
PostVisit(tree->right);
print(tree->value);
}
void PostVisit(TreeNode *tree) {
if(!tree)
return;
stack stkNodes;
stkNodes.push(tree);
while(!stkNodes.empty()) {
TreeNode *node = stkNodes.top();
if(node->left)
stkNodes.push(node->left);
else if(node->right)
stkNodes.push(node->right);
else {
... 阅读全帖 |
|
b***e
发帖数: 1419 | 39 /*
Here's a solution with JS, O(n) time and O(1) space.
You can copy&paste the full body of this post and run it in
a browser console.
*/
var minCandies = function(children) {
var maxHeight = children.length;
var state = 'desc';
var height = maxHeight;
var accumulated = 0;
var count = 0;
for (var i = 0; i < children.length - 1; i++) {
accumulated += height;
count++;
if (state == 'desc') {
if (a[i] > a[i+1]) {
height--;
... 阅读全帖 |
|
h**o
发帖数: 548 | 40 我觉得和cc150 8.2 design a call center 类似。
bank/callcenter 收到一个request,分给一个空闲的elevator/employee
如果没闲人，把request入queue. 一旦有人闲下来，就来queue里找任务去处理。bank/
callcenter就好像server, elevator/employee 就好象process/thread/task.
passanger 是 request 中的 subrequest.
贴一个我的码吧。 欢迎指正。网上有些code有铃啊，门的。我不明白。就不加入我的
码了。
test_evelatorSystem(){
mg = Manager::getInstance();
for (i = 0; i < 4; i++){
//sb. press button UP at floor 5
Request* req = new Request(floor=5, direction=UP);
mg.dispatchRequest(req)... 阅读全帖 |
|
d****n
发帖数: 397 | 41 class Solution {
public:
int evalRPN(vector &tokens) {
int n;
n=tokens.size();
return eval(tokens,0,n-1);
}
int eval(vector& tokens, int i, int j) {
int k,l,n,v1,v2,v,np,nn;
n=j-i+1;
np=0;
nn=0;
if(n==1) return stringtovalue(tokens[i]);
else {
for(l=j-1;l>=i;l--) {
if(tokens[l]=="+"||tokens[l]=="-"||tokens[l]=="*"||tokens[l]
=="/") np++;
else nn+... 阅读全帖 |
|
b***e
发帖数: 1419 | 42 Assume we know the height of each node, which can be computed on the fly
with O(n). Then it's just an extensive case study on the 3 possible status
of a subroot: incomplete, complete (but not perfect), perfect.
if (!tree.left is not complete) {
tree is not complete
} else {
if (tree.left is not perfect) {
tree is not complete
} else {
if (tree.right is not complete) {
tree is not complete
} else {
if (tree.right is not perfect) {
if (tree.left.height == tre... 阅读全帖 |
|
e********3
发帖数: 18578 | 43 Backtrack, recursive, and dynamic programming.
Here is the code (changes size to see the solution for matrices of different
sizes), the time complexity is O(n) (n = size*size) and the memory usage is
O(n) as well:
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMap
Integer>();
static class CacheKey{
public int x, y;
public Cac... 阅读全帖 |
|
l**********i
发帖数: 84 | 44 面了1小时15分，前几题感觉不错，结果被问到tcp vs udp的时候根本不知道是啥玩意
儿，估计是悲催了。哎，题目如下：
1.Can you talk a little about yourself first?
2.Why do you choose p?
3.Difference between linkedlist and array
4.In what condition do you use tree structure? How do you keep them balanced?
5.TCP protocol vs UDP protocol (have no idea)
6.How do you implement a hash table?
following up question:
Data structure; size; hashfunction; linkedlist vs hashtable in dealing with
collision
7.coding
print spiral matrix
Given a matrix of m x n elem... 阅读全帖 |
|
e***s
发帖数: 799 | 45 之前看错题了，以为返回是否存在a[i] + b[j] = c[k]
但是复杂度是一样的。
public static boolean another3Sum(int[] A, int[] B, int[] C){
HashSet ha = new HashSet();
HashSet hb = new HashSet();
int i = 0, j = 0;
for(int k = 0; k < C.length; k++){
if(i < A.length && j < B.length){
if(A[i] + B[j] > C[k]){
if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
return true;
}
el... 阅读全帖 |
|
r******g
发帖数: 138 | 46 出来混了6年，想换换环境。可能是因为local，google没有给我电面直接onsite了。自
己感觉onsite表现还不错，但是还是被拒。我就简单把题目分享给大家吧。面的Java
position。所以写的都是java code。
1. 白人。
a. 设计自己的一个Iterator class。 constructor输入的是List. 实现一
个method: Object getNext(); 每次得出的结果如下。
加入输入是
Iterator1: a, b, c, d, e
Iterator2: f, g, h, i, j
getNext() 出来的顺序是 a, f, b, g, c, h, d, i, e, j
写完代码后直接问我time complexity 然后就move on下一个题了。。。也没有跟我
discuss还是walk through一下code。
b. 问我在什么情况下选择n^2的复杂度而不是nlogn. Open ended question。
c. f(string a, string op, string b)， 要我写出各种tes... 阅读全帖 |
|
T*******e
发帖数: 18 | 47 非常感谢楼上各位的指点。我会根据自身coding速度做调整。
euclid2003在另一帖中的code就是个很好的参考。
http://www.mitbbs.com/article_t/JobHunting/32611137.html
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMap
Integer>();
static class CacheKey{
public int x, y;
public CacheKey(int x, int y){
this.x = x;
this.y = y;
}
@... 阅读全帖 |
|
a****r
发帖数: 87 | 48 我的算法：
对两个BST同时进行in-order traversal in an iterative way.
bool is_BST_eq(TreeNode *r1, TreeNode *r2){
if(r1 == nullptr && r2 == nullptr) return true;
stack st1;
stack st2;
TreeNode *p = r1;
TreeNode *n1 = nullptr;
TreeNode *q = r2;
TreeNode *n2 = nullptr;
while(true){
// iterative inorder traversal for r1
while(!st1.empty() || p){
if(p){
st1.push(p);
p = p->left;
... 阅读全帖 |
|
g***j
发帖数: 1275 | 49 Median of Two Sorted Arrays
这个题目，有两个地方总是想不明白
1) Line 1，这个地方为啥不能加等号，加了就会出错，为啥else部分可以处理这个等
号的情况呢？
2) Line 2 and Line 3，这两个地方为啥是 m/2 + n/2 +1 >=k，我理解的是如果算上A
[m/2] B[/2] 总共有m/2+n/2 +2 个元素，那么就是说 m/2 + n/2 +2 > k， 分别换成
这句话，这里是work的，但是我的疑问是，为啥加一个等号就不work了，m/2 + n/2 +2
>= k，为啥在else部分，就可以处理这个等号的情况呢？
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((n + m) % 2 == 0) {
return (findkth(A, m, B, n, (m+n)/2) + findkth(A, m, B, n, (m+n... 阅读全帖 |
|
a***e
发帖数: 413 | 50 题目
https://oj.leetcode.com/problems/search-a-2d-matrix/
我写的如下，先搜索行，再列。后面那个简短的是看到的别人的答案，简洁很多，但要
不要考虑行数*列数overflow的情况呢？多谢！
bool searchMatrix(vector > &matrix, int target) {
int row = matrix.size();
if (row==0) return false;
int col = matrix[0].size();
if (col==0) return false;
int rmin=0, rmax=row-1, cmin=0, cmax=col-1,rmid,cmid;
while (rmin<=rmax)
{
rmid = rmin+(rmax-rmin)/2;
if (matrix[rmid][0]>target... 阅读全帖 |
|
