389 - 找不同(find-the-difference)

Create by jsliang on 2019-7-23 22:05:48
Recently revised in 2019-7-23 22:46:53

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 暴力破解
3.2 解法 - Map
3.3 解法 - 奇技淫巧

二 前言

返回目录

给定两个字符串 s 和 t,它们只包含小写字母。

字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入:
s = "abcd"
t = "abcde"

输出:
e

解释:
'e' 是那个被添加的字母。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 暴力破解

返回目录

  • 解题代码
var findTheDifference = function(s, t) {
  s = s.split('').sort();
  t = t.split('').sort();
  for (let i = 0; i < t.length; i++) {
    if (s[i] !== t[i]) {
      return t[i];
    }
  }
};
  • 执行测试

  • sae

  • taea
  • return
a
  • LeetCode Submit
√ Accepted
  √ 54/54 cases passed (88 ms)
  √ Your runtime beats 84.81 % of javascript submissions
  √ Your memory usage beats 76.09 % of javascript submissions (35.2 MB)
  • 知识点

  • split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍

  • sort():排序,保持返回数组的数字为顺序排列。sort() 详细介绍

  • 解题思路

首先,先将 st 切割成数组并排序。

然后,遍历最长的数组(即 t,因为 ts 的变形),判断同一个坐标下,两个数组的元素是否相同。

最后,如果不同则返回 t[i],因为 ts 长,如果不同的时候,例如 aeaae,相对的应该是 t[i] 不同的。

3.2 解法 - Map

返回目录

  • 解题代码
var findTheDifference = function(s, t) {
  s = s.split('');
  t = t.split('');
  let map = new Map();
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i]) !== undefined) {
      map.set(s[i], map.get(s[i]) + 1);
    } else {
      map.set(s[i], 1);
    }
  }
  for (let j = 0; j < t.length; j++) {
    if (map.get(t[j]) === undefined) {
      return t[j];
    } else {
      map.set(t[j], map.get(t[j]) - 1);
      if (map.get(t[j]) === 0) {
        map.delete(t[j]);
      }
    }
  }
  return t.join('');
};
  • 执行测试

  • sae

  • taea
  • return
a
  • LeetCode Submit
√ Accepted
  √ 54/54 cases passed (84 ms)
  √ Your runtime beats 91.56 % of javascript submissions
  √ Your memory usage beats 75 % of javascript submissions (35.2 MB)
  • 知识点

  • split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍

  • Map:保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍
  • join()join() 方法将一个数组(或一个类数组对象)的所有元素连接成一个字符串并返回这个字符串。join() 详细介绍

  • 解题思路

相对于暴力破解而言,哈希表也是一种解法。

首先,将字符串打成数组。

然后,先遍历 s,将它的每个元素的值和出现的次数记录起来。再遍历 t,如果 t 从未出现过,那么可以立马判定它为两者不同的值;如果曾经出现过,那么将其长度减去 1,之后这个长度减去 1 后刚好为 0,那么就去掉这个 Map 的元素。

最后,将 t 打成字符串返回出去,就是我们的求值。

3.3 解法 - 奇技淫巧

返回目录

  • 解题代码
var findTheDifference = function(s, t) {
  for (let item of s) {
    t = t.replace(item, '');
  }
  return t;
};
  • 执行测试

  • sae

  • taea
  • return
a
  • LeetCode Submit
√ Accepted
  √ 54/54 cases passed (108 ms)
  √ Your runtime beats 45.15 % of javascript submissions
  √ Your memory usage beats 5.43 % of javascript submissions (37.8 MB)
  • 知识点

  • replace()replace()方法返回一个由替换值(replacement)替换一些或所有匹配的模式(pattern)后的新字符串。模式可以是一个字符串或者一个正则表达式,替换值可以是一个字符串或者一个每次匹配都要调用的回调函数。replace() 详细介绍

  • 解题思路

有时候一些想法可能是你想不到或者别人想不到,但是非常奇妙的。

这个解法是在【题解】看到的,思路非常清晰:

遍历 s,判断 s 的元素是否在 t 中存在,如果存在,则替换为 '' 空字符串。

最后替换完毕后,即 t 剩下一个字符串了,那么返回 t 即可。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-24 09:56:27

results matching ""

    No results matching ""