Go Java算法之找不同示例詳解
找不同
給定兩個(gè)字符串 s 和 t ，它們只包含小寫(xiě)字母。
字符串 t 由字符串 s 隨機(jī)重排，然后在隨機(jī)位置添加一個(gè)字母。
請(qǐng)找出在 t 中被添加的字母。
- 示例 1：
輸入：s = "abcd", t = "abcde"
輸出："e"
解釋?zhuān)?#39;e' 是那個(gè)被添加的字母。
- 示例 2：
輸入：s = "", t = "y"
輸出："y"
提示：
0 <= s.length <= 1000
t.length == s.length + 1
- s 和 t 只包含小寫(xiě)字母
方法一：計(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í)，說(shuō)明該字符在字符串 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)文章
Mybatis無(wú)法獲取帶有下劃線(xiàn)前綴的字段的值問(wèn)題
這篇文章主要介紹了Mybatis無(wú)法獲取帶有下劃線(xiàn)前綴的字段的值問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
spring boot actuator監(jiān)控超詳細(xì)教程
Spring Boot Actuator就是一款可以幫助你監(jiān)控系統(tǒng)數(shù)據(jù)的框架,其可以監(jiān)控很多很多的系統(tǒng)數(shù)據(jù)，接下來(lái)通過(guò)本文給大家介紹spring boot actuator監(jiān)控超詳細(xì)教程，感興趣的朋友一起看看吧2021-10-10
springboot啟動(dòng)時(shí)如何指定spring.profiles.active
這篇文章主要介紹了springboot啟動(dòng)時(shí)如何指定spring.profiles.active問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
Springboot項(xiàng)目啟動(dòng)到一半卡住了,不報(bào)錯(cuò)問(wèn)題及解決
這篇文章主要介紹了Springboot項(xiàng)目啟動(dòng)到一半卡住了,不報(bào)錯(cuò)問(wèn)題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
Java設(shè)計(jì)模式之橋模式（Bridge模式）介紹
這篇文章主要介紹了Java設(shè)計(jì)模式之橋模式（Bridge模式）介紹,本文講解了為什么使用橋模式、如何實(shí)現(xiàn)橋模式、Bridge模式在EJB中的應(yīng)用等內(nèi)容,需要的朋友可以參考下2015-03-03
Java 基于TCP Socket 實(shí)現(xiàn)文件上傳
這篇文章主要介紹了Java 基于TCP Socket 實(shí)現(xiàn)文件上傳的示例代碼，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-12-12
Java中的三種校驗(yàn)注解的使用(@Valid,@Validated和@PathVariable)
本文主要介紹了Java中的三種校驗(yàn)注解的使用(@Valid,@Validated和@PathVariable)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
配置了jdk的環(huán)境idea卻提示找不到j(luò)dk解決辦法
在使用Java編程語(yǔ)言進(jìn)行開(kāi)發(fā)時(shí),IDEA是一個(gè)非常流行和強(qiáng)大的集成開(kāi)發(fā)環(huán)境,這篇文章主要給大家介紹了關(guān)于配置了jdk的環(huán)境idea卻提示找不到j(luò)dk的解決辦法,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了springboot集成與使用Sentinel的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
Java的集合類(lèi)型都是對(duì)java.util包中Collection接口的繼承,這里我們主要介紹依賴(lài)于collection的一些主分支,一起來(lái)看一下Java中的collection集合類(lèi)型總結(jié)2021-08-08