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

目录
  • 找不同
  • 方法一：计数（Java）
  • 方法二：求和（Go）

找不同

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

字符串 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 中出现的次数大于在字符串 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码，按照字符的ASCII码进行查找不同的字符。一次遍历计算出两个字符串的ASCII总和，根据差值既可以得出插入的字符

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

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

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

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

时间复杂度：O(N)

空间复杂度：O(1)

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

赞 (0)

相关推荐

  • Go Java算法最大单词长度乘积示例详解

    目录 最大单词长度乘积 方法一:位运算(java) 方法一:位运算(go) 最大单词长度乘积 给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母.如果不存在这样的两个单词,返回 0 . *示例 1: 输入:words = ["abcw","baz","foo","bar","xtfn","ab

  • Go Java算法之累加数示例详解

    目录 累加数 方法一:穷举法(java) 方法二:深度优先遍历(go) 累加数 累加数 是一个字符串,组成它的数字可以形成累加序列. 一个有效的 累加序列 必须 至少 包含 3 个数.除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和. 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 .如果是,返回 true :否则,返回 false . 说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1

  • Go java 算法之括号生成示例详解

    目录 括号生成 方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=

  • Go Java算法之单词搜索示例详解

    Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go Java算法之解码方法示例详解

    目录 解码方法 方法一:动态规划(Java) 方法二:动态规划——优化(go) 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法).例如,"11106" 可以映射为: "AAJF" ,将消息分组为 (1 1 1

  • Go Java 算法之迷你语法分析器示例详解

    目录 迷你语法分析器 方法一:深度优先遍历(Java) 方法二:栈(Go) 迷你语法分析器 给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger . 列表中的每个元素只可能是整数或整数嵌套列表 示例 1: 输入:s = "324", 输出:324 解释:你应该返回一个 NestedInteger 对象,其中只包含整数值 324. 示例 2: 输入:s = "[123,[456,[789]]]", 输出:[1

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

    目录 找不同 方法一:计数(Java) 方法二:求和(Go) 找不同 给定两个字符串 s 和 t ,它们只包含小写字母. 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母. 请找出在 t 中被添加的字母. 示例 1: 输入:s = "abcd", t = "abcde" 输出:"e" 解释:'e' 是那个被添加的字母. 示例 2: 输入:s = "", t = "y" 输出:"y&q

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

  • Go Java 算法之字符串解码示例详解

    目录 字符串解码 方法一:栈(Java) 方法二:递归(Go) 字符串解码 给定一个经过编码的字符串,返回它解码后的字符串. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正重复 k 次.注意 k 保证为正整数. 你可以认为输入字符串总是有效的:输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的. 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入. 示例 1: 输入:

随机推荐