g*******4
发帖数: 155 | 1 处理一个字符串，删除里面所有的A，double所有的B
例子，输入 CAABD, 输出是CBBD
要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算 |
f*******t
发帖数: 7549 | |
w****x
发帖数: 2483 | 3 第一趟从左到右去A数B,
第二趟从右到左double B |
g*******4
发帖数: 155 | 4
不是说了么 O(1)，再直白点就是两遍扫描了
【在 f*******t 的大作中提到】
: 没有时间复杂度的要求？
|
l*********8
发帖数: 4642 | 5 bool Convert(char * buf, int bufSize)
{
int length = strlen(buf);
int newLength = length;
for (int i=0; i
if (buf[i] == 'A')
newLength--;
else if(buf[i] == 'B')
newLength++;
if (newLength > bufSize - 1) return false;
int w = newLength-1;
for (int r = length-1; r>=0; r--) {
if(buf[r] != 'A')
buf[w--] = buf[r];
if (buf[r] == 'B')
buf[w--] = buf[r];
}
buf[newLength] = '\0';
return true;
} |
g*******4
发帖数: 155 | 6 这里面有一个假设的，就是这个char*指向的位置有足够的内存空间可用
不能因为处理后字符串超过原来长度就返回错误
【在 l*********8 的大作中提到】
: bool Convert(char * buf, int bufSize)
: {
: int length = strlen(buf);
: int newLength = length;
: for (int i=0; i: if (buf[i] == 'A')
: newLength--;
: else if(buf[i] == 'B')
: newLength++;
: if (newLength > bufSize - 1) return false;
|
l*********8
发帖数: 4642 | 7 Here bufLength is the length of the 内存空间, not the string.
【在 g*******4 的大作中提到】
: 这里面有一个假设的，就是这个char*指向的位置有足够的内存空间可用
: 不能因为处理后字符串超过原来长度就返回错误
|
l*********8
发帖数: 4642 | 8 Let me call it bufSize then :-)
【在 l*********8 的大作中提到】
: Here bufLength is the length of the 内存空间, not the string.
|
I*******l
发帖数: 203 | 9 I am confused here: it seems you may erase some of the original characters
in the string. For example, if newLength < length, then starting from the
end, you will overwrite the characters that have not been processed.
【在 l*********8 的大作中提到】
: bool Convert(char * buf, int bufSize)
: {
: int length = strlen(buf);
: int newLength = length;
: for (int i=0; i: if (buf[i] == 'A')
: newLength--;
: else if(buf[i] == 'B')
: newLength++;
: if (newLength > bufSize - 1) return false;
|
l*********8
发帖数: 4642 | 10 good catch! thanks!
【在 I*******l 的大作中提到】
: I am confused here: it seems you may erase some of the original characters
: in the string. For example, if newLength < length, then starting from the
: end, you will overwrite the characters that have not been processed.
|
|
|
m********a
发帖数: 559 | 11 有bug吧？如果newlength < length，你中间把原值覆盖了。前面一位说的先去A，再添
B应该是正确解法吧。
【在 l*********8 的大作中提到】
: bool Convert(char * buf, int bufSize)
: {
: int length = strlen(buf);
: int newLength = length;
: for (int i=0; i: if (buf[i] == 'A')
: newLength--;
: else if(buf[i] == 'B')
: newLength++;
: if (newLength > bufSize - 1) return false;
|
l*********8
发帖数: 4642 | 12 yes, InnerCool also pointed it out. thanks
【在 m********a 的大作中提到】
: 有bug吧？如果newlength < length，你中间把原值覆盖了。前面一位说的先去A，再添
: B应该是正确解法吧。
|
A*H
发帖数: 127 | 13 how to remove A inplace at first step?
【在 m********a 的大作中提到】
: 有bug吧？如果newlength < length，你中间把原值覆盖了。前面一位说的先去A，再添
: B应该是正确解法吧。
|
c****p
发帖数: 6474 | 14 把字符串从后往前移
【在 A*H 的大作中提到】
: how to remove A inplace at first step?
|
b***u
发帖数: 12010 | 15 这是O(n)..
【在 g*******4 的大作中提到】
: 这里面有一个假设的，就是这个char*指向的位置有足够的内存空间可用
: 不能因为处理后字符串超过原来长度就返回错误
|
c****p
发帖数: 6474 | 16 他说的是O1 space吧
【在 b***u 的大作中提到】
: 这是O(n)..
|
D********g
发帖数: 650 | 17 我的code：
先扫一遍找到A的个数和B的个数
然后再扫一遍处理A
再扫一遍处理B
code里处理A和B的算法不太一样，第二种更好一点。另外，有没有包子？
/*input is assumed to end at '\0' and input is assumed to be long enough to
hold the
* transformed string
* */
static char[] deleteADoubleB(final char[] input) {
if (input == null || input.length == 0) {
return input;
}
int aCount = 0, bCount = 0, originalLen = 0;
for (int i = 0; i < input.length; ++i) {
if (input[i] == 'A') {
aCount ++;
}
if (input[i] == 'B') {
bCount ++;
}
if (input[i] == '\0') {
originalLen = i;
break;
}
}
int offSet = 0;
int idx = 0;
while (offSet <= aCount) {
while (idx < originalLen && input[idx] != 'A' ) {
if (offSet > 0) {
input[idx - offSet] = input[idx];
}
idx ++;
}
if (idx == originalLen) {
break;
}
offSet ++;
idx ++;
}
int newEnd0 = originalLen - aCount - 1;
int newEnd1 = originalLen + bCount - aCount - 1;
while (newEnd0 >= 0) {
if (input[newEnd0] != 'B') {
input[newEnd1] = input[newEnd0];
newEnd1 --; newEnd0 --;
} else {
input[newEnd1] = 'B';
newEnd1 --;
input[newEnd1] = 'B';
newEnd1 --; newEnd0 --;
}
}
return input;
}
static void testDeleteADoubleB() {
char[] input = new char[] {};
System.out.println(Arrays.toString(deleteADoubleB(input)));
input = new char[] {'C','D','E', '\0'};
System.out.println(Arrays.toString(deleteADoubleB(input)));
input = new char[] {'A','D','B', '\0'};
System.out.println(Arrays.toString(deleteADoubleB(input)));
input = new char[] {'B', 'C', 'A','D','B','\0','\0'};
System.out.println(Arrays.toString(deleteADoubleB(input)));
}
【在 w****x 的大作中提到】
: 第一趟从左到右去A数B,
: 第二趟从右到左double B
|
K*******i
发帖数: 399 | |
r*****t
发帖数: 68 | 19 可不可以这样呢:
suppose 字符串长=n
1.在该字符串后面append原字符串 （得到2n 串）
2.j=0; i=n To 2n-1
对于追加字符串（n To 2n-1）:
if 'A', j 不变
if ‘B’， 位置j,j+1填‘B’， j=j+2
if 其他字符：位置j,填其他字符， j=j+1
3. 位置j 填‘\0’
【在 g*******4 的大作中提到】
: 处理一个字符串，删除里面所有的A，double所有的B
: 例子，输入 CAABD, 输出是CBBD
: 要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算
|
s******o
发帖数: 2233 | 20 void
Process(string& s) {
int size = s.size();
int count = 0;
for (int i = 0; i < size; ++i) {
if (s[i] == 'A') {
s[i] = '\0';
for (int j = i; j < size - 1; ++j) {
s[j] = s[j+1];
}
--size;
--i;
} else if (s[i] == 'B') {
count++;
}
}
int end = size + count - 1;
s.resize(end+1);
for (int i = size - 1; i >= 0; --i) {
if (s[i] == 'B') {
s[end--] = 'B';
s[end--] = 'B';
} else {
s[end--] = s[i];
}
}
}
【在 g*******4 的大作中提到】
: 处理一个字符串，删除里面所有的A，double所有的B
: 例子，输入 CAABD, 输出是CBBD
: 要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算
|
|
|
p*****2
发帖数: 21240 | |
s******e
发帖数: 114 | 22 要结合＂从左添＂和＂从右添＂，
比如一个CAABBBCAABAACB要分成三段
CAABB BCAAB AACB
CAABB 从左添：CBBBB
BCAAB 从右添：BBCBB
AACB 从左添：CBB
＂从左添＂的段都是A在B前，继续scan，直到AB的个数相同，即convert后长度不变。 |
m*******o
发帖数: 457 | 23 thanks!
【在 g*******4 的大作中提到】
: 处理一个字符串，删除里面所有的A，double所有的B
: 例子，输入 CAABD, 输出是CBBD
: 要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算
|
t****t
发帖数: 6806 | 24 第一遍处理A, 同时数B
第二遍处理B
to
【在 D********g 的大作中提到】
: 我的code：
: 先扫一遍找到A的个数和B的个数
: 然后再扫一遍处理A
: 再扫一遍处理B
: code里处理A和B的算法不太一样，第二种更好一点。另外，有没有包子？
: /*input is assumed to end at '\0' and input is assumed to be long enough to
: hold the
: * transformed string
: * */
: static char[] deleteADoubleB(final char[] input) {
|
r****k
发帖数: 21 | 25 void deleteADoubleB(char *str, int length)
{
if (str == NULL || length < 0) return;
int newLen = 0;
int bCount = 0;
for (int i = 0; i < str[i] !='\0'; i++)
{
if (str[i] != 'A')
{
str[newLen++] = str[i];
}
if (str[i] == 'B')
{
bCount++;
}
}
if (newLen + bCount > length) return;
int i = newLen - 1;
newLen += bCount;
str[newLen--] = '\0';
while (i>0)
{
str[newLen--] = str[i];
if (str[i] == 'B')
{
str[newLen--] = 'B';
}
i--;
}
} |
s******e
发帖数: 114 | 26 Test Case: ABCCCCCCCCCCCCCCC
nothing wrong, but there is unnecessary shift in your algorithm.
【在 r****k 的大作中提到】
: void deleteADoubleB(char *str, int length)
: {
: if (str == NULL || length < 0) return;
:
: int newLen = 0;
: int bCount = 0;
: for (int i = 0; i < str[i] !='\0'; i++)
: {
: if (str[i] != 'A')
: {
|
t**********h
发帖数: 2273 | 27 谢谢。
看来是把150题两道原题给揉在一起了。给一个string，删掉特定的字符。比如“I am
a student"删”aeiou".第二个，把一个string里所有的space替换成20%
【在 g*******4 的大作中提到】
: 处理一个字符串，删除里面所有的A，double所有的B
: 例子，输入 CAABD, 输出是CBBD
: 要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算
|
s*******f
发帖数: 1114 | 28 i only have scan 2 times version.
1st scan for to delete A and count B.
2nd scan double b from the end that we calculated from 1st scan.
【在 g*******4 的大作中提到】
: 处理一个字符串，删除里面所有的A，double所有的B
: 例子，输入 CAABD, 输出是CBBD
: 要求in space , O (1), no extra memory cost,因为字符串处理变长的空间不算
|
o****o
发帖数: 1398 | 29 public class StringProcessor {
//return new length
//assume ary is large enough
public static int process(char[] ary, int length) {
int i=0, j=-1;
int countB = 0;
while(i < length) {
if(j == -1) {
if(ary[i] == 'A')
j = i;
} else {
if(ary[i] != 'A') {
ary[j] = ary[i];
j++;
}
}
if(ary[i] == 'B')
countB++;
i++;
}
//j == new length
if(countB > 0) {
int n = j + countB - 1;
i = j-1;
while(i >= 0) {
ary[n] = ary[i];
n--;
if(ary[i] == 'B') {
ary[n] = ary[i];
n--;
}
i--;
}
}
return j + countB;
}
}
【在 w****x 的大作中提到】
: 第一趟从左到右去A数B,
: 第二趟从右到左double B
|
o****o
发帖数: 1398 | 30 改进一下
public class StringProcessor {
//return new length
//assume ary is large enough
public static int process(char[] ary, int length) {
int i=0, j=0;
int countB = 0;
while(i < length) {
char c = ary[i++];
if(c != 'A') ary[j++] = c;
if(c == 'B') countB++;
}
//j == new length
if(countB > 0) {
int n = j + countB - 1;
i = j - 1;
while(i >= 0) {
char c = ary[i--];
ary[n--] = c;
if(c == 'B') ary[n--] = c;
}
}
return j + countB;
}
【在 o****o 的大作中提到】
: public class StringProcessor {
: //return new length
: //assume ary is large enough
: public static int process(char[] ary, int length) {
: int i=0, j=-1;
: int countB = 0;
: while(i < length) {
: if(j == -1) {
: if(ary[i] == 'A')
: j = i;
|
|
|
t*****j
发帖数: 1105 | 31 nod，扫描两遍，第一遍数数计算 output string长度。
第二遍从后向前移动处理。
【在 c****p 的大作中提到】
: 把字符串从后往前移
|
y**********u
发帖数: 6366 | 32 这就不是O(1)了啊
【在 w****x 的大作中提到】
: 第一趟从左到右去A数B,
: 第二趟从右到左double B
|
m***y
发帖数: 1 | 33 同意楼上peking2。从前往后，去A，从后往前，double B。
C代码如下：
#include
#define MAX_S_LENGTH 1024
void remove_a_double_b(char *s) {
int i, j, n, na, nb, nc; // nc is number of characters other than A
na = nb = 0;
j = 0;
for (i = 0; s[i] != '\0'; i++) {
if (s[i] == 'A')
na++;
else {
s[j] = s[i];
j++;
if (s[i] == 'B')
nb++;
}
}
n = i;
nc = j;
i = n - na + nb;
s[i] = '\0';
i--;
for (j = nc - 1; j >= 0; j--) {
if (s[j] == 'B') {
s[i] = 'B';
i--;
s[i] = 'B';
i--;
}
else {
s[i] = s[j];
i--;
}
}
}
void main()
{
char s[MAX_S_LENGTH];
scanf("%s", s);
remove_a_double_b(s);
printf("%s\n", s);
}
【在 p*****2 的大作中提到】
: 从前往后再从后往前就可以了吧。
|
J**9
发帖数: 835 | 34 char *hkStringRemoveADoubleB(char *str)
{
if (!str) return NULL;
char *s=str;
char *d=str;
int countb = 0;
int len=0;
while(*s)
{
if (*s=='B') countb++; /// Count B
if(*s!='A') /// Remove A
{
*d++=*s++;
len++;
}
else
s++;
}
if(len)
{
s = str+(len+countb); ///New string length
*s = '\0';
s--;
d--;
while(d!=str)
{
if (*d=='B')
*s-- = 'B';
*s--=*d--;
}
if (*d=='B') /// If the first one is B
*s = 'B';
}
return str;
}
Test cases:
str1=CAABD
str1=CBBD
str1=ACAABDB
str1=CBBDBB
str1=BACAABDBA
str1=BBCBBDBB
str1=ABCCCCCCCCCCCCCCC
str1=BBCCCCCCCCCCCCCCC |
r*****s
发帖数: 74 | 35 Test case:
AAAAAAAAAAAAAAAAAAA
这样的输入怎么办 |
s****n
发帖数: 245 | |
e***s
发帖数: 799 | 37 弱问一句，如果JAVA怎么办？String是immutable,不可能in place。那用一个
StringBuilder直接见‘A'忽略，'B'写两次，其他照写。。。
是不是如果你说你写JAVA他就不考这题了？ |
f**l
发帖数: 44 | 38 Java 可以认为传进来的是char［］，然后算法就基本一样了。当然，如果非要追根问
底的话String.toCharArray()其实已经make了一个new copy了。。。感觉类似这种题都
是在很早以前存储比较贵，容量比较小的时候make sense，目前基本都是空间换时间。
。。但是如果面试题的话，没办法，咱们是做题的，没法评判考卷，呵呵。有空贴个
Java代码上来。 |
f**l
发帖数: 44 | 39 Java version:
/*
* Process string, remove 'A' and double 'B'
*/
public static String processString(char[] array, int realLen) {
int newLen = realLen;
int pos = 0;
for (int i = 0; i < realLen; i++) {
char c = array[i];
if (c == 'A')
newLen--;
else {
if (c == 'B')
newLen++;
array[pos++] = array[i];
}
}
int j = newLen - 1;
for (int i = pos - 1; i >= 0; i--) {
if (array[i] == 'B') {
array[j--] = 'B';
}
array[j--] = array[i];
}
return new String(array, 0, newLen);
} |
f**l
发帖数: 44 | 40 Related test cases:
@Test
public void testProcessString() {
String s1 = "CAABD";
String target1 = "CBBD";
Assert.assertEquals(target1, StringAndArray.processString(s1.
toCharArray(), s1.length()));
String s2 = "ACAABDB";
String target2 = "CBBDBB";
Assert.assertEquals(target2, StringAndArray.processString(s2.
toCharArray(), s2.length()));
String s3 = "BACAABDBA";
String target3 = "BBCBBDBB";
Assert.assertEquals(target3, StringAndArray.processString(s3.
toCharArray(), s3.length()));
String s4 = "ABCCCCCCCCCCCCCCC";
String target4 = "BBCCCCCCCCCCCCCCC";
Assert.assertEquals(target4, StringAndArray.processString(s4.
toCharArray(), s4.length()));
String s5 = "BBC";
int len5 = s5.length();
s5 += " ";
String target5 = "BBBBC";
Assert.assertEquals(target5, StringAndArray.processString(s5.
toCharArray(), len5));
} |
|
|
u******g
发帖数: 89 | 41 我想他是O(n)的意思。。。不可能O(1)啊你至少要把输入过一边。。当然如果n代表的
是输入的整个string那是O(1)的……
【在 y**********u 的大作中提到】
: 这就不是O(1)了啊
|
