- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我在我的学校开始使用 C 并且(因为我正在慢慢结束)我遇到了一个关于编程 anagram 检查器的问题。经过一番思考,除了为每个特定字母设置一个单独的计数器之外,我仍然想不出任何其他东西,如果计数器匹配,那将是一个字谜。但这似乎写起来太长了(尤其是在纸上)。所以我通过谷歌搜索某种答案,寻找一个变位词求解器并设法找到了一些代码,但有一件事我不明白:
#include <stdio.h>
int check_anagram(char [], char []);
int main() {
char a[100], b[100];
int flag;
printf("Enter first string\n");
gets(a);
printf("Enter second string\n");
gets(b);
flag = check_anagram(a, b);
if (flag == 1)
printf("\"%s\" and \"%s\" are anagrams.\n", a, b);
else
printf("\"%s\" and \"%s\" are not anagrams.\n", a, b);
return 0;
}
int check_anagram(char a[], char b[]) {
int first[26] = {0}, second[26] = {0}, c = 0;
while (a[c] != '\0') {
first[a[c] - 'a']++;
c++;
}
c = 0;
while (b[c] != '\0') {
second[b[c] - 'a']++;
c++;
}
for (c = 0; c < 26; c++) {
if (first[c] != second[c])
return 0;
}
return 1;
}
起初我认为这对长度超过 26 个字母的字谜不起作用,所以我尝试了一些长度超过 26 个的随机字符串,它确实有效。然而,当我浏览代码时,我发现我无法理解什么:first[a[c]-'a']++;
和 second[b[c]-'a']++;
意思是。有人可以澄清这是什么,它做什么,或者至少我应该寻找什么来实现这些事情,因为它在我的脑海中加起来不太好。
编辑 1- 首先你们的速度很快...- 其次,如果我理解正确的话,这个程序应该不能很好地处理大写字母或不同的大写字母(例如:HELLO 和 hello)?
最佳答案
这是一个常用的技巧,真的:a
是一个字符数组,每个字符都是一个ASCII值(即numeric,int兼容),所以你可以在数学表达式中使用它。 c
是一个int,用于遍历字符数组a
。假设 a
中的所有字符都是小写字母,那么表达式
a[c] - 'a'
a
的计算结果为 0
,b
的计算结果为 1
,依此类推。因为 first
是一个整数数组,长度为 26 (int first[26]
),每个小写字母都有一个有效的对应索引 ('a' - ' a' = 0, 'z' - 'a' = 25), 所以你基本上是在计算每个字符的出现次数。 second[b[c] - 'a']++
对第二个字符串执行完全相同的操作:计算字符串中每个字母的出现次数。
最后,您将遍历这些字母计数数组,比较每个字母的值 (occ.count)。如果所有字母在两个字符串中出现的次数相同,那么您正在处理一个变位词。如果不是,您将返回 0
。
这个技巧更常用于将数字转换为整数:
char foo[] = "123";
int result = 0;
for (int i=0;foo[i] != 0;++i)
result = result * 10 + (foo[i] - '0');
printf("String: %s vs int: %d\n", foo, result);
Char Dec Oct Hex | Char Dec Oct Hex | Char Dec Oct Hex | Char Dec Oct Hex-------------------------------------------------------------------------------------(nul) 0 0000 0x00 | (sp) 32 0040 0x20 | @ 64 0100 0x40 | ` 96 0140 0x60(soh) 1 0001 0x01 | ! 33 0041 0x21 | A 65 0101 0x41 | a 97 0141 0x61(stx) 2 0002 0x02 | " 34 0042 0x22 | B 66 0102 0x42 | b 98 0142 0x62(etx) 3 0003 0x03 | # 35 0043 0x23 | C 67 0103 0x43 | c 99 0143 0x63(eot) 4 0004 0x04 | $ 36 0044 0x24 | D 68 0104 0x44 | d 100 0144 0x64(enq) 5 0005 0x05 | % 37 0045 0x25 | E 69 0105 0x45 | e 101 0145 0x65(ack) 6 0006 0x06 | & 38 0046 0x26 | F 70 0106 0x46 | f 102 0146 0x66(bel) 7 0007 0x07 | ' 39 0047 0x27 | G 71 0107 0x47 | g 103 0147 0x67(bs) 8 0010 0x08 | ( 40 0050 0x28 | H 72 0110 0x48 | h 104 0150 0x68(ht) 9 0011 0x09 | ) 41 0051 0x29 | I 73 0111 0x49 | i 105 0151 0x69(nl) 10 0012 0x0a | * 42 0052 0x2a | J 74 0112 0x4a | j 106 0152 0x6a(vt) 11 0013 0x0b | + 43 0053 0x2b | K 75 0113 0x4b | k 107 0153 0x6b(np) 12 0014 0x0c | , 44 0054 0x2c | L 76 0114 0x4c | l 108 0154 0x6c(cr) 13 0015 0x0d | - 45 0055 0x2d | M 77 0115 0x4d | m 109 0155 0x6d(so) 14 0016 0x0e | . 46 0056 0x2e | N 78 0116 0x4e | n 110 0156 0x6e(si) 15 0017 0x0f | / 47 0057 0x2f | O 79 0117 0x4f | o 111 0157 0x6f(dle) 16 0020 0x10 | 0 48 0060 0x30 | P 80 0120 0x50 | p 112 0160 0x70(dc1) 17 0021 0x11 | 1 49 0061 0x31 | Q 81 0121 0x51 | q 113 0161 0x71(dc2) 18 0022 0x12 | 2 50 0062 0x32 | R 82 0122 0x52 | r 114 0162 0x72(dc3) 19 0023 0x13 | 3 51 0063 0x33 | S 83 0123 0x53 | s 115 0163 0x73(dc4) 20 0024 0x14 | 4 52 0064 0x34 | T 84 0124 0x54 | t 116 0164 0x74(nak) 21 0025 0x15 | 5 53 0065 0x35 | U 85 0125 0x55 | u 117 0165 0x75(syn) 22 0026 0x16 | 6 54 0066 0x36 | V 86 0126 0x56 | v 118 0166 0x76(etb) 23 0027 0x17 | 7 55 0067 0x37 | W 87 0127 0x57 | w 119 0167 0x77(can) 24 0030 0x18 | 8 56 0070 0x38 | X 88 0130 0x58 | x 120 0170 0x78(em) 25 0031 0x19 | 9 57 0071 0x39 | Y 89 0131 0x59 | y 121 0171 0x79(sub) 26 0032 0x1a | : 58 0072 0x3a | Z 90 0132 0x5a | z 122 0172 0x7a(esc) 27 0033 0x1b | ; 59 0073 0x3b | [ 91 0133 0x5b | { 123 0173 0x7b(fs) 28 0034 0x1c | 62 0076 0x3e | ^ 94 0136 0x5e | ~ 126 0176 0x7e(us) 31 0037 0x1f | ? 63 0077 0x3f | _ 95 0137 0x5f | (del) 127 0177 0x7f
In short, then: read first[a[c] -'a']++;
as though it says:
first[a[c] - 97]++;//a[c] will be value between 97 and 122 so first[0..25]++
由于您不是 100% 了解在处理大写字符串时可能出现的问题,下面是如果您传递 "FOO" 和“OOF” 到您的函数:
int first[26] = {0};// valid indexes are 0 to 25
//if a[c] == 'F', this evaluates to first[65-97] or first[-32]
first[a[c] - 'a']++;//DANGER: Out of bounds!
您可能没有立即注意到问题的原因很简单,因为您将一个字符数组(一个字符串)传递给您的函数。一旦传递给函数,数组就会衰减为指针。可以说,数组几乎总是衰减为指针:
The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).
这意味着写a[c]
和写*(a+c)
是一样的,写first[a[c] - ' a']
等同于:*(first + (a[c] - 'a'));
,在这种情况下可以计算为 first[-32]
,这当然与 *(first - 32);
相同。
这要求您的机器获取 first[0]
的地址,并向后移动 32 步(每一步都是 sizeof(int)
)。您无法知道正在访问的内存中有什么:陷阱值、其他变量……任何事情都可能发生。此类表达式的行为未定义。
要解决此问题,您可以检查以确保字符在 a-z
范围内,如下所示:
if (a[c] > 96 && a[c] <= 'z')//96 == 'a' -1
first[a[c] -'a']++;
else
return -1;//indicate error
或简单地转换为小写:
首先[tolower(a[c]) - 'a']++;
调用 tolower
天真地假设 a
中的字符将是大写或小写字母。这不一定是这种情况,所以如果我是你,我会同时做:转换为较低的,然后检查生成的字符是否确实是一个字母(理论上,你的函数可以接收像 这样的字符串” foo: 123!",包含空格、数字和其他字符)。
总而言之,您可以简单地将first
和second
的大小增加到256
,然后这样写:
first[a[c]]++;
//and
second[b[c]]++;
这解决了大小写问题,也解决了 EBCDIC 与 ASCII 的问题。检查字谜时,您可以安全地跳过第一个元素(first[0]
现在只计算终止 nul 字符,这无论如何都没有用)。
关于C 什么是 ""first[a[c] -'a' ]++;",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34618584/
我是一名优秀的程序员,十分优秀!