博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Golang面试考题记录 ━━ 有效的字母异位词,久违的双100%,拓展reflect.DeepEqual()用法和[26]int{}的值
阅读量:4115 次
发布时间:2019-05-25

本文共 1906 字,大约阅读时间需要 6 分钟。

===问:

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”

输出: true

示例 2:

输入: s = “rat”, t = “car”

输出: false

说明:

你可以假设字符串只包含小写字母。

进阶:

如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

===答:

如果之前做过这题《》的话,那么这道题就非常简单了。

方法一:

执行用时 :0 ms,击败了100.00% 的用户
内存消耗 :3 MB, 击败了37.50%的用户

方法一是我的起手式,

首先将两个字符串中各个元素出现的次数记录到数组ab
其次利用反射函数比较两个数组是否一致,一致则返回true,否则false

func isAnagram1(s string, t string) bool {
a := [26]int{
} b := [26]int{
} l := len(s) if len(t) != l {
return false } for i := 0; i < l; i = i + 1 {
a[s[i]-97]++ b[t[i]-97]++ } return reflect.DeepEqual(a, b)}

方法二:

执行用时 :0 ms, 击败了100.00% 的用户
内存消耗 :3 MB, 击败了37.50%的用户

方法一的执行效率为100%,这说明程序结构没问题,现在看看有没有细节可提升呢?

数组ab,长度一样,键名也几乎一致~~那么就让st所遍历的值一个正增长+1,一个负增长-1
数组a通过反射方法reflect.DeepEqual()[26]int{}进行比较,如果26个值全为0则返回true
结果和方法一没什么区别,我估计原因在于反射比较时仍旧需要创建[26]int{}来占用内存。

func isAnagram2(s string, t string) bool {
a := [26]int{
} if len(s) != len(t) {
return false } for i := range s {
a[s[i]-97]++ a[t[i]-97]-- } return reflect.DeepEqual(a, [26]int{
})}

方法三:

执行用时 :0 ms, 击败了100.00% 的用户
内存消耗 :3 MB, 击败了62.50%/80.00%/100.00% 的用户

如果方法二不使用反射,而使用循环遍历来判断是否为字母异位词的话,是否会减少内存占用呢?

于是~~方法三诞生了,最高记录达到了执行效率100%,内存占用100%

func isAnagram3(s string, t string) bool {
// if s==t {
// return true // } if len(s) != len(t) {
return false } a := [26]int{
} for i, v := range s {
a[v-97]++ a[t[i]-97]-- } for _, v := range a {
if v != 0 {
return false } } return true}

方法四:

执行用时 :8 ms, 击败了59.85% 的用户
内存消耗 :3 MB, 击败了40.00%/37.50%的用户

根据方法三,想进一步让内存的占用下来,结果惨败

func isAnagram4(s string, t string) bool {
if len(s) != len(t) {
return false } a := make(map[byte]int, 26) for i := range s {
a[s[i]]++ a[t[i]]-- } for _, v := range a {
if v != 0 {
return false } } return true}

===拓展:

  1. 这道题我们接触了reflect.DeepEqual(),用法可以参考《》
  2. 数组如果这样写[3]int{},其值相当于[0 0 0],因此在方法二中[26]int{}可与数组a比较

转载地址:http://jtkpi.baihongyu.com/

你可能感兴趣的文章
学会常用的CSS居中方式
查看>>
Vue.js 开篇---Vue的介绍及准备工作
查看>>
大型网站技术架构(一)
查看>>
微信小程序使用flex的一些基础样式属性
查看>>
7种方法实现移动端Retina屏幕1px边框效果
查看>>
CSS滚动条实现步骤及美化小技巧
查看>>
【AngularJS教程】快速入门篇之 双向绑定
查看>>
【JavaScript 教程】标准库—Array 对象
查看>>
那些坚持写博客的程序员,后来都怎么样了?
查看>>
这些惊人的“二八”法则,你必须要知道
查看>>
三个值得期待的 JavaScript 新特性!
查看>>
【JavaScript 教程】标准库—包装对象
查看>>
辞退你,培养你,从来都不是看能力!
查看>>
【JavaScript 教程】标准库—Boolean 对象
查看>>
18个你可能不相信的前端炫酷特效,附观赏地址与下载源码
查看>>
自己没本事,认识谁都没用!!!
查看>>
我关注的那些大佬程序员
查看>>
【JavaScript 教程】标准库—Number 对象
查看>>
毕业10年,一个上海女程序员的职业之路—01
查看>>
【JavaScript 教程】标准库—String 对象
查看>>