p****e
发帖数: 37 | 1 贴个楼主事后写的：
bool _re_match(const char *str, const char *pattern, char prev_char) {
// 如果str匹配完，检查pattern是否匹配完，或者还剩一个"*"
if (*str == NULL)
return (*pattern == NULL || (*pattern == '*' && *(pattern+1) == NULL
)) ? true : false;
if (*pattern != '*')
{
// 如果当前pattern char不是'*', 试图匹配当前的str char, 然后
继续。
if (*pattern == '.' || *pattern == *str)
{
if (_re_match(str+1, pattern+1, *pattern))
return true;
... 阅读全帖 |
|
h**i
发帖数: 431 | 2 贴个新手写的
// compare two characters
bool char_equal(const char *a, const char *b)
{
if (*a!='\0')
return (*b=='.' || *a==*b);
else
return *b=='\0';
}
// the required function
bool isMatch(const char *s, const char *p)
{
if (*s=='\0' && *p=='\0')
return true;
if (*p=='\0')
return *s=='\0';
if (*(p+1)=='\0')
{
if (*s=='\0')
return false;
... 阅读全帖 |
|
b*******a
发帖数: 68 | 3 xyf501 (Ivan) 帖子中提到的G面试题目，请问正确的算法？xyf501 (Ivan)提到的贪吃
蛇算法能展开说说吗？谢谢了
一个吸地毯的irobot，和一个长方形的屋子，四面有墙，四个指令：
Bool moveForward（）//向前走一格，走不了的话返回false
Void Rotate（int degree）//就是左拐右拐
Bool isClean（）//当前单元格是否干净
Void clean（）
把irobot 扔在屋子任意位置，写代码让irobot清理房间，每一格都要走过（单元格没
有坐标）。 |
|
c**z
发帖数: 669 | 4 not sure where is wrong? Can someone help?
Thanks
class myclass
{
private:
myclass() {}
static myclass uniqueinstance;
static bool b;
public:
static myclass getinstance()
{
if(b==false)
{uniqueinstance=myclass();
b=true;
}
return uniqueinstance;
}
};
bool myclass::b=false;
void main()
{
myclass.getinstance();
} |
|
r*****n
发帖数: 20 | 5 //A full binary tree (sometimes proper binary tree or 2-tree or strictly
binary tree) is a tree in which every node other than the leaves has two
children.
bool isFull(Node *s){
if(!s->L && !s->R)
return true;
if(!s->R || !s->L)
return false;
return isFull(s->L) && isFull(s->R);
}
//A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible.[2]
int minHeight(Node *... 阅读全帖 |
|
g***x
发帖数: 494 | 6 which of below is incorrect?
方法1.
int getheight(node r)
{
if r==0 return 0;
return max(getheight(r.left),getheight(r.right))+1;
}
bool checkbalance(node r)
{
if r==0 return true;
int diff=getheight(r.left)-getheight(r.right)
if | diff|>1 return false;
else
return checkbalance(r.left)&&checkbalance(r.right);
}
方法2.
int getmaxheight(node r)
{
if r==0 return 0;
else
return max(getmaxheight(r.left),getmaxheight(r.right))+1;
}
int getminheight(node r)
{
if r==0 return 0;
else
return min(getminheig... 阅读全帖 |
|
E*****7
发帖数: 128 | 7 Algorithm:
Store each input into std::vector v;
Compare its first (i=0) and last element(j=v.size()-1)
if (v[i] != v[j]) return false;
Compare its 2nd and 2nd to last element
if (v[i+1] != v[j-1]) return false;
until i meets j
======= C++ Code (efficient and O(N) =========
#include
#include
bool isPalindrome(const std::vector &v) {
size_t len = v.size();
if ( len < 2 )
return false;
int i = 0;
int j = len - 1;
while ( i < j ) {
... 阅读全帖 |
|
a***r
发帖数: 93 | 8 memory O(n)
time O(nlogn)
//~ Given a array,find out if there exist a subarray such its sum is zero
#include
#include
using namespace std;
static void swap(int *p, int i, int j) {
int t=p[i]; p[i]=p[j];p[j]=t;
}
static int partition(int *p,int left,int right) {
int j=left;
for(int i=left;i
if(p[i]
}
swap(p,j,right);
return j;
}
static void binary_sort(int *p, int left, int right) {
if(left>=r... 阅读全帖 |
|
f********e
发帖数: 166 | 9 我觉得楼主递归写的有问题，check 函数参数没传对
刚才写错了，改了一下
bool isMirror(treeNode* root)
{
if(!root)
return true;
else
return(isMirrorHelper(root.left,root.right));
}
bool isMirrorHelper(treeNode* l, treeNode* r)
{
if(l^r)
return false;
else if(!l)
if(l.data==r.date){
return isMirrorHelper(l.left,r.right)&&isMirrorHelper(l.right,r.left)
}
else return true;
}
希望大家指点一下，谢谢 |
|
c**********e
发帖数: 2007 | 10 Error information in the following code is Error: equals is not a member of
B.
My question: Why equals() is not a member of B but print() is?
While this seems obvious, what is the general rule that a function will be
inherited?
#include
using namespace std;
class A {
public:
bool equal(A a) { return true; }
void print() { cout << "print\n"; }
};
class B: public A {};
int main() {
B b;
bool x = b.equals(b);
b.print();
return 0;
} |
|
s*******f
发帖数: 1114 | 11 // 打印从棋盘的一个角落到另一个角落所有路径
// this is toooooo hard, seems NP hard. cannot be DP
// if chess can only go right or down, here it is
struct Point{
int x;
int y;
Point(int xx, int yy):x(xx),y(yy){ };
friend bool operator== (Point &p1, Point &p2);
};
bool operator== (Point &p1, Point &p2){
return p1.x == p2.x && p1.y == p2.y;
}
void PrintPoint(Point &p){
printf("(%d, %d)", p.x, p.y);
}
void PrintAllChessPath(Point &p1, Point &p2){
static vector path;
path.push_back... 阅读全帖 |
|
s*******f
发帖数: 1114 | 12 // 打印从棋盘的一个角落到另一个角落所有路径
// this is toooooo hard, seems NP hard. cannot be DP
// if chess can only go right or down, here it is
struct Point{
int x;
int y;
Point(int xx, int yy):x(xx),y(yy){ };
friend bool operator== (Point &p1, Point &p2);
};
bool operator== (Point &p1, Point &p2){
return p1.x == p2.x && p1.y == p2.y;
}
void PrintPoint(Point &p){
printf("(%d, %d)", p.x, p.y);
}
void PrintAllChessPath(Point &p1, Point &p2){
static vector path;
path.push_back... 阅读全帖 |
|
s*******f
发帖数: 1114 | 13 //O(nlogn) version
struct Info{
int start;
int end;
bool flag;
};
bool MyCmp(Info &x, Info &y){
return x.start < y.start;
}
void SetFlag(Info arr[], int len){
sort(arr, arr + len, MyCmp);
for (int i = 0; i < len; ++i){
arr[i].flag = false;
}
int cur_idx = 0;
int cur_end = arr[0].end;
for (int i = 1; i < len; ++i){
if (cur_end > arr[i].start){
arr[i].flag = true;
arr[cur_idx].flag = true;
}
if (cur_end... 阅读全帖 |
|
j*******g
发帖数: 4 | 14 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' || s... 阅读全帖 |
|
k***t
发帖数: 276 | 15 题目其实很简单，自己摆乌龙了。细节如下。
虽然连on-site都没拿到，个人感觉，作为第一次电面，基本达到操练面试的目的。自
我介绍，项目表达要言简意赅。Coding要冷静，不紧张，确保看清题目，自我检查code
要细。
与大家分享面经/经历。也希望大家给comment。Code是我从collabedit上直接贴过来的
。欢迎comment，帮我提高。谢谢。
一电面：老美。
前半部分是简历上Performance Tuning的各种Projects的细节；
后半部分是Website Performance的各种问题。
基本对答如流，获面试人认同。并说我们网站增长快，急需你这样有Performance方面
经验的人。Highly recommend for the next step.
二电面：老印。题目其实很简单，自己摆乌龙了。
开始讲Projects，老印问了一个简历上Resource Leakage Finding的东西。
回答不够简洁清晰，偏冗长。老印试图澄清，最后彻底澄清。花了一些时间。
后半个小时，两道Coding题：
1。判断string是否数字？如1.2。并写TestCa... 阅读全帖 |
|
p*****2
发帖数: 21240 | 16 ===================================================
//1.2
// -, ., number
bool isNumber (char *in, int n) {
//这个n不需要吧？
bool isSign=false, isDot=false;
//isSign not used?
// skip spaces/tab in the beginning of the string
int first = 0;
if (!in) return false;
// how about in=""?
while (in && in[first] && (in[first]==' ' || in[first]=='\t')) ++first;
//这句怎么那么罗嗦呀？in 不是已经判断了吗？
if (!in[first]) return false;
//这里边判断in[first]就不用在上边判断了吧？
for (int i = first; i < n; ++i ) {
... 阅读全帖 |
|
k***t
发帖数: 276 | 17 谢谢。See //// inline...
===================================================
//1.2
// -, ., number
bool isNumber (char *in, int n) {
//这个n不需要吧？
///// agree, realized but didn't bother to change it.
bool isSign=false, isDot=false;
//isSign not used?
//// realized later but forgot to remove.
// skip spaces/tab in the beginning of the string
int first = 0;
if (!in) return false;
// how about in=""?
//// no special handling is needed.
while (in && in[first] && (in[first]==' ' || in[... 阅读全帖 |
|
g*********8
发帖数: 64 | 18 我觉得一面的那个题目真的在面试里面全部正确很难啊，我写了一个用C++的，楼主给
的测试用例都测了，可能还有bug，望指正：
bool isDigit(char c){
if(c-'0'>=0&&c-'0'<=9) return true;
else return false;
}
bool isNumber(const string& s){
if(s.length()==0) return false;
int i=0;
while(s[i]==' '){i++;}
//trim the leading space
string ss=s.substr(i,s.length()-i);
//Multiple E or e
if(ss.find_first_of('e')!=ss.find_last_of('e')) return false;
if(ss.find_first_of('E')!=ss.find_last_of('E')) return false;
//e shou... 阅读全帖 |
|
g*********8
发帖数: 64 | 19 恩，第三题想法不对，没有读懂题目，不好意思
是不是可以这样，先sort所有start point，然后从最小的start point开始，如果两个
interval overlap则合并，一直合并到最后，如果还剩一个interval则连续，否则就不
连续
struct interval{
int x;
int y;
interval(int a, int b):x(a),y(b){};
};
bool compare(interval i, interval j){
return (i.x
}
bool isConsistent( vectorxs, vectorys){
assert(xs.size()==ys.size());
vector v;
int n=xs.size();
int i,x,y;
for(i=0;i
interval in(xs[i],ys[i]);
v.push_back(in);
}
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 20 8,2,4,7,1,0,3,6
第一遍得到最小值0， 最大值8
bool[] flags=new bool[9];
第二遍填flags, {1,1,1,1,1,0,1,1,1}
第三遍得到两个group 0-4 6-8
开两个list
第四遍，把每个数填到相应的list里 |
|
k***t
发帖数: 276 | 21 #3 GetMedian() 感觉写得有点复杂，insert()应该还可以简化。
==============
#include
#include
#include
#include
using namespace std;
class Median {
public:
Median() : maxhc(0), minhc(0) {}
~Median() {}
void insert (int v) {
if (maxhc==minhc) {
if (maxh.empty() || maxh.top()>=v)
_enQ(true, v);
else _enQ(false, v);
} else if (maxhc>minhc) {
if (maxh.top()>v) {
_enQ(false, _deQ(true));
_enQ(true, v);
} e... 阅读全帖 |
|
b******c
发帖数: 70 | 22 这种题纯粹考编程
写一个bool IsVowel(char c, bool isPrevVowel)
Loop through the string, using one flag to indicate if the previous one is
vowel or not, if it is, do mult, else reset current value
is |
|
H*****g
发帖数: 638 | 23 这种纯OO设计其实没有实际用处，就是来骗骗学生。
真正工业界的设计应该是：
class Person
{
bool IsBlind();
bool IsDeaf();
...
};
又好用又容易维护。
纯OO设计已经过时了，特别维护是大问题。
没有一个纯OO设计的工业界的系统能活过一年，一年以后一抓肯定能抓出一大堆不符合
OO设计的漏洞。 |
|
l*****a
发帖数: 14598 | 24 比方说对于3，6,9,12,15,18,21,27。。。...已经是非质数，下次就不用判断9,15,21,27等
的倍数了
bool flag[]=new bool[n];
for(int i=0;i
for(i=2;i
{
if(flag[i]==false) continue;
k=2;
while(i*k
{
if (flag[i*k]) flag[i*k]=false;
k++;
}
} |
|
i**********e
发帖数: 1145 | 25 用 long long 检测 overflow，简单一些。。。
int atoi(const char *str) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int sign = 1;
while (*str == ' ') {
str++;
}
if (*str == '+') {
str++;
} else if (*str == '-') {
sign = -1;
str++;
}
long long num = 0;
bool overflow = false;
while (!overflow && isAlpha(*str)) {
int dig = *str... 阅读全帖 |
|
S********t
发帖数: 3431 | 26 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
现在有个树的类，不让你直接知道树的结构，但是有一个visitor可以访问前
序和后序的节点，现在你要写一个你自己的visitor目的是重建树，给你一场面试的时
间你能写吗？
struct Node { ... };
class Tree {
public:
void Walk(TreeVisitor *visitor);
...
};
class TreeVisitor {
public:
virtual ~TreeVisitor();
virtual void PreOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
virtual void PostOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
};
现在你要做的是：
1 定义一个你自己的tree data structure (class MyTree)
2 写一个... 阅读全帖 |
|
j*******g
发帖数: 4 | 27 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' ||... 阅读全帖 |
|
v***a
发帖数: 365 | 28 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager 听我面的很好，对algorithm 和 backend很熟
悉，
于是 onsite 时特地来面我... 阅读全帖 |
|
m*****a
发帖数: 636 | 29 Congrats!
啥叫带宽限制，toplogic已知 -> master 节点 Gossip
积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager ... 阅读全帖 |
|
|
m*****a
发帖数: 636 | 31 Congrats!
啥叫带宽限制，toplogic已知 -> master 节点 Gossip
积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager ... 阅读全帖 |
|
c***g
发帖数: 472 | 32 可以算出部分结果来，但是到了后来，似乎死循环了，不能正常的结束
请问谁帮我看看，哪儿有个bug
/*
check whether [level, position] is OK
output stored the valid position so far between [0,level-1];
*/
bool check(int output[], int level, int position){
bool isOK = true;
for(int i = 0; i < level; i++) {
if( position == output[i]
|| i - output[i] == level - position
|| output[i] - i == position - level
|| i + output[i] == level + position) {
... 阅读全帖 |
|
w****o
发帖数: 2260 | 33 这个不太好，占用了太多的空间，因为一个 bool 占用的空间和一个 integer是一样的
，通常也是4bytes.就是说一个bool根本就不是一个bit. |
|
t*********n
发帖数: 89 | 34 2sum,如果用hash table的话，循环中每一次查元素都只在已有的hash table 查，比如
1 -> 此时 hash table为空，则无结果
2 -> 此时 hash table 里有仅有1， 无结果
....
9 -> 此时 hash table 里有{1，2，3，..8},查到1，成立
对于duplicate,我的想法是在hash_table的value以一个bool来表示是否已经用过，即
hash_table myhash。比如数组为{5，5，5}，目标是10
5-> 此时hash table为空，无结果
5-> 此时hash table里面有5，标记myhash[5] = false;
5 -> 此时hash table里面虽然有5，但是myhash[5] = false,则不成立。
请问下大家有没有更巧的方法？ |
|
S********t
发帖数: 3431 | 35 好吧，那我说清楚些
有个general tree，内部结构就是:
class Tree {
public:
void Walk(Visitor *v) {
// in preorder sequence
v->PreVisit(...);
...
// in postorder sequence
v->PostVisit(...);
...
}
private:
ValueType node_value;
vector children_;
}
class Visitor {
public:
virtual void PreVisit(const ValueType &node_value, bool is_leaf) = 0;
virtual void PostVisit(const ValueType &node_value, bool is_leaf) = 0;
}
Let's say you define your own tree data structure:
struct MyTree ... 阅读全帖 |
|
A**u
发帖数: 2458 | 36 #include
using namespace std;
bool is_same_bst(int* A, int m, int* B, int n)
{
if ( m == 0 & n == 0 )
return true;
if ( m != n)
return false;
else
{
if ( A[0] != B[0] ) // root
return false;
else
{
//看看，root,左右儿子数目是否一致
int smaller1 = 0;
int larger1 = 0;
for(int i = 1; i < m; ++i)
{
if ( A[i] < A[0] ) ++smaller1;
if ( A[i] > A[0] ) ++larger1;
}
int smaller2 = 0;
int larger2 = 0;
for(int i = 1; i < n; ++i)
{
if ( B[i] < B[0] ) ++smaller2;
if ( B[i] > B[0] ) ++larger2;
}
//递归
if (smalle... 阅读全帖 |
|
m******s
发帖数: 204 | 37 前一个想法需要记录很多无用的中间信息，下面的想法除了hash table, 还需记录额外
的m个boolean：IsCombination(c[m-1, m-1]), IsCombination(c[m-2, m-1])...
IsCombination(c[k, m-1])原因是避免重复计算， 试想如果已经递归过IsCombination
(c[k, ... m-1], 那么相应的一些较短的以c[m-1]结尾的字符串也被判断过。
和zhangchitc 想法的区别在于对已遍历的前k个字符不做IsCombination的考虑
代码与之前一个帖子类似但加了中间结果存储：
bool IsCompositeWord(char* word， int start, int end, bool* table)
{
//check whether it is recorded before
if (table[start] == false)
return false;
//check all possible pair: check first is word or n... 阅读全帖 |
|
z********c
发帖数: 72 | 38 现在有一个容器的iterator,支持
bool hasNext () 是否还有元素
T next () 取出下个元素，并迭代器后移
现在要你写一个wrapper类
class wrapper {
wrapper (iterator it);
bool hasNext ()
T next ()
T peek ()
}
以一个iterator为构造函数，在支持hasNext和next的同时，添加peek ()，即查看下一
个元素的值，但迭代器不后移 |
|
i**********e
发帖数: 1145 | 39 刚写了一个，没测过。
分隔符有哪些？
bool isSpace(char c) {
return c == ' ' || c == '\t'; // maybe newline considered as a space too?
}
int lengthOfLastWord(const char *s) {
if (!s) return 0;
int len = 0;
bool inWord = false;
while (*s) {
if (!inWord && !isSpace(*s)) {
inWord = true;
len = 0;
} else if (inWord && isSpace(*s)) {
inWord = false;
}
if (inWord) len++;
s++;
}
return len;
} |
|
k*****y
发帖数: 744 | 40 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.st... 阅读全帖 |
|
k*****y
发帖数: 744 | 41 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.st... 阅读全帖 |
|
b********g
发帖数: 43 | 42 我的理解是每次都预读一个next, 然后就ok 了
Iterator it = null;
Predicate pr = null;
T next =null;
Iterator conditionIterator(Iterator input, Predicate pred)
{
it = input;
pr = pred;
next();
}
T next() {
T ret = next;
bool found = false;
while(it.hasNext()) {
T val = it.next();
if(pr.accept(val))｛
next = val;
found = true;
break;
｝
}
if(!found) next = NULL;
return ret;
}
bool hasnext() {
return !next;
} |
|
l*********8
发帖数: 4642 | 43 class ConditionIterater : public Iterator
{
public:
ConditionIterater(Iterator input, Predicate pred)
: m_Input(input), m_Pred(pred), m_HasNext(false)
{
}
T Next()
{
T returnValue = m_Value;
finxNext();
return returnValue;
}
bools hasNext()
{
return m_HasNext;
}
private:
void findNext()
{
m_HasNext = false;
while(m_Input.hasNext())
{
m_Value = m_Input.Next();
if (m_Pred.accept(m_Value) {
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 44 根据peking2的程序和建议改一下：）
class ConditionIterater : public Iterator
{
public:
ConditionIterater(Iterator input, Predicate pred)
: m_Input(input), m_Pred(pred), m_HasNext(false)
{
findNext();
}
T Next()
{
if (m_HasNext==false)
throw exception;
T returnValue = m_Value;
fintNext();
return returnValue;
}
inline bools hasNext()
{
return m_HasNext;
}
private:
void findNext()
{
m_HasNext = false;
while(m_Input.... 阅读全帖 |
|
l*****a
发帖数: 14598 | 45 根据题意，实际上可以看成一个有序一维数组。一遍binary search will work
bool contains(int a[][],int index,int target)
{
int y=index%n;
int x=index/n;
return target==a[x][y];
}
bool Search(int a[][],int m,int n,int target)
{
int lo=0;
int hi=m*n-1;
int x,y;
while(lo
{
int mid=lo+(hi-lo)>>1;
if(contains(a,mid,target) return true;
if(target
else lo=mid;
}
if(contains(a,hi,target) return true;
if(contains(a,lo,target) return true;
return false;
} |
|
l*********8
发帖数: 4642 | 46 贴一下我的程序，通过了leetcode judge.
感觉还是有些繁琐.
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 || !p)
return false;
if(p[0] == '\0' && s[0] != '\0')
return false;
const char * star = NULL;
const char * nextStar = NULL;
if (p[0] == '*') {
star = p;
p++;
}
while (1) {
n... 阅读全帖 |
|
d****n
发帖数: 233 | 47 Here is a iterative one. I know there is another iterative one which is more
compact.
bool isMatch(const char *str, const char *pattern) {
const char *pstr = str, *pp = pattern;
bool findStar = false;
while (*pstr && *pp) {
if (*pp == '*') {
str = pstr;
pattern = pp + 1;
findStar = true;
}
if (*pstr == *pp || *pp == '?') {
pstr++;
pp++;
con... 阅读全帖 |
|
w****x
发帖数: 2483 | 48 面试官第二题的考点是什么???
如果是RPC: bool GetIndex(int x, int y),
这个RPC是由比如master机器映射到不同机器上读取数据, 主要问题是Map太大了不能放
到一台机器上??
如果考分布式计算那么每台计算机计算一个block, 给每个block的端口编号, 每个编号
不同从 1...n, 然后计算所有两两之间的通路, 然后再把block连起来??
如果是这样的话既然不同block的端口不一样, 那么知道端口号也知道了block号, 也知
道这两点间怎么走.
把所有的端口到端口的pair混在一起来做一个3元组PORT_PATH:
1. 根据start point 和 end point 找到最近的端口ptBeg & ptEnd, 问题就是在<
port1, port2, path>这一堆3元组中找到通路让ptBeg ..... --> ptEnd
2. bool FindPath(int ptBeg, int ptEnd, map> mp, bRec[
n])
... 阅读全帖 |
|
s*******f
发帖数: 1114 | 49 class MyRead{
static char buf[4096];
char *left, *right;
bool stop;
void read4096(char *buf);
public:
MyRead(){
//memset(buf, 0, 4096);
read4096(buf);
left = buf;
right = buf + 4096;
stop = false;
}
bool Readline(char *dst){
if (stop)
return false;
while (1){
while (left < right){
if (*left != '\n' && *left != '\0')
*dst++ = *left++;
else... 阅读全帖 |
|
f*********m
发帖数: 726 | 50 （1）Jump Game：
Given an array of non-negative integers, you are initially positioned at the
first index of the array.
Each element in the array represents your maximum jump length at that
position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
不知道我下面的解法对不对？用了DP，用f存储以前的计算结果。
bool jump(vector& A, int n, vector f){
if (n == 0){
f[0] = true;
return true;
}
if (f[n] != -1)
retur... 阅读全帖 |
|
