Go Java算法之找不同示例詳解
找不同
給定兩個字符串 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 只包含小寫字母
方法一：計數(shù)（Java）
首先遍歷字符串 s，對其中的每個字符都將計數(shù)值加 1；然后遍歷字符串 t，對其中的每個字符都將計數(shù)值減 1。
當(dāng)發(fā)現(xiàn)某個字符計數(shù)值為負(fù)數(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 :字符串的長度
Σ :字符集
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(∣Σ∣)
方法二：求和（Go）
本方法主要是利用了ASCII碼，按照字符的ASCII碼進行查找不同的字符。一次遍歷計算出兩個字符串的ASCII總和，根據(jù)差值既可以得出插入的字符
將字符串 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)
}
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
以上就是Go Java算法之找不同示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java 算法找不同的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了Mybatis無法獲取帶有下劃線前綴的字段的值問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
spring boot actuator監(jiān)控超詳細(xì)教程
Spring Boot Actuator就是一款可以幫助你監(jiān)控系統(tǒng)數(shù)據(jù)的框架,其可以監(jiān)控很多很多的系統(tǒng)數(shù)據(jù)，接下來通過本文給大家介紹spring boot actuator監(jiān)控超詳細(xì)教程，感興趣的朋友一起看看吧2021-10-10
springboot啟動時如何指定spring.profiles.active
這篇文章主要介紹了springboot啟動時如何指定spring.profiles.active問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-04-04
這篇文章主要介紹了Springboot項目啟動到一半卡住了,不報錯問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要介紹了Java設(shè)計模式之橋模式（Bridge模式）介紹,本文講解了為什么使用橋模式、如何實現(xiàn)橋模式、Bridge模式在EJB中的應(yīng)用等內(nèi)容,需要的朋友可以參考下2015-03-03
Java 基于TCP Socket 實現(xiàn)文件上傳
這篇文章主要介紹了Java 基于TCP Socket 實現(xiàn)文件上傳的示例代碼，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-12-12
Java中的三種校驗注解的使用(@Valid,@Validated和@PathVariable)
本文主要介紹了Java中的三種校驗注解的使用(@Valid,@Validated和@PathVariable)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
配置了jdk的環(huán)境idea卻提示找不到j(luò)dk解決辦法
在使用Java編程語言進行開發(fā)時,IDEA是一個非常流行和強大的集成開發(fā)環(huán)境,這篇文章主要給大家介紹了關(guān)于配置了jdk的環(huán)境idea卻提示找不到j(luò)dk的解決辦法,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了springboot集成與使用Sentinel的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
Java的集合類型都是對java.util包中Collection接口的繼承,這里我們主要介紹依賴于collection的一些主分支,一起來看一下Java中的collection集合類型總結(jié)2021-08-08