Go Java算法之找不同示例詳解
找不同
給定兩個(gè)字符串 s 和 t ，它們只包含小寫字母。
字符串 t 由字符串 s 隨機(jī)重排，然后在隨機(jī)位置添加一個(gè)字母。
請(qǐng)找出在 t 中被添加的字母。
- 示例 1：
輸入：s = "abcd", t = "abcde"
輸出："e"
解釋：'e' 是那個(gè)被添加的字母。
- 示例 2：
輸入：s = "", t = "y"
輸出："y"
提示：
0 <= s.length <= 1000
t.length == s.length + 1
- s 和 t 只包含小寫字母
方法一：計(jì)數(shù)（Java）
首先遍歷字符串 s，對(duì)其中的每個(gè)字符都將計(jì)數(shù)值加 1；然后遍歷字符串 t，對(duì)其中的每個(gè)字符都將計(jì)數(shù)值減 1。
當(dāng)發(fā)現(xiàn)某個(gè)字符計(jì)數(shù)值為負(fù)數(shù)時(shí)，說明該字符在字符串 t 中出現(xiàn)的次數(shù)大于在字符串 s 中出現(xiàn)的次數(shù)，因此該字符為被添加的字符。
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 :字符串的長(zhǎng)度
Σ :字符集
時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(∣Σ∣)
方法二：求和（Go）
本方法主要是利用了ASCII碼，按照字符的ASCII碼進(jìn)行查找不同的字符。一次遍歷計(jì)算出兩個(gè)字符串的ASCII總和，根據(jù)差值既可以得出插入的字符
將字符串 s 中每個(gè)字符的 ASCII 碼的值求和，得到 A_s
對(duì)字符串 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)
}
時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
以上就是Go Java算法之找不同示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java 算法找不同的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Tomcat服務(wù)無法啟動(dòng)的問題的解決方法
這篇文章主要介紹了Tomcat服務(wù)無法啟動(dòng)的問題的解決方法,需要的朋友可以參考下2014-02-02
IDEA生成項(xiàng)目maven-tree依賴目錄樹結(jié)構(gòu)方式
這篇文章主要介紹了IDEA生成項(xiàng)目maven-tree依賴目錄樹結(jié)構(gòu)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
這篇文章主要為大家介紹了RocketMQ?源碼分析Broker消息刷盤服務(wù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Java使用JSqlParser解析SQL語句應(yīng)用場(chǎng)景
JSqlParser是一個(gè)功能全面的Java庫,用于解析SQL語句,支持多種SQL方言,它可以輕松集成到Java項(xiàng)目中,并提供靈活的操作方式,本文介紹Java使用JSqlParser解析SQL語句總結(jié),感興趣的朋友一起看看吧2024-09-09
這篇文章主要介紹了SpringBoot全局處理統(tǒng)一返回類型方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
Java中ArrayList和LinkedList的區(qū)別
ArrayList和LinkedList在這個(gè)方法上存在一定的性能差異，本文就介紹了Java中ArrayList和LinkedList的區(qū)別，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
Java設(shè)計(jì)模式之動(dòng)態(tài)代理模式實(shí)例分析
這篇文章主要介紹了Java設(shè)計(jì)模式之動(dòng)態(tài)代理模式,結(jié)合實(shí)例形式分析了動(dòng)態(tài)代理模式的概念、功能、組成、定義與使用方法,需要的朋友可以參考下2018-04-04
如何去掉IntelliJ IDEA中mybatis對(duì)應(yīng)的xml文件警告
這篇文章主要介紹了如何去掉IntelliJ IDEA中mybatis對(duì)應(yīng)的xml文件警告問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
使用Feign傳遞請(qǐng)求頭信息(Finchley版本)
這篇文章主要介紹了使用Feign傳遞請(qǐng)求頭信息(Finchley版本)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
Java基礎(chǔ)之打印萬年歷的簡(jiǎn)單實(shí)現(xiàn)(案例)
下面小編就為大家?guī)硪黄狫ava基礎(chǔ)之打印萬年歷的簡(jiǎn)單實(shí)現(xiàn)(案例)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-07-07