首页 > 代码库 > Leetcode:389.Find the Difference

Leetcode:389.Find the Difference

2024-09-02 09:08:47   225人阅读

题目：

      Given two strings s and t which consist of only lowercase letters.

      String t is generated by random shuffling string s and then add one more letter at a random position.

      Find the letter that was added in t.

　　给定两个字符串 s 和 t ，只包含小写字母。

 　  字符串 t 是有字符串 s 随机打乱，并且在任意位置加上一个字母产生。

　　从 t 中找出添加的字母。

 

求解思路一：

　　定义一个大小为26的数组，对 s 中的每个字母进行计数，

　　然后扫描 t ，在数组中将 t 中字母出现的次数减掉，当数组某元素小于0时，说明对应的字母在 t 中出现的次数比在 s 中多，该字母即为所求。

 1 public class Solution {
 2     public char findTheDifference(String s, String t) {
 3         int a[] = new int[26];
 4         
 5         int i;
 6         for(i = 0; i < s.length(); i++){
 7             int index = s.charAt(i) - ‘a‘;
 8             a[index]++;
 9         }
10         
11         for(i = 0; i< t.length(); i++){
12             int index = t.charAt(i) - ‘a‘;
13             if(--a[index] < 0){
14                 break;
15             }
16         }
17         return t.charAt(i);
18     }
19 }

 

求解思路二：

     (1)使用位运算^，利用^的性质，相同的位异或后为0。

 1 public class Solution {
 2     public char findTheDifference(String s, String t) {
 3         int result = 0;
 4         for(int i = 0; i < s.length(); i++){
 5             result ^= s.charAt(i);
 6         }
 7         
 8         for(int i = 0; i < t.length(); i++){
 9             result ^= t.charAt(i);
10         }
11         
12         return (char)result;
13     }
14 }

     (2)类似于异或运算方法，使用加减法，将相同的抵消，最后得到多出来的字母。

 

 1 public class Solution {
 2     public char findTheDifference(String s, String t) {
 3         int result = 0;
 4         for(int i = 0; i < s.length(); i++){
 5             result -= s.charAt(i);
 6         }
 7         
 8         for(int i = 0; i < t.length(); i++){
 9             result += t.charAt(i);
10         }
11         
12         return (char)result;
13     }
14 }

 

 

 

 

 

 

 

 

 

 

　　









































Leetcode:389.Find the Difference


联系
我们