- 📢前言
- 🌲原題樣例：找不同
- 🌻C#方法：排序遍歷
- 🌻Java 方法一：計數
- 🌻Java 方法二：求和
- 💬總結
📢前言
| 🚀 演算法題 🚀 |
- 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
- 🌲 今天是力扣演算法題持續打卡第71天🎈！
| 🚀 演算法題 🚀 |
🌲原題樣例：找不同
給定兩個字串 s 和 t，它們只包含小寫字母，
字串 t 由字串 s 隨機重排，然后在隨機位置添加一個字母，
請找出在 t 中被添加的字母，
示例1:
輸入：s = "abcd", t = "abcde"
輸出："e"
解釋：'e' 是那個被添加的字母，
示例2:
輸入：s = "", t = "y"
輸出："y"
示例3:
輸入：s = "a", t = "aa"
輸出："a"
示例4:
輸入：s = "ae", t = "aea"
輸出："a"
提示：
- 0 <= s.length <= 1000
- t.length == s.length + 1
- s 和 t 只包含小寫字母
🌻C#方法：排序遍歷
- 看到題目就想到可以先排序在遍歷對比即可
- 遇到不相同的回傳這個值就是結果了！
代碼：
public class Solution {
public char FindTheDifference(string s, string t) {
var s1 = s.ToCharArray();
var t1 = t.ToCharArray();
Array.Sort(s1);
Array.Sort(t1);
for (int i = 0; i < t1.Length; i++)
{
if (i == s1.Length || s1[i] != t1[i])
return t1[i];
}
return t1[0];
}
}
執行結果
通過
執行用時：92 ms，在所有 Java 提交中擊敗了64.50%的用戶
記憶體消耗：37.4 MB，在所有 Java 提交中擊敗了34.50%的用戶
🌻Java 方法一：計數
思路決議
- 首先遍歷字串 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 ' ';
}
}
執行結果
通過
執行用時：3 ms，在所有 Java 提交中擊敗了48.26%的用戶
記憶體消耗：36.8 MB，在所有 Java 提交中擊敗了37.05%的用戶
復雜度分析
時間復雜度：O( n )
空間復雜度：O( |Σ|)
🌻Java 方法二：求和
思路決議
- 將字串 s 中每個字符的 ASCII 碼的值求和，得到As?；
- 對字串 t 同樣的方法得到 At?，
- 兩者的差值 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);
}
}
執行結果
通過
執行用時：2 ms，在所有 Java 提交中擊敗了77.26%的用戶
記憶體消耗：36.9 MB，在所有 Java 提交中擊敗了22.05%的用戶
復雜度分析
時間復雜度：O( n )
空間復雜度：O( 1)
💬總結
- 今天是力扣演算法題打卡的第七十一天！
- 文章采用
C#和Java兩種編程語言進行解題 - 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
- 那今天的演算法題分享到此結束啦，明天再見！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353293.html
標籤：其他
上一篇：2021-11-08每日刷題打卡