s*****y 发帖数: 897 | 1 看了各位大牛的实现后,写了个O(nlgk)的C实现
#include
#include
//assume input array size < 20
#define ARRAY_SIZE 20
/*P[k] —stores the position of the
predecessor of X[k] in the longest increasing subsequence ending at X[k].*/
static int P[ARRAY_SIZE];
/*M[j] stores the position k of the smallest value X[k]
such that there is an increasing subsequence of length j ending
at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here)*/
static int M[ARRAY_SIZE];
void Find_Lis(int input[], int size, int... 阅读全帖 |
|
s*****y 发帖数: 897 | 2 仿照大牛的写了个C的
static int array[] = { 2, 4, 1, 9 };
//static int array[] = {-1, 4 , 2, 1, 9 , 10 };
int _tmain(int argc, _TCHAR* argv[])
{
int i;
int tmp;
int size = sizeof(array)/sizeof(int);
for (i = 0; i < size; ) {
if ((array[i] <= 0) || (array[i] > size)|| (array[i] == i+1)) {
i++;
continue;
}
/*switch array[i] and array[array[i]-1]*/
tmp = array[array[i]-1];
array[array[i]-1] = array[i];
array[i]... 阅读全帖 |
|
o****d 发帖数: 2835 | 3 来自主题: JobHunting版 - 问个面试题 C程序
思路如上面的朋友所说
=======
#include
#include
void setMatrix (int ** matrix, int x, int y, int n, int start)
{
int i,j;
if(n==0)return;
else if(n==1) matrix[x][y]=start;
else{
for(j=y;j
matrix[x][j]=start++;
for(i=x;i
matrix[i][y+n-1]=start++;
for(j=y+n-1;j>y;j--)
matrix[x+n-1][j]=start++;
for... 阅读全帖 |
|
i**********e 发帖数: 1145 | 4 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... 阅读全帖 |
|
w****x 发帖数: 2483 | 5 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****4 发帖数: 1359 | 6 没测试过,假设node value是int
该函数不能处理:所有lists都是循环list
#define MININTEGER -32767
typedef struct Node
{
int value;
Node *next;
} Node;
void KListInte(Node ** klists)
{
if (klists == NULL) return;
int currentMax = MININTEGER;
int k = sizeof(klists) / sizeof(Node **);
while (1)
{
for (int i = 0; i < k; i++)
{
if (klists[i] == NULL) return;
if (klists[i]->value > currentMax)
currentMax = klists[i]->value;
}
for (int i = 0; i < k; i++)
{
while (klists[i]... 阅读全帖 |
|
i**********e 发帖数: 1145 | 7 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 | 8 写了好几个小时,终于用差不多brute force得解了,算了1337的几个例子,全部都一
样,但是我是算好了一个result,就return了,其他的就不算了。
速度还行,1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试,真的是算了10分钟还没有好,难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
i**********e 发帖数: 1145 | 9 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 | 10 写了好几个小时,终于用差不多brute force得解了,算了1337的几个例子,全部都一
样,但是我是算好了一个result,就return了,其他的就不算了。
速度还行,1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试,真的是算了10分钟还没有好,难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
s*****y 发帖数: 897 | 11 写了一个基于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*****y 发帖数: 897 | 12 int smallest = INT_MAX;
int second_smallest = INT_MAX;
for (int i = 0; i < sizeof(input)/sizeof(int);i++) {
if (second_smallest < input[i]) {
if (smallest < input[i]) {
second_smallest = smallest ;
smallest = input[i];
} else {
second_smallest = input[i];
}
}
}
return second_smallest; |
|
s*****y 发帖数: 897 | 13 来自主题: 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 | 14 来自主题: 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... 阅读全帖 |
|
b******c 发帖数: 70 | 15 #include
#include |
|
g*****k 发帖数: 623 | 16 似乎不对,
举个例子吧,假设有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 |
|
b******c 发帖数: 70 | 17 #include
#include |
|
g*****k 发帖数: 623 | 18 似乎不对,
举个例子吧,假设有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 | 19 把map当作hashmap用,可处理重复的数字
#include |
|
d*******l 发帖数: 338 | 20 我不敢说完全明白,但有点感觉,谈谈我得想法。
就像上面说的,为了保证能返回一个对齐的地址且有足够的空间,需要打出一些富裕。
多少富裕足够呢?就是代码里的offset。我记得在OS课上老师提到过这种做法,好像叫
container,就是比实际需要多分配空间,把中间开始的某个地址返回,前面的地方存
放些信息。
下面说说offset怎么来的。假设我们用malloc分配了一段空间,起始地址是p1。此时我
们想得到一个对齐的地址,最直接的做法就是& ~(alignment-1),这样低位清0,结果
就是对齐的。但这样做的结果相当于把原地址减去了一个[0, alignment-1]的数,也就
是低位被减掉了。得到的新地址的开始的一部分就是未分配的。代码中对p2进行这个操
作,得到的结果是p2=p1+offset-x,x就是在对齐过程中被减掉的数,可以看出p2>=p1+
1,这就保证了对齐之后的地址也是分配过的。
再说说p2[-1]=p1的作用。上面说的container方法有一个需要注意的就是free的时候,
如果直接free alloc返回的那个地址,其实是有问题的,因为那个是最初分配空间的中
... 阅读全帖 |
|
b***r 发帖数: 4186 | 21 扫两边?
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
if(input[i]<0) //want to move this number to the front.
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i阅读全帖 |
|
b***r 发帖数: 4186 | 22 扫两边?
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
if(input[i]<0) //want to move this number to the front.
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i阅读全帖 |
|
a***r 发帖数: 93 | 23 My solution is about the same as bitwise, it uses an array:
#include
#include
void add_range(int D[], int l, int a, int b) {
if(b
for (int i=a; i<=b; i++) {
D[i%l]+=1;
}
}
bool is_overlap_array(int a,int b,int c,int d) {
int D[7]= {};
int l=sizeof(D)/sizeof(D[0]);
add_range(D,l,a,b);
add_range(D,l,c,d);
for (int i=0; i
if (D[i]>1) { return true; }
}
return false;
}
void main(int argc, const char *... 阅读全帖 |
|
c**********e 发帖数: 2007 | 24 C++ Q93: formal parameter T
What is the purpose of declaring the formal parameter T?
A. T specifies that any data sent to the function template must be of type T
B. T is a place-holder for a C++ data type
C. T can only hold a single data type int
D. T can hold any language data type
C++ Q94: Pointer
Multiple choices: Identify the true statements about the use of pointers in
C++.
A. A pointer is a variable that can contain the memory address of another
variable as its value
B. Although not necess... 阅读全帖 |
|
c**********e 发帖数: 2007 | 25 Q95 Answer: A and D.
C++ Q95: Files and Streams
Multiple choice: Which of the following statements are true about writing an
integer to a file?
A. The write() function must know the exact location of the integer and the
address operator (&) enables it to locate it
B. The write() function must know the size of the integer and the address
operator (&) returns the amount of storage needed for it
C. The write() function must know the exact location of the integer and the
sizeof operator enables it ... 阅读全帖 |
|
z****u 发帖数: 104 | 26 C version,求指正
int NextNumber(int i)
{
int max_length = 1;
int* digits = (int*) malloc(sizeof(int) * max_length);
/* break number down to digits */
int idx = 0;
while(i)
{
if (idx > max_length - 1)
{
max_length *= 2;
digits = (int*) realloc(digits, sizeof(int) * max_length);
}
digits[idx++] = i % 10;
i /= 10;
}
int length = idx;
/* find the break digit */
for (idx = 1; idx < length; idx++)
... 阅读全帖 |
|
r******n 发帖数: 170 | 27 贴个tree的版本,不过空string对应空tree的时候,似乎空指针处理的有些ugly,求更
简洁版本。
struct BNode
{
char c;
BNode* left;
BNode* right;
BNode():c(0){}; //avoid uninitialized value for c
BNode(char _c):c(_c),left(NULL),right(NULL){};
};
void pre2bst(string pre, size_t& start, size_t len, BNode* &p)
{
if(start
{
p=new BNode(pre[start]);
size_t curr=start;
start++;
if(pre[curr]=='+'||pre[curr]=='-'||pre[curr]=='*'||pre[curr]=='/')
{
pre2bst(pre,s... 阅读全帖 |
|
k***t 发帖数: 276 | 28 来自主题: JobHunting版 - 问个算法题 也来凑个热闹。主要是练练trie。
花了些时间才调通:( 谁帮忙给Review一下?谢了。
运行结果:
ad: 5
bc: 3
bb: 2
aaa: 1
aa: 1
源码:
#include
#include
using namespace std;
struct Node {
int cnt;
char c;
struct Node *n[26];
char *p; // to the 1st occurrence in the original input string
};
#define idx(x) (x-'a')
void add2trie (Node *r, char *p1, char *p2) {
char *p; Node *cur=r; Node *n;
p=p1;
cur=r;
while (p!=p2 && cur->n[idx(*p)]) {cur=cur->n[idx(*p)]; ++p;}
if (p==p2) { cur->cnt++;... 阅读全帖 |
|
k***t 发帖数: 276 | 29 以前看见一个版上大拿做的一个O(N)的find/union。不过那个是找
最长连续子序列,所以并集时只需更新边界元素,且并集操作只会
在边界发生。动态更新最长序列,只需扫描一遍即可。
下面是原贴。不知可否借鉴得上?
发信人: battlesc (zerg), 信区: JobHunting
标 题: Re: G题讨论
发信站: BBS 未名空间站 (Fri Jul 15 11:37:33 2011, 美东)
#include
#include |
|
r***h 发帖数: 70 | 30 在看Programming interview exposed
不太明白里面讲link list插入新head的程序的例子.给出2个例子,书上说第一个是错的
,第二个才对.不明白为什么必须用**head而不是*head,难道head本身做为pointer pass
给函数不改变指针的内容吗? 请帮忙讲解一下,谢谢!
For example, the following code is incorrect because it fails to update the
head pointer in the calling function:
int BadInsert(element *head)
{
element *newElem;
newElem = (element *) malloc(sizeof(element));
if (!newElem) return 0;
newElem->next = head;
head = newElem;
return 1;
}
The correct way to update the head pointer in C is to pas... 阅读全帖 |
|
c****p 发帖数: 6474 | 31 #include
#include
int C(int m, int n)
{
int *A, *B;
int tmp;
int i, j, k;
if((m <=0 ) || (n <=0 ))
return -1;
if(n == 1)
return m;
if(n == m)
return 1;
if(m - n < n)
n = m - n;
A = malloc(n*sizeof(int)); // A = {m, m - 1, .... m - n + 1}
B = malloc((n-1)*sizeof(int)); // B = {2, 3, ... n}
for(i = 0; i
{
A[i] = m - i;
B[i] = i + 2;
}
A[n-1] = m - n + 1;
//i ... 阅读全帖 |
|
p*i 发帖数: 411 | 32 If you are on a 64bit environment and compiles the source code in 64bit mode
, the main function will output len = 5 (length of the C string) and the
RemoveDuplicate function will output len=8, which is exactly sizeof(char*)/
sizeof(char)
= |
|
S**I 发帖数: 15689 | 33 ☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.... 阅读全帖 |
|
s******n 发帖数: 3946 | 34 写了几遍才对。。。
#include
#define exchangenum(a,b) {a^=b;b^=a;a^=b;}
void print(int* a, int count, int sum, int* out, int outindex)
{
if (sum==0) {
for (int i=0; i
printf("\n");
return;
}
if (count==0) return;
out[outindex] = a[0];
print(a+1, count-1, sum-a[0], out, outindex+1);
print(a+1, count-1, sum, out, outindex);
}
int main(int argc, char** argv)
{
int a[5] = {1,3,4,2,6};
int sum = 7;
int out[5];
print(a, sizeof(a)/sizeof(a[0... 阅读全帖 |
|
s******n 发帖数: 3946 | 35 如果有1,3,3,4,5,3重复,则需要特别处理,2个连续的3,分别处理3,3,4... 3,4... ,4.... 三种情况,应该没比我这程序更简短的了吧。:)
#include
void print(int* a, int count, int sum, int* out, int outindex)
{
if (sum==0) {
for (int i=0; i
printf("\n");
return;
}
if (sum<0 || count==0) return;
int samea=1;
for (; samea
for (int k=0; k<=samea; k++) {
print(a+samea, count-samea, sum-a[0]*(k), out, outindex+k);
out[outindex+k] = ... 阅读全帖 |
|
a***y 发帖数: 50 | 36 俺写了一个, 没有测试过只有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* ... 阅读全帖 |
|
y****e 发帖数: 1012 | 37 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
为啥string vector太大的时候结果是错的呢?
大家帮忙看看吧~~
谢谢!
#include
#include
#include |
|
f*******t 发帖数: 7549 | 38 #include
#include
bool isSet(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
return bitarray[index] & (char)(1 << offset);
}
void set(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
bitarray[index] |= (char)(1 << offset);
}
void printMissingNum(int *array, int arraysize, int N)
{
int bitarraysize = (N + 7) / 8;
char *bitarray = (char*)calloc(bitarraysize, 1);
for(int i = 0; i < arraysize; ++i) {
... 阅读全帖 |
|
c**********e 发帖数: 2007 | 39 Is the answer sizeof(arr)/sizeof(int) if an integer array? |
|
C*O 发帖数: 389 | 40 对 。。。
不过
func(int* arr)
{
sizeof(arr)/sizeof(int) 返回是1,
} |
|
t****e 发帖数: 463 | 41 可以是 sizeof array/sizeof array[0] |
|
c**********e 发帖数: 2007 | 42 It does not work even it is not from a function.
For example,
int* arr=new int[10];
cout << sizeof(arr)/sizeof(arr[0]) << endl;
You will get 1.
You are right, size should be sent as a parameter. |
|
c**********e 发帖数: 2007 | 43 For array on stack, it works.
int arr[100];
cout << sizeof(arr)/sizeof(int) << endl;
You do get 100. Though I am not sure if it is system dependent. |
|
k***g 发帖数: 166 | 44 弱人路过,用的是楼上说的两个指针往中间走的办法
#include
using namespace std;
void find2sum(int a[], int size, int target)
{
if (size<2)
return;
for (int i=0, j=size-1; i
int sum = a[i]+a[j];
if (sum == target) {
cout<
i++; j--;
} else if (sum > target) {
j--;
} else if (sum < target) {
i++;
}
}
}
int main(int argc, char* argv[])
{
//int a[] = {1, 4, 5, 5, 5, 5, 6, 7, 8... 阅读全帖 |
|
n********k 发帖数: 40 | 45 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
语言啊。
1.NV总部。
>事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。
>题:讲讲你自己;讲讲这一个你做过的项目;你给我讲讲shared memory是什么,应该
怎么用;你给我讲讲atomic operation是什么,怎么用;你会什么语言,各个语言的自
信程度;C++里面的virtual function是什么,pure virtual function是什么;你用过
C++ S... 阅读全帖 |
|
r********g 发帖数: 1351 | 46 第一题记得是用两个list来记录正的最大值和负的最大值。但是corner case不是很清
楚:
比如:如果只有一个元素,是负数,那返回这个负数,还是返回0呢?(0的意思可以理
解成0个连续元素)。
int maxSubArray(int A[], int n) {
if(n == 0) return 0;
//init
int *minList = new int[n];
int *maxList = new int[n];
memset(minList, 0, sizeof(int)*n);
memset(maxList, 0, sizeof(int)*n);
int maxP = 0;
if(A[0] > 0) {
maxList[0] = A[0];
maxP = A[0];
}
else minList[0] = A[0];
//compute
for(int i = 1; i < n; i++){
if(A[i] == 0)... 阅读全帖 |
|
l****c 发帖数: 838 | 47 You should read in the string and parse.
You don't know how long the first part string is or how long the number is.
So if you define:
char tempprice[10];
char ticker[10];
You have the risk of buffer overflow.
Here is my solution. I debug it as I wrote it, so it is not optimized.
it is pure C. You can get result with 2 lines of perl or python code
============================
#include
#include
#include
int main()
{
char *str = "GOOD|89.34";
char *ptoken, *... 阅读全帖 |
|
l****c 发帖数: 782 | 48 换了DP,觉得和你第二页做的很像,应该是n^2了。
可过了小测试,过不了大测试啊。
您的那个代码也是只能过小测试。。。。。。
boolean isInterleave(string s, string s1, string s2)
{
if (s.length()!=(s1.length()+s2.length())) return false;
int l1 = s1.length()+1;
int l2 = s2.length()+1;
bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
for (int i = 0; i < l1; i++)
dpt[i] = (bool*)malloc(sizeof(bool)*l1);
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (i==0&&j==0)
dpt[i][j] = tr... 阅读全帖 |
|
c******t 发帖数: 391 | 49 今天面试码工职位,被问到了一道coding题,说有一个m x n的二维矩阵Item[][],每一
个元素都是一个Item类的object, 其中Item类定义如下:
public class Item{
public int x; //
public int y;
}
x和y分别是矩阵里的另一个元素的横纵坐标。实现一个函数,给定一个起始点的横纵坐
标startX 和startY,返回从起始点出发的traversal是否能cover矩阵里的每一个点。
我的想法是用一个hashSet,每初始化一个Item,都放入这个set, 直到遇到重复元素
或null为止,然后计算hashSet的size是否等于matrix的size。我写的基本算法:
boolean getCoverage(Item[][] items, int startX, int startY){
Item item = items[startX][starty];
HashSet- set = new HashSet
- ();
set.add(item);
while(item... 阅读全帖 |
|
w****x 发帖数: 2483 | 50
struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
struct ENDPOINT
{
int nIndex;
bool bStart;
int nVal;
};
bool lessThan(const ENDPOINT& ed1, const ENDPOINT& ed2)
{
return ed1.nVal < ed2.nVal;
}
void setFlg(EVENT events[], int n)
{
if (events == NULL || n <= 0)
return;
ENDPOINT* ends = new ENDPOINT[n*2];
for (int i = 0; i < n; i++)
{
ends[2*i].bStart = true;
ends[2*... 阅读全帖 |
|