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

UVaOJ 1584 - Circular Sequence

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

问题描述

p1584

原题链接:UVaOJ 1584 - Circular Sequence

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

解法一:模拟

字典序(lexicographical order)概念题,可以自己实现字符串字典序的比较逻辑(这里选择调用 string.compare 方法)。另外需要实现一个循环左移 k 位操作(对于此题 k==1 ),可以当成是拆开成两个子串 s1+s2 的调换位置拼接,变成 s2+s1, 记得在多次左移操作的同时比较字典序维护 ans 的值。

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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    string seq;
    cin >> seq;
    if (seq.length() == 1) {
      cout << seq << endl;
      continue;
    }
 
    string cur = seq, ans = seq;
    for (int i = 1; i < seq.length(); ++i) {
      cur = cur.substr(1, cur.length() - 1) + cur.substr(0, 1);
      if (cur.compare(ans) < 0) ans = cur;
    }
    cout << ans << endl;
  }
  return 0;
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
t = int(input())
for _ in range(t):
    seq = input()
    if len(seq) == 1:
        print(seq)
        continue
 
    cur = ans = seq
    for i in range(1, len(seq)):
        cur = cur[1:len(cur)] + cur[:1]
        if cur < ans:
            ans = cur
    print(ans)
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz