i***t
发帖数: 34 | 1 输入是一个字符串,然后判断这个字符串是不是26个字母都出现了,并打印出没有出现的
字母
万分感谢
char *getMissingLetters(const char *sentence){
int len;
char * ret;
int i, index = 0;
int marker[26]; //remember how many time char occurs in the string
if(sentence == NULL)
return "";
ret = (char*)malloc(sizeof(char)*26); //malloc buffer for return
string
if(ret == NULL) //malloc fail
return "";
len = strlen(sentence); //get string length
for(i = 0; i < 26 |
|
P********l
发帖数: 452 | 2 How about this version using Dynamic Programming?
The basic idea is fill in a table for a matching path. If the last pair
matches, the whole string will match.
mtch is the array, which is of (string length + 1)*(pattern length + 1).
mtch[0][*] and mtch[*][0] is padded with false.
Then the function is something like:
mtch[i][j] =
1. if pattern char='.', mtch[i][j]=mtch[i-1][j-1]
2. if pattern char='*', mtch[i][j]=mtch[i-1][j-1] || mtch[i][j]=mtch[i-1][
j]
3. if pattern char=string char, mtc... 阅读全帖 |
|
i**********e
发帖数: 1145 | 3 我已经写了，但是感觉不是最简洁的，所以就没好意思post上来。
我相信有更简洁的版本，所以我还在努力写更简洁的代码。
感觉上递归的方法可以写的更简洁些，但会更加难写对，尤其这问题细节那么多。
注：我没有处理 ‘.’（‘.’match一个的任意字符）。
bool match(const char *str, const char *pattern) {
const char *p1 = pattern, *p2 = str;
while (*p1 && *p1 != '*') {
if (!*p2) return false;
if (*p1 != *p2)
return false;
p1++;
p2++;
}
if (!*p1) {
if (*p2) return false;
else return true;
}
while (*p1) {
while (*p1 == '*')
p1++;
if (!*p1) return true;
const char *p... 阅读全帖 |
|
h*****g
发帖数: 944 | 4 Q1) Which of the following general functions gives a pointer to the
immediate
base class of a derived class, i.e. the direct parent class?
A) parent()
B) super()
C) base()
D) This function does not exist.
我好像选了super(), 这个java里有，c++里有没有啊？
Q2) What is the problem with the following code snippet?
class myclass;
myclass* pmc = new myclass();
free(pmc);
A) The problem is that releasing memory with "free" is possible only if the
memory was allocated with "malloc".
B) The problem is that "free" ... 阅读全帖 |
|
i******s
发帖数: 301 | 5 你的解法应该是对的，基于这个写了如下C++代码
/*
* Author: Shengzhe Yao
* Date: 08 Nov 2010
*/
#include
#include
#include
#include
using namespace std;
// T(n) = \sum_{i=1}^{n-1} (T(i) * H(i+1))
int findAllStr(const set &dict, char *str,
int end, int *lookup_table) {
if (lookup_table[end] > 0)
return lookup_table[end];
int total = 0;
for (int i=1; i < end; ++i) {
char *substr = (str+i+1);
if (dict.find(substr) != dict.end()) {
char tmp =... 阅读全帖 |
|
i**********e
发帖数: 1145 | 6 这题蛮有意思的，我刚写完。
其实 idea 挺容易明白，我说一次给你听就明白了，但是没图解释起来比较费劲。这题
最复杂的地方其实就是选择怎么把数据结构结合起来。
一开始我以为要用 dp，其实 greedy 就可以了。
总复杂度是 O(N lg M)，N 为 str 的长度，M 为 pattern 的长度。
主要原因有个 lg M 是因为 STL map 里的 find() 函数复杂度为 O(lg M).
我用的是 map + queue + hashtable （有点吓人呵呵，可能我想太复杂了）。
我暂时还没想到怎么提升到 O(N)，应该是利用一个更好的数据结构吧。如果有高人知
道怎么提升到 O(N)，请指点一下吧~
这是我做的 test cases:
第一行是 string 和 pattern，
第二行是函数 return 的 start and end position，然后是 shortest substring。
cabeca cae
3 5 eca
cfabeca cae
4 6 eca
cabefgecdaecf cae
9 11 aec
cabwefgewcw... 阅读全帖 |
|
s*******f
发帖数: 1114 | 7 //A. Given an arbitrary tree, can you print it level by level (with each
level
//printed on the same line).Define your own tree node structure, can be
//binary tree or n-ary tree.
struct Node{
int d;
std::vector children;
};
void PrintByLevel(Node *r){
if (!r)
return;
std::queue q;
q.push(r);
int pre_count = 1;
int count = 0;
while (!q.empty()){
Node *p = q.front();
for (std::vector::const_iterator ci = p-
>children.begin(); ci != p->children.end(); ++ci){
q.push(*ci);
++cou... 阅读全帖 |
|
w**********y
发帖数: 1691 | 8 ////////////////////////////
class A{ }; A a;
那么 sizeof(a) is 1;
class X{
void doNothing(){}
char a;
};
sizeof(x) 咋还是1,不是 1+1 =2 呢?
////////////////////////////
class Y{
virtual void doNothing(){}
};
sizeof(y) is 4..这个应该是指向virtual table的地址大小吧?
class Y{
virtual void doNothing(){}
virtual void doNothing2(){}
char a;
};
为啥是8不是4+1=5啊? 而且再添加一个member: char b..还是8..
如果换成char* b就成了12...
如果换成char a[2],结果是8
如果换成char a[10],结果是16
非常不理解.. |
|
g*******s
发帖数: 490 | 9 感想，居然第一题就考到了goto。。我靠。。
有两三道题程序实在是太长，一堆指针+loop,看不清楚，不过这些程序基本是找错。。只能看答案猜了
最好两台电脑，一台要打程序，查资料操作不过来，如果有帮手就更好了
1. variable definition 和 declaration的 区别
2. 怎么是最portable的方法操作integer最高位的那个byte,比如设1
3. vfprintf考到了
4. char *x;
x="abcd"
请问这个操作的意义，合法不合法？空间是怎么allocate
5. freebsd某个头文件的一个macro
#if defined xxxx
#define _p(xxx) (xxx)
#else
#define _p(xxx) ()
#end
what does this macro for
6. memcpy 在某个iso xxx标准中的标准declaration是
7. memmve
8.哪个方法是一个c program必须的方法，main?
9. c提供了哪个方法获取 any file的 size
10. file * fp ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 10 来自主题: JobHunting版 - fb 面经 For number 1, the problem of proving the statement sounds MORE interesting..
. hmm..
My solution using character pointer manipulation.
#include
using namespace std;
void printCharCounts(const char *in, char out[]) {
int count = 1;
char *pOut = out;
const char *pIn = in;
while (*pIn) {
if (*pIn == *(pIn+1)) {
count++;
} else {
*pOut++ = '0' + count;
*pOut++ = *pIn;
count = 1;
}
pIn++;
}
*pOut = '\0';
}
int main() {
char str[100] = "... 阅读全帖 |
|
g*****1
发帖数: 998 | 11 g++里warning:deprecated conversion from string constant to 'char*'
刚试了"char*" to "const char*" in vc 还是不行。。
vc里的compile error很多，以下是第一个：
g:\program files\microsoft visual studio 10.0\vc\include\algorithm(4296):
error C2784: 'bool std::operator <(const std::move_iterator<_RanIt> &,const
std::move_iterator<_RanIt2> &)' : could not deduce template argument for '
const std::move_iterator<_RanIt> &' from 'std::basic_string<_Elem,_Traits,_
Ax>'
1> with
1> [
1> _Elem=char,
... 阅读全帖 |
|
b********n
发帖数: 29 | 12 来自主题: JobHunting版 - 问个算法题 #define N 4
void FindWordsBoggle(char board[][N])
{
int i=0,j=0;
char* outStr = (char*) malloc((N*N+1)*sizeof(char));
int* occupMap = (int*) calloc((N*N),sizeof(int));
int level = 0;
RecursiveBoggle(board, outStr, level, occupMap);
free(occupMap);
free(outStr);
}
void RecursiveBoggle(char board[][N], char* outStr, int level, int*
occupMap)
{
int* occupMapCopy = (int*) malloc((N*N)*sizeof(int));
memcpy(occupMapCopy, occupMap, N*N*sizeof(int));
int i=0,j=0;
for ( ; i < N; i++... 阅读全帖 |
|
l*****g
发帖数: 685 | 13 用C++写了一个版本:
void RecursivelyRemoveSubString(char *str, const char *sub)
{
if (!str || !sub || *sub == 0 || *str == 0 || strlen(str) < strlen(sub))
return;
char *end = str;
char *cur = str;
int subLen = strlen(sub);
char subEnd = sub[subLen - 1];
while (*cur != 0)
{
*end = *cur;
if (*end == subEnd)
{
char *reCur = end;
int subIndex = subLen - 1;
bool match = true;
bool reCurEnd = false;... 阅读全帖 |
|
c******t
发帖数: 1500 | 14 我改了一点你的程序，刚在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;
}
}
... 阅读全帖 |
|
w****x
发帖数: 2483 | 15 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... 阅读全帖 |
|
i**********e
发帖数: 1145 | 16 我写的 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... 阅读全帖 |
|
i**********e
发帖数: 1145 | 17 我刚找到你代码有个 bug，请试一下这个 case:
isMatch("a", "ab*") -> 这个应该返回的是 true.
我尝试写这个递归程序的时候也犯了跟你同样的错误了。
我的代码如下，感觉跟你思路挺像，但是我的多了个 while loop. （那个 do-while
loop 不用管它，只是跳掉多余的 '*'s).
bool isMatch(const char *s, const char *p) {
assert(s && p);
if (*p == '\0') return *s == '\0';
// next char is not '*': must match current character
if (*(p+1) != '*') {
assert(*p != '*');
return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
}
// next char is '*'
char rep = *p; // repeated ch... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 我刚找到你代码有个 bug，请试一下这个 case:
isMatch("a", "ab*") -> 这个应该返回的是 true.
我尝试写这个递归程序的时候也犯了跟你同样的错误了。
我的代码如下，感觉跟你思路挺像，但是我的多了个 while loop. （那个 do-while
loop 不用管它，只是跳掉多余的 '*'s).
bool isMatch(const char *s, const char *p) {
assert(s && p);
if (*p == '\0') return *s == '\0';
// next char is not '*': must match current character
if (*(p+1) != '*') {
assert(*p != '*');
return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
}
// next char is '*'
char rep = *p; // repeated ch... 阅读全帖 |
|
s***h
发帖数: 662 | 19 贡献一点面经.
我准备的时间还不够, 今天这二面有点忐忑.面我的人是个白人小伙子, 说话很快, 不
停的提附加问题.
1. how to pick first k maximum numbers in an array.
me: most straightforward, sort then pick, nlgn + k
he: ok...
me: better way, quick select, n * k
he: what is quick select, why is it linear time?
me: talking...
he: what if array is way bigger than the memory, can this work?
me:...yes...but slower due to swapping...
he: anything better?
me: ...
我不太明白他想问什么,所以没答上这一问,最后他问我有什么问题的时候我就
问了他,他说,你可以构造一个size k heap. then it is nlogk. 哎, 我当时真
没往... 阅读全帖 |
|
s*******f
发帖数: 1114 | 20 // 给一个字符串，例如"30*(5+10)",输出计算结果。
double GetValue(double b1, double b2, char op){
switch(op){
case '+':
return b1 + b2;
case '-':
return b1 - b2;
case '*':
return b1 * b2;
case '/':
if (b2 < 0.00000001)
return 0;
return b1 / b2;
default:
return 0;
}
}
bool OpPriority(char op1, char op2){
if (op1 == '*' || op1 == '/'){
return true;
}else if ((op1 ==... 阅读全帖 |
|
j*******g
发帖数: 4 | 21 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' || s... 阅读全帖 |
|
k***t
发帖数: 276 | 22 题目其实很简单，自己摆乌龙了。细节如下。
虽然连on-site都没拿到，个人感觉，作为第一次电面，基本达到操练面试的目的。自
我介绍，项目表达要言简意赅。Coding要冷静，不紧张，确保看清题目，自我检查code
要细。
与大家分享面经/经历。也希望大家给comment。Code是我从collabedit上直接贴过来的
。欢迎comment，帮我提高。谢谢。
一电面：老美。
前半部分是简历上Performance Tuning的各种Projects的细节；
后半部分是Website Performance的各种问题。
基本对答如流，获面试人认同。并说我们网站增长快，急需你这样有Performance方面
经验的人。Highly recommend for the next step.
二电面：老印。题目其实很简单，自己摆乌龙了。
开始讲Projects，老印问了一个简历上Resource Leakage Finding的东西。
回答不够简洁清晰，偏冗长。老印试图澄清，最后彻底澄清。花了一些时间。
后半个小时，两道Coding题：
1。判断string是否数字？如1.2。并写TestCa... 阅读全帖 |
|
f*******l
发帖数: 66 | 23 #include
#include
using namespace std;
bool isValid( char currentChar,int x, int y, int columnSize, int
rowSize,
char desiredChar, bitset <20> mybitset )
{
if(x < 0 || x > columnSize || y < 0 || y > rowSize )
{
return false ;
}
if ( mybitset[x*columnSize+y] == 1 )
{
return false;
}
if ( currentChar != desiredChar)
{
return false ;
}
return true ;
}
bool moveforward( int rowSize, int columnSize, char Array[][4], int... 阅读全帖 |
|
j*******g
发帖数: 4 | 24 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' ||... 阅读全帖 |
|
p****n
发帖数: 148 | 25 C版
／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／
int match (const char *s1, const char *s2, const int len) {
int r = 0;
for (int i = 0; i < len; i++)
if (*(s1+i) == *(s2+i))
r++;
return r;
}
size_t edit (const char *s, const char *u, int *begin, int *end) {
size_t maxmatch = 0;
for (int i = 0, j = strlen(u)-1; i < strlen(s); (j > 0)?j--:i++) {
int len = min(strlen(u) - j, strlen(s) - i);
int m = match(s+i, u+j, len);
if (m > maxmatch) {
... 阅读全帖 |
|
c**********e
发帖数: 2007 | 26 It looks f1() is OK, but f2 is not.
Is my understanding correct? Thanks.
char* f1() {
char* p=new char;
*p='x';
return p;
}
char* f2() {
char ch='a';
char* p=&ch;
return p;
} |
|
r*********n
发帖数: 4553 | 27 0：aa
1：aabbccaa
2：bb
3：bbc
4：bbbbbb
5：cc
6：ccbb
比如你要判断A = aabbccaa能否由其他词组成：
A[0] = a，所以你在所有words里面做binary search（with respect to the first
char），你发现arr[0]，和arr[1]是由char a开头的
然后在[0,1]里面binary search A[1] = a（with respect to 2nd char），你还是得
到[0, 1]，这个时候因为arr[0]只有2个char，所以你发现arr[0]是A的prefix。
然后在[0 - 6]里面binary search A[2] = b（with respect to 1st char），你得到[
2,3,4]
然后在[2，3，4]里面binary search A[3] = b（with respect to 1st char），你得
到[2,3,4]....
整个思路和MSD string sort是一样的，解释起来比较verbose，你理解了MSD sort，也
就理解这个算法... 阅读全帖 |
|
f*******t
发帖数: 7549 | 28 #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) {
... 阅读全帖 |
|
d****n
发帖数: 1637 | 29 差不多用了30分钟
#define BSZ 4096
char buffer[BSZ];//buffer same size as 4096
int curr=BSZ-1; //current position read in buffer
int eof=0; //eof flag
extern char * read4096();
char *getline(){
char *s; //return string
int i, ssz=0; //size of s
for(;;){
if (!eof){
if (curr==(BSZ-1)) {
strcpy(buffer, read4096()); //read API
curr=0;
if (strlen(buffer)<4096 ) e... 阅读全帖 |
|
r****k
发帖数: 21 | 30 #define MAX_BUFFER_SIZE 4096
extern char *read4096();
char buffer[MAX_BUFFER_SIZE+1];
char *readline()
{
static int EOF = 0;
static int currentPos = MAX_BUFFER_SIZE;
char *s = NULL;
int i, ssz = 0;
for(;;)
{
if (!EOF)
{
// buffer is not empty, check buffer
if (currentPos != MAX_BUFFER_SIZE)
{
for ( i = currentPos; i < MAX_BUFFER_SIZE; i++)
if (buffer[i] = '\0' || buffer[i] = '... 阅读全帖 |
|
s******n
发帖数: 3946 | 31 递归非DP做法
bool isScramble(char* str1, char* str2, int length) {
if (length==1) return *str1 == *str2;
for (int i=1; i
if (isScramble(str1, str2+(length-i), i)
&& isScramble(str1+i, str2, length-i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1+i, str2+i, length-i))
return true;
}
return false;
}
递归DP做法
class Solution {
char* str1;
char* str2;
int m;
int m2;
int m3;
int* DP;
#define dp(i,j,k) DP[m2 * (i) + m * (j) + (k) ]
public:
Solution(cha... 阅读全帖 |
|
j********e
发帖数: 1192 | 32 我没有说字符集相同就能scramble，字符集相同是必要条件，而不充分。
我的做法是，先找到一个位置i在s1,j在s2使得分割后的4个字符串两两
有相同的字符集（i=j 或者i=N-j)。然后接着对这2对字符串继续做同样
的事情连寻找分割位置。这样递归下去，如果有某对字符串无法找到分割
位置，则表示失败。否则，最后分隔最小的字符串只有一个字符。就可以
判断scramble成功。
问题是，如果有多个分割位置，是否任选一个都可以？如果必须测试每个可能的分割位置，那复杂度就不好说了。
下面是我的简单实现代码，通过了leetcode的online judge (包括judge large)。这段代码中会处理所有可能的分割位置。如果只选第一个可能的分割位置，有一个测试失败了。
#include
#include
#include
#include
using namespace std;
#define BITMAP_LEN 256
bool compare_char_set(const char *s1, con... 阅读全帖 |
|
t**********h
发帖数: 2273 | 33 来自主题: JobHunting版 - a电面面经 1. Given two input sorted arrays of integers, merge the input arrays and
output in sorted order
2. Stream of characters, at any point you should be able to answer --
what is the most recent character that happened only once
a, b, c, d, c, a => d
, d => b
void add(char c)
char getMostRecent( )
这一题是说有一个char的stream，不是array，比如是用户端的输入，每次输入都是单个的
char，add函数是用来增加当前输入的这个char的，调用getMostRecent可以得到离当前输入最
近的那个只出现一次的char
3. Home automation controller
// controll devices e.g. TV, L... 阅读全帖 |
|
f**********t
发帖数: 1001 | 34 I have this string s1 = "My name is X Y Z" and I want to reverse the order
of the words so that s1 = "Z Y X is name My".
我写出了算法，结果正确，但是最后一步memory release时出错：
int ReverseWords (char *str) {
if (!str || str == "")
return 0;
char *newstr = new char[strlen(str)];
int i = strlen(str) - 1;
int start, end, k = 0;
while (i >= 0) {
start = end = i;
while (start >= 0 && str[start] != ' ')
--start;
for (int j = start+1; j <= end; ++j)
... 阅读全帖 |
|
i***h
发帖数: 12655 | 35 用C++ STL, 还好了
下面的代码少了最后一步, 也没有sanity check
但也不难
当然效率不是最好的
#include
#include
#include
#include
using namespace std;
bool
compstr(char* a, char* b)
{
return strcmp(a,b)<0;
}
void
suffixArray(char *a, char *b)
{
char *m = (a>b)? a-1 : b-1;
char* suffix[strlen(a)+strlen(b)];
for(int i = 0; i
suffix[i] = a+i;
}
for(int i=0; i
suffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), comp... 阅读全帖 |
|
s********k
发帖数: 6180 | 36 上一个我写的，没有检查字符串是否都在0-9和'.'，不知道这个是否需要补上(如果某
个版本不符合要求(10.1.a)，返回什么？)。基本思路是第一个.之前按照数字大小比较
，然后其余的一个个位置比较,只要某一个位置其中一个大，剩下的就不需要比较了(比
如2.07和2.1，小数点之后后面的1》前面的0，直接2.1版本大),然后如果某个字符串先
到.,别的还有数字，那么后者大(1.05>1.0.5),如果最后一个已经晚了，另外一个还有
数字，后面大（3.2.1<3.2.10或者3.2.1<3.2.1.5）
大牛指点一下
const char *compVersion(const char *version1, const char * version2){
const char *v1 = version1;
const char *v2 = version2;
//compare the digit before first '.'
if(getNum(v1)>getNum(v2)) return v1;
else if(getNum(v1)>ge... 阅读全帖 |
|
z******e
发帖数: 82 | 37 new test cases:
--------------------
char str[] = "\\"; // test \ inside "
char str[] = "\\";
char str[] = '\"'; // test \ inside "
char str[] = '\"';
code:
---------------------------
private static String uncomment(String str) {
boolean slash2 = false;
boolean inStr = false;
boolean slashstar = false;
boolean escape = false;
StringBuilder sb = new StringBuilder();
char lastc = ' ';
char c = ' ';
int deleteStart = -1;
... 阅读全帖 |
|
b***m
发帖数: 5987 | 38
嗯，这个我看到了，我的版本是这样：
// caller has to free memory allocated
char *string_reverse2(const char *string)
{
if( !string ) return NULL;
int len = strlen(string);
char *res = (char *)malloc(len + 1);
if( !res ) return NULL;
char *str = (char *)string + len - 1;
while( str >= string )
{
*res = *str;
res++;
str--;
}
*res = '\0';
return res;
} |
|
h****n
发帖数: 1093 | 39 无聊写了一个，请大牛指点
void ReverseWordList(char * str)
{
char * p = str;
char * start = str;
char * end = str;
bool inWord = false;
while(*end++);
end--;
Reverse(start, end);
while(*p)
{
if(*p==' ')
{
if(inWord)
{
inWord = false;
end = p-1;
Reverse(start, end);
}
}
else
{
if(!inWord)
{
inWord = true;
... 阅读全帖 |
|
s*****n
发帖数: 5488 | 40 争取最简洁奖。很久不写C聊。
char* ls(const char* input, char* result){
int start = 0; int end = 0;
char first = 0; char second = 0;
char* p = input;
int i = 0;
int rs = 0; int re = 0;
which(*p){
if (*p != first || *p != second){
first= second;
second = *p;
start = i - 1 < 0 ? 0 : i - 1;
second = i;
}
if (*p == first){
swap (first, second);
end ++;
}
if (*p == second)
end++;
if (re - rs < start -end... 阅读全帖 |
|
s*****n
发帖数: 994 | 41 多谢各位，刚才把regular expression match理解为wildcard matching了，
那就顺便把wildcard matching的code给贴上来吧
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m=strlen(s);
int n=strlen(p);
bool dp[1000][1000] = {false};//dp[i][j] means last i chars in s
matches last j chars in p
dp[0][0] = true;
for (int i=1; i<=n; ++i){
dp[0][i] = dp[0][i-1]... 阅读全帖 |
|
x*********w
发帖数: 533 | 42 来自主题: JobHunting版 - 问道算法题 const char* minimumPadding(const char* szStr, char res[])
{
if (NULL == szStr || *szStr == 0 || NULL == res)
return 0;
int nLen = strlen(szStr);
int rec[100][100] = { 0 };
for (int i = 0; i < nLen-1; i++)
{
rec[i][i+1] = szStr[i] == szStr[i+1] ? 0 : 1;
}
for (int i = 2; i < nLen; i++)
{
for (int j = 0; j < nLen-i; j++)
{
rec[j][j+i] = 1 + min(rec[j+1][j+i], rec[j][j+i-1]);
if (szStr[j] == szStr[j+i])
... 阅读全帖 |
|
e*******i
发帖数: 56 | 43 Here is shorter version after incorporated some tricks posted by others
/************************/
#include
#include
#include
using namespace std;
void maxRep(char *s)
{
int maxFreq=0;
int counter=0;
string result;
char target=*s;
do{
if(*s!=target)
{
if( counter >= maxFreq && isalpha(target) ){
if(counter>maxFreq) result.clear();
result+=target;
maxFreq=counter;
}
target=*s;... 阅读全帖 |
|
j********r
发帖数: 25 | 44 参考一下我的做题记录里提取出来的：
class Solution {
public:
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector > ret;
int n = num.size();
bool *used = new bool[n];
vector index;
memset(used, 0, n*sizeof(bool));
permute(num, used, index, 0, ret);
delete[] used;
return ret;
}
void permute(const vector &num, bool used[], vector& candidate
, int pos, vector阅读全帖 |
|
d*k
发帖数: 207 | 45 //欢迎拍砖，共同提高。
char* readLine(char* ret) {
vector store;
static char buf[SIZE];
static buf_size = 0;
while (true) {
if (buf_size == 0) {
buf_size = read(buf, SIZE);
}
int last = 0;
for (last = 0; last < buf_size && buf[last] != '\n'; ++last);
copy(buf, buf + last, back_inserter(store));
if (last < buf_size) {
buf_size = buf_size - (last + 1);
memmove(buf, buf + last + 1, buf_size)
... 阅读全帖 |
|
t********e
发帖数: 12 | 46 大概是trie+backtrace+hashtable...
建立trie是为了按prefix快速查找。
backtrace from 0 to 3, at each step i, fill in row i and col i at the same
time. chars before i are already determined, and char at i must be the same.
create hash table to group candidates from row i and col i that char i are
equal. test and keep going down or backtrace.
for example, suppose we are at level 2. we have
x x A x
x x B x
C D = ?
x x ? ?
'x's and A/B/C/D are the chars we already fill out.
at level 2, all information we know is:
1.... 阅读全帖 |
|
h**o
发帖数: 548 | 47 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<>(8-i);
if (ch ^ pattern==0) cnt++; //^ means XOR
}
return cnt;
}
int countPattern(char* str, char pattern){
if (!str || *str == ‘ |
|
h**o
发帖数: 548 | 48 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countPattern(char* str, char pattern){
if(!str) return 0;
int sum = 0;
while(!(str+1) && *(str+1)!= 0){
sum += countByte(str, str+1, pattern);
str++;
}
return sum;
}
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<> (8-i);
if (ch ^ pattern==0) cnt++;
}
return cnt;
} |
|
s***e
发帖数: 403 | 49 我也给个解。
这个题目的关键其实是两个字符之间的bitwise roll。因为要检验的只有8个bits。所
以只要每次取两个字符c1和c2，然后依次roll bits即可。
int countPattern2(char c1, char c2, char pattern)
{
int count = 0;
static const char mask = (1 << 7);
int i;
for(i = 0; i < 8; ++i)
{
if (c1 == pattern)
++count;
c1 <<= 1;
c1 += ((c2 & mask) ? 1 : 0);
c2 <<= 1;
}
return count;
}
int countPattern(const char* str, char pattern)
{
const s_length = strlen(str);
int i;
int count = 0... 阅读全帖 |
|
S******1
发帖数: 216 | 50 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = ne... 阅读全帖 |
|
