k***t
发帖数: 276 | 1 以前看见一个版上大拿做的一个O(N)的find/union。不过那个是找
最长连续子序列，所以并集时只需更新边界元素，且并集操作只会
在边界发生。动态更新最长序列，只需扫描一遍即可。
下面是原贴。不知可否借鉴得上？
发信人: battlesc (zerg), 信区: JobHunting
标 题: Re: G题讨论
发信站: BBS 未名空间站 (Fri Jul 15 11:37:33 2011, 美东)
#include
#include |
|
k***t
发帖数: 276 | 2 参照网上的思路，写了一个wildcard match。
做面试用还算简洁。谁给Review一下？
#include
using namespace std;
bool match(char* in, int iidx, char* ptn, int pidx)
{
if (!in || !ptn) return false;
// base case
if (!in[iidx] && !ptn[pidx]) return true;
if (!ptn[pidx]) return false;
if (!in[iidx]) {
while(ptn[pidx]) if (ptn[pidx++]!='*') return false;
return true;
}
if (ptn[pidx]=='?' || ptn[pidx]==in[iidx])
return match(in, iidx+1, ptn, pidx+1);
if (ptn[pidx]==... 阅读全帖 |
|
l****c
发帖数: 838 | 3 You can write a simple test case, cannot you?
my test shows no difference:
=========================================
#include
using namespace std;
class A {
public:
A() {
cout<<"ctr"<< endl;
throw 1;
}
~A() {
cout <<"dstr"<< endl;
}
};
int main()
{
A* pa = new A;
delete pa;
return 0;
}
==========================
Both terminated. |
|
l*****a
发帖数: 559 | 4 I tried. Your code is not working.
#include
#include
#include
#include
#include
#include
using namespace std;
double GetMedian (int* a, int n, int* b, int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMe... 阅读全帖 |
|
w*******s
发帖数: 96 | 5 有没有对Careercup的C/C++的Solution感兴趣的同学啊？准备做几个样题和我的实现放
上来大家讨论讨论：先来一个拍拍
////////////////////////////////////////////////////////////////////////////
////////
// Problem 3.6: (第4版）
//
// Analysis and points:
// 1. You are asking to implement one sort algorithm with input
parameter is a stack.
// 2. If we allow to use extra space, we can use another stack to
help. Each time, we
// insert the top element into the proper postion. The stack is
used each other as
// buffer ... 阅读全帖 |
|
c*****e
发帖数: 737 | 6 1, class A {virtual void f();}
class B:public A {};
class C:public B {};
class D:public A, B {virtual void f();}
让你说明D的virutal table
2, class A
{public:
A(int v) {var = v;}
void f(){cout << var << endl;}
int var;
}
class B:public A
{
public:
public B(int v1, v2){var = v1; var2 = v2;}
void f()
{cout << var << "," << var2 << endl;}
int var, var2;
}
main()
{
B* pb = static_cast(new A(1);
pb... 阅读全帖 |
|
p*i
发帖数: 411 | 7 #include
#include
#include
#include
using namespace std;
inline void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
int partition(vector& work, vector& indices, int p, int q) {
// use work[q] to partition the array
const int x = work[q];
int i = p-1;
for (int j = p; j < q; j++) {
if (work[j] < x) {
i++;
swap(work[i], work[j]);
swap(indices[i], indices[j]);
}
}
i++;... 阅读全帖 |
|
q******0
发帖数: 15 | 8 See the code below. I am confused that "len = 5" from main function, "len =
4" from RemoveDuplicate function. When does terminate '\0' count? Thanks.
#include
using namespace std;
void RemoveDuplicate(char str[])
{
int len = sizeof(str)/sizeof(str[0]);
cout << "len = " << len << endl;
}
int main()
{
char a[] = "abcd";
int len = sizeof(a)/sizeof(a[0]);
cout << "len = " << len << endl;
RemoveDuplicate(a);
return 0;
} |
|
i**********e
发帖数: 1145 | 9 Try this and figure out why:
void foo(int str[])
{
int len = sizeof(str)/sizeof(str[0]);
cout << "len = " << len << endl;
}
int main()
{
int a[] = {1,2,3,4};
int len = sizeof(a)/sizeof(a[0]);
cout << "len = " << len << endl;
foo(a);
return 0;
} |
|
r*****k
发帖数: 1281 | 10 来自主题: JobHunting版 - 上一道题吧 把我程序里面的match found condition
从if(i==0 || next != ')') 改为 if(i==0 && next != '(')应该就可以handle你这种
情况了。
-----------------------------------------------------
void matchs1(char* str, int& max, int &num){
int i =0; max=0, num=0;
int curr_len=0;
if(*str == '\0' || str == NULL) {max=0; num=0; return;}
//if there is a match, put the len of this match to vector
vector match;
while(*str != '\0'){
char next = *(str+1);
... 阅读全帖 |
|
p*i
发帖数: 411 | 11 来自主题: JobHunting版 - 上一道题吧 #include
#include
#include
using namespace std;
void process(const string& str) {
stack s, s1;
for (unsigned i = 0; i < str.size(); i++) {
if ('(' == str[i]) {
s.push(i);
} else {
if (!s.empty()) {
unsigned left = s.top(); s.pop();
unsigned& right = i;
if (s1.empty() || (s1.top()+1 < left)) {
s1.push(left);
s1.push(right);
... 阅读全帖 |
|
A**u
发帖数: 2458 | 12 #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... 阅读全帖 |
|
F********u
发帖数: 7 | 13 bool is_same_BST(int *A, int m, int a_min, int a_max, int *B, int n, int b_
min, int b_max)
{
if( A == NULL || B == NULL )
return false;
if( m == 0 && n == 0 )
return true;
if( m == 0 || n == 0 )
return false;
if( A[0] != B[0] )
return false;
int i, j, a, b;
// A tree -> left subtree root
for( i = 1; i < m; i++ )
{
if( A[i] > a_min && A[i] < A[0] )
break;
}
// B tree -> left subtree root
for( j = 1; j... 阅读全帖 |
|
a***y
发帖数: 50 | 14 俺写了一个, 没有测试过只有1, 2, 或者0 的情况...
请高手指正...
思路就是维护了三个指针p0, p1, p2, 分别指向了数组index最小的0, 1, 2值所在位置,
然后遍历的过程中,不断swap(值和指针同时swap), 复杂度为O(n), 常数空间.
请高手们多指正了!
#include
#include
using namespace std;
class MITbbSolver
{
public:
MITbbSolver() {}
virtual ~MITbbSolver() {}
public:
void swap_pv(int* &p1, int* &p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
int* p = p1;
p1 = p2;
p2 = p;
return;
}
void sort_012_array(int* ... 阅读全帖 |
|
w****x
发帖数: 2483 | 15 [sourcecode language="cpp"]
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
wh... 阅读全帖 |
|
w****x
发帖数: 2483 | 16 [sourcecode language="cpp"]
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
wh... 阅读全帖 |
|
Z**********4
发帖数: 528 | 17 我的意思是不用整个pair用一个hash map就可以了。不过我想做点改动 利用hash里面
key对应的value来标志对（3，4）已经找过了，下次不论是（4，3）还是（3，4）都视
而不见。
hash_map hash;
vector::iterator iter;
vector result;
for(iter = array.begin(); iter!= array.end(); iter++){
if(hash.find(*iter) == hash.end() && hash.find(n-*iter) == hash.end(
)){
hash[n-*iter] = 1; //这是第一次遇见3的时候，存入 4->1
}
else if(hash[*iter]==1){ //发现hash里面有4，而且value是1 就算找到了
（3，4）
hash[*iter]=0; //将hash... 阅读全帖 |
|
z********i
发帖数: 568 | 18 /* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i
/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i... 阅读全帖 |
|
z********i
发帖数: 568 | 19 /* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i
/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i... 阅读全帖 |
|
w****x
发帖数: 2483 | 20 //Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 ... 阅读全帖 |
|
w****x
发帖数: 2483 | 21 //Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 ... 阅读全帖 |
|
i*********7
发帖数: 348 | 22 int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<
cout<
max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = ... 阅读全帖 |
|
C***U
发帖数: 2406 | 23 class Base {
public:
int x;
};
class LevelOneA: public Base {
public:
void show() { std::cout << x << std::endl; }
};
class LevelOneB: public Base {
public:
void show() { std::cout << x << std::endl; }
};
class LevelTwo: public LevelOneA, public LevelOneB {
public:
};
这个是不是有diamond inheritance problem？
我在VS里面测试没问题。
那LevelTwo这个类里面有几个x啊？ |
|
d****o
发帖数: 1055 | 24 我完成了一个版本，可以过small test,但是过不了large test。
1. 请问我的版本的时间复杂度是多少？
2. 哪位有更好得解法，请教一下。
bool wordSearch(vector > &board, string word, int level,
vector >& used, int curRow, int curCol)
{
if(curRow<0||curRow>=board.size()||curCol<0||curCol>=board[0].size()
){
return false;
}
if(used[curRow][curCol])
return false;
if(board[curRow][curCol]!=word[level])
return false;
if(level==word.siz... 阅读全帖 |
|
O*******d
发帖数: 20343 | 25 int printHelloWorld()
{
cout << "Hello World before main()" << endl;
return 0;
}
static int a = printHelloWorld();
void main(int argc, char** argv)
{
cout << "Hello World in the main() " << endl;
}
那个printHelloWorld就是在main()之前被call。
用这种方法，你可以在main()之前运行整个庞大的程序。 |
|
a******a
发帖数: 2646 | 26 来自主题: JobHunting版 - G电面一题 请指教。我的解答
#include "stdafx.h"
#include
using namespace std;
void transform(char* ,char* ,int ,int,int );
int _tmain(int argc, _TCHAR* argv[])
{
char b[100];
char a[100];
cin.getline(a,100);
int length;
for( length=0;length<100;length++)
if(a[length]=='\0')
break;
transform( a, b, length,0,0);
return 0;
}
void transform(char* a,char* b,int length,int loca,int locb)
{
char x,y[2];
x=*(a+loca);
*(b+locb)=static_cast(atoi(&x)+97... 阅读全帖 |
|
j******2
发帖数: 362 | 27 为什么没有signed的问题？
P.366 L10
bitfield[n/8]|=1<<(n%8);
在n<0时就会出错（n是从文件读进的int）
how about this:
void print_missing_one_pass(char *file_name)
{
ifstream infile(file_name);
assert(infile);
int size=0x20000000;
char *flag=new char[size];
memset(flag, 0, size);
int i;
while (infile >> i)
{
int byte=(unsigned)i>>3;
int bit=i&7;
flag[byte]|=1<
}
for (unsigned k=0; k
{
char t=flag[k];
if (t!='\xff')
... 阅读全帖 |
|
s***0
发帖数: 117 | 28 #include
#include
#include
#include
#include
using namespace std;
class ProcessParen
{
public:
ProcessParen(){};
void processString(string& inString)
{
stack charStack;
for (int i = 0; i< inString.length(); ++i)
{
if(inString[i] == '{')
{
mResult += "{";
charStack.push('{');
}
if(inString[i] == '}')
{
... 阅读全帖 |
|
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
... 阅读全帖 |
|
l*******b
发帖数: 2586 | 30 经过很久挣扎终于调成功了。。。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
... 阅读全帖 |
|
M**A
发帖数: 78 | 31 int find_max_sec(int *a, int n) {
if(n<2) return 0;
int max, sec_max;
if(a[1]
max=a[0];
sec_max=a[1];
}
else {
max=a[1];
sec_max=a[0];
}
for(int i=2;i
if(a[i]>max) {
sec_max=max;
max=a[i];
}
if(a[i]sec_max){
sec_max=a[i];
}
}
cout<<"Largest element is "<
cout<<"Second largest e... 阅读全帖 |
|
r*c
发帖数: 167 | 32 二爷，坑爹算法来也。用状态机搞砸一切面面！哈哈
#include
#include
#include
using namespace std;
class Numericality;
void TestNumericality();
void TestNumericalityHelper(const string& str, const bool expected,
Numericality& nc);
class Numericality
{
public:
struct State
{
const string _str;
int _index;
State() {}
State(string s, int i) : _str(s), _index(i){}
virtual State* MoveNext(){
if(_str.empty() || _index < 0 || _index >= _str... 阅读全帖 |
|
d**********x
发帖数: 4083 | 33 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
，这点overhead基本可以忽略不计了。欢迎找bug：
#include
#include
#include
using namespace std;
#include
static int get_index(int i) {
if (i == 0) {
return 1;
}
return (1 << i) + 1;
}
void rearrange(vector& vec) {
int bitmap = 0; //"O(1)" space for length < (1 << 32)
int k = vec.size() / 2;
int n = vec.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
... 阅读全帖 |
|
w****x
发帖数: 2483 | 34 后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
... 阅读全帖 |
|
w****x
发帖数: 2483 | 35 后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
... 阅读全帖 |
|
d**********x
发帖数: 4083 | 36 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
nMaxStep我设置为了2 * target，不知道会不会引起问题。
在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
对比程序：（前半部分还是coldknight的）
#include
#include
#include
using namespace std;
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - ... 阅读全帖 |
|
U***5
发帖数: 2796 | 37 一边看球一边草草写了写，corner case没时间搞了，只写了头2个search的情况：
小于key的最大值 - op_max_less
大于key的最小值 - op_min_great
其他几种情况自己加Functor就是了。感觉myfind return那里比较繁琐，应该有更好办
法整理一下。
写得不好，轻拍。
//Compare.h
enum Op_code
{
op_max_less = 0,
op_min_great
};
class Less
{
public:
Less(int v): val_(v), op_(op_max_less){}
bool operator()(int v1)
{
return v1 < val_;
}
const Op_code op_;
private:
int val_;
};
class Greater
{
public:
Greater(int v): val_(v), op_(op_min_great){}
bool opera... 阅读全帖 |
|
p****e
发帖数: 3548 | 38 不知对不，欢迎测试
// 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
#include
using namespace std;
int findnotsubarray(vector &rlt, vector &temp, int &X, int a[],
int &length, int start)
{
if(start>=length) return 0;
for(int t=0; t<=X; ++t)
{
int i = start;
for(; i
{
if(t==a[i])
{
... 阅读全帖 |
|
l***i
发帖数: 168 | 39 在C＋＋里可以用pointer的reference直接改变一个memory location的值，比如下面这个
#include
using namespace std;
void update(int*);
int main()
{
int x = 5;
int* pi = &x;
cout << "Before update, " << x << endl;
update(pi);
cout << "After update, " << x << endl;
return 0;
}
void update(int* t)
{
*t = 8;
}
输出是
Before update, 5
After update, 8
是不是可以说，在java里 没有相应的功能？
null |
|
j******2
发帖数: 362 | 40 如果在一个函数里
int rand_n(int n)
{
srand ( (unsigned)time(NULL) );
return rand()%n;
}
void main()
{
for(int i=0;i<1000;i++)
cout<
}
出来就全部一个数。
如果改成
int rand_n(int n)
{
return rand()%n;
}
void main()
{
srand ( (unsigned)time(NULL) );
for(int i=0;i<1000;i++)
cout<
}
就对了。
敢问这是为虾米呢？ |
|
x******a
发帖数: 6336 | 41 【 以下文字转载自 Programming 讨论区 】
发信人: xiaojiya (xiaojiya), 信区: Programming
标 题: 请问关于overloading <<
发信站: BBS 未名空间站 (Wed Feb 27 11:59:50 2013, 美东)
I am working on the example in accelerated C++.
I have overloaded operator+= , operator+ , and operator<<.
the following code does not work.
I got "invalid operands to binary expression('ostream'(aka 'basic_ostream<
char>') and 'myString') when compiling the code.
myString s1="hello";
myString s2="world";
std::cout<< s1+s2 <
it worked in the foll... 阅读全帖 |
|
o******3
发帖数: 91 | 42 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过sample test
但是目前还不能过所有的Test
题目：
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs which have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topm... 阅读全帖 |
|
o******3
发帖数: 91 | 43 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过sample test
但是目前还不能过所有的Test
题目：
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs which have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topm... 阅读全帖 |
|
o******3
发帖数: 91 | 44 我今天又写了一下
现在这个可以过所有数据集合了
方法还是BFS
区别的 这次我没有模拟stack
直接在Array上操作 这样程序更简单 写的可以快一点
#include
#include
#include
#include
#include |
|
b*******e
发帖数: 217 | 45 example: { 3, 2, 4, 1 3} 3 is the fist repeated.
// const space
for (int i = 0; i < N; i++) {
int x = a[i];
if ( x> 0 ) {
if ( a[x] < 0 ) { // means the xith item has been changed before.
that means X has shown up already
cout << x << endl;
break;
}
else { // means the xth item has not bee changed yet. let us change
the xth item to negative. Also this mean X does not show up yet
a[x] = a[x]- N;
}
}
... 阅读全帖 |
|
b*******e
发帖数: 217 | 46 Some modificaiton on my code. don't need to use x-N to track whether a X is
hit. Simply use -X is okay.
-------------
are you talking about my algorithm?
It gives 2 for 1221.
(1) go to a[0], 1 -> will change a[1] to 2-4 = -2. the array becomes 1, -2,
2, 1
(2) go to a[1], -2, calculate the original = 4-2 = 2. check a[orig] = a[2] =
2 > 0, so change a[2] to 2-4
= -2. now the array becomes 1, -2, -2, 1. Note here a[2] is changed because
of a[1] originally == 2.
(3) go to a[2], -2, calculate the or... 阅读全帖 |
|
o******3
发帖数: 91 | 47 听了二爷的话，开始做hackerrank
今天被lego blocks绊住了
测试数据集可以过 但是提交数据集就超时了 虽然我用的确实是DP
下面是题目和我的代码，还望指点
You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3
and 1 * 1 * 4. Assume you have infinite number of blocks of each type.
You want to make a wall of height N and width M out of these blocks. The
wall should not have any holes in it. The wall you build should be one solid
structure. A solid structure means that it should not be possible to
separate the wall along any vertical line withou... 阅读全帖 |
|
h*******8
发帖数: 29 | 48 搞了一个下午，一直超时，难道复杂度可以比O(n^2)小么。请教各位了。感觉自己实在
是太菜了。
代码是依据以下的方程，a[N]是input
f[i] = max( max(for all j, 0
(i-1)*a[i] - (a[1]+a[2]+...+a[i-1]) )
以下是代码
int main() {
int T;
#define RF
#ifdef RF
ifstream& in = ifstream("input.txt" , ios::in);
#else
istream& in = cin;
#endif
in>>T;
for(int t=0 ; t
int N;
in>>N;
vector a(1,0);
vector cache(1 , 0);
int accu = 0;
... 阅读全帖 |
|
d*******3
发帖数: 58 | 49 C++ version
void LevelTraverse(Node* root)
{
if(root == NULL)return;
vector v;
v.push_back(root);
int cur = 0;
int last =0;
while(cur < v.size())
{
last = v.size();
while(cur < last)
{
cout<data<
if(v[cur]->left !=NULL)v.push_back(v[cur]->left);
if(v[cur]->right != NULL)v.push_back(v[cur]->right);
cur++;
}
cout<
}
} |
|
j*****y
发帖数: 1071 | 50 写了一个，欢迎测试
#include
#include
#include
#include
#include
using namespace std;
bool isNumber(string s)
{
if(s[0] == '+' || s[0] == '-' || s[0] == '(' || s[0] == ')')
{
return false;
}
return true;
}
int helper(int a, int b, char c)
{
if(c == '+')
{
return a + b;
}
else
{
return a - b;
}
}
bool valid(vector &s)
{
stack v;
stack c;
for(int i = 0; i < s.size(); ++i)
... 阅读全帖 |
|
