s******c
发帖数: 1920 | 1 任意取两点，计算斜率和截距，能得到一条直线，然后把其他落在这条直线上的点也打
印出来。用一个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 | 2 最近Amazon面试好像喜欢问LRU (least recently used cache)的设计
我用doubly-linked list 和 hashtable 实现了一个简单的LRU, 抛砖引玉，供大家做
参考。祝大家都顺利拿到offer.
using System;
using System.Collections.Generic;
namespace LRU
{
public class Cache
{
public class Container
{
public Object obj;
public Container next;
public Container prev;
public Container(object o)
{
this.obj = o;
}
}
private const int MaxSize ... 阅读全帖 |
|
j***y
发帖数: 2074 | 3 从网上抄了一段源代码：
－－－
#include
#include |
|
l*********y
发帖数: 142 | 4 #include
#include
#include
using namespace std;
int square[1000000];
int result[1000000];
int main()
{
int M = 1000000;
int limit = sqrt(M);
fill_n(result, 1000000, numeric_limits::max());
for (int i = 0; i <= limit; i++) {
square[i] = i * i;
result[i*i] = 1;
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= limit; j++) {
if (i - square[j] >= 0) {
result[i] = min(result[i], result[i-... 阅读全帖 |
|
l*********y
发帖数: 142 | 5 #include
#include
using namespace std;
int square[1000000];
int best = 4;
int result[4];
void RecurSearch(int count, int target, int start)
{
count ++;
if (count > best) return;
for (int i = start; i >= 1; i --) {
int value = target - square[i];
if (value < 0) continue;
if (square[i] < (target / (best - count))) continue;
result[count - 1] = square[i];
if (value == 0) {
if (count <= best) {
best =... 阅读全帖 |
|
l*******e
发帖数: 309 | 6 #include
#include |
|
b*****n
发帖数: 482 | 7 How to check the top 2 objects? It seem we can only look at the top
object.
Another question is we have to check N-1 chars from the top of the
stack, where N is the length of the str2. If there are multiple
characters in str2 that are the same as its last char (e.g. accccbc),
then even if str1 is the same as string 2, we have to do extra check 4
times whenever we meet a 'c' in str1.
My idea is to have a companion array recording the maximum matched index
of the char sequence in str1. If there is... 阅读全帖 |
|
h*****g
发帖数: 944 | 8 g++总是说我的14行有错，为啥？
1 #include
2 #include
3 #include
4 #include
5
6 using namespace std;
7 int main(){
8 int numbers [] ={20, -30, 10, 40, 0};
9 vector five (numbers, numbers+5);
10 int cx = count_if(numbers, numbers+5, bind1st(greater_equal(),
15));
11 cout<<"There are "<
12 int dx = count_if(numbers, numbers+5, bind2nd(greater_equal(),
15));
13 c... 阅读全帖 |
|
o*******p
发帖数: 722 | 9 in C++:
#include
#include |
|
r******r
发帖数: 700 | 10 我当年的 homework,翻出来了。另一个 homework project, 帮我找到了第一个工作。
#ifndef LIST_H
#define LIST_H
#include
#include
#include
#include "node.h"
using namespace std;
/*=========================================================================*/
/**
* Implementation of a List ADT using a doubly-linked list.
*
* @version 1.0 2/25/05
*/
/*.........................................................................*/
/**
* Definition of exception handling class
*/
class ListEmpty : public ... 阅读全帖 |
|
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 的形式填满矩阵，最后再一行一行打印。
感觉面试时利用这方法比较直观，不容易出错。
#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 | 13 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;
... 阅读全帖 |
|
E*******0
发帖数: 465 | 14 我用C#写的
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace PrintMatrixCsharp
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int[,] A=GetMatrix(Convert.ToInt16(input.Text));
PrintMatrix... 阅读全帖 |
|
l**********3
发帖数: 161 | 15 贴个简单点的，但是比较长 。。。
==============
#include
#include
#include
#include
using namespace std;
enum direct_t { RIGHT, DOWN, LEFT, UP };
void print_spiral_matrix(int dimX, int dimY)
{
int** matrix = new int*[dimX];
for (int i=0; i
{
matrix[i] = new int[dimY];
memset(matrix[i], 0, sizeof(int)*dimY);
}
int num = 1;
direct_t dir = RIGHT;
int i, j;
for (i=j=0; num <= dimX*dimY; ++num)
{
ma... 阅读全帖 |
|
h*****g
发帖数: 944 | 16 执行的时候总说segmentation fault,
谢谢大家指点
===================================
#include
using namespace std;
template< class T>
class ListNode{
public:
T data;
ListNode(T v);
ListNode< T > *next;
};
template ListNode < T >::ListNode(T v)
{
}
template
class LinkedList{
ListNode *head;
public:
LinkedList(){}
~LinkedList(){
while(head){
ListNode* next = head->next;
delete head;
... 阅读全帖 |
|
h*****g
发帖数: 944 | 17 谢谢大家指点，compile有warning, 执行起来segmentation fault
#include
using namespace std;
void reverse (char *str);
int main(){
char * str = "hello";
reverse(str);
cout<
}
void reverse(char *str){
char * end = str;
char tmp;
if(str){
while(*end){
++end;
}
--end;
while(str
tmp = *str;
*str++=*end;
*end--=tmp;
}//end while
}
} |
|
c******t
发帖数: 1500 | 18 我改了一点你的程序，刚在VS 2008下编译通过了
#include
using namespace std;
void reverse (char *str);
int main(){
char str[] = "hello";
reverse(str);
cout<
}
void reverse(char *str){
char* begin = str;
char* end = str;
char tmp;
if(str)
{
while(*end)
++end;
--end;
while(begin
{
tmp = *begin;
*begin = *end;
*end=tmp;
++begin;
--end;
}
}
... 阅读全帖 |
|
h*****g
发帖数: 944 | 19 谢谢大家帮我看看，我实在不知道为啥错了
#include
using namespace std;
template< class T>class TreeNode{
public:
T data;
TreeNode(T v);
TreeNode *left;
TreeNode *right;
friend ostream &operator<<(ostream &stream, TreeNode &o);
};
template TreeNode ::TreeNode(T v)
:data(v), left(NULL), right(NULL)
{
}
template ostream &operator<<(ostream &stream, TreeNode &o){
stream<data<<" ";
}
int main(){
TreeNode * head = n... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 I think you need to do DFS from all possible starting points in the grid, not just the top left point.
My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
#include
#include
using namespace std;
const int MAX_ROWS = 100;
const int MAX_COLS = 100;
bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
int charIndex, string target, bool visited[][MAX_COLS]) {
if (ro... 阅读全帖 |
|
x********o
发帖数: 519 | 21 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 ... 阅读全帖 |
|
f********3
发帖数: 210 | 22 我也是新人，呵呵。不过刚好做过这道题。
有包子没？=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;
... 阅读全帖 |
|
d*******l
发帖数: 338 | 23 来自主题: JobHunting版 - 问个面试题 #include
using namespace std;
int f[110];
int p[50];
int cur = 1;
int ans;
void solve(int n, int m, int s)
{
if(m == 0) {
/* for(int i = 0; i < cur; i++)
cout << p[i]+1 << " ";
cout << endl;
*/ ans += n-1-p[cur-1];
return ;
}
for(int i = s; i < n; i++) {
if(!f[i]) {
p[cur++] = i;
for(int j = cur-1; j >= 0; j--)
if(2*i-p[j] < n)
f[2*i-p[j]]++;
solve(n, m... 阅读全帖 |
|
f*****y
发帖数: 444 | 24 #include
using namespace std;
template class complex {
public:
complex(T re, T im) { re = re, im=im ;};
void print(){cout<
private:
T re,im;
};
int main()
{
complex(2,3).print();
complex c = complex(3,4);
c.print();
} |
|
f*****y
发帖数: 444 | 25 #include
using namespace std;
template class complex {
public:
complex(T re, T im) { re = re, im=im ;};
void print(){cout<
private:
T re,im;
};
int main()
{
complex(2,3).print();
complex c = complex(3,4);
c.print();
} |
|
a******r
发帖数: 9 | 26 就是想转换helloWorlD这个字符串全部为大写，并打印。可是以下程序，打印出来的字
符串次数不对。新手上路，不知道怎么改比较好，求指点，多谢
#include
#include
#include
#include
using namespace std;
int main()
{
string str("helloWorlD");
vector svec;
for (string::size_type i=0; i
{
svec.push_back(str);
}
for (vector :: size_type ix=0; ix
{
for (string::size_type index=0; index
{
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 27 我写的代码如下。
这样打印出来的所有路线还真不是一般的多，
我在想题目的原意是不是指只要路线有相交就不允许？
例如：
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 | 28 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 ... 阅读全帖 |
|
s*****y
发帖数: 897 | 29 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
i**********e
发帖数: 1145 | 30 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 ... 阅读全帖 |
|
s*****y
发帖数: 897 | 31 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
w*******s
发帖数: 138 | 32 can be done in O(log 10 N), where N is the largest input number:
#include
#include
#include
using namespace std;
int x[16][128];
int heavy(int n) {
vector d;
while (n) {
d.push_back(n % 10);
n /= 10;
}
int results = 0;
for (int i = 1; i < d.size(); ++i) {
results += x[i][i * 7 + 1] - x[i - 1][i * 7 + 1];
}
int m = d.size() * 7 + 1;
for (int i = d.size() - 1; i >= 0; --i) {
int s = 0;
if (i == d.size() - 1) {
s = 1;
... 阅读全帖 |
|
s*****y
发帖数: 897 | 33 写了一个基于tree的，插入的原则是
1.比较最高位的digit，大的插入右边，小于或者等于的插入左边
2.如果最高位相等，比较combine 2个数的结果，哪个大决定插入左边或者右边
所有node都插入到树的最低层。
建完tree后，traverse tree按照right, current left的顺序，测了一下案例，似乎是
对的，
//int A[] = {2, 3, 5, 78 }; //pass
//int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {3,3,43}; //pass
int A[] = {9, 98, 987, 902, 399, 380}; //pass
//int A[] = {900, 9001, 2}; //pass
// int A[] = {2, 3, 89,94, 899 }; //pass
// int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {2, 3, 5... 阅读全帖 |
|
s*******d
发帖数: 4135 | 34 扔一块砖
/*
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 | 35 多谢指出错误。。。还是要多检查啊。
/*
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... 阅读全帖 |
|
r******n
发帖数: 170 | 36 看来楼主跟我面到一起去了，我这题当时也没答出来，事后写的：
//output dnum dices permutation as a string
#include
#include
using namespace std;
void throwDice(int dnum, string out_str, int level)
{
if (level == dnum)
{
cout<
return;
}
for (int i=1; i<7;i++)
{
out_str+=(char)(i+'0');
throwDice(dnum,out_str, level+1);
out_str.resize(out_str.size()-1);
}
}
int main()
{
string out_str;
throwDice(6, out_str, 0);
return... 阅读全帖 |
|
j*******r
发帖数: 52 | 37 试贴一个C++代码，循环+递归，用一个bitset代表当前字符是否已经在之前位置被使用。
1 #include
2 #include
3 #include
4
5 using namespace std;
6
7 void permutation(const char* str, bitset<4> used, string r){
8 if(r.size() == strlen(str)){
9 cout<
10 }
11 for(int i = 0; i < strlen(str); ++i){
12 if(used[i])
13 continue;
14 used.set(i);
15 r += str[i];
16 permutation(str, used, r);
17... 阅读全帖 |
|
j*******r
发帖数: 52 | 38 试贴一个C++代码，循环+递归，用一个bitset代表当前字符是否已经在之前位置被使用。
1 #include
2 #include
3 #include
4
5 using namespace std;
6
7 void permutation(const char* str, bitset<4> used, string r){
8 if(r.size() == strlen(str)){
9 cout<
10 }
11 for(int i = 0; i < strlen(str); ++i){
12 if(used[i])
13 continue;
14 used.set(i);
15 r += str[i];
16 permutation(str, used, r);
17... 阅读全帖 |
|
i**********e
发帖数: 1145 | 39 我写的 boggle 游戏算法，DFS + trie.
一秒以内给出所有 5x5 的答案。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Trie {
bool end;
Trie *children[26];
Trie() {
end = false;
memset(children, NULL, sizeof(children));
}
void insert(const char *word) {
const char *s = word;
Trie *p = this;
while (*s) {
int j = *s-'A';
assert(0 <= j && j < 26);
if (!p->childre... 阅读全帖 |
|
h*****g
发帖数: 312 | 40 zz:
原文：
http://blog.csdn.net/njnu_mjn/archive/2010/04/04/5449098.aspx
八皇后问题(C++) 收藏
1 、问题描述： 在一个8*8 的棋盘上放置8 个皇后，不允许任何两个皇后在棋盘的同
一行、同一列和同一对角线上。
2 、关键字： 递归、上溯
3 、技巧：
1 ）、
经观察发现，对8 x 8 的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7 的值（范围在(0,14) ）均相等；
其从对角线（即右上至左下）上的每个点的i+j 的值（范围在(0,14) ）均相等；
且每个主对角线之间的i-j+7 的值均不同，每个从对角线之间的i-j+7 的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15] 分别表示主、从对角线是否安全
（为1 表示有皇后，不安全；为0 表示安全）
2 ）、
每行有且仅有一个皇后：
每i 个皇后放在每i 行(0<=i<=7)
void eightQueens( int line );
4 、源码（... 阅读全帖 |
|
s*****y
发帖数: 897 | 41 来自主题: 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 ... 阅读全帖 |
|
e***s
发帖数: 799 | 42 来自主题: JobHunting版 - 问个编程题 #include
#include
#include
#include
#include
using namespace std;
vector FindSet(unsigned int sum, vector &coinset)
{
vector rtn;
int *Min = new int[sum + 1];
vector *Combination = new vector[sum + 1];
Min[0] = 0;
unsigned int i;
unsigned int j;
for(i = 1; i <= sum; i++)
{
Min[i] = INT_MAX;
}
for(i = 1; i <= sum; i++)
{
for(j = 0; j < co... 阅读全帖 |
|
d*******l
发帖数: 338 | 43 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include |
|
b******c
发帖数: 70 | 44 #include
#include |
|
g*****k
发帖数: 623 | 45 似乎不对，
举个例子吧，假设有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 | 46 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include |
|
b******c
发帖数: 70 | 47 #include
#include |
|
g*****k
发帖数: 623 | 48 似乎不对，
举个例子吧，假设有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 |
|
f*******t
发帖数: 7549 | 49 把map当作hashmap用，可处理重复的数字
#include |
|
z**********n
发帖数: 3 | 50 #include
#include
using namespace std;
class Matrix
{
public:
Matrix(int r, int c)
{
pData = new int[r * c];
_rowNum = r;
_colNum = c;
}
// TODO pData is a pointer, so deep copy struct is needed
// TODO write copy structor and assign operateo
//Matrix(Matrix& m)
//{
//}
//Matrix& operator = (Matrix& m)
//{
//}
void SetNum(int r, int c, int num)
{
pData[r * _colNum + c] = num;
}
const i... 阅读全帖 |
|
