计算机创新协会冬令营——暴力枚举题目01

发布时间:2024年01月03日

首先是欢迎大家参加此次的冬令营,我们协会欢迎所有志同道合的同学们。话不多说,先来看看今天的题目吧。

题目

力扣题号:2351.?第一个出现两次的字母

注:下述题目和示例均来自力扣

题目

给你一个由小写英文字母组成的字符串?s?,请你找出并返回第一个出现?两次?的字母。

注意

  • 如果?a?的?第二次?出现比?b?的?第二次?出现在字符串中的位置更靠前,则认为字母?a?在字母?b?之前出现两次。
  • s?包含至少一个出现两次的字母。

示例

示例 1:

输入:s = "abccbaacz"
输出:"c"
解释:
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母,因为在所有字母中,'c' 第二次出现的下标是最小的。

示例 2:

输入:s = "abcdd"
输出:"d"
解释:
只有字母 'd' 出现两次,所以返回 'd' 。t

提示?

  • 2 <= s.length <= 100
  • s?由小写英文字母组成
  • s?包含至少一个重复字母

Java题解一:直接暴力

给了一个小写英文字母组成的字符串s,找出第一个出现两次的字母,并且可以在注意中看见,如果a的第二次比b的第二次位置更靠前,就认为a在b之前先出现,那么就需要一个信号位置来判断。代码如下,注释很详细

class Solution {
    public char repeatedCharacter(String s) {
        // 在java中字符串不好操作,先转换成字符数组
        char[] charS = s.toCharArray();
        // 由于第二个字母先出现的才算真正的先出现所以这里记录一下
        char res = 'A';
        int position = Integer.MAX_VALUE;
        for (int i = 0; i < charS.length; i++) {
            for (int j = i + 1; j < charS.length; j++) {
                if (charS[i] == charS[j] && j < position) {
                    res = charS[i];
                    position = j;
                }
            }
        }
        return res;
    }
}

暴力就是很慢┭┮﹏┭┮


如果采用数组进行优化呢?

直接记录每一个字母出现了多少次,达到了两次的要求之后直接返回即可。

Java题解二:数组解法

class Solution {
    public char repeatedCharacter(String s) {
        // 在java中字符串不好操作,先转换成字符数组
        char[] charS = s.toCharArray();
        // 这里定义一个长度为26的数组,代表a-z
        // ASCII码表都知道吧,通过这个转化的 a 是 97
        int[] ans = new int[26];
        for (int i = 0; i < charS.length; i++) {
            int position = charS[i] - 'a';
            if (ans[position] == 0){
                ans[position]++;
            }else if (ans[position] == 1){
                // 这里已经等于1了,那么这次再+就是2
                // 是它!!1出现了我的目标字母@!!!
                return charS[i];
            }
        }
        // 由于题目的条件可以看出这里其实不会有没有两次出现的情况
        // 如果有,根据题目要求来即可比如返回-1啥的,我这里就随意返回了
        return 'A';
    }
}

直接打败全世界的人!!


其他语言同步,我就只提供优化的方法了,暴力java的应该也能看懂

C++

class Solution {
public:
    char repeatedCharacter(string s) {
        // 将字符串转换为字符数组
        std::vector<char> charS(s.begin(), s.end());

        // 定义一个长度为26的数组,代表a-z
        // 'a'的ASCII码是97
        std::vector<int> ans(26, 0);

        for (int i = 0; i < charS.size(); i++) {
            int position = charS[i] - 'a';
            if (ans[position] == 0) {
                ans[position]++;
            } else if (ans[position] == 1) {
                // 已经等于1,表示找到目标字符
                return charS[i];
            }
        }

        // 如果没有找到重复字符,则返回默认字符
        return 'F';
    }
};

?Python3

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        # 将字符串转换为字符列表
        charS = list(s)

        # 定义一个长度为26的数组,代表a-z
        # 'a'的ASCII码是97
        ans = [0] * 26

        for char in charS:
            position = ord(char) - ord('a')
            if ans[position] == 0:
                ans[position] += 1
            elif ans[position] == 1:
                # 已经等于1,表示找到目标字符
                return char

        # 如果没有找到重复字符,则返回默认字符
        return 'F'


结语

虽然我们这道题是一个暴力枚举的题目,但是一般能够暴力的题目都有优化的空间,大家可以好好理解一下。

ヾ( ̄▽ ̄)Bye~Bye~

文章来源:https://blog.csdn.net/DDDDWJDDDD/article/details/135369933
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。