資訊專欄INFORMATION COLUMN
摘要：題目地址題目描述給定兩個(gè)字符串和，它們只包含小寫字母。字符串由字符串隨機(jī)重排，然后在隨機(jī)位置添加一個(gè)字母。示例輸入輸出解釋是那個(gè)被添加的字母。解答這一題可以用兩種解法。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定兩個(gè)字符串 s 和 t，它們只包含小寫字母。
字符串 t 由字符串 s 隨機(jī)重排，然后在隨機(jī)位置添加一個(gè)字母。
請找出在 t 中被添加的字母。
示例:
輸入：
s = "abcd"
t = "abcde"
輸出：
e
解釋：
"e" 是那個(gè)被添加的字母。
解答：
這一題可以用兩種解法。
解法一：利用hash表存儲第一個(gè)字符串的字母的數(shù)量，然后遍歷第二個(gè)字符串的時(shí)候
先查找到字母，然后把數(shù)量減一，如果減完之后小于0，說明這個(gè)字母就是多出來的字母
這里的hash表可以用一個(gè)數(shù)組來代替，因?yàn)檫@里不需要解決hash沖突！??！
java ac代碼：
class Solution {
public char findTheDifference(String s, String t) {
int[] hash = new int["z"+1];
for(int i = 0;i < s.length();i++)
hash[s.charAt(i)]++;
for(int i = 0;i < t.length();i++)
if( --hash[t.charAt(i)] < 0)
return t.charAt(i);
return " ";
}
}
解法二：把這題看作是一個(gè)數(shù)組里除了一個(gè)數(shù)出現(xiàn)了一次，其他都出現(xiàn)了偶數(shù)次，然后找出這個(gè)數(shù)，可以
利用異或，因?yàn)榕紨?shù)個(gè)自己異或自己為0，而0異或一個(gè)數(shù)就等于那個(gè)數(shù)本身，比如說，有偶數(shù)個(gè)a,現(xiàn)在這
偶數(shù)個(gè)a異或結(jié)果為0，a^a^a^a...^a=0,而0^b=b。
java ac代碼
class Solution {
public char findTheDifference(String s, String t) {
char ans = 0;
for(int i = 0;i < s.length();i++)
ans ^= s.charAt(i);
for(int i = 0;i < t.length();i++)
ans ^= t.charAt(i);
return ans;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72916.html
摘要：題目鏈接題目分析給定兩個(gè)字符串，其中一個(gè)字符串比另一個(gè)字符串在隨機(jī)位置多一個(gè)字符。思路用計(jì)算字符串中字符出現(xiàn)的次數(shù)，對比兩個(gè)字符串的字符出現(xiàn)次數(shù)。計(jì)算差集，返回差異部分即可。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D73 389. Find the Difference 題目鏈接 389. Find the Difference 題目分析 給定兩個(gè)字符串，其中一個(gè)字符串比另一...
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個(gè)具有樹特征的無向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個(gè)人主頁：應(yīng)無所住而生...
摘要：題目要求假設(shè)兩個(gè)只包含小寫字母的字符串和，其中是中字母的亂序，并在某個(gè)位置上添加了一個(gè)新的字母。最后只需要遍歷整數(shù)數(shù)組檢查是否有某個(gè)字符計(jì)數(shù)大于。 題目要求 Given two strings s and t which consist of only lowercase letters. String t is generated by random shuffling strin...
閱讀 2272·2021-08-23 09:46
閱讀 922·2019-08-29 18:31
閱讀 1872·2019-08-29 17:04
閱讀 2464·2019-08-29 12:23
閱讀 1860·2019-08-26 14:05
閱讀 1086·2019-08-26 13:44
閱讀 3154·2019-08-26 12:23
閱讀 2208·2019-08-26 10:46
