请教一个编程题 - OurCoders (我们程序员)

amosji 回复于 2014年11月27日

抛砖引玉 假设输入只有字母和数字

#!/usr/bin/python
import re
def revert_string_recursively(strings):
 if len(strings) <= 0:
 return ''
 return strings[-1] + revert_string_recursively(strings[0:-1])
def main():
 with open('case.txt') as f:
 for line in f:
 sub_strings = re.findall('\d+|\D+', line.strip('\n'))
 print revert_string_recursively(sub_strings)
if __name__ == '__main__':
 main()

case.txt:

APPLE1234BOOK5678
APPLE
1234

sadcat 回复于 2014年11月27日

1楼 @amosji 谢谢回复!看了代码,方法是先把字符串根据字母,数字拆分成字符串数组,再通过递归,从后往前连接。如果不事先拆分字符串的话,实现起来比较复杂吧。

xiaotie 回复于 2014年11月27日

2楼 @sadcat 不拆分字符串的方法。

 public class WeightedChar : IComparable<WeightedChar>
 {
 public Char Char;
 public double Weight;
 public int CompareTo(WeightedChar other)
 {
 return this.Weight.CompareTo(other.Weight);
 }
 public static List<WeightedChar> Build(String txt)
 {
 // 给每个字符赋个权重。这里就不用递归了。那位有兴趣可以将这里转换为递归。
 List<WeightedChar> list = new List<WeightedChar>();
 if(String.IsNullOrEmpty(txt) == false)
 {
 double length = txt.Length;
 int level = 0;
 for (int idx = 0; idx < length; idx++)
 {
 if (idx > 0 && Char.IsDigit(txt[idx]) != Char.IsDigit(txt[idx - 1])) level++;
 list.Add(new WeightedChar { Char = txt[idx], Weight = -level + idx / length });
 }
 }
 return list;
 }
 public static void Test(String txt = "APPLE1234BOOK5678")
 {
 List<WeightedChar> list = Build(txt);
 list.Sort(); // SORT 可以用递归实现。直接调用库函数了。
 StringBuilder sb = new StringBuilder();
 foreach (WeightedChar item in list) sb.Append(item.Char);
 String result = sb.ToString();
 Console.WriteLine(result); // 5678BOOK1234APPLE
 }
 }

xiaotie 回复于 2014年11月27日

另一个版本,谁来改成递归版:

 public static void Insert(StringBuilder txt, Char c)
 {
 for(int i = 0; i < txt.Length; i++)
 {
 if( Char.IsDigit(txt[i]) != Char.IsDigit(c))
 {
 txt.Insert(i, c);
 return;
 }
 }
 txt.Append(c);
 }
 public static void Test2(String txt = "APPLE1234BOOK5678")
 {
 StringBuilder sb = new StringBuilder();
 foreach(Char c in txt)
 {
 Insert(sb, c);
 }
 Console.WriteLine(sb);
 //5678BOOK1234APPLE
 }

peterwang 回复于 2014年11月27日

pythonic string reversing

def reverse_words(s):
 i,l,r = 0,len(s),''
 for j in range(1,l+1):
 if j == l or s[j-1].isdigit() != s[j].isdigit():
 r += s[i:j][::-1]
 i = j
 return r[::-1]
if __name__ == '__main__':
 ss = ['APPLE1234BOOK5678','1234','abc', 'abc1234', '1234abc']
 for s in ss:
 print "%s -> %s" % (s, reverse_words(s))

amosji 回复于 2014年11月27日

不拆当然可以啦
但是你总要用某种方法判断哪一块是单词 哪一块是数字
下面的code 是先把每一个单词或数字反转 再把整个字符串反转
example: APPLE1234BOOK5678 -> ELPPA1234BOOK5678 -> ELPPA4321BOOK5678 -> ELPPA4321KOOB5678 -> ELPPA4321KOOB8765 -> 5678BOOK1234APPLE
其中反转字符串是递归实现的

#include <stdio.h>
#include <ctype.h>
void revert_sub_string(char *string, int start, int end) {
 if (start >= end) return;
 char temp = string[start];
 string[start] = string[end];
 string[end] = temp;
 revert_sub_string(string, start+1, end-1);
}
void revert_string_by_word(char *string) {
 int start = 0, i, string_length = 0;
 for (i = 0; string[i] != ''; i++) {
 if (isdigit(string[i]) != isdigit(string[i+1])) {
 revert_sub_string(string, start, i);
 start = i+1;
 }
 string_length++;
 }
 if (start != 0)
 revert_sub_string(string, 0, string_length-1);
}
int main() {
 char test_string[1024];
 while(scanf("%s", test_string) == 1) {
 revert_string_by_word(test_string);
 printf("%s\n", test_string);
 }
 return 0;
}

adad184 回复于 2014年11月27日

- (void)revert:(NSString*)str start:(int)index
{
 if ( index>=str.length )
 {
 return;
 }
 int len = 1;
 BOOL isNum = ( ([str characterAtIndex:index]>='0') && ([str characterAtIndex:index]<='9') );
 if ( isNum )
 {
 for ( int ind = index+1 ; ind < str.length ; ++ind )
 {
 if ( ([str characterAtIndex:ind] < '0') || ([str characterAtIndex:ind] > '9') )
 {
 break;
 }
 len++;
 }
 }
 else
 {
 for ( int ind = index+1 ; ind < str.length ; ++ind )
 {
 if ( ([str characterAtIndex:ind] < 'A') || ([str characterAtIndex:ind] > 'Z') )
 {
 break;
 }
 len++;
 }
 }
 [self revert:str start:index+len];
 NSLog(@"%@",[str substringWithRange:NSMakeRange(index, len)]);
}

测试

[self revert:@"APPLE1234BOOK5678" start:0];
2014年11月27日 17:25:54.483 MMParallaxCell[7838:1199123] 5678
2014年11月27日 17:25:54.484 MMParallaxCell[7838:1199123] BOOK
2014年11月27日 17:25:54.484 MMParallaxCell[7838:1199123] 1234
2014年11月27日 17:25:54.484 MMParallaxCell[7838:1199123] APPLE

newguy 回复于 2014年11月27日 | 更新于 2014年12月01日

看了 @peterwang 的解法,才知道python原来有isdigit这个函数,惭愧。python语法实在太优美了,附上我的答案:

def reverse(s):
 if len(s) <= 1:
 return s
 i = -2
 begin = s[-1]
 while -i <= len(s):
 if s[i].isdigit() != begin.isdigit():
 s = s[:i+1]
 break
 else:
 begin = s[i] + begin
 if begin == s:
 return s
 i = i - 1
 return begin + reverse(s)
input_str = raw_input("Your string: ")
print reverse(input_str)

amosji 回复于 2014年11月27日

8楼 @newguy 你的code有问题
比如1A2B 你的结果是B21A
事实上 只要输入字符串的前两个字符一个是数字一个是字母 你的结果就错啦
我想你的问题是在

if -i == len(s): 
 return s 

这里

newguy 回复于 2014年11月28日

9楼 @amosji 谢谢指出,我把那个判断去掉了,在

begin = s[i] + begin

后面加了一个判断语句。