I**********s
发帖数: 441 | 1 最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), lef... 阅读全帖 |
|
I**********s
发帖数: 441 | 2 最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), lef... 阅读全帖 |
|
s********x
发帖数: 914 | 3 2吧
class CharNode {
private char value;
private CharNode next;
private CharNode previous;
public CharNode getPrevious() {
return previous;
}
public void setPrevious(CharNode previous) {
this.previous = previous;
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public CharNode getNext() {
return next;
}
public void setNext(CharNode next) {
this... 阅读全帖 |
|
l******o
发帖数: 144 | 4 不用60行。43行我这个（没编译没跑没测，如果错误请见谅）
vector f(const vector& vs) {
map> edges;
unordered_set out_vertices;
for (size_t i = 0; i + 1 < vs.size(); i++) {
const auto& s1 = vs[i];
const auto& s2 = vs[i + 1];
size_t j;
for (j = 0; j < s1.size() && j < s2.size(); j++) {
if (s1[j] != s2[j]) {
edges[s1[j]].insert(s2[j]);
break;
}
}
if (j == s2.size() && j < s1.size()) throw runtime_error();
for (char c ... 阅读全帖 |
|
u**l
发帖数: 35 | 5 c/c++的code好像不受欢迎：
#include
#include
using namespace std;
char* GetAlphabet(char* str) {
while ('\0' != *str && !((*str >= 'a' && *str <= 'z') || (*str >= 'A' &&
*str <= 'Z'))) {
++str;
}
return str;
}
char* GetOthers(char* str) {
while ((*str >= 'a' && *str <= 'z') || (*str >= 'A' && *str <= 'Z')) {
++str;
}
return str;
}
void Reverse(char* s, char* e) {
while (s < e) {
char c1 = *s;
char c2 = *e;
*s = c2;
... 阅读全帖 |
|
g*********s
发帖数: 1782 | 6 The following code has compilation errors if "-DDEBUG" is not specified.
In function `StripePainter::init_tab(std::basic_string
std::char_traits, std::allocator >)':
inclass_static.cpp:(.text+0xb): undefined reference to
`StripePainter::colorset'
inclass_static.cpp:(.text+0x1b): undefined reference to
`StripePainter::orig_color'
inclass_static.cpp:(.text+0x23): undefined reference to
`StripePainter::colorset'
inclass_static.cpp:(.text+0x58): undefined reference to
`StripePainte... 阅读全帖 |
|
f********3
发帖数: 210 | 7 我也是新人，呵呵。不过刚好做过这道题。
有包子没？=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;
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 8 这个是很基本的数据结构，建议看一下wiki
我前几天实现了它，只有基本的insert和search，没有对查找child list进行优化，代
码贴出来供参考：
#include
#define MAX_LENGTH 64
using namespace std;
static char buff[MAX_LENGTH];
class Trie {
public:
Trie();
Trie(char value);
bool Insert(const char *str);
bool Search(const char *str) const;
void PrintAll(int pos) const;
private:
char _value;
Trie *_sibling;
Trie *_child;
};
Trie::Trie()
{
_value = 0;
_sibling = NULL;
_child = NULL;
}
Trie::Trie(char value)
... 阅读全帖 |
|
s********r
发帖数: 137 | 9 只处理出现次数小于10的情况，但是可以很容易修改处理出现次数多余9次的情况。
我写的，见笑了：
/***********************************************************************
*********************/
/* Compress a String: AAABBCDDDD will be A3B2CD4 */
//
private static String compressString(String str)
{
char[] chars = str.toCharArray();
char current = chars[0];
int count = 1;
int indexCounter = 1;
int shiftBack = 0;
for(int i = 1; i< chars.length; i++){
if (curren... 阅读全帖 |
|
t*********h
发帖数: 941 | 10 void foo(char* s) {
if(!*s) return;
int end[2], start[2], chars[2];
int maxlen=2,maxstart=0,i,n=strlen(s),p;
if(n<3) {printf("%s\n",s);}
start[0]=0;end[0]=0;chars[0]=s[0];
if(s[1]==s[0]) {
start[1]=0;end[1]=1;chars[1]=chars[0];
} else {
start[1]=1;end[1]=1;chars[1]=s[1];
}
for(i=2;i
if(s[i]!=chars[0]&&s[i]!=chars[1]) {
p=end[0]
chars[p]=s[i];
start[p]=i;
start[1-p]=end[p]+1;
end[p]=i;
} else {
p=(chars[0]=... 阅读全帖 |
|
s********u
发帖数: 1109 | 11 挖个坟，这个readline的题目，搜了一下，好像应该是这个意思吧：
用一个buffer来存字符流，如果中间有换行，那么将这一行返回成一个字符串输出，但
是这个buffer里面的东西继续保留，下次readline（）再输出；
如果一行非常长，那么可能需要用到几次read（），来拼出这个完整的line。
/*Implement a function char* readLine(); which returns single lines from a
buffer.
To read the buffer, you can makes use of a function int read(char* buf, int
len) which fills buf with upto len chars and returns the actual number of
chars filled in. Function readLine can be called as many times as desired.
If there is no valid data or newline ter... 阅读全帖 |
|
s*******s
发帖数: 1031 | 12 follow一下我的面经。
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
ve... 阅读全帖 |
|
s*******s
发帖数: 1031 | 13 follow一下我的面经。
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
ve... 阅读全帖 |
|
s*****b
发帖数: 8 | 14 我来贴一个。
Rocket fule (Software Engineer - Machine Learning Scientist ) 技术电面后code
test. code通过了所有test cases. 人家看过code 后就拒了。问题在哪里呢？请各位
牛人不吝赐教。题目本版以前贴过
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its cours... 阅读全帖 |
|
B********t
发帖数: 147 | 15 自己写的最少行的版本，感觉背下来都要敲25分钟
class Solution {
public:
bool solveSudoku(vector> &v1, vector> &v2,
vector> &v3, vector > &board) {
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board.size(); ++j)
if (board[i][j] == '.') {
int k = (i/3)*(board.size()/3) + j/3;
for (char c = '1'; c <= '9'; ++c) {
if (v1[i].find(c) == v1[i].end... 阅读全帖 |
|
n*******s
发帖数: 482 | 16 恩 仔细看了一下，是我的测试代码写错了。
String s(" hello world ");
cout<
const char* o = (const char*)s;
cout<<"const char* o="<
char* o1 = (char*)o;
cout<<"char* o1="<
remove_blanks(o1);
cout<<"remove_blanks(const char* -> char*)o1="<
结果没啥问题。
我想对于这种Const char* --> char*的转换，如果后面对char*的操作是变短 就没
啥问题，如果变长 可能会覆盖其他变量吧。
谢谢observer RP++
:) |
|
X****r
发帖数: 3557 | 17 No, this understanding is wrong.
If you declare 'char a[10];', 'a' has type 'char [10]', and '&a' has
type 'char (*)[10]'.
If you declare 'char *b;', 'b' has type 'char *', and '&b' has type
'char **'.
Type 'char []' can be implicitly converted into type 'char *', so 'a'
can be used in almost everywhere 'char *' is required. However,
'char (*)[]' cannot be converted to 'char **', so your code won't work.
which |
|
h****8
发帖数: 599 | 18 Char **array[12][12][12] 三维数组，元素是char**
char ***** p = array; p是5维指针，从数组到指针的转换是可以。所以我认为这个对的
char * (* p) [12][12][12] = array; p是指针，指向一个三维数组，数组元素是char
*,所以错
const char ** p [12][12][12] = array; p是三维数组，元素类型是const char**,我
觉得这里non-const应该不能转换成const,因为是元素而不是指针，所以也错
char (** p) [12][12] = array; p是二维指针，指向一个二维数组，元素类型为char,
很明显连dimension都不对
char ** (* p) [12][12] = array;p是一个指针，指向一个二维数组，元素类型为char
**,与array所指向的数组类型不同 不能赋值
所以只有1是对的我认为。 |
|
l*******o
发帖数: 791 | 19 楼上说的对。
问题出现在你的test函数，test函数接受的是一个以值传递的指针。比如说一个经典的
swap（int a, int b）的例子，必须写成swap(int * a, int * b)或者引用才能改变外
界传入函数参数的值。同理如果你想改变一个指针的值，你需要用对一个指向这个指针
的指针进行操作，
所以test必须写成
void test (char * * p)
{
*p = new char[10];
memset((*p), 'A', 10);
}
然后main函数写成
int main(int argc, char *argv[])
{
char *k;
test(&k);
cout << k << endl;
}
不过一般倾向于使用引用即reference这样你就不会混淆，reference版本如下
void test( char * & p )
{
p = new char[10];
memset(p, 'A', 10);
int main(int argc, char *argv[])
{... 阅读全帖 |
|
J******8
发帖数: 132 | 20 The question is not hard. But I missed two key points.
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0... 阅读全帖 |
|
x***n
发帖数: 70 | 21 第二题用栈来解决好像很容易。不过可能跟上面说的递归的算法是一样的。
public class patternMatch {
static java.util.Stack stackS = new java.util.Stack
>();
static java.util.Stack stackP = new java.util.Stack
>();
static void initStack( char [] s, char [] p ) {
for( char s1 : s ) {
stackS.add(s1);
}
for( char p1 : p ) {
stackP.add(p1);
}
}
static boolean is_match_stack( char [] s, char [] p) {
while( (!stackS... 阅读全帖 |
|
x***n
发帖数: 70 | 22 第二题用栈来解决好像很容易。不过可能跟上面说的递归的算法是一样的。
public class patternMatch {
static java.util.Stack stackS = new java.util.Stack
>();
static java.util.Stack stackP = new java.util.Stack
>();
static void initStack( char [] s, char [] p ) {
for( char s1 : s ) {
stackS.add(s1);
}
for( char p1 : p ) {
stackP.add(p1);
}
}
static boolean is_match_stack( char [] s, char [] p) {
while( (!stackS... 阅读全帖 |
|
v***a
发帖数: 365 | 23 来自主题: JobHunting版 - 问个算法题 第一次写 c 程序，不保证正确，请自己 debug
程序假设单词是 a to z 组成
用的 bst counting, 然后 导出来 qsort
#include
#include
struct _node;
typedef struct _node {
int cc;
char c;
struct _node * n[26];
struct _node * fa;
} node;
void addToTree(node * root, node * r, const char * p1, const char * p2) {
int t;
int i;
if (p1 == p2) {
if (r->cc == 0) root->cc++;
r->cc++;
return;
}
t = (*p1) - (int)'a';
if (r->n[t] == NULL) {
r->n[t] = (node *... 阅读全帖 |
|
f*******t
发帖数: 7549 | 24 平衡括号的题可以用贪心法做吧
#include
#include
#include
#include
#define INVALIDCHAR -1
using namespace std;
char *balance(char *str)
{
int len = strlen(str);
if(len < 1)
return NULL;
char *buff = (char*)calloc(len + 1, 1);
stack left;
for(int i = 0; i < len; i++) {
if(str[i] == '(')
left.push(i);
else if(str[i] == ')') {
if(left.empty()) {
buff[i] = INVALIDCHAR;
co... 阅读全帖 |
|
S**I
发帖数: 15689 | 25 ☆─────────────────────────────────────☆
coconut001 (coconut001) 于 (Sat Apr 16 20:51:09 2011, 美东) 提到:
我是这周三面试的，周四回来歇了两天，压跟就没有心情来版上询问。我总共面了6个
人，5个
leader（真的各个title都是leader or senior leader，我就纳闷，M家木有engineer
吗？）和一
个PM。 问题比较简单，
实现strcmp，
实现malloc and free，讨论memory leak怎么解决，以及memory fragment问题
pointer问题（这个问的很杂，比如什么指针存的是一个已经out of scope的address之
后会发生
什么之类的，具体记不清楚了）
multi-processor相关问题，比如multi-processor的机器实现lock要怎么做，我好像说
了memory
bus之类的，中断这时候不起作用了。
Open question（这个问题我用数学模型解释，以至于面我的人以为我是Math的。。。
。。。... 阅读全帖 |
|
l*********8
发帖数: 4642 | 26 贴一下我的程序，通过了leetcode judge.
感觉还是有些繁琐.
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!s || !p)
return false;
if(p[0] == '\0' && s[0] != '\0')
return false;
const char * star = NULL;
const char * nextStar = NULL;
if (p[0] == '*') {
star = p;
p++;
}
while (1) {
n... 阅读全帖 |
|
k*****y
发帖数: 744 | 27 请问像 s = "abadabadabadeabecd", p = "*ab?c*d"这样的不用递归怎么办？
我也贴一个，大家帮忙看看，谢谢~
===========================
bool isMatch(const char* s, const char* p) {
if(*s == 0) return !hasNonStar(p);
if(*p == 0) return false;
if(*p != '*'){ //case: *p != '*'
while(*s && *p && *p!='*') {
if(*p!='?' && *p!=*s)
return false;
++p; ++s;
}
return isMatch(s, p);
}
else{ // case: *p == '*'
if(!skipStars(s, p)) return false;
... 阅读全帖 |
|
z******e
发帖数: 82 | 28 多谢大牛的test case
private static String uncomment(String str) {
boolean slash2 = false;
boolean inStr = false;
boolean slashstar = false;
StringBuilder sb = new StringBuilder();
char lastc = ' ';
char c = ' ';
int deleteStart = -1;
for (int i = 0; i < str.length(); i++) {
lastc = c;
c = str.charAt(i);
sb.append(c);
// ""
if (c == '"' && !slash2 && !slashstar) {
... 阅读全帖 |
|
J**9
发帖数: 835 | 29 1) For this signature
char* add(const char*a, const char *b)
It's definitely caller-free since you can't modify either one.
(allocation within the function)
(Or use a static buffer, but not recommended)
2) You can overwrite a with this, assuming a has enough spaces:
char* add(char*a, const char *b)
3) It's all caller's responsibility:
char* add(const char*a, const char *b, char *results)
Caller pre-allocates a buffer and passes in, of course, frees it later IF it
's from heap.
Choice 3) is the r... 阅读全帖 |
|
n**********e
发帖数: 88 | 30 (char*)&(s->ptr) 是 s 中第一个元素的地址。
(char*)s 是 s的地址.
所以， (char*)&(s->ptr) = (char*)s
所以， (char*)&(s->ptr)-(char*)s = 0
所以， buffer[(char*)&(s->ptr)-(char*)s] = buffer[0]
所以，最后一行：
*(int **)&buffer[(char*)&(s->ptr)-(char*)s] = (int *)&buffer[offset];
就是为s->ptr赋值。 |
|
j********8
发帖数: 10 | 31 static int setBit(int input, int bit)
{
int mask = 1;
mask <<= bit;
return input |= mask;
}
// assumption all characters are lower case
static vector findSubStr(string source, vector chars)
{
vector result;
// first convert chars into an integer, where bit 0-25 correspond to
a-z, o(n)
int charsBits = 0;
for (int i = 0; i < chars.size(); i++)
{
int bit = chars[i] - 'a';
... 阅读全帖 |
|
y***n
发帖数: 1594 | 32 原题在这里。 http://www.mitbbs.com/article_t/JobHunting/32517841.html 但是觉得不太对
搞这些题觉得很没思路。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector calculate(unsigned long m, unsigned long n, int k) {
if(... 阅读全帖 |
|
f**********t
发帖数: 1001 | 33 Well, my code is complex and sigfault. Let me go back if I have time.
This is too hard for a 45 minutes interview.
void skipSpace(const char **s) {
while (isspace(**s)) {
++(*s);
}
}
int getNum(const char **s) {
bool neg = false;
if (**s == '-') {
neg = true;
++(*s);
}
int cur = 0;
while (isdigit(**s)) {
cur = cur * 10 + (**s - '0');
++(*s);
}
--(*s);
return neg ? -cur : cur;
}
int opNum(int x, int y, char op) {
switch (op) {
case '+':
return x + y... 阅读全帖 |
|
t****t
发帖数: 6806 | 34 把fb去掉再来, cdecl不接受参数名, 比如说
cdecl> explain char foo(char)
declare foo as function (char) returning char
cdecl> explain char foo(char x)
syntax error
所以
cdecl> explain char *(*ff(char *(*)()))()
declare ff as function (pointer to function returning pointer to char)
returning pointer to function returning pointer to char |
|
F********g
发帖数: 475 | 35 /* add chars */
char test_str[32] = "Mr John Smith ";
void string_add_char(char *str)
{
unsigned int indx = 0;
char string_m[32];
//char *string_m;
while(*(str+indx) != '\0')
{
if(*(str+indx) != ' ')
{
indx++;
}
else
{
indx++;
if(*(str+indx) == ' ')
{
break;
}
else
{
strcpy(string_m,str+indx);
printf("%s\r\n",string_m);
indx += 2;
strcpy(str+indx,string_m);
*(str+indx-3*sizeof(char))='%';
... 阅读全帖 |
|
t********e
发帖数: 1169 | 36 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
t********e
发帖数: 1169 | 37 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
s*******e
发帖数: 93 | 38 这题是怎么做的呢？
可不可以这样：
设一个临时变量a
a=第一个char
读第2个char的时候 1／2的概率 a=第2个char （这样第一第二个数的返回概率各50%）
读第3个char的时候 1／3的概率 a=第3个char
（这时第3个char的返回概率为1/3, 又因为上一步第1第2的概率相等，这时3个char的
概率都相等）
。。。
读第n个char的时候1/n的概率 a＝第n个char
不过要求是 “该文件里每行返回的概率”
怎么处理每行字数不一样的情况呢？ |
|
b*****n
发帖数: 482 | 39 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... 阅读全帖 |
|
f********3
发帖数: 210 | 40 比如面试时，用set显然更好写。但hashset快。
hashset不是STL里面的，那么是不是所有的函数都得自己写。。。。感觉太麻烦了。。。
在这里看到个例子。那么面试时是不是还得这样写？
有没有好点的hashset的例子？多谢了
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
void lookup(const hash_set, eqstr>& Set,
const char* word)
{
hash_set, eqstr>::const_iterator it
= Set.find(word);
cout << word << ": "
<< (it != Set.end() ? "present" : "not prese... 阅读全帖 |
|
k***t
发帖数: 276 | 41 来自主题: 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++;... 阅读全帖 |
|
y****n
发帖数: 743 | 42 扫描式，空间O(n)，时间O(n)，一遍扫描。
public class BracketInfo
{
public char OperatorBefore = '\0'; // Low-Pri
public char OperatorInner = '$'; // Hi-Pri
public char OperatorAfter = '\0'; // Low-Pri
public int BracketStart = -1;
public int BracketEnd = -1;
}
public class BracketChecker
{
private Dictionary operatorPriority = null;
public Dictionary OperatorPriority
{
get
{
... 阅读全帖 |
|
a******a
发帖数: 2646 | 43 来自主题: 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... 阅读全帖 |
|
n**********e
发帖数: 45 | 44 感觉预处理字典挺麻烦的，如果字典很大呢？
试贴一简单解法：
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if ( dict.find(s.substr(l*N,N)) == dict.end() ) return false;
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
... 阅读全帖 |
|
n**********e
发帖数: 45 | 45 感觉预处理字典挺麻烦的，如果字典很大呢？
试贴一简单解法：
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if ( dict.find(s.substr(l*N,N)) == dict.end() ) return false;
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
... 阅读全帖 |
|
a***e
发帖数: 413 | 46 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt
不知道啊，但好像是可以得。我是觉得这种写法很简单， 比起同样的naive matching
char *strStr(const char *haystack, const char *needle) {
// if needle is empty return the full string
if (!*needle) return (char*) haystack;
const char *p1;
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++; // advance p1_advance M-1 times
}
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char*) p1;
p2 = needle;
while (*p1... 阅读全帖 |
|
D*****r
发帖数: 6791 | 47 http://www.ariel.com.au/jokes/The_Evolution_of_a_Programmer.html
High School/Jr.High
10 PRINT "HELLO WORLD"
20 END
First year in College
program Hello(input, output)
begin
writeln('Hello World')
end.
Senior year in College
(defun hello
(print
(cons 'Hello (list 'World))))
New professional
#include
void main(void)
{
char *message[] = {"Hello ", "World"};
int i;
for(i = 0; i < 2; ++i)
printf("%s", message[i]);
printf("\n");
}
... 阅读全帖 |
|
g****c
发帖数: 299 | 48 Basic String Handling Functions
All the string handling functions are prototyped in:
#include
The common functions are described below:
char *stpcpy (const char *dest,const char *src) -- Copy one string into
another.
int strcmp(const char *string1,const char *string2) - Compare string1 and
string2 to determine alphabetic order.
char *strcpy(const char *string1,const char *string2) -- Copy string2 to
stringl.
char *strerror(int errnum) -- Get error message corresponding to specified
er |
|
c*****a
发帖数: 55 | 49 A function header define is like:
aaa(const char *&x, const char *&y);
我这么implement 可以么？怎么给char *&类型负值尼？
const char *a;
const char *b;
aaa(const char *&x, const char *&y)
{
x=(char *&)a;
y=(char *&)b;
}
Thanks a lot. |
|
c**b
发帖数: 2999 | 50 都用到c++了,怎么还用一些c的东西? 比如那个index()2个参数,直接用array不就行了,
为什么要用指针呢.尽管这样也对,但是太复杂.简单点,干脆用pass by reference,连指针也不用了.答案确实是对的而且构思很简单.我能想到的算法比答案差点,但是逻辑更清晰些:
int index(char s[],char t[])
{
int i,j,k,foundIt=-1;
for(i=0;s[i] != '\0';i++)
for (j=i,k=0;t[k] != '\0';j++,k++)
if (s[j] != t[k])
foundIt = -1;
else foundIt = i;
return foundIt;
}
编写函数int index(char *s， char *t)，返回字符串t 在字符串s中出现的最左边的
位置，
如果在s中没有与t匹配的子串，就返回-1。
#inc... 阅读全帖 |
|
