Go Java算法之找不同示例详解

2022-09-03 15:22:04 71 0
魁首哥

目录

  • 找不同
  • 方法一:计数(Java)
  • 方法二:求和(Go)

找不同

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

Go Java算法之找不同示例详解

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

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

  • 示例 1:

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

输出:"e"

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

编程
  • 示例 2:

输入:s = "", t = "y"编程

输出:"y"

提示:

0 <= s.length <= 1000

t.length == s.length + 1

  • s 和 t 只包含小写字母

方法一:计数(Java)

首先遍历字符串 s,对其中的每个字符都将计数值加 1;然后遍历字符串 t,对其中的每个字符都将计数值减 1。

当发现某个字符计数值为负数时,说明该字符在字符串 t 中出现的次数大于在字符js串 s 中出现的次数,因此该字符为被添加的字符。

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            cnt[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); ++i) {
            char ch = t.charAt(i);
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
}

N:字符串的长度

Σ:字符集

时间复杂度:O(N)

空间复杂度:O(∣Σ∣)

方法二:求和(Go)

本方法主要是利用了ASCII码,按照字符的ASCpythonII码进行查找不同的字符。一次遍历计算出两个字符串的ASCII总和,根据差值既可以得出插入的字符

将字符串 s 中每个字符的 ASCII 码的值求和,得到 A_s

对字符串 t 同样的方法得到 A_t

两者的差值 A_t-A_s即代表了被添加的字符。

func findTheDifference(s, t string) byte {
    sum := 0
    for _, ch := range s {
        javascriptsum -= int(ch)
    }
    for _, ch := range t {
        sum += int(ch)
    }
    return byte(sum)
}

时间复杂度:O(N)

空间复杂度:O(1)

以上就是Go Java算法之找不同示例详解的详细内容,更多关于Go Java 算法找不同的资料请关注我们其它相关文章!

收藏
分享
海报
0 条评论
71
上一篇:Java基础之String类使用与字符串比较 下一篇:SpringCloud实现文件上传功能的方法详解

本站已关闭游客评论,请登录或者注册后再评论吧~

忘记密码?

图形验证码