MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 401 - Palindromes
AOAPC II

UVaOJ 401 - Palindromes

Chai
2021-11-24 0:00:00在线评测阅读 277

问题描述

p401

原题链接:UVaOJ 401 - Palindromes

相关说明:本题为《算法竞赛入门经典(第2版)》例题 3-3

解法一:模拟

模拟读入,每次读一行字符串 s ,然后判断是否是回文串或镜像串:

  • 回文串:对于每个 s[i] 都必须满足 s[i]==s[len-i-1], 这个验证起来比较简单;
  • 镜像串:对于每个 s[i] 都必须满足 FindMirror(s[i])==s[len-i-1], 需要知道如何设计 FindMirror 函数

我们可以借助字符串常量 MIRR_ALPHAS 和 MIRR_NUMBER 来建立字符(字母和数字)到其镜像字符的映射 ,实现上用不同字符编码的相对偏移量当作对应索引值。同时这里在处理输出字符串时用到了一些技巧,由于回文串和镜像串都是简单的 0/1 关系,所以可以用二进制来映射所有的 NUM_CASE = 4 种情况。

容易忽视的地方:此题的输出需要在输入字符串后面接内容,因此在从标准流读入的时候记得关注换行符的处理。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
 
using namespace std;
 
// For comparison:        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
char const* MIRR_ALPHAS = "A   3  HIL JM O   2TUVWXY5";
char const* MIRR_NUMBER = "1SE Z  8 ";
//                        "123456789"
 
const int NUM_CASE = 4;
const array<string, NUM_CASE> SUFFIX = {
    " -- is not a palindrome.", " -- is a regular palindrome.",
    " -- is a mirrored string.", " -- is a mirrored palindrome."};
 
char FindMirror(const char& ch) {
  if (isalpha(ch))
    return MIRR_ALPHAS[ch - 'A'];
  else  // isdigit
    return MIRR_NUMBER[ch - '1'];
}
 
int main() {
  string s;
  while (getline(cin, s)) {
    int len = s.size();
    bool is_palindrome = 1, is_mirrored = 1;
    for (int i = 0; (is_palindrome || is_mirrored) && i < (len + 1) / 2; ++i) {
      char mirr_char = FindMirror(s[i]);
      if (mirr_char != s[len - i - 1]) is_mirrored = 0;
      if (s[i] != s[len - i - 1]) is_palindrome = 0;
    }
    cout << s + SUFFIX[is_palindrome + is_mirrored * 2] << "\n\n";
  }
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
MIRR_ALPHAS = "A   3  HIL JM O   2TUVWXY5"
MIRR_NUMBER = "1SE Z  8 "
 
SUFFIX = [" -- is not a palindrome.",
          " -- is a regular palindrome.",
          " -- is a mirrored string.",
          " -- is a mirrored palindrome."]
 
 
def find_mirr_char(ch):
    return MIRR_ALPHAS[ord(ch) - ord("A")] if ch.isalpha() else MIRR_NUMBER[ord(ch) - ord("1")]
 
while True:
    try:
        line = input()
        is_palindrome = 1
        is_mirrored = 1
        for i, _ in enumerate(line):
            mirr_char = find_mirr_char(line[i])
            if mirr_char != line[len(line) - i - 1]:
                is_mirrored = 0
            if line[i] != line[len(line) - i - 1]:
                is_palindrome = 0
        print(line + SUFFIX[is_palindrome + is_mirrored * 2], end="\n\n")
    except EOFError:
        break
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz