给定一个 32 位的有符号整数,将这个整数按位翻转。
示例:
Input: 123
Output: 321
Input: -123
Output: -321
Input: 120
Output: 21
如果执行环境只能存储得下 32 位有符号整数,那么其数值范围为 (最高位为符号位),翻转时如果溢出请返回 0。
不考虑溢出的话很简单,使用数学方法,除 10 取余拿出最后一位,加到翻转数上,然后将原数字除 10 取整向前进位即可。
pop = x % 10;
x /= 10;
temp = rev * 10 + pop; // 为了方便讲解引入一个 temp 变量
rev = temp;
对于可能存在的溢出风险,需要进行如下讨论:
如果 temp = rev * 10 + pop
导致溢出,则一定有:
然而实际上,由于最大值或最小值的最高位的数字为 2,即最高位的 pop
的绝对值不会超过 2,所以并不会存在溢出的情况。
上述解法的复杂度为:
class Solution {
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10; // 取余拿最后一位(不用区分正负)
x /= 10; // x 向前进一位(最后一位归零)除法自动取整
if (rev > Integer.MAX_VALUE / 10) return 0;
if (rev < Integer.MIN_VALUE / 10) return 0;
rev = rev * 10 + pop;
}
return rev;
}
}
class Solution:
def reverse(self, x: int) -> int:
rev = 0
if x <= (-2**31): # 判断负数时的例外情况(最小负数时不能取绝对值)
return 0
num = abs(x)
while (num != 0):
pop = num % 10 # 由于python是求模而不是取余,所以要转化为正数
num = num // 10
if rev > ((2**31)-1)//10:
return 0
rev = rev * 10 + pop
if x < 0:
return -rev
else:
return rev
实现一个 atoi
函数,将字符串转换为整数。
首先,函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。
当寻找到第一个非空字符为正或者负号时,则将该符号与之后面尽可能多得连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后的连续的数字字符组合起来,形成整数。
该字符串在有效的整数部分之后存在的多余字符可以被忽略。如果该字符串的第一个非空格字符不是一个有效字符,则不需要进行转换,返回 0(其他不能有效转换的情况同理)。
注意:本题同样存在 32 位限制,如果超出此范围,返回最大值或最小值。
示例:
Input: " -42"
Output: -42
Input: "4193 with words"
Output: 4193
Input: "words and 987"
Output: 0
Input: "-91283472332"
Output: -2147483648
骚方法是使用正则表达式,python 解法中使用了这个方法(其实这里并没有判断溢出,只是为了满足输出条件设置了最大值和最小值函数)。
max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
关于正则表达式的解释如下:
^
:匹配字符串开头[\+\-]
:代表一个+字符或-字符?
:前面一个字符可有可无\d
:一个数字(\D
表示非数字字符)+
:前面一个字符的一个或多个*
是 python 的解包操作,在本例中将含有匹配后的字符串的列表转换为字符串,注意 int(*[]) = 0
。
该方法的复杂度取决于正则操作的复杂度。
class Solution {
public int myAtoi(String str) {
int cValue = Integer.MAX_VALUE / 10; // 21473864
if (str == null) {
return 0;
}
int n = str.length();
int i = 0;
int res = 0;
boolean is_negative = false;
// 跳过所有空格
while (i < n && str.charAt(i) == ' ') {
i++;
}
// 全是空格则直接返回 0
if (i == n) {
return 0;
}
// 判断正负号
if (str.charAt(i) == '-' || str.charAt(i) == '+') {
if (str.charAt(i) == '-') {
is_negative = true;
}
i++; // 进一位
}
// 循环判断数字(如果第一位非数字直接返回0了)
while (i < n && str.charAt(i)>= '0' && str.charAt(i) <= '9') {
int tmp = str.charAt(i) - 48; // '0'对应48
if (!is_negative && (res > cValue || (res == cValue && tmp >= 7))) {
return Integer.MAX_VALUE; // 2147483647
}
if (is_negative && (-res < -cValue || (-res == -cValue && tmp >= 8))) {
return - Integer.MIN_VALUE; // -2147483648
}
res = res * 10 + tmp;
i++;
}
if (is_negative) {
return -res;
}
return res;
}
}
class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
给定一个字符串 s
和一个字符规律 p
,请实现一个支持 '.'
和 '*'
的正则表达式匹配。
'.'
匹配任意单个字符'*'
匹配零个或多个前面的那一个元素匹配需要涵盖整个字符串 s
,而不是部分字符串。
说明:
S
可能为空字符串,且只包含从 a-z
的小写字母。P
可能为空字符串,且只包含从 a-z
的小写字母,以及字符 .
和 *
示例:
Input:
s = "aa"
p = "a"
Output: false
Input:
s = "aa"
p = "a*"
Output: true
Input:
s = "ab"
p = ".*"
Output: true
本题可以考虑回溯和动态规划两种方法。
回溯法属于暴力搜索法的一种,其基本思想是:尝试分步地去解决一个问题,在分步解决问题的过程中,当通过尝试发现现有的分步答案不能得到有效的正确解答的时候,它将取消上一步甚至是上几步的计算,再通过其他可能的分步解答再次寻找问题的答案。
回溯法通常用最简单的递归结构来实现,在反复重复上述的步骤后可能出现两种情况:
对于本题,回溯法的流程如下:
如果只有 '.'
,那么只需要从左到右依次判断 s[i]
和 p[i]
是否匹配:
def isMatch(self,s:str, p:str) -> bool:
if not p: return not s # 边界条件
first_match = s and p[0] in {s[0],'.'} # 比较第一个字符是否匹配,使用set
return first_match and self.isMatch(s[1:], p[1:])
如果有 '*'
,那么它会出现在 p[1]
的位置(因为每次递归只考虑最左边的一位),这时分两种情况:
'*'
代表匹配 0 个前面的元素,如 'bb'
和 'a*bb'
,此时我们可以忽略掉 p
的 'a*'
,直接比较 'bb'
和 'bb'
'*'
代表匹配一个或多个前面的元素,如 'aabb'
和 'a*bb'
,此时我们可以忽略掉 s
的第一个元素(要保证第一个元素匹配),比较 'abb'
和 'a*bb'
(此时又需要再分两种情况比较,通过递归实现)上述两种情况,任意一种是匹配的,我们都可以认为 s
和 p
匹配。
用 和 分别表示匹配串和模式串的长度,则回溯法的复杂度为(证明较复杂,这里只给出结果):
动态规划法的关键就是找到状态和状态转移方程。在本题中,我们将状态 dp[i][j]
定义为 s
的前 i
个能否匹配 p
的前 j
个字符。状态转移方程则需要进行分情况讨论:
情况一:s[i] == p[j] or p[j] == '.'
:此时很容易得到 dp[i][j] = dp[i-1][j-1]
情况二:p[j] == '*'
:此时需要比较星号前面的字符 p[j-1]
和 s[i]
的关系:
p[j-1] != s[i]
:则说明星号匹配了 0 次,此时可以忽略这两个字符,即 dp[i][j] = dp[i][j-2]
p[j-1] == s[i] or p[j-1] == '.'
:则星号可能匹配了 0 次(如 ab 和 abb*),也可能匹配了多次,这是我们得到 dp[i][j] = dp[i][j-2] or dp[i-1][j]
情况三:如果不满足上述两种情况,那么 dp[i][j] = False
关于初始化,首先 dp
数组的大小为字符串和模式串的长度加一,因为要考虑空字符串的匹配情况。然后我们需要对 dp[0][j]
这一行与 dp[i][0]
这一列进行初始化,具体来说:
dp[0][0]=true、dp[0][1]=false
,dp[0][2]
到 dp[0][p.length]
需要基于星号判断dp[1][0]~dp[s.length][0]
都是 false
,因为字符串不为空模式串为空一定不匹配最终的输出为 dp[s.length][p.length]
。
动态规划法仅用到了 个 boolean 类型的缓存变量,且每个 dp[i][j]
只会被计算一次,因此复杂度为:
class Solution {
public boolean isMatch(String s, String p) {
if (p.isEmpty()) return s.isEmpty();
boolean firstMatch = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) ||
p.charAt(0) == '.')); // 单个字符可用等号比较
if (p.length() >= 2 && p.charAt(1) == '*') {
return (isMatch(s, p.substring(2)) ||
(firstMatch && isMatch(s.substring(1), p))); // substring单参数表示起始索引
} else {
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1, n = p.length() + 1;
boolean[][] dp = new boolean[m][n];
// 初始化
dp[0][0] = true;
for (int c = 2; c < n; c++) {
if (p.charAt(c - 1) == '*') dp[0][c] = dp[0][c - 2];
}
int i = 0, j = 0;
// 循环填表
for (int r = 1; r < m; r++) {
i = r - 1;
for (int c = 1; c < n; c++) {
j = c - 1;
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
dp[r][c] = dp[r - 1][c - 1];
} else if (p.charAt(j) == '*') {
if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
dp[r][c] = dp[r - 1][c] || dp[r][c - 2];
} else {
dp[r][c] = dp[r][c - 2];
}
} else {
dp[r][c] = false;
}
}
}
return dp[m - 1][n - 1];
}
}
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p: return not s # 判断p是否为空字符串,作为回溯的最终结束条件,若全部匹配完则返回真
# 比较第一个字符是否匹配,使用set
first_match = bool(s and p[0] in {s[0],'.'}) # 不加bool可能会返回空
# 如果p的第二个字母是 *
if len(p) >= 2 and p[1] == "*":
return self.isMatch(s, p[2:]) or \ # 换行
first_match and self.isMatch(s[1:], p) # 分两种情况
else:
return first_match and self.isMatch(s[1:], p[1:]) # 切片不会溢出
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s) + 1, len(p) + 1 # 注意数组大小要加一
dp = [[False for _ in range(n)] for _ in range(m)] # 初始化dp数组
# 初始化,默认为False的省略
dp[0][0] = True
for c in range(2,n): # dp[0][2]到dp[0][len(p)] 的初始化
if p[c - 1] == '*':
dp[0][c] = dp[0][c-2]
# 开始循环填表
for r in range(1, m):
i = r - 1 # 减一得到索引
for c in range(1, n):
j = c - 1
if s[i] == p[j] or p[j] == '.':
dp[r][c] = dp[r - 1][c - 1]
elif p[j] == '*':
if p[j - 1] == s[i] or p[j - 1] == '.':
dp[r][c] = dp[r - 1][c] or dp[r][c - 2]
else:
dp[r][c] = dp[r][c - 2]
else:
dp[r][c] = False
return dp[m - 1][n - 1]