最近在网上看到一道关于字符串操作的算法题,不过原题的表述以及给出的数据都有问题.这里我给出修正后的题目:
题目:
设计一个方法 String encode(String str),对字符串str进行如下转换操作为一个新字符串:
逐个扫描str的每个字符,
1.若当前字符为'_',则添加"\UL"到新字符串; 否则:
2.若当前字符表示一大于0的数字N,且该字符不是最后一个字符,则将后继字符添加N+1次到新字符串;否则:
3.直接添加当前字符到新字符串.
并且用一个字符'_'将相邻的变换隔开
并设计一个String decode(String code)方法执行encode的逆操作,即将由encode(str)方法返回的字符串还原为str.
encode方法的设计没有任何难度,只需要把题目"直译"成程序代码就OK了,有难度的地方在于decode方法.注意到字符串中的字符在encode之后的新字符串中是由'_'分开的,并且原字符串中的每个字符只由这个字符串变换后的字符串以及其后继字符有关,因此我们很容易可以想到先将编码后的字符串按'_'分解成一系列字符串,其中每个字符串对应原字符串的一个字符,然后从后向前一个个求出其所表示的字符.算法的大体想法就是这样,只有一点要注意:类似"4_"这种数字后跟'_'的情形会被编码成一列连续的"_____",应该区分出这种情形并加以处理
.
其实如果对压缩算法有所了解的话,很容易看出这个题目其实是行程编码(
Run-Length Encoding
)的一个变形.
下面给出本题的代码:
java 代码
-
-
-
-
- import
java.util.Scanner;
- public
class
StringCode{
-
public
static
void
main(String[] args){
- Scanner s =
new
Scanner(System.in);
-
while
(
true
){
- String text =s.next();
-
if
(
"exit"
.equalsIgnoreCase(text))
break
;
- String code =encode(text);
-
boolean
flags =
true
;
-
try
{
-
if
(!decode(code).equals(text)) flags =
false
;
- }
catch
(IllegalStateException e){
- flags =
false
;
- }
-
if
(flags){
- System.out.println(
"Code :"
+code);
- }
-
else
{
- System.out.println(
"Error code :"
+code);
- }
- }
- }
-
private
static
final
String ESC_S =
"\\UL"
;
-
private
static
final
char
ESC_C = '_';
-
-
-
-
-
-
public
static
String decode(String str)
throws
IllegalStateException{
- StringBuilder sb =
new
StringBuilder();
-
char
next =
0xffff
;
-
int
end =str.length(), start;
-
while
(end>
0
){
-
if
(next==ESC_C&&str.charAt(end-
1
)==ESC_C){
-
for
(start =end -
1
;start>
0
&&str.charAt(start-
1
)==ESC_C;start--);
-
if
(start!=
0
) start ++;
- }
-
else
{
- start =str.lastIndexOf(ESC_C,end -
1
) +
1
;
- }
-
- String code =str.substring(start,end);
-
-
if
(code.equals(ESC_S)){
- next = ESC_C;
- }
-
else
if
(end-start==
1
){
- next = code.charAt(
0
);
- }
-
else
{
-
for
(
int
index =
0
;index
-
if
(code.charAt(index)!= next)
throw
new
IllegalStateException(
"Illegal code: ["
+start+
","
+end+
"]"
);
- next =(
char
)('
0
'+end-start-
1
);
- }
- sb.insert(
0
,next);
- end =start -
1
;
- }
-
return
sb.toString();
- }
-
-
-
-
-
public
static
String encode(String str){
- StringBuilder sb =
new
StringBuilder();
-
for
(
int
index =
0
;index
-
char
c =str.charAt(index);
-
-
if
(c==ESC_C){
- sb.append(ESC_S);
- }
-
else
if
(c>'
0
'&&c<='
9
'&&index+
1
-
char
next =str.charAt(index+
1
);
-
for
(
int
count =c-'
0
';count>=
0
;count--)
- sb.append(next);
- }
-
else
{
- sb.append(c);
- }
-
-
if
(index+
1
- }
-
return
sb.toString();
- }
- }
分享到:
- 2007-08-01 19:46
- 浏览 2734
- 评论(2)
- 论坛回复 / 浏览 (2 / 3922)
- 查看更多
相关推荐
* 输入第一个字符串: * shao * 输入第二个字符串: * shaod * 最短编辑距离 * 1 (2)本题思路分析 * 定义两个字符串s1 ,s2 * 比较两字符串的某两个相同位置时:(例如s1[i] s2[j] 这时i=j)有三种办法 * 1.把...
包含面试中经常考的数据结构,算法以及字符串的操作等常见的面试问题,经典解答
麦克风没插好,本节没声音;...主要讲解了数组做参数,以及一些作业中要求做的一些字符串函数。 如果实在想学这一节内容,可以参照我们推出最新的VS2015的视频教程。 讲的内容基本是一样的,全套视频无损失。
程序员面试笔试合集,包括FAQ,内存管理、数据结构和算法、字符串操作等常见题,绝对能在笔试面试中加分!chm格式,方便阅读!
题目:给定一个字符串,输出其所有子字符串,例如给定字符串abc,则输出 :a,b,c,d,ab,bc,cd,abc,bcd,abcd。 分析:今天看到csdn博客上面的一题,说是阿里巴巴电面的题目。初看到这道题的时候,就感觉很...
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、打印九九乘法表、判断素数、快速排序的递归实现和非递归实现、随机数、字符串操作、50人围成一圈,数到3和3的倍数的人出局,最后剩下的人是谁。...
字符串-Java解题分析-学习资料.zip 是一个关于Java中字符串处理的解题分析和学习资料的压缩文件。该资源主要涵盖了Java中字符串的基本操作、常见算法和问题解析,旨在帮助开发者深入理解字符串在Java中的运用,提高...
该资源是一个入门级别的C++算法练习,旨在帮助读者熟悉两串旋转的操作和相关算法。通过这个练习,读者将学习如何在C++中编写代码来判断两个字符串是否是通过旋转得到的,并解决与字符串旋转相关的算法问题。 文档中...
思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止。 def longestCommonPrefix(self, ...
主要介绍了C#常见算法面试题,包含了常见的排序、字符串操作、类的操作等技巧,需要的朋友可以参考下
本题提出了一些关于将字符串x[1..m]转换成y[1..n]的操作。这些操作有复制、替代、删除、插入、互换和终止。这些操作所需的开销是不同的,但每个操作的开销都可以看是一个我们已经的常量,我们假设复制和替代这类操作...
java上机试题 非常经典 SQL 编程 不限制语言于不同的字符串,我们希望能有办法判断相似程度,我们定义了一套操作方法来把两个不相同的字符串变得...给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?
第一章 字符串 o 1.0 本章导读 o 1.1 旋转字符串 o 1.2 字符串包含 o 1.3 字符串转换成整数 o 1.4 回文判断 o 1.5 最长回文子串 o 1.6 字符串的全排列 o 1.10 本章习题 第二章 数组 o 2.0 本章导读 o 2.1 寻找最小的...
在华为OD机试真题中,应聘者需要解决一系列的算法和数据结构问题,例如字符串处理、数组操作、链表操作、树操作、图操作等等。此外,应聘者还需要熟练掌握编程语言,例如C++、Java、Python等等,能够熟练地使用各种...
数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。 数据结构是为算法服务的,...算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
DFS(深度优先遍历)与BFS(广度优先遍历)算法是基于树和图结构...然而,对于字符串和数组类的结构,我自己在开始的时候很难将其与DFS和BFS算法结合起来。所以为了更深入的理解DFS和BFS算法的精髓,这里针对这些数据
字符串相似度 经典算法题每日演练——第四题 最长公共子序列 经典算法题每日演练——第三题 猴子吃桃 经典算法题每日演练——第二题 五家共井 经典算法题每日演练——第一题 百钱买百鸡 开发利器系列(1)介绍一个小...
举例:题目: 给定一个字符串,其中包含大小写字母、数字和特殊字符,请编写一个程序,统计并输出其中的字母、数字和特殊字符的个数 以上是一些常见的蓝桥杯C++案例题和模拟题的示例。这些题目涵盖了各种算法和数据...
2. 字符串处理:字符串的基本操作、模式匹配、字符串编码等。 3. 数值计算:大数运算、进制转换、数值处理等。 4. 位运算:利用位运算进行编码、加密、压缩等。 5. 递归与动态规划:利用递归思想和动态规划解决复杂...
请编写一个字符串过滤程序,若字符串中出现多个相同的字符,将非首次出现的字符过滤掉。 比如字符串“abacacde”过滤结果为“abcde”。 要求实现函数:void stringFilter(const char *pInputStr, long lInputLen, ...