- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564647 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174617
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
|
953. 验证外星语词典
# K! g9 G: A- F+ \5 y0 y) O9 g E7 G9 f
解题思路:根据题目要求,比较两个相邻字母是否按照order排序;创建(map)letter_orders,记录字典顺序;) T# a4 [, q. `2 r
比较即可
$ m( E+ B. Z: q& e* ~/ I# @7 W2 P( Z* L! n8 x2 z! ?
class Solution {
& ~7 [! _3 ^4 }/ t3 U# ]( ^public:/ P* J/ v Z& t# |, P
bool isAlienSorted(vector<string>& words, string order)0 s+ n8 T% ^6 ]1 u3 y
{
# j5 J9 Y3 h- X9 D int min_letter_length = words[0].length();( ~: L# R/ D) r7 A9 K- ?
map<char, int> letter_orders;
6 n. x+ N% u) v$ k8 X6 i' y4 E, r letter_orders[' '] = 0;//空字符比其他字符都小记为0. u6 i4 B p( U9 H' G8 ?% S4 b
for (int i = 0; i < order.length(); i++)
) k: Y4 Y/ S, f8 b* @4 f {( J v( r5 u8 i. d9 Q* }4 Q0 s
letter_orders[order] = i + 1; U/ S- ?) [" _- U7 x4 X/ q
}
3 \( C" C* ]6 A for (int i = 0; i < words.size() - 1; i++)* C7 K6 J/ b! E8 V- ?# h% t
{: f' J1 E% w. o' [
if (!check(words, words[i + 1], letter_orders))% }: F4 k" ?. }4 M) t0 p3 f
return false; t d1 Q8 g- `, Y4 M* S
}
) u% `( e) C { return true;; p) |4 B. c @
}: M' Q* P& j: f$ I9 D: f3 O/ \
bool check(string a, string b, map<char, int>letter_orders)
& J8 Q8 ]* t! z {
) ~1 i3 d+ s/ y; [4 o( k int sign = -1;
& f. N |; n/ u3 Q/ X for (int i = 0; i < a.length(); i++)
. E2 P+ ` V# k {
( t4 N k9 b, Q& j if (letter_orders[a] < letter_orders[b])% q( T8 _ i$ N E0 k. Z
{
" e1 W: j5 r( B return true;* ]$ ]9 G! s6 @' m- e
}
" E! t; w" ]: t7 F' M; Q else if (letter_orders[a] > letter_orders[b])9 U1 _7 J! d/ a7 Z6 o- U3 C
{+ G: }. I& P; H: ]' |
return false;# s; j9 j0 O% ]* M5 \
}' V, M5 S7 ?& B& L
}
" l, }8 X% l t# A) H8 e$ D* O return true;
* v) G, R8 j4 v, L. K: M4 I }
7 z2 T5 T* B u7 [. B};
- W, G: h: P! F2 M3 S' P--------------------- ! G- U% A" e8 N9 f8 O. L" D
2 @# \$ T8 E: D) T a& g
0 \& I. B6 d+ u# d
% g" c- @" e) y% h( [( V2 f8 U: U( i2 s) S1 p3 V
|
zan
|