亲宝软件园·资讯

展开

C++ LeetCode1796字符串中第二大数字

LetMeFly 人气:0

LeetCode 1796.字符串中第二大的数字

力扣题目链接:leetcode.cn/problems/se…

给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 。

混合字符串 由小写英文字母和数字组成。

示例 1:

输入:s = "dfa12321afd"
输出:2
解释:出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。

示例 2:

输入:s = "abc1111"
输出:-1
解释:出现在 s 中的数字只包含 [1] 。没有第二大的数字。

提示:

方法一:遍历

题目分析

题目中说的“第二大”数字,到底什么是第二大?英文原文是“Second largest”

也就是说,是从大到小第二个数,不是从小到大第二个数。

样例中“123”,不论是从小到大还是从大到小都是“2”,不如把样例换成“1234”,这样答案是“3”,就一目了然了。

解题思路

首先开辟一个大小为“10”的布尔数组,初始值为false

接着遍历字符串,如果字符串的某个字符是数字,那么就将对应的那个布尔值标记为true

接着,用一个变量foundFirst来记录是否已经找到了最大值,初始值为false

90遍历布尔数组,如果遇到某个值为true,就看foundFirst是否已经为true

若遍历结束后仍未找到“第二大数”,那么就返回-1

复杂度分析

AC代码

C++

class Solution {
public:
    int secondHighest(string& s) {
        bool bin[10] = {false};
        for (char c : s) {
            if (c >= '0' && c <= '9')
                bin[c - '0'] = true;
        }
        bool foundFirst = false;
        for (int i = 9; i >= 0; i--) {
            if (bin[i]) {
                if (foundFirst) {
                    return i;
                }
                else {
                    foundFirst = true;
                }
            }
        }
        return -1;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论