当前位置:网站首页>【LeetCode-389】找不同
【LeetCode-389】找不同
2022-08-11 05:30:00 【Ring*】
6.8 找不同【389】
6.8.1 题目描述
给定两个字符串 s
和 t
,它们只包含小写字母。
字符串 t
由字符串 s
随机重排,然后在随机位置添加一个字母。
请找出在 t
中被添加的字母。
6.8.2 方法一:计数
首先遍历字符串 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 ' ';
}
}
复杂度分析
- 时间复杂度:O(N),其中 N 为字符串的长度。
- 空间复杂度: O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣),其中 Σ \Sigma Σ 是字符集,这道题中字符串只包含小写字母, ∣ Σ ∣ = 26 ∣ |\Sigma|=26∣ ∣Σ∣=26∣。需要使用数组对每个字符计数。
6.8.3 方法二:求和
将字符串 s 中每个字符的 ASCII 码的值求和,得到 A s A_s As;对字符串 t 同样的方法得到 A t A_t At。两者的差值 A t − A s A_t-A_s At−As 即代表了被添加的字符。
class Solution {
public char findTheDifference(String s, String t) {
int as = 0, at = 0;
for (int i = 0; i < s.length(); ++i) {
as += s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
at += t.charAt(i);
}
return (char) (at - as);
}
}
复杂度分析
- 时间复杂度:O(N)。
- 空间复杂度:O(1)。
6.8.4 方法三:位运算
如果将两个字符串拼接成一个字符串,则问题转换成求字符串中出现奇数次的字符。类似于「136. 只出现一次的数字」,我们使用位运算的技巧解决本题。
class Solution {
public char findTheDifference(String s, String t) {
int ret = 0;
for (int i = 0; i < s.length(); ++i) {
ret ^= s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
ret ^= t.charAt(i);
}
return (char) ret;
}
}
复杂度分析
- 时间复杂度:O(N)。
- 空间复杂度:O(1)。
6.8.5 my answer—排序/计数
class Solution {
// map计数
public char findTheDifference(String s, String t) {
Map<Character,Integer> map = new HashMap<>();
char[] chars = s.toCharArray();
char[] chart = t.toCharArray();
for (char c : chars) {
map.put(c,map.getOrDefault(c,0)+1);
}
for (char aChar : chart) {
if(map.containsKey(aChar)){
map.put(aChar,map.getOrDefault(aChar,0)-1);
}else {
return aChar;
}
if(map.get(aChar)<0)return aChar;
}
return '1';
}
// 排序
public char findTheDifference(String s, String t) {
char[] chars = s.toCharArray();
char[] chart = t.toCharArray();
Arrays.sort(chars);
Arrays.sort(chart);
for (int i = 0; i < Math.max(chars.length, chart.length); i++) {
if(i==chars.length)return chart[i];
if(chars[i] != chart[i])return chart[i];
}
return '1';
}
}
边栏推荐
- Compilation exception resolution
- C-自定义类型(结构体、枚举、联合)
- The official website of OpenMLDB is upgraded, and the mysterious contributor map will take you to advance quickly
- Day 75
- Day 69
- Dark Horse Event Project
- Day 77
- 微信小程序_开发工具的安装
- The third phase of the contributor task is wonderful
- heap2 (tcache attack,house of orange)
猜你喜欢
8-byte standard request parsing during USB enumeration
He Kaiming's new work ViTDET: target detection field, subverting the concept of layered backbone
微信小程序_开发工具的安装
Day 86
JVM tuning and finishing
轻松理解进程与线程
JVM学习四:垃圾收集器与内存回收策略
JS进阶网页特效(pink老师笔记)
Use the adb command to manage applications
【剑指offer系列】面试题日记(前期题)
随机推荐
Vscode remote connection server terminal zsh+Oh-my-zsh + Powerlevel10 + Autosuggestions + Autojump + Syntax-highlighting
C语言-7月18日-二维数组的学习
C语言-内存操作函数
【LeetCode-278】第一个错误的版本
Day 68
Wonderful linkage | OpenMLDB Pulsar Connector principle and practical operation
Fourth Paradigm OpenMLDB optimization innovation paper was accepted by VLDB, the top international database association
基于微信小程序云开发实现的电商项目,可以自行定制开发
mk文件介绍
Day 83
编译异常解决
mongoose连接mongodb不错,显示encoding没有定义
连接数据库时出现WARN: Establishing SSL connection without server‘s identity verification is not recommended.
品优购项目实战笔记
JVM学习四:垃圾收集器与内存回收策略
C语言-7月21日-指针的深入
helm安装
Node 踩坑之80端口被占用
C语言-6月10日-my_strcpy函数的编写
手把手导入企业项目(快速完成本地项目配置)