【Android开发】算法题合集（三）赎金信和字符串中的第一个唯一字符

Android面试题算法篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐，更多精彩内容可以扫描文末二维码加v获得更多咨询~

上接：
【Android面试】算法题合集（一）二叉树和反转字符串
【Android开发】算法题合集（二）相对名次和反转字符串中的元音字母

🌲真题一：赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例1:

输入：ransomNote = "a", magazine = "b"
输出：false 

示例2:

输入：ransomNote = "aa", magazine = "ab"
输出：false 

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true 

提示：

• 你可以假设两个字符串均只含有小写字母。

---

🌻C#方法：数组存储

利用数组储存字母出现次数，然后进行比较即可得出结果！

代码：

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        int[] alphabets = new int[26];
        char[] m = magazine.ToCharArray(), r = ransomNote.ToCharArray();
        foreach (char c in m) {
            alphabets[c - 'a']++;
        }
        foreach (char c in r) {
            if (alphabets[c - 'a'] != 0) alphabets[c - 'a']--;
            else return false;
        }
        return true;
    }
} 

执行结果

通过
执行用时：76 ms，在所有 Java  提交中击败了79.50%的用户
内存消耗：42.4 MB，在所有 Java 提交中击败了5.50%的用户 

---

🌻Java 方法：数组存储

思路解析

• 使用a和b两个数组分别存储ransomNote和magazine每个字符出现的次数，

• 如果a里面每个字符出现的次数都小于等于b里面的

• 则判断为true，如果有一个大于b的则返回false

• 这样就可以完成需求啦！

代码：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] a = new int[26];
        int[] b = new int[26];
        char[] aChar = ransomNote.toCharArray();
        char[] bChar = magazine.toCharArray();
        for (int i = 0; i < aChar.length; i++) {
            a[aChar[i] - 'a'] += 1;
        }
        for (int i = 0; i < bChar.length; i++) {
            b[bChar[i] - 'a'] += 1;
        }
        for (int i = 0; i < a.length; i++) {
            if(a[i] > b[i]) {
                return false;
            }
        }
        return true;
    }
} 

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了90.26%的用户
内存消耗：45.2 MB，在所有 Java 提交中击败了8.05%的用户 

---

🌲真题二：字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例1:

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2 

提示：

• 你可以假定该字符串只包含小写字母。

---

🌻C#方法

用数组存放当前字符串中各字符数量

代码：

public class Solution {
public int FirstUniqChar(string s) {

    int[] arr=new int[26];  //26个字母的数组
    for(int i=0;i<s.Length;i++)
    {
        arr[s[i]-'a']+=1;  //a--0 b--1………… 对应位置数字+1
    }
    for(int i=0;i<s.Length;i++)
    {
        if(arr[s[i]-'a']==1)  //当该位置数字为1
        {
            return i;
        }
    }
    return -1;
}
} 

执行结果

通过
执行用时：64 ms，在所有 Java  提交中击败了99.50%的用户
内存消耗：43.4 MB，在所有 Java 提交中击败了16.50%的用户 

---

🌻Java 方法：使用哈希表存储频数

思路解析 可以对字符串进行两次遍历。

在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。

在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 −1。

代码：

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
} 

执行结果

通过
执行用时：26 ms，在所有 Java  提交中击败了39.26%的用户
内存消耗：38.2 MB，在所有 Java 提交中击败了88.05%的用户 

复杂度分析

时间复杂度：O( n )
空间复杂度：O( |Σ|) 

---

💬总结

• 文章采用 C# 和 Java 两种编程语言进行解题。一些方法也是参考力扣大神写的，也是边学习边分享，希望能够尽可能的帮助Android开发的伙伴们，大家一起学习，共同进步！！

• 今天的算法题分享到此结束，这里附上上述的面试题相关的几十套字节跳动，京东，小米，腾讯、头条、阿里、美团等公司19年的面试题。把技术点整理成了视频和PDF（实际上比预期多花了不少精力），包含知识脉络 + 诸多细节。
  详细可扫描下方二维码，免费领取资料。