96 - 找不同

题目

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

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

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

示例:

输入： s = "abcd" t = "abcde"
输出： e
解释： 'e' 是那个被添加的字母。

解答

感觉可以变成数组，然后一个个找index。不过这样有重复的就不行了。。

然后就想到，可以先排序，再一个个比对。

不过需要先判断下长短才行

排序

const getWrongOne = function (longer, shorter) {
  for (let i = 0; i < longer.length; i++) {
    if (longer[i] !== shorter[i]) {
      return longer[i];
    }
  }
}
var findTheDifference = function (s, t) {
  let sArr = s.split('').sort()
  let tArr = t.split('').sort()
  if (sArr.length > tArr.length) {
    return getWrongOne(sArr, tArr)
  } else {
    return getWrongOne(tArr, sArr)
  }
};

Runtime: 80 ms, faster than 10.49% of JavaScript online submissions for Find the Difference.
Memory Usage: 35.2 MB, less than 100.00% of JavaScript online submissions for Find the Difference.

起码是做出来了😂😂

go的string是切片，却似乎无法直接排序

s := "bcd"
sort.Slice(s, func(i, j int) bool {
  return s[i] < s[j]
})

直接这样的话会报错

goroutine 1 [running]: reflect.Swapper(0x10a5800, 0xc00009c030, 0x11754c0) /usr/local/Cellar/go/1.12.7/libexec/src/reflect/swapper.go:16 +0x730 sort.Slice(0x10a5800, 0xc00009c030, 0xc000084f50) /usr/local/Cellar/go/1.12.7/libexec/src/sort/slice.go:19 +0xb2 main.main() /Users/joey/Study/leetcode/test/code.go:57 +0x93 exit status 2

所以只能先转成slice

func getDiff(longer, shorter []rune) byte {
    for i := 0; i < len(shorter); i++ {
        if longer[i] != shorter[i] {
            return byte(longer[i])
        }
    }
    return byte(longer[len(longer)-1])
}
func findTheDifference(s string, t string) byte {
    sArr := []rune(s)
    sort.Slice(sArr, func(i, j int) bool {
        return sArr[i] < sArr[j]
    })
    tArr := []rune(t)
    sort.Slice(tArr, func(i, j int) bool {
        return tArr[i] < tArr[j]
    })
    if len(sArr) > len(tArr) {
        return getDiff(sArr, tArr)
    } else {
        return getDiff(tArr, sArr)
    }
}

Runtime: 4 ms, faster than 19.81% of Go online submissions for Find the Difference.
Memory Usage: 2.5 MB, less than 100.00% of Go online submissions for Find the Difference.

在gitDiff()函数里面，报错过指针越界。结果是因为指向longer最后一位，shorter是没有的。。

这点在js就不用考虑，因为没有，就是空，那自然啥都直接返回否

可能这就是为啥，刷题记录都是python之类的弱类型语言吧。。很多事情都不用考虑，主体思想有了就能直接写

用go刷题，没有高并发场景，感觉很吃亏啊

与其用map，不如用更快的桶排序

var findTheDifference = function (s, t) {
  let data = new Array(26)
  for (let i = 0; i < 26; i++) {
    data[i] = 0
  }
  for (const item of s) {
    data[item.charCodeAt() - 97]++
  }
  for (const item of t) {
    data[item.charCodeAt() - 97]--
  }
  for (let i = 0; i < data.length; i++) {
    if (data[i] !== 0) {
      return String.fromCharCode(i + 97);
    }
  }
};

Runtime: 64 ms, faster than 53.33% of JavaScript online submissions for Find the Difference.
Memory Usage: 35.6 MB, less than 100.00% of JavaScript online submissions for Find the Difference.

疯狂for循环，感觉很蠢哈哈😂

go对应的排序就不能这么写了。。因为如果一开始定义的data变成了0，再-1就会报error

这就让我想到，完全可以一次遍历么。。

func findTheDifference(s string, t string) byte {
    var data [26]int
    for _, value := range s {
        data[value-97]++
    }
    for _, value := range t {
        if data[value-97] == 0 {
            return byte(value)
        } else {
            data[value-97]--
        }
    }
    return t[len(t)-1]
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Find the Difference.
Memory Usage: 2.2 MB, less than 100.00% of Go online submissions for Find the Difference.

js也可以

var findTheDifference = function (s, t) {
  let data = []
  for (let i = 0; i < 26; i++) {
    data[i] = 0
  }
  for (const item of s) {
    data[item.charCodeAt() - 97]++
  }
  for (const item of t) {
    if (data[item.charCodeAt() - 97] === 0) {
      return item
    } else {
      data[item.charCodeAt() - 97]--
    }
  }
  return t[t.length - 1]
};

Runtime: 68 ms, faster than 33.79% of JavaScript online submissions for Find the Difference.
Memory Usage: 35.4 MB, less than 100.00% of JavaScript online submissions for Find the Difference.

写这个的时候遇到了一个坑，当我想偷懒少打几个字，把data[item.charCodeAt()-9]令为了一个elem

在下面else的时候，不能执行elem—。或者说执行了之后data并未改变。go和js都不行

...
for (const item of t) {
  const elem = data[item.charCodeAt() - 97]
  if (elem === 0) {
    return item
  } else {
    elem--
  }
}
...

可能是因为，这是把其中的值拿出来赋值给了elem，即使是改了elem，也不会影响到原来的data。。

作者：YarkAwk 链接：https://leetcode-cn.com/problems/find-the-difference/solution/pythonbi-jiao-mei-ge-zi-fu-zai-liang-ge-zi-fu-ch-2/

python可以直接比较出现的次数，都不用建数组

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for i in t:
            if t.count(i) - s.count(i) != 0:
                return i

Runtime: 40 ms, faster than 74.95% of Python3 online submissions for Find the Difference.
Memory Usage: 14 MB, less than 10.00% of Python3 online submissions for Find the Difference.

直接相减ascii

作者：QQqun902025048
链接：https://leetcode-cn.com/problems/find-the-difference/solution/python-1-xing-ascii-he-zhi-chai-by-qqqun902025048/

俩ascii加起来，再相减，差的那个就是想要的数

这操作。。服气吼

var findTheDifference = function (s, t) {
  let count = 0
  for (const item of s) {
    count += item.charCodeAt() - 97
  }
  for (const item of t) {
    count -= item.charCodeAt() - 97
  }
  return String.fromCharCode(Math.abs(count) + 97)
};

Runtime: 52 ms, faster than 96.21% of JavaScript online submissions for Find the Difference.
Memory Usage: 35.7 MB, less than 100.00% of JavaScript online submissions for Find the Difference.

我是怕它溢出，强行减一个97😂😂

func findDiff(longer, shorter string) byte {
    var count int32
    for _, value := range longer {
        count += value - 97
    }
    for _, value := range shorter {
        count -= value - 97
    }
    if count < 0 {
        count = -count
    }
    return byte(count + 97)
}
func findTheDifference(s string, t string) byte {
    if len(s) > len(t) {
        return findDiff(s, t)
    } else {
        return findDiff(t, s)
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Find the Difference.
Memory Usage: 2.2 MB, less than 100.00% of Go online submissions for Find the Difference.

为了避开变成0之后的panic。。只能这么做。

一开始是count==0之后直接return，但有可能中间变成0的。。

作者：QQqun902025048 链接：https://leetcode-cn.com/problems/find-the-difference/solution/python-1-xing-ascii-he-zhi-chai-by-qqqun902025048/

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(sum(map(ord, t)) - sum(map(ord, s)))

Runtime: 36 ms, faster than 91.95% of Python3 online submissions for Find the Difference.
Memory Usage: 13.7 MB, less than 10.00% of Python3 online submissions for Find the Difference.

异或

作者：guanpengchn 链接：https://leetcode-cn.com/problems/find-the-difference/solution/hua-jie-suan-fa-389-zhao-bu-tong-by-guanpengchn/

感觉找不同，异或都是一个思路，毕竟相同的就会变成0

func findDiff(longer, shorter string) byte {
    ans := longer[len(longer)-1]
    for i := 0; i < len(shorter); i++ {
        ans ^= longer[i]
        ans ^= shorter[i]
    }
    return ans
}
func findTheDifference(s string, t string) byte {
    if len(s) > len(t) {
        return findDiff(s, t)
    }
    return findDiff(t, s)
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Find the Difference.
Memory Usage: 2.2 MB, less than 100.00% of Go online submissions for Find the Difference.

js好像做不了。。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        n = 0
        for i in s:
            n ^= ord(i)
        for i in t:
            n ^= ord(i)

        return chr(n)

Runtime: 36 ms, faster than 91.95% of Python3 online submissions for Find the Difference.
Memory Usage: 13.7 MB, less than 10.00% of Python3 online submissions for Find the Difference.

测试代码

go

go怎么取字符串的byte呢？

因为是切片所以可以直接后面加[0]取😂

func Multi(t *testing.T) {
    var DATA = []struct {
        a        string
        b        string
        expected byte
    }{
        {"acde", "caebd", "b"[0]},
        {"abcd", "abcde", "e"[0]},
        {"aa", "a", "a"[0]},
    }

    for i, elem := range DATA {
        ans := findTheDifference(elem.a, elem.b)
        if ans != elem.expected {
            t.Error("😶 wrong:", i+1)
            t.Errorf("* target: %v", elem.expected)
            t.Error("* ans:", &ans)
            return
        }
    }
}

func TestFunc(t *testing.T) {
    // Single(t)
    Multi(t)
}

python

想在以后刷题中加入python，于是查了单元测试怎么写

import unittest2 as unittest


# ================ code ===================
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for i in t:
            if t.count(i) - s.count(i) != 0:
                return i


# ========================================
TEST_DATA = [
    {
        "input": ["abcd", "abcde"],
        "target": "e"
    },
    {
        "input": ["acbd", "acebd"],
        "target": "e"
    }
]


class Test(unittest.TestCase):
    @unittest.skipIf(not isinstance(TEST_DATA[0]["input"], list), "skip")
    def test_multi(self):
        for t in TEST_DATA:
            self.assertEqual(Solution.findTheDifference(self, *t["input"]), t["target"])

    @unittest.skipIf(isinstance(TEST_DATA[0]["input"], list), "skip")
    def test_single(self):
        for t in TEST_DATA:
            self.assertEqual(Solution.findTheDifference(self, t["input"]), t["target"])


if __name__ == '__main__':
    unittest.main()

我更喜欢用json把所有数据存起来😂

话说这个skip的装饰器，有点酷吼。只要输入是放在list里面的，就不会测试它

于是找了一下go的跳过

package main

import (
    "testing"
)

// ==== prepare =======
...

func a(input string) int {
    return 1
}

// ======= test ============
func Single(t *testing.T) {
    var DATA = []struct {
        input    string
        expected int
    }{
        {"leetcode", 0},
        {"loveleetcode", 2},
        {"aa", -1},
    }

    for i, elem := range DATA {
        ans := a(elem.input)
        if ans != elem.expected {
            t.Error("😶 wrong:", i+1)
            t.Errorf("* target: %v", elem.expected)
            t.Error("* ans:", ans)
            return
        }
    }
}

func Multi(t *testing.T) {
    var DATA = []struct {
        a        string
        b        string
        expected byte
    }{
        {"acde", "caebd", "b"[0]},
        {"abcd", "abcde", "e"[0]},
        {"aa", "a", "a"[0]},
    }

    for i, elem := range DATA {
        ans := findTheDifference(elem.a, elem.b)
        if ans != elem.expected {
            t.Error("😶 wrong:", i+1)
            t.Errorf("* target: %v", elem.expected)
            t.Error("* ans:", &ans)
            return
        }
    }
}

func TestMulti(t *testing.T) {
    Multi(t)
}

func TestSingle(t *testing.T) {
    t.SkipNow()
    Single(t)
}

关键是v嗯额skipnow()函数，配上go的简单输出模式，很舒服。

Previous130 - 43 字符串相乘 Next111 - 605种花问题

Last updated 5 years ago

Was this helpful?