w*z
发帖数: 75 | 1 第一个就是用递归实现循环的意思吧
#include
int a = 1;
int b = 1;
bool first = true;
void f(n) { // print all fib nums <= n in normal order, n >= 1
if (first){
cout<
first = false;
}
int c = a + b;
if (c > n)
return;
cout<
a = b;
b = c;
f(n);
}
2)
30 |
|
i**********e
发帖数: 1145 | 2 刚想到很精简的 code，不需要用 post-fix stack-based expression，直接储存进一
个 string 数组即可。
效率应该是不错的了，有一些方面可以考虑提高效率，例如用 vector 需要删除元素可
能会慢些，但 vector 里的元素很少，应该影响不大。
还有一点就是每次传递归的时候，都需要把所有的数组重新 copy 一次。这是无可避免
的，因为每次进入下一层递归时必须传 copy，不能在原有数组中更改。
#include
#include
#include
#include
#include
using namespace std;
void generate(vector A, int target, int s, vector expression);
template
void eraseAt(vector &vec, int i) {
typename vector::iterator ... 阅读全帖 |
|
M7
发帖数: 219 | 3 你不一定要机械的读code, 你可以说begin of the for loop, end of the for loop.
a[0]: a sub 0
-> : arrow
cout << a可以直接说cout a |
|
g*********s
发帖数: 1782 | 4 so:
cout << "hello, world!" << endl;
"cout left shift double quote hello comma space world exclamatory mark
double quote left shift endl semi-comma change a line" |
|
n*******r
发帖数: 22 | 5 class A
{
private:
int n;
public:
virtual void Fun1(int no=10)
{
n = no;
cout<<"A::Fun1"<
}
};
class B : public A
{
private:
int m;
public:
virtual void Fun1(int no=20)
{
m = no;
cout<<"B::Fun1()"<
}
}
int main()
{
B b;
A &a =b;
a.Fun1();
return 0;
}
这个程序的输出是 B::Func1()10
实在想不明白为什么输出10，而不是20. |
|
g*******n
发帖数: 86 | 6 void f()
{
const int i=9;
......;
cout<
}
-1
问中间的......怎样写能输出－1这结果。我一开始说用const_cast，他说还有其他方
法吗，最后告诉我建立int arr[10],修改
arr[-1]的值就能间接修改i的值。我当时称赞他的方法很妙。回来后试验了一下发现都
不是这么回事。第一，const_cast不
能改变被修改的变量的属性，就是说不能去掉i的const属性；第二，他说的方法也不
可行，我建立一个数组它－1项的地
址根本不是i，如果我强制让它指向i并修改，cout时i还是9。
这确实是个边边角角的钻牛角尖问题。不过我我还是很想知道答案，对compiler比较熟
悉的同学谁能给点hint？ |
|
s*z
发帖数: 37 | 7 wonder if this works...
void f() {
const int i=9;
cout << -1;
return
cout << i;
} |
|
h*********3
发帖数: 111 | 8 私下问了jerryju 大虾，大概弄明白了。照葫芦画瓢写了个c++版本的，
打印出最大长度和最大序列。
jerryju大虾别骂我抄袭啊。
void mit_LIS(int arr[],int len)
{
vector incIndex;
vector preIndex;
int index;
incIndex.push_back(0);
preIndex.push_back(-1);
for ( int i=1;i
{
if ( arr[i] >= arr[incIndex[incIndex.size()-1]] )
{
preIndex.push_back(incIndex[incIndex.size()-1]);
incIndex.push_back(i);
}
else
{
int l=0,r=incIn... 阅读全帖 |
|
y*******i
发帖数: 100 | 9 读入一系列 string 对象，直到同一
个单词连续出现两次，或者所有的单词都已读完，才结束读取
string preword,currword;
while(cin>>currword){
if(preword==currword){
cout<<"the word is: "<
break;
}//end if
else preword=currword;
}//end while
if(currword.empty()||(currword!=preword))
cout<<"there are no adjacent words are the same"<
有重复单词测试成功，但是如果输入一系列没重复单词的单词，总是打印不出"there
are no adjacent words are the same"，为什么呢？找了半天找不出逻辑错误。
谢谢各位。 |
|
o*******p
发帖数: 722 | 10 in C++:
#include
#include |
|
g******0
发帖数: 221 | 11 Start from the front and the back at the same time.
Back always decrease, front can increase or reset to 0.
O(n)
working code attached in c++.
===========================
#include
#include
using namespace std;
char* longestPalindromePrefix(char* str, int len)
{
bool flag = 0;
int front = 0;
int back = len-1;
// Find palindrome
while(front < back)
{
if (str[front] == str[back])
{
flag = 1;
front++;
back--;
}
else
{
fl... 阅读全帖 |
|
i**********e
发帖数: 1145 | 12 比较简单的解法是用一个二维矩阵，然后用 spiral 的方法把矩阵填满，最后一行一行
打印出来。
以下的解法不必要额外空间，给行数和列数就可以马上返回矩阵里的值。
int getVal(int row, int col, int n) {
if (row <= col) {
int k = min(row, n-1-col);
int start = 1 + 4*k*(n- k);
return start + (row - k) + (col - k);
} else {
int k = min(n-1-row, col);
int start = 1 + (n-1)*(2+4*k) - 4*k*k;
return start + (n-1-row-k) + (n-1-col-k);
}
}
void printMatrix(int n) {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
cout << getVal(r, c,... 阅读全帖 |
|
i**********e
发帖数: 1145 | 13 这是用矩阵来储存，利用 spiral 的形式填满矩阵，最后再一行一行打印。
感觉面试时利用这方法比较直观，不容易出错。
#include
#include
using namespace std;
const int N_MAX = 100;
void fill(int row, int col, int dx, int dy, int startVal, int numToFill, int
mat[][N_MAX]) {
int currVal = startVal;
int endVal = startVal + numToFill - 1;
for (int r = row, c = col; currVal <= endVal; r += dy, c += dx) {
mat[r][c] = currVal;
currVal++;
}
}
void generateMatrix(int n, int mat[][N_MAX]) {
if (n <= 0) return;
int row = ... 阅读全帖 |
|
c******t
发帖数: 1500 | 14 I wrote this last night. Any comment is welcome!
#include
#include
using namespace std;
const int N_MAX = 100;
void fill_in(int row, int size, int start_val, int** mat)
{
int start_col = row;
if (size == 1)
{
mat[row][start_col] = start_val;
return;
}
// top left to top right.
int size_of_square = (size - row * 2);
for (int i = start_col; i < row + size_of_square; ++i)
{
mat[row][i] = start_val;
++start_val;
... 阅读全帖 |
|
x********o
发帖数: 519 | 15 here is the C++ code:
#include
#include
#include
using namespace std;
void print_vector(const vector &v){
vector::const_iterator iter=v.begin();
while(iter!=v.end()){
cout<<*iter<<" ";
++iter;
}
cout<
}
void subset(vector v, vector sub, int size,set > &s){
if(sub.size()==size){
sort(sub.begin(),sub.end());
s.insert(sub);
return;
}
vector::iterator iter=v.begin();
size_t l=v.size();
for(int ... 阅读全帖 |
|
d*******l
发帖数: 338 | 16 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
ru... 阅读全帖 |
|
g*****k
发帖数: 623 | 17 Why you people like to decrement m instead of incrementing m?
By increment, you can get rid of push_back and erase, if you reserve size m
for subset.
Thus you can access subset[m] each time and don't need to erase elements.
题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_bac... 阅读全帖 |
|
w****x
发帖数: 2483 | 18 void MarkMap(const char* szStrs[], int n, int nBegIndex, bool chrMap[26][26])
{
assert(szStrs && nBegIndex >= 0 && n >= 0);
if (n <= 1) return;
int nDiv = -1;
for (int i = 0; i < n-1; i++)
{
char tmp1 = *(szStrs[i] + nBegIndex);
char tmp2 = *(szStrs[i+1] + nBegIndex);
assert(((tmp1 >= 'a' && tmp1 <= 'z') || tmp1 == 0));
assert(((tmp2 >= 'a' && tmp2 <= 'z') || tmp2 == 0));
if (tmp1 != 0 && nDiv < 0)
nDiv = i;
if (tmp1... 阅读全帖 |
|
f********3
发帖数: 210 | 19 我也是新人，呵呵。不过刚好做过这道题。
有包子没？=D
#include
using namespace std;
using std::string;
char *reverseEachword(char *src, int len)
{
char *p = src, *q = src + len - 1;
char tmp;
while(p < q)
{
tmp = *p;
//src[0] = 'z';
*p = *q; // why this step is wrong?
*q = tmp;
p++;
q--;
}
return src;
}
char *reverseWholeStr(char *srcstr, int len)
{
char *p = srcstr, *q;
int count;
while(*p != '\0')
{
count = 0;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 我写的代码如下。
这样打印出来的所有路线还真不是一般的多，
我在想题目的原意是不是指只要路线有相交就不允许？
例如：
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... 阅读全帖 |
|
i**********e
发帖数: 1145 | 21 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 22 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
d*******d
发帖数: 2050 | 23 didn't see the code you guys posted, maybe you guys already covered my
method.
bool compare_string(const string & str1, const string & str2){
int length1 = str1.length();
int length2 = str2.length();
int max = length1 > length2 ? length1 : length2;
int i1 = 0, i2 = 0;
int i=0;
while(i
if( str1[i1] > str2[i2] )
return true;
else if( str1[i1] < str2[i2])
return false;
else{
i1++;
if( i1>=length1){
i1 = i1 - length1;
}
i2++;
... 阅读全帖 |
|
s*******d
发帖数: 4135 | 24 扔一块砖
/*
Given an array of elements find the largest possible number that can
be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100
*/
#include
#include
#include
#include
using namespace std;
bool compare(int a, int b)
{
stringstream ss;
ss << a;
string as = ss.str();
ss << b;
string bs = ss.str();
int i = 0;
int as_len = as.length();
int bs_len = bs.length();
while (... 阅读全帖 |
|
s*******d
发帖数: 4135 | 25 多谢指出错误。。。还是要多检查啊。
/*
Given an array of elements find the largest possible number that can
be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100
*/
#include
#include
#include
#include
using namespace std;
bool compare(int a, int b)
{
stringstream ss,ss1;
ss << a;
string as = ss.str();
ss1 << b;
string bs = ss1.str();
int i = 0;
int as_len = as.length();
int bs_len = bs.length... 阅读全帖 |
|
d**e
发帖数: 6098 | 26 你发现有什么错?感觉没什么错误.
但如果说以整个code来看,其实后面两个return是多余的,可删去,另外print的message
有bug,head是空就说是empty list,但因为用了递归,head->next为null时,不代表它是
empty list
手痒写了个,但没验证...
void reversePrint(Node * head){
if(!head){
cout << "the end ..." << endl; // print some message here if needed...
return;
}
reversePrint(head->next);
cout << head->data << endl;
} |
|
s*****y
发帖数: 897 | 27 http://zebozhuang.blog.163.com/blog/static/17147980420112710523
在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组
数据的全排列.但是怎么用,原理如何,我做了简单的剖析.
首先查看stl中相关信息.
函数原型:
template
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
两个重载函数,第... 阅读全帖 |
|
s*****y
发帖数: 897 | 28 http://zebozhuang.blog.163.com/blog/static/17147980420112710523
在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组
数据的全排列.但是怎么用,原理如何,我做了简单的剖析.
首先查看stl中相关信息.
函数原型:
template
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
两个重载函数,第... 阅读全帖 |
|
z**z
发帖数: 222 | 29 queue for 1 question
YANGHUI(int n) {
1. Queue q; q.makeempty();
2. q.enqueue(1);q.enqueue(1);
3. int s = 0;
4. for(i=1;i<=n; i++) {
5. cout << endl;
6. q.enqueue(0);
7. for(int j = 1; j<=i+2; j++) {
8. int t = q.dequeue();
9. q.enqueue(s+t);
10. s = t;
11. if(j!=i+2) cout << s << " ";
}
}
} |
|
s*****y
发帖数: 897 | 30 You sure this works?
My code, generate up to level 10. Verify on Visual Studio:
int p1[20];
memset(p1, 0, 20*4);
p1[0] = 1;
for(int i=0; i<10; i++) {
int next = 0;
int prev = 0;
for (int j = 0; j < i+1; j++) {
if (j == 0) {
p1[j] = 1;
prev = 1;
} else if (j == i) {
p1[j] = 1;
} else {
next = p1[j];
p1[j] += prev;
prev = next;
}
cout << p1[j] << " ";
}
cout << endl;
}
result:
1... 阅读全帖 |
|
i**********e
发帖数: 1145 | 31 利用 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 | 32 LZ，32 的 super cool 应该是 32 才对吧？
因为 32 = 2^5.
刚写了一个程序，利用 binary search 的思路.
首先选定一个 upper bound，也就是 ceiling(log(n)).
然后再 i=2 到 upper bound 每一个做 binary search.
例如，n=32，upper bound = log(32) = 5.
i=2，从 low = 1 到 high = ceiling(n^(1/2))
i=3, 从 low = 1 到 high = ceiling(n^1/3))
..
以此类推...
binary search 的 invariant 就是比较 target 和 middle and middle's next，看哪
一个比较近。如果是离 middle 比较近，那就 middle's next 和它上边的值都可以抛
掉了。相反，那就 middle 和它下边的值就可以抛掉。
这里，我们确保 middle's next 不会大于 high。这个条件可以保证，因为取的是
lower middle = (L+H)/2.
... 阅读全帖 |
|
a**********2
发帖数: 340 | 33 没有仔细验证
typedef pair PAIR;
void getCountArray(vector input)
{
int len = input.size();
vector count(len, 0);
vector input1;
int i;
for( i = 0; i < len; i++)
input1.push_back(PAIR(input[i],i));
vector tmp( len, PAIR(0,0));
MergeSort(input1, 0, len-1, tmp, count);
for( i = 0; i < len; i++)
cout << count[i] ;
cout << endl;
}
void Merge(vector& input, int low, int mid, int high,vector&
tmp
, vector& co... 阅读全帖 |
|
s*****y
发帖数: 897 | 34 来自主题: JobHunting版 - 问个编程题 #include
#include
#include
#include
using namespace std;
vector FindSet(int target, const vector &input)
{
vector rtn;
int dp[10][100]; //dp table to save the result
bool used[10][100];
for (int i = 0; i <= target; i++) {
dp[0][i] = 0;
if (i <= 1) {
dp[1][i] = i;
used[1][i] = true;
} else {
dp[1][i] = INT_MAX;
used[1][i] = false;
}
}
for ... 阅读全帖 |
|
d*******l
发帖数: 338 | 35 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include |
|
b******c
发帖数: 70 | 36 #include
#include |
|
g*****k
发帖数: 623 | 37 似乎不对，
举个例子吧，假设有2个区段，[m..i], [i+2..j]
并且下一步处理 i+1和j-1
处理i+1将使得ht[m]=ht[j]=j-m+1
但是处理j-1的时候，假设ht[j-2]=t(some old value)
之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
束。
#include
#include |
|
d*******l
发帖数: 338 | 38 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include |
|
b******c
发帖数: 70 | 39 #include
#include |
|
g*****k
发帖数: 623 | 40 似乎不对，
举个例子吧，假设有2个区段，[m..i], [i+2..j]
并且下一步处理 i+1和j-1
处理i+1将使得ht[m]=ht[j]=j-m+1
但是处理j-1的时候，假设ht[j-2]=t(some old value)
之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
束。
#include
#include |
|
m******e
发帖数: 353 | 41 ok, my bad, keep track of range [0, neg) and [numNeg, pos), and do not
rearrange those (since they are already in the correct place)
use [neg, numNeg) and [pos, N) as circular buffer for un-processed elements
#include
#include
#include
using namespace std;
void print(const vector& input) {
for(size_t i = 0; i < input.size(); ++i) {
cout << input[i] << " ";
}
cout << endl;
}
int numNegatives(const vector& input) {
int cnt = 0;
... 阅读全帖 |
|
d*******d
发帖数: 2050 | 42 void path(int * a, int n){
int lastjump = 0;
int lastjumpreach = a[0];
int cur = 1;
int farest = a[0];
for( int i = 1; i
if( i+a[i] > farest && farest < n-1){
farest = i+ a[i];
cur = i;
}
if( i >= lastjumpreach ){
// finalize last jump
cout << lastjump << " ";
lastjump = cur;
lastjumreach = farest;
}
}
cout << n-1 << endl;
} |
|
s**********e
发帖数: 326 | 43 我来贴个general的code
void diagnalPattern(char* str, int rowNum){
int charNum = 0;
for(int i = 0; i < strlen(str); i++){
if(isValidChar(str[i])){
charNum++;
}
}
int colNum = (charNum + rowNum - 1) / rowNum;
char** arr;
arr = new char*[rowNum];
for(int i = 0; i < rowNum; i++)
arr[i] = new char[colNum];
for(int i = 0 ; i < rowNum; i++)
for(int j = 0; j < colNum; j++)
arr[i][j] = ' ';
int curPos = 0;
... 阅读全帖 |
|
P**********c
发帖数: 3417 | 44 跟你说的差不多。其实DFS也可以用recursion做哈。
void print_path(tree* root, vector& path){
if(!root)
return;
path.push_back(root);
if(!root->left_child && !root->right_child){
for(int i=0; i
cout<data<<" ";
cout<
}
else{
if(root->left_child)
print_path(root->left_child, path);
if(root->right_child)
print_path(root->right_child, path);
}
path.pop_back();
}
test tree:
3
1 5
0 ... 阅读全帖 |
|
f*****i
发帖数: 835 | 45 tried
const int a = 2;
const_cast(a) = 3;
if print out:
std::cout << a;
shows 2;
std::cout << const_cast(a);
shows 3;
why??
Thanks. |
|
S**I
发帖数: 15689 | 46 The result is undefined behavior. When a variable is declared const, the
compiler can store the variable anywhere it wants (may be read-only memory
location), when you cast away the constness of this variable and make
assignment, the compiler is forced to create a variable on the stack. So in
your example, a and const_cast(a) could be two different variables and
have different memory location.
If you run the following code, you can see the difference:
const int a = 2;
int b = &cons... 阅读全帖 |
|
l*********y
发帖数: 142 | 47 顺手写了一个，46min整。也没用状态压缩，待会看一下gloomyturkey的code。
#include
#include
#include
#include
#include
#include
#include
|
|
c**********e
发帖数: 2007 | 48 Faint. I made such a low level mistake. Then what is the output of the
following code?
#include
using namespace std;
class A {
public:
bool equals(A a) { return data==a.data; }
void setData(int input) { data=input; }
private:
int data;
};
class B: public A {};
void main() {
A a;
a.setData(7);
B b;
b.setData(7);
cout << a.equals(b) << endl;
cout << b.equals(a) << endl;
} |
|
C***y
发帖数: 2546 | 49 有没有办法强制基类中定义的pure virtual function在所有的继承类中实现
For example:
class A
{
public:
virtual void func() = 0;
};
class B: public A
{
public:
void func() { std::cout<<"In B"<
};
class C: public B
{
public:
void func() { std::cout<<"In C"<
};
class C中也必须实现 func，否则报错 |
|
C***y
发帖数: 2546 | 50 有没有办法强制基类中定义的pure virtual function在所有的继承类中实现
For example:
class A
{
public:
virtual void func() = 0;
};
class B: public A
{
public:
void func() { std::cout<<"In B"<
};
class C: public B
{
public:
void func() { std::cout<<"In C"<
};
class C中也必须实现 func，否则报错 |
|
