检查句子中的数字是否递增【LC2042】
A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.
- For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.
Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).
Return true if so, or false otherwise.
双指针+parseInt
- 思路：使用双指针找到字符串中的数字，并转化为int类型，与前一个数字进行比较，若不满足严格递增，就返回false
- 实现
class Solution { public boolean areNumbersAscending(String s) { int n = s.length(); int pre = -1; int l = 0; while (l < n){ char ch1 = s.charAt(l); if ( ch1 >= '0' && ch1 <= '9'){ int r = l + 1; while (r < n && s.charAt(r) != ' '){ r++; } int cur = Integer.parseInt(s.substring(l, r)); if (cur <= pre){ return false; } pre = cur; l = r + 1; }else{ l++; } } return true; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
一个指针
- 思路：使用一个指针找到字符串中的数字字符，通过累加的方式将其转化为数字，与前一个数字进行比较，若不满足严格递增，就返回false
- 实现
class Solution { public boolean areNumbersAscending(String s) { int n = s.length(); int pre = -1; int l = 0; while (++l < n){ char ch1 = s.charAt(l); if ( ch1 >= '0' && ch1 <= '9'){ int cur = ch1 -'0'; while (l + 1 < n && s.charAt(l + 1) >= '0' && s.charAt(l + 1) <= '9'){ cur = cur * 10 + s.charAt(++l) - '0'; } if (cur <= pre){ return false; } pre = cur; } } return true; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
split
- 思路：通过split函数获得以空格为分割符的子字符串，判断当前子字符串首字母是否为数字，若是数字，那么与之前出现的数字进行比较，如果不为递增顺序，返回false
- 实现
class Solution { public boolean areNumbersAscending(String s) { int pre = -1; for (String str : s.split(" ")) { if (str.charAt(0) >= 'a') continue; if (Integer.parseInt(str) <= pre) return false; pre = Integer.parseInt(str); } return true; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
