数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
1 c+ I! f+ O* ?, O' Y
" z7 S1 f! ~/ j2 l- L. h+ L
解题思路：根据题目要求，比较两个相邻字母是否按照order排序；创建（map）letter_orders，记录字典顺序；
0 Q/ c) B0 @* }* p0 l0 q+ _
比较即可
4 |3 f' E7 O$ O
- ]# x0 j* A' V9 {0 h
class Solution {
9 O! t; F9 G- P5 |3 M' r+ l! K6 W
public:
) P) s- m- R+ O9 \; R
bool isAlienSorted(vector<string>& words, string order)
4 `$ t# c. g% F' C# z7 L2 ^
{
: n6 q c3 l* x; c& z4 r
int min_letter_length = words[0].length();
# ]4 {0 G$ S# I( A; r" c5 w6 e
map<char, int> letter_orders;
8 H3 w/ ?4 l9 ?/ Z/ [6 D
letter_orders[' '] = 0;//空字符比其他字符都小记为0
- |( H/ M; f: Q* F& F
for (int i = 0; i < order.length(); i++)
( Q% M. r( Y j2 E
{
6 y2 a# O9 }2 L
letter_orders[order
] = i + 1;
, n3 {/ ` [* y' t
}
. Y+ d, N3 A( s4 w! u$ A. ?
for (int i = 0; i < words.size() - 1; i++)
: _7 J! k4 ?2 J* }+ y: z# y
{
6 T6 x% f) O* y; `/ P# ]* |
if (!check(words
, words[i + 1], letter_orders))
7 a$ j' W* u6 t5 c P# A
return false;
9 u ^5 Y) _% y0 V3 g7 z1 X% P' V
}
4 s7 E' G" _. D+ C" y. `! K8 z+ e
return true;
0 M' j* l, w" o/ J: ]: C, c+ b" B
}
* Y! g% B/ _% @7 Q5 f0 K* V
bool check(string a, string b, map<char, int>letter_orders)
" G/ J* E3 }# [* z Z) f6 R
{
0 y9 {( a& e. _4 @7 u
int sign = -1;
' |8 i& F$ U9 f9 n8 s5 |6 h
for (int i = 0; i < a.length(); i++)
) P9 y3 g, K' W& X+ T5 t7 E9 `
{
3 N, z, B' a5 V) p3 O" w: {
if (letter_orders[a
] < letter_orders[b
])
, R. h% p( [+ R; Q1 g0 d
{
8 K( d4 a: m2 @+ Y+ \; n
return true;
: w* b3 x: @' h! k" q. g3 T
}
1 ^# {& N6 w0 m( c$ ~# V6 N
else if (letter_orders[a
] > letter_orders[b
])
0 _0 g2 n1 N4 g
{
* l: O4 L$ ^6 L; B
return false;
_" i; {0 W' V# u$ B X* \) m% |6 I
}
* z( z" M3 ~3 V) K; ^( \1 ]7 w* l6 W
}
E$ J8 K$ _9 T. O
return true;
) x1 y/ O9 g3 [& t. y$ |
}
( p$ r& t' _" ^# ?) G8 g
};
0 ]0 |+ [' u# f7 m- c1 T1 g
---------------------
2 p9 p! t, Q- G3 b8 C& N9 U" ]( n! A
: q% X: @5 B4 ?) Z' K
9 o; k: Q D8 ^/ A& @1 v& S
3 {9 q# w/ Q3 G3 D6 F# h6 v/ T
% H/ X3 I- A7 e* w# z) o
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗，还有数据库从哪里找
) Q3 `) x$ k+ [8 H
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
