检查句子中的数字是否递增

标签: 字符串

难度: Easy

句子是由若干 token 组成的一个列表，token 间用 单个 空格分隔，句子没有前导或尾随空格。每个 token 要么是一个由数字 0-9 组成的不含前导零的 正整数 ，要么是一个由小写英文字母组成的 单词 。

  • 示例，"a puppy has 2 eyes 4 legs" 是一个由 7 个 token 组成的句子："2" 和 "4" 是数字，其他像 "puppy" 这样的 tokens 属于单词。

给你一个表示句子的字符串 s ，你需要检查 s 中的 全部 数字是否从左到右严格递增（即，除了最后一个数字，s 中的 每个 数字都严格小于它 右侧 的数字）。

如果满足题目要求，返回 true ，否则，返回 false 。

示例 1：

example-1

输入：s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
输出：true
解释：句子中的数字是：1, 3, 4, 6, 12 。
这些数字是按从左到右严格递增的 1 < 3 < 4 < 6 < 12 。

示例 2：

输入：s = "hello world 5 x 5"
输出：false
解释：句子中的数字是：5, 5 。这些数字不是严格递增的。

示例 3：

example-3

输入：s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
输出：false
解释：s 中的数字是：7, 51, 50, 60 。这些数字不是严格递增的。

示例 4：

输入：s = "4 5 11 26"
输出：true
解释：s 中的数字是：4, 5, 11, 26 。
这些数字是按从左到右严格递增的：4 < 5 < 11 < 26 。

提示：

  • 3 <= s.length <= 200
  • s 由小写英文字母、空格和数字 0 到 9 组成（包含 0 和 9）
  • s 中数字 token 的数目在 2 和 100 之间（包含 2 和 100）
  • s 中的 token 之间由单个空格分隔
  • s 中至少有 两个 数字
  • s 中的每个数字都是一个 小于 100 的 正 数，且不含前导零
  • s 不含前导或尾随空格

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        pre = i = 0
        while i < len(s):
            if s[i].isdigit():
                cur = 0
                while i < len(s) and s[i].isdigit():
                    cur = cur * 10 + int(s[i])
                    i += 1
                if cur <= pre:
                    return False
                pre = cur
            else:
                i += 1
        return True

Explain

此题解采用逐字符检查的方法来遍历句子中的每个字符。当遇到数字字符时，会把当前的数字字符转换为整数值，并与前一个数字进行比较。如果当前数字不大于前一个数字，则直接返回 false。如果循环结束没有发现递增顺序的问题，则返回 true。这个方法有效地利用了字符串遍历和条件判断来确保所有数字的递增顺序。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        pre = i = 0  # 初始化前一个数字 pre 为 0，索引 i 为 0
        while i < len(s):  # 遍历字符串中的每个字符
            if s[i].isdigit():  # 如果当前字符是数字
                cur = 0  # 初始化当前数字 cur
                while i < len(s) and s[i].isdigit():  # 继续读取整个数字
                    cur = cur * 10 + int(s[i])  # 将字符转换为数字并构建整数
                    i += 1  # 移动索引到下一个字符
                if cur <= pre:  # 如果当前数字不大于前一个数字
                    return False  # 返回 False，因为不满足递增关系
                pre = cur  # 更新前一个数字为当前数字
            else:  # 如果当前字符不是数字
                i += 1  # 移动索引到下一个字符
        return True  # 如果所有数字都递增，返回 True

Explore

在此解法中，初始的前一个数字 `pre` 被设为 0。这种设定是假设句子中不会包含小于或等于 0 的数字，从而确保第一个数字总是大于 0。如果第一个遇到的数字大于 0，比较总是成立，算法继续正常执行。如果句子开始就是数字且该数字为 1 或更大，它将成功地与 0 比较，并被接受为新的 `pre` 值。

在提供的代码示例中，并没有直接处理整数溢出的问题。Python 通常会自动处理大整数，但在其他编程语言中，如 C++ 或 Java，这可能会导致整数溢出。如果考虑到整数溢出，我们需要在数字构建过程中检查当前数字是否将超过整数允许的最大值，或者转而使用可以处理更大数值的数据类型。

当算法遇到非数字字符时，`else` 分支将执行，索引 `i` 通过 `i += 1` 自增，从而跳过当前的非数字字符。循环继续执行，直到 `i` 再次指向数字或字符串遍历完成。这保证了每次遇到数字时，都会重新开始检查和更新数字，而非数字字符被逐一跳过。

当输入的句子为空，或者完全不包含任何数字时，由于没有任何比较发生，算法将返回 `True`。这是因为没有找到违反递增规则的情况。在这种特定逻辑下，不需要特别处理这种情况，因为从技术上讲，一个空的或没有数字的序列默认是满足递增条件的。