ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

数据结构:变位词问题的解法 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

数据结构:变位词问题的解法

Data Structures: Anagram Problem Solution

嗨 我是Gayle Laakmann McDowell 《程序员面试金典》的作者
Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.
今天我们要解决变位词问题
Today I’m going to solve a problem called making anagrams.
该问题描述如下
This problem goes as follows: You have
你有两个字符串 只包含小写字母“a”到“z”
two strings, just with the lowercase characters, “a” to “z”,
你需要从这两个字符串中去掉多少字符 才能使它们互为变位词呢
how many characters would you have to remove from the two strings to make them anagrams?
你可能还记得 变位词就是单词的排列
So, anagrams as you might remember are just permutations of a word,
即单词中字母的重新排列
so rearrangements of the words.
所以如果两个词是变位词 就意味着它们包含的字符相同
So for two words to be anagrams it means that they have the same characters but just
只是顺序不同 比如说你有两个词
in different orders. So for example you have the input
hello和billion 你一共需要去掉6个字符:hello中的“h”和“e”
hello and billion you’d have to remove six characters total – the “h” and the “e” from
billion中的“b” “i” “i” “n” 然后这两个字符串
hello and the “b” “i” “i” “n” from billion and then that will leave you with “l” “l” and “o”
就都剩下了“l” “l” “o” 所以对于任意两个字符串
in each of the two strings. So given two arbitrary strings how many characters
你需要从每个字符串中移除多少字符才能使他们互为变位词 变位词就是……
would you have to remove from each string to make them anagrams? Well anagrams are..
它们字符组成相同 并且每个字符的个数也相同
…they have the same exact characters and the same number of each characters,
而顺序不同 所以如果你想知道……
without the order mattering. So if you want to know…if you have just
如果你有字符串“aaa”和“a” 并且你想让它们互为变位词
the string “a” “a” “a” and “a” and you want to make those two things anagrams of each
你就必须从第一个字符串中移除两个“a”
other, you’d have to remove 2 a’s from the first string.
字符很多的情况下 处理步骤也基本相同
So if we have a whole bunch of characters it’s the same process essentially,
如果我们想让两个
if we want to make two
字符串互为变位词 只需数出它们中每个字符出现的次数
strings anagrams of each other, count how many times each character appears in each
然后计算它们的差值 我们看一下代码吧
string and then look at the difference between those values. So let’s turn to
我已经有了一个处理输入的主函数
the code now. So I already have a main function written that handles my input,
现在我只需要写这个函数 这里的代码逻辑就是
so now I just need to write this function. Okay. What the logic here is
数出每个字符出现的次数
going to be is just count how many times each character appears, and then
然后计算它们之间的差值 “int charcount1=”——
get the delta between these. So int charcount1 is going to be – I’ll
我会把这个操作放在另一个函数中 稍后再写它
just push this off to another function I’m not going to write it right now –
——“getCharCount(first)” 对第二个字符串也执行相同的操作
get char counts of first. Then, I do basically the same thing for the second
然后返回它们的差值 你可以看到
string and then I return the delta between these. Okay. So note here that I’ve
这里的模块化程度已经非常高了 这是一种好的做法
been pretty aggressive with modularization. That’s kind of a good thing to do in order to
它可以展现出良好的编码风格
show great coding style.
现在我们看一下getCharCount函数是怎样实现的
Okay, now let’s turn to how get char works, get char counts works.
它会接收一个字符串参数 我就把它叫做“s”
So, that’s going to take in a string, I’ll just call it “s,”
我要创建一个数组
and it’s going to create, so it’s gonna
它的每个位置对应一个字母
need an array with one slot for each letter.
我就把它叫做charCounts
So I’m going to call this charCounts
它表示每个字母的个数
and it’s going to be a size number of letters
然后我们要遍历每个字符串
and then it’s going to go through each string,
每个字符 “for(int i = 0;
each character, and so for int i equals 0
i < s.length();
i less than s dot length,
i++)”
i++
“char c = s.charAt(i);”
char c equals s dot char at i.
然后我们需要做一些转换 比如“a”到0 “b”到1 “c”到2等
And then I need to convert like “a” to 0, “b” to 1, “c” to 2 etc.
一种实现方式是计算它们的偏移量
So one way of doing that is I get the offset
所以我可以把字符“a”
so I can take the character “a”
转换为它的ASCII码
and convert that to its ASCII code.
下一个整型数就是字符“b”
Then the character “b” will be the next integer.
在Java里 你可以认为整型数……
So in Java we can kind of treat integers,
你可以认为字符就像整型数一样
you can treat characters sort of as integers and so
这样做就可以得到字符“a”的值
doing this will get the character value of “a”
如果用“b”减去“a” 可以得到1
so, if I do “b” minus “a” I’d actually get 1.
所以这里的变量code就等于
So the code here is going to be
字符c减去这个偏移量
this character “c” minus this offset
这样我们就可以得到“a”为0 “b”为1 “c”为2等
and then so that’s going to give me like “a” to 0, “b” to 1, “c” to 2 etc.
然后只需要给code表示的值加1 并且返回这个数组
then I just need to increment the value of that code and return that array.
最后一个方法是getDelta函数
My final method is this getDelta function
它需要接收
and it’s going to take in
两个字符串 不 是两个数组
two strings, two arrays,
并计算每个对应值的差值
and compute the delta between each value.
所以
So,
我要写一些基本的错误处理语句
I’ll do some very basic error handling right now.
理想情况下 我可能应该抛出一个异常
In an ideal world I should probably, you know, throw an exception at that,
但这里我们就只返回一个-1 所以这两个数组长度必须相同
but I’m just going to give it a negative one, so the arrays need to be the same length.
好了
Okay,
现在我要遍历这个数组中的每个值
now I just need to walk through each value in the arrays
并计算它们差的绝对值
and compute the absolute value of their differences.
所以
So,
“math.abs(array1[i]
math dot absolute value of array of 1 of
-array2[i])”
i minus array 2 of i
然后是“delta += difference;” “return delta;”
and delta plus equals difference return delta.
现在我们来看一下它的效果
Okay, now let’s see how this works.
运行它
I’ll run this.
我们通过了测试示例 非常棒 我要尝试一些稍微高级的测试案例
Alright! We passed our test cases, that’s fantastic. I’ll try a slightly more advanced one.
看起来我们做的不错 现在检查一下代码的运行流程
Looks like we’re doing great, so let’s review how our code works.
我们有一个numberNeeded函数
So we have this number needed function
它可以计算每个字符串中每个字符出现的次数
and it counts how many times each character appears in each string
然后遍历这两个计数数组 计算它们的差值
and then it walks through the two counts and computes the difference of it.
所以获取每个字符串中每个字符的个数非常简单
So, to get the number of characters in each string, that’s pretty easy,
只需要用一个简单的数组就够了
we just use a simple array will be sufficient here.
如果我们有一个更大的字符串或字符集
If we had a bigger variety of strings or characters,
或其他稍微不同的数据集 我们可能就会使用hashmap
some other slightly different data set, we might want to use a hashmap instead.
但这里整数数组就够了
Our integer array is sufficient here.
然后遍历这两个数组 计算出对应值的差值
and then we walk through and get the delta between each value in each array.
我们应该知道 数组长度必须相同
Now we need to know again that it’s the same length.
这是一个非常直接的问题
So that’s, you know, this is a pretty straightforward problem.
有一个对包括这个问题在内的许多问题都有用的技巧
One tip that’s useful in a lot of problems and was useful here
就是认真思考 并明确怎样做才能
is to really define and think about what exactly does it take to
使两个字符串成为变位词 这个算法基本上也可以这样解释
make two things anagrams, and the algorithm sort of follows from that explanation.
一定要记住这些 以后的问题会用到
So keep that in mind for your future problems.
祝你好运
Good luck.

发表评论

译制信息
视频概述

本节介绍了变位词问题的解决方法。

听录译者

收集自网络

翻译译者

[B]hugue

审核员

审核团1024

视频来源

https://www.youtube.com/watch?v=3MwRGPPB4tw

相关推荐