a********e
发帖数: 5251 | 1 哈哈。有些长，但值得看。
==============================================================
原版：
某日晚，门头沟警方接到报警，北京大学一男一女两学生在灵山游玩时走失。当地警方
和北大保卫科派人连夜搜山未果。次日上午，两名学生与学校恢复联系。
原来，两人投宿旅馆后关掉手机，与其失去联系的同学误以为他们走失才报警。“夜间
的灵山已经零下几度了，我们就在上面找了一晚上。”参加搜山行动的清水派出所冯所
长介绍，前晚6时50分，他们接到一名自称北大学生的女生报警，她的两名同学(一男一
女)早晨去龙口涧风景区游玩，但到现在却跟他们失去联系，怀疑他们走失。
昨日中午，冯所长接到同样参加搜山的北大保卫科通知，说两名学生已经跟他们联系上
并汇合。
据门头沟警方掌握的情况，这两名学生游玩后当晚在旅馆投宿，随后关掉手机。
第二天，两人开机后发现学校正在寻找他们，立即与校方取得了联系。
“这属于一个误会，虚惊一场。”昨晚，北大新闻发言人赵部长证实了该消息。他说，
学生周末出去旅游是个人权利，学校无权干涉。
北大清华的才子们没有放过任何一个表露才华的... 阅读全帖 |
|
o******r
发帖数: 259 | 2 从这个版受益很多，攒人品
尽量用中文，免得google到麻烦
就是那个一个数组3堆栈了，空间复杂度O(1)
闲话少说，上code，
思路很简单，就是两头各一个stack,
第3个stack放中间，浮动的，可以往左、右推
有啥bug随便挑，轻点拍啊
#include
#include
using namespace std;
const int n=3;
int R[3*n];
int TopA = 0, TopB = 2*n - 1, BottomB = 2*n-1, TopC = 3*n -1;
bool IsABFull(){return TopA == TopB + 1;};
bool IsBCFull(){return BottomB == TopC;};
int MoveBLeft()
{
// can not move
if (IsABFull()) return 0;
// ensure nOffset >= 1
int nOffset = max(1, (TopB |
|
g*******y
发帖数: 1930 | 3 排列有几种不同的方法。我喜欢的其中一种方法很直观，不需要保存中间结果。
N数排列:
template void Permutation(T *arr, int N, int count){
if(N<=0) return;
if(count == N){ printAll(arr,N);return;}
for(int i=count;i!=N;i++){
swap(arr[count],arr[i]);
Permutation(arr,N,count+1);
swap(arr[count],arr[i]);
}
}
组合用一个bool chosen[n]保存中间结果
int N; //N numbers
int m; //select m numbers;
int arr[N];
bool chosen[n];
void Combination(int start, int selected){
if(selected == m){ printCombination(arr, chosen); return;}
selected++;
for(int i=start |
|
b***e
发帖数: 1419 | 4 这个东西叫Chruch Numerals. 不但减一可以定义，四则运算，幂等都可以定义。 严
格的说这个东西和primitive recursion的表达能力是一样的。
这个题本身有很多解法。但是通解如下：
定义isZero(x)：
y = 1;
for(x) {
y = 0;
}
return y;
定义not(x):
y = 0;
if (isZero(x)) {
y = 1;
}
return y;
定义bool(x):
return not(not(x));
定义 if(x) then S1 else S2 为：
for(bool(x)) {S1}
for(not(x)) {S2}
有了if/then/else还有什么你不能干的：
pred(x)定义为：
y = 0;
z = 0;
for(x) {
if(z) {
y++;
} else {
z++;
}
}
return y; |
|
f****4
发帖数: 1359 | 5 明天bbg，第2次电面，紧张的期待中，求bless
整理了一下stl container element的一些东西，还有auto_ptr直接赋值
class A做为container element，run下代码就知道A成为container element的限制条
件；auto_ptr直接赋值，有地方说这个动作属于未定义，但没找到standard
class A{
private:
A(){}
//~A(){} // Error:
//A(A &a){} // Error:
//operator =(A &a){} // Error:
bool operator ==(A &a){}
bool operator <(A &a){}
int member;
public:
A(int a):member(a){}
};
int main(){
typedef tr1::shared_ptr SharePtr;
vector vec1;
Share |
|
c**********r
发帖数: 472 | 6 O(n)
List> data = //input from some where;
data.sort();
int inRangeCount=0;
int rangeStart = 0;
bool reset = true;
int overall = 0;
foreach(var v in data)
{
if(var.y==true)//start point
{
inRangeCount++;
}
else
{
inRangeCount--;
}
if(inRangeCount>0)
{
if(reset) rangeStart = v.x; reset = false;
}
else
{
overall += (v.x - rangeStart);
reset = true;
}
} |
|
m******9
发帖数: 968 | 7 我再贴个另外的写法吧，思路还是沿用你自己的思路，就是每个index 分成选择，或者
不选择。 你可以加上一个辅助数组，用来标记那些index被选择了，哪些没有被选择。
void combination(char* s, int start, bool* c, int n)
{
if(s[start]=='\0'){
print_combination(s, c, n);
return;
}
c[start] = true;
combination(s, start+1,c,n);
c[start] = false;
combination(s, start+1, c,n);
}
void print_combination(char* s, bool* c, int n)
{
for(int i=0; i
if(c[i]==true)
cout<
}
cout<
} |
|
i**********e
发帖数: 1145 | 8 我以前贴过，但不知道为什么找不回那个帖子了。
#include
#include
#include
using namespace std;
const int TAB_SPACE = 4;
void outputJSon(istream &in, int indentLevel) {
bool firstChar = true;
bool inBracket = false;
while (in) {
char c = in.get();
if (firstChar) {
cout << endl << setw(indentLevel) << c;
firstChar = false;
}
else {
cout << c;
}
if (c == '{') {
outputJSon(in, indentLevel+TAB_SPACE);
c = in.get();
assert(c == '... 阅读全帖 |
|
h**6
发帖数: 4160 | 9 楼上的代码好像仍然不是很对，这是两个版本的代码，假设a已排序。
由于a排序需要额外的复杂度，因此两个版本的复杂度差别不是很大。
逐个查找，O(M)，总复杂度O(MlogM+MlogN)
bool findelements(int* a, int M, int K, int x)
{
int prev = a[0];
int count = 1;
for(int i=1; i
{
if(a[i] >= prev+x)
{
count++;
prev = a[i];
}
}
return count>=K;
}
二分查找，O(KlogM)，总复杂度O(MlogM+KlogMlogN)
bool findelements(int* a, int M, int K, int x)
{
int* prev = a;
for(int i=1; i
{
int* curr = lower |
|
h**6
发帖数: 4160 | 10 我其实是回你上一个帖子：
“有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大
于等于给定的X？”
给出两个版本的代码，分别是O(M)和O(KlogM)复杂度。
两个函数的声明完全相同
bool findelements(int* a, int M, int K, int x)
判断已排序的长度为 M 的数组 a 中，是否存在 K 个元素的子集，其半径不小于 x ，返回值
为 bool 类型。 |
|
d**e
发帖数: 6098 | 11 来自主题: JobHunting版 - 请教个题目 应该需要两个matrix
P_Require[i,j] = 1 表示 process i 需要 resource j
P_Holding[i,j] = 1 表示 process i 持有 resource j
如果process m需要update/read/write resource n
那么set p_require[m,n] = 1
然后开始check有没有形成一个环，
如果有，则不lock，并且reset p_require[m,n]=0，没有就可以lock。
大概可能是这样，但我这个只假设一个process只能hold/require一个resource,
如果能hold/require多个resources,那么就用其它的数据结构。
bool flag[] = {false}
bool check_loop (m, n)
flag[m] = true
for all i loop
if !flag[i] && p_holding[i,n] == 1 then
check what process i requires
... 阅读全帖 |
|
E*****7
发帖数: 128 | 12 分析:为什么GOOGLE考这么"简单"的C++题 (写一个函数来计算x的n次方)?
答案1:
int XraisedtoN(int x, int N) {
int result = 1;
for (int i = 0; i < N; i++) {
result = result * x;
}
return result;
}
且慢, 如果 N = 0 或者 N = -2, 答案1死定了.
答案2:
int XraisedtoN(int x, int N) {
if (N == 0) // X^0 = 1
return 1;
int num;
bool negative;
if (N < 0) // handle X^-2 for example
{
num = -N;
negative = true;
}
else {
num = N;
negative = false;
}
int result = 1;... 阅读全帖 |
|
A*H
发帖数: 127 | 13 #q2
#include
#include |
|
r*******l
发帖数: 511 | 14 Another solution is to do an in-order traversal of the binary tree, and
verify that the previous value (can be passed into the recursive function as
reference) is less than the current value. This works because when you do
an in-order traversal on a BST, the elements must be strictly in increasing
order. This method also runs in O(N) time and O(1) space.
bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
if (!p) return true;
return (isBSTInOrderHelper(p->left, prev) &&
(p->data > ... 阅读全帖 |
|
e**********6
发帖数: 78 | 15 bool is_bst_inorder(BTNODE *root, int &prev){
if(!root)
return true;
bool vb1,vb2;
vb1=is_bst_inorder(root->left,prev);
if(prev>root->a)
return false;
prev=root->a;
vb2=is_bst_inorder(root->right,prev);
return vb1&&vb2;
} |
|
d***n
发帖数: 832 | 16 //pseudo code (c# like). it can be updated to record the path(s).
public bool CanReachTheMazeEnd(int[] input)
{
if(input == null || input.Length == 0) return false;
return CanReachTheMazeEndRecursive(input, 0, 0);
}
private bool CanReachTheMazeEndRecursive(int[] input, int index, int step)
{
if(index+step == input.Length-1) return true;
for(int i=1; i
{
if(CanReachTheMazeEndRecursive(input, index+step, i))
{
return true;
... 阅读全帖 |
|
g*****x
发帖数: 799 | 17 // DP: f(n-1) = max{f(i)}, where i from n to n-1+a[n-1] and i
bool maze(const vector &vec)
{
if(vec.size() < 2)
return true;
vector reach(vec.size(), false); // reachability of the nth pos to
the last pos
reach[reach.size() - 1] = true; // last position is always reachable to
itself
for(int i = reach.size() - 2; i >= 0; --i)
{
for(int j = i + 1; j <= i + vec[i] && j < reach.size(); ++j)
if(reach[j] == true)
{
... 阅读全帖 |
|
g*****x
发帖数: 799 | 18 // DP: f(n-1) = max{f(i)}, where i from n to n-1+a[n-1] and i
bool maze(const vector &vec)
{
if(vec.size() < 2)
return true;
vector reach(vec.size(), false); // reachability of the nth pos to
the last pos
reach[reach.size() - 1] = true; // last position is always reachable to
itself
for(int i = reach.size() - 2; i >= 0; --i)
{
for(int j = i + 1; j <= i + vec[i] && j < reach.size(); ++j)
if(reach[j] == true)
{
... 阅读全帖 |
|
L*******e
发帖数: 114 | 19 可不可以用vector + small map variables, like the following:
/* assume range 'from' ... 'to' */
void findDupTri(int a[], size_t size, int from, int to, int& dup, int& trip)
{
vector v( to-from+1, false);
map small;
for( int i = 0; i < size; i++ ){
if( v[a[i]-from] == true ) {
small[a[i]]++;
}
else{
v[a[i]-from] = true;
}
}
// scan the map to find dup and trip
if ( small.size() != 2 ) //error
... 阅读全帖 |
|
s*****n
发帖数: 994 | 20 bool findZeroSum (int set[], int size){
int i,jk, left, right;
int vi, vj, vk;
bool found=false;
if (size<3) return false;
sort (set,set+size);
for (i=size-1;i>1;i--){
left = 0; right = i-1;
while (right>left){
if (set[left]+set[right]==-set[i]) {found=true; j=left; k=right; break
;}
else if (set[left]+set[right]>-set[i]) left++;
else right--;
}
if (found) break;
}
if (found){
return true;
}return false;
}
+A |
|
e***s
发帖数: 799 | 21 对不起，我又没认真看回复。。。。
public static bool FindSum(int[] arr)
{
bool found = false;
Array.Sort(arr);
int lenght = arr.Length;
int left, right;
for(int i = lenght - 1; i >= 2; i--)
{
left = 0;
right = i - 1;
while (left < right)
{
if (arr[left] + arr[right] == -arr[i])
return true;
else if (arr[left... 阅读全帖 |
|
c*****e
发帖数: 74 | 22 题目：一个board上，每个cell是一个字母，从一个cell出发，可以到它相邻的8个cell
。这样可以在board上walk。但是一个walk上一个cell不能出现2次。
要求：找出所有的可以由walk得到到的不同的单词。编程中可以自己假定一些已经实现
的方法。
以前面试被问到过，时间浪费在一些细节（怎么解决8个相邻cell的问题，怎么检查是
否一个cell重复出现）上了，当时也没有充分利用try，没答好，主要还是对递归、Try
的接口不熟。今天好好想了想该怎么写，下面是我的代码，花了不少时间，觉得收获不
少。好好写写这道题应该对面试很有帮助的。
有问题帮忙指出一下。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
class CTryNode;
class CTry
{
public:
CTryNode* Advance(CTryNode* pNode, char ch);
CTryNode* Back(CTryNode* pNode);
string GetValue(pTryNode* pNode);
bool IsCurr... 阅读全帖 |
|
x***y
发帖数: 633 | 23 int numOfReaders = 0;
int numOfWriters = 0;
int numOfWaitingWriters = 0;
Lock aLock;
void read(...){
bool hasNotRead = true;
while(hasNotRead){
aLock.lock();
if(numOfWriters==0 && numOfWaitingWriters==0){
numOfReaders++;
hasNotRead = flase;
}
aLock.unlock();
}
............//open file and read
aLock.lock();
numOfReaders--;
aLock.unlock();
}
void write(...){
aLock.lock();
numOfWaitingWriters++;
aLock.unlo... 阅读全帖 |
|
N*D
发帖数: 3641 | 24 这个Lock用法不对呀，你只是用Lock保证了对Counter的Atomic访问，对于文件的读写
没有Lock呀。
比如先来个Writer，正写文件呢，前面对counter的update的lock都release了，又来个
writer，也进入Lock去，if statement一判断，啥也不用干，release lock，it也写文
件去了。呵呵。
int numOfReaders = 0;
int numOfWriters = 0;
int numOfWaitingWriters = 0;
Lock aLock;
void read(...){
bool hasNotRead = true;
while(hasNotRead){
aLock.lock();
if(numOfWriters==0 && numOfWaitingWriters==0){
numOfReaders++;
hasNotRead = flase;
}
aLock.unlock();
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 25 不是大侠，贴一贴我的代码，代码如果不好看 请多多包涵
恐怕只能 handle 以上的 sample test case。
基本思路就是递归，如果有更复杂的情况可以再慢慢改进。
#include
#include
#include
using namespace std;
const int TAB_SPACE = 4;
void outputJSon(istream &in, int indentLevel) {
bool firstChar = true;
bool inBracket = false;
while (in) {
char c = in.get();
if (firstChar) {
cout << endl << setw(indentLevel) << c;
firstChar = false;
}
else {
cout << c;
}
if (c == '{') {
outputJSon(in... 阅读全帖 |
|
i**********e
发帖数: 1145 | 26 其实不递归 代码或许会更简单些
void outputJSon(istream &in) {
bool newLine = false;
bool inBracket = false;
int indentLevel = 0;
while (in) {
char c = in.get();
if (newLine) {
cout << endl << setw(indentLevel) << c;
newLine = false;
}
else {
cout << c;
}
if (c == '{') {
indentLevel += TAB_SPACE;
newLine = true;
} else if (!inBracket && c == ',') {
newLine = true;
} else if (c == '}') {
newLine = true;
} else if (c == '[') {
... 阅读全帖 |
|
s*******f
发帖数: 1114 | 27 using System;
using System.Collections.Generic;
using System.Text;
namespace MSC
{
class Program
{
//“bool F(string s, char ch1, char
ch2, int n)”
//The function determines whether
or not there exists an occurrence of
//ch1 and ch2 separated by a
distance of no more than n in the given
//string s, where s is ascii and
user entered (your function needs
//to work on any input.) The
function must be efficient and
//**optimized** for both space... 阅读全帖 |
|
l*****g
发帖数: 685 | 28 Good question!
I was wrong. It's not really a BST, but rather a BT.
The nodes don't have explicit keys, and line numbers are implied by the in-
order traveral of the tree. Each node holds prevCount, number of all lines
before it, and nextCount, number of all lines after it.
Here is a rough implementation of this idea.
class Line
{
public:
//char * text;
Line * prev;
Line * next;
int prevCount;
int nextCount;
Line(char * text)
{
// clone text data
prev ... 阅读全帖 |
|
i**9
发帖数: 351 | 29 写了一个 检查bst对称的
bool symmetrical(Node * root){
if(root==NULL){
return true;
}
return symmetrical(root->left,root->right);
}
bool symmetrical(Node * l,Node * r){
if(l==NULL && r==NULL){
return true;
}
if(l==NULL && r!=NULL){
return false;
}
if(l!=NULL && r==NULL){
return false;
}
if(l->data!=r->data){
return false;
}
return symmetrical(l->left,r->right)&&symmetrical(l->right,r->left);
} |
|
p****g
发帖数: 355 | 30 一定要指向父节点的指针么？做post-order traverse，用两个bool表示那两个点是否
被traversed，返回第一个both bool are true的点。 |
|
S**I
发帖数: 15689 | 31 error message说的很清楚：string类的operator<没有定义，改成这样子就行了：
#include
#include
#include
#include
#include
using namespace std;
bool comp(const string& s1, const string& s2){
return strcmp(s1.c_str(), s2.c_str()) < 0;
}
int main () {
char *m1[] = {"a","e","c","m"};
vector v1(m1,m1+4);
char *m2[] ={"n"};
vector v2(m2,m2+1);
vector u;
/* int m1[] = {1,2,3,4};
vector v1(m1,m1+4);
int m2[] ={... 阅读全帖 |
|
s******c
发帖数: 1920 | 32 任意取两点，计算斜率和截距，能得到一条直线，然后把其他落在这条直线上的点也打
印出来。用一个set保存unique的（斜率，截距），这样不会重复选取。特殊情况是斜
率为无穷大，没有截距。
=============================================
#include
#include
using namespace std;
#define N 5
class Line{ //y=a*x+b
public:
float a,b;
Line ():a(0),b(0){}
Line (int n1,int n2):a(n1),b(n2){}
bool operator<(const Line &right)const{
if (a==right.a)
return b
else return a
}
bool operator==(const Line &right)const{
... 阅读全帖 |
|
l*****g
发帖数: 685 | 33 为什么用remove_if? remove_if 会破坏原来的vector. 应该用 find_if 比较好
最简单的：
bool greaterThan50(int num)
{
return (num > 50);
}
find_if (v.begin(), v.end(), greaterThan50);
稍微改进一点：
template
bool greaterThanInt(T const &num)
{
return (T > i); // type T should be comparable to Int.
}
find_if(v.begin(), v.end(), greaterThan);
更灵活一点：
find_if(v.begin(), v.end(), bind2nd(Greater(), 50)); |
|
s*****y
发帖数: 897 | 34 can you give me your input to test.
I extend your solution in finding kth smallest element without calling it
two times.
I test
1. {1} {2}
2. {1}, {2,3}
3, {1,2}, {3,4}
4 {1,2} {4,5,6}
#define MAX(A,B) ((A) > (B) ? (A):(B))
#define MIN(A,B) ((A) < (B) ? (A):(B))
static int A[] = {2};
static int B[] = {1};
/* Find the Kth smallest element of sorted array A and B */
double Find_Kth_Smallest(int A[], int len1, int B[], int len2, int k, bool
divide)
{
int i, j;
int Ai, Ai_1, Bj, Bj_1; /* Ai_... 阅读全帖 |
|
l*****g
发帖数: 685 | 35 用C++写了一个版本:
void RecursivelyRemoveSubString(char *str, const char *sub)
{
if (!str || !sub || *sub == 0 || *str == 0 || strlen(str) < strlen(sub))
return;
char *end = str;
char *cur = str;
int subLen = strlen(sub);
char subEnd = sub[subLen - 1];
while (*cur != 0)
{
*end = *cur;
if (*end == subEnd)
{
char *reCur = end;
int subIndex = subLen - 1;
bool match = true;
bool reCurEnd = false;... 阅读全帖 |
|
k***t
发帖数: 276 | 36 我也试一个，in-placed的。先把要删掉的mark成'*'。第二次遍历时再删掉。
#include
// /a/b/./../../c/d => /c/d
void path (char *in) {
char *p, *q;
bool isSlash;
char inv='*';
if (!in || !*in) return;
int i=0;
// parse
p=in; isSlash=false;
while (*p) {
/* first slash */
if (*p=='/') {
if (!isSlash) {
isSlash=true;
} else {
*p=inv;
}
p++; continue;
}
isSlash=false;
... 阅读全帖 |
|
g*****x
发帖数: 799 | 37 以前曾经去过一次西雅图，过几天又要去了
感觉面试的时候设计题是我的软肋，答的时候总是磕磕绊绊的
想跟大家一起来讨论一下
以下列出一些我自己遇到过的或者在网上见过的题
欢迎大家讨论，补充
1. DB design of sys that enable paid customers to park, customers can either
book online beforehead or park at empty positions that are not booked
table Lot(id(pk), position, occupied);
table Customer(id(pk), name, phone);
table Lot_Customer(lid(pk), cid, start_time(pk), end_time);
2. OOD deck of cards
class Card {
enum Suits suit;
int value;
// getters & setters(check if suit & value are valid)
};... 阅读全帖 |
|
x*****l
发帖数: 148 | 38 mark
以前曾经去过一次西雅图，过几天又要去了
感觉面试的时候设计题是我的软肋，答的时候总是磕磕绊绊的
想跟大家一起来讨论一下
以下列出一些我自己遇到过的或者在网上见过的题
欢迎大家讨论，补充
1. DB design of sys that enable paid customers to park, customers can either
book online beforehead or park at empty positions that are not booked
table Lot(id(pk), position, occupied);
table Customer(id(pk), name, phone);
table Lot_Customer(lid(pk), cid, start_time(pk), end_time);
2. OOD deck of cards
class Card {
enum Suits suit;
int value;
// getters & setters(check if suit & value are val... 阅读全帖 |
|
b*******y
发帖数: 1240 | 39 在delete head的时候，书上有两种写法
一是P27
bool deleteElement( IntElement **head, IntElement *deleteMe )
{
IntElement *elem = *head;
if( deleteMe == *head ){ /* special case for head */
*head = elem->next;
delete deleteMe;
return true;
}
}
第二种是 P37
bool remove( Element *elem ){
if (elem == head) {
head = elem->next;
delete elem;
return true;
}
...
那种方法是对的 |
|
r*******y
发帖数: 1081 | 40 来自主题: JobHunting版 - 问一个题目 bool IsNodeInside(TreeNode * root, TreeNode * node){
if(root==NULL)
return false;
if(node == root)
return true;
bool tmp = IsNodeInside(root->left, node);
if(tmp == true)
return true;
tmp = IsNodeInside(root->right, node);
if(tmp == true)
return true;
return false;
}
TreeNode * find(TreeNode * root, TreeNode * node1, TreeNode * node2){
if(root == NULL)
return NULL;
if(node1==root)
retur... 阅读全帖 |
|
i**********e
发帖数: 1145 | 41 我写的代码如下。
这样打印出来的所有路线还真不是一般的多，
我在想题目的原意是不是指只要路线有相交就不允许？
例如：
1->9->7->3 就不允许，因为 7->3 与 1->9 相交。
如果有以上的条件的话，用 visited cells 就不能解决了。
似乎比较复杂。
#include
#include
using namespace std;
int crossPoint[10][10] = {
{0},
{0, 0, 0, 2, 0, 0, 0, 4, 0, 5},
{0, 0, 0, 0, 0, 0, 0, 0, 5, 0},
{0, 2, 0, 0, 0, 0, 0, 5, 0, 6},
{0, 0, 0, 0, 0, 0, 5, 0, 0, 0},
{0},
{0, 0, 0, 0, 5, 0, 0, 0, 0, 0},
{0, 4, 0, 5, 0, 0, 0, 0, 0, 8},
{0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
{0, 5, 0, 6, 0, 0, 0, 8... 阅读全帖 |
|
s*****y
发帖数: 897 | 42 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
s*****y
发帖数: 897 | 43 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
i**********e
发帖数: 1145 | 44 利用 next_permutation 效率要好些。
代码请参考这里：
http://www.mitbbs.com/article0/JobHunting/31891031_0.html
递归的话，循环里跳到下一个不重复的元素。
例如：
[2 2 3]
=> [2 ...] ( [2 2 3] and [2 3 3] )
把重复的 2 跳过
=> [3 ...] ( [3 2 2] )
// precondition: A must be sorted
void printPermutations(int A[], int n, int count, bool used[], int perm[]) {
if (count == n) {
for (int i = 0; i < n; i++)
cout << A[perm[i]] << " ";
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) continue;
perm[count] ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 45 利用链表来实现 trie insert 的非递归代码如下，要复杂写。对 double pointer 的
理解请参考这个帖：
http://www.mitbbs.com/article_t0/JobHunting/31881903.html
struct Trie {
Trie() : c(0), son(NULL), next(NULL), end(false) {
}
Trie(char key) : c(key), son(NULL), next(NULL), end(false) {
}
void insert(const char *s) {
Trie *trie = this;
while (*s) {
Trie **p = NULL;
if (!trie->find(*s, p)) {
Trie *temp = *p;
*p = new Trie(*s);
(*p)->next = temp;
}
trie = *p;
asser... 阅读全帖 |
|
n**e
发帖数: 116 | 46 Your code looks works to me, but not elegant.
See the following for your reference:
template
bool isBst(Node* node, T low, T high) {
if (node == NULL) return true;
if (node->data < low && node->data > high) return false;
return isBst(node->left, low, node->data
&& isBst(node->right, node->data, high);
}
template
bool isBst(Node* root) {
return isBst(root, limits::min(), limits::max());
} |
|
B*********e
发帖数: 9 | 47 真屈辱，心情恢复平静中。
写出来大家面他家的时候也做好思想准备吧
L公司刚上市，现在狂招人中,不知道是不是大家都cash out了。
本来要面9个人，后来只见了3个。就被人家说“I do not think we should carry on, in respectful of your time and our time”
写写吧，攒rp。大家轻拍，知道自己业务知识不强，回家读书过后再来过。
第一场本来要见host manager，后来跑来两个engineer说调换一下顺序。没有寒暄，直接问，我们问你technical的问题。
第一个给你一个FilterIterator Class（predicate p, iterator i), 写
bool hasnext() 还有bool next()
搞了半天什么是predicate，还有那个iterator i到底是哪个list上头的。但是后来这个在对方提示下写的差不多了。
第二个说给你一个很长的string list，让你分行打印。然后告诉你一行只能写L（比如
25）个字符，而且首位和末尾不能是空格，空格只能在中间，两个词中间可以空两... 阅读全帖 |
|
f*******t
发帖数: 7549 | 48 我刚写的，至少例子都能通过。话说我没觉得递归哪里不好啊。。。
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 ... 阅读全帖 |
|
p****e
发帖数: 37 | 49 贴个楼主事后写的：
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;
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 50 我刚写的，至少例子都能通过。话说我没觉得递归哪里不好啊。。。
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 ... 阅读全帖 |
|
