目录
一、881. 救生艇
贪心-排序-双指针
二、8. 字符串转换整数 (atoi)
1.模拟-未考虑溢出
2.考虑溢出问题
三、9. 回文数
1.双指针-字符串
2.数字翻转
3.数字翻转-只翻转一半
一、881. 救生艇
贪心-排序-双指针
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
# 贪心-排序-双指针
n = len(people)
people.sort()
ans = 0
if people[0] >= limit:
return n
left, right = 0, n - 1
# while people[right] >= limit: # 合在后面
# right -= 1
# ans += 1
# 闭区间
# 当l == r时,无论进哪里都是ans+1然后移动指针,跳出循环
while left <= right:
if people[left] + people[right] <= limit:
# ans += 1
left += 1
right -= 1
else:
# ans += 1
right -= 1
ans += 1
return ans
二、8. 字符串转换整数 (atoi)
1.模拟-未考虑溢出
class Solution:
def myAtoi(self, s: str) -> int:
# 模拟
n = len(s)
ans = 0
idx = 0
flag = 1
# 处理前导空格
while idx < n and s[idx] == ' ':
idx += 1
# 处理符号位
if idx < n and (s[idx] == '+' or s[idx] == '-'):
if s[idx] == '-':
flag = -1
idx += 1
# 处理剩余位数
while idx < n:
if not s[idx].isdigit():
break
ans = ans * 10 + int(s[idx])
idx += 1
ans *= flag
ans = min(ans, 2 ** 31 - 1)
ans = max(ans, - 2 ** 31)
return ans
2.考虑溢出问题
来自题解(. - 力扣(LeetCode)),优雅。
class Solution:
def myAtoi(self, s: str) -> int:
# 考虑溢出问题
ans, i, sign, n = 0, 0, 1, len(s)
int_max, int_min, bndry = 2 ** 31 - 1, - 2 ** 31, 2 ** 31 // 10
if not s: return 0 # 空字符串
# 处理前导空格
while s[i] == ' ':
i += 1
if i == n: return 0 # 字符串全为空
# 处理符号位
if s[i] == '-': sign = -1
if s[i] in '+-': i += 1
# 处理剩余位数
for j in range(i, n):
if not '0' <= s[j] <= '9': break
# 溢出,同时考虑正负
if ans > bndry or (ans == bndry and s[j] > '7'):
return int_max if sign == 1 else int_min
ans = 10 * ans + ord(s[j]) - ord('0')
return ans * sign
三、9. 回文数
1.双指针-字符串
class Solution:
def isPalindrome(self, x: int) -> bool:
# 双指针-字符串
if x < 0: return False # 负数肯定不是
s = str(x)
l, r = 0, len(s) - 1
# 闭区间
while l <= r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
2.数字翻转
class Solution:
def isPalindrome(self, x: int) -> bool:
# 数字翻转
# 不使用字符串
if x < 0: return False # 负数肯定不是
# 将数字进行逆序
reverse_num = 0
num = x
while x > 0:
reverse_num = reverse_num * 10 + x % 10
x //= 10
return reverse_num == num
3.数字翻转-只翻转一半
来自官方题解(. - 力扣(LeetCode))。
class Solution:
def isPalindrome(self, x: int) -> bool:
# 数字翻转-只翻转一半
if x < 0 or (x % 10 == 0 and x != 0): return False # 负数肯定不是,末尾为0的也不是
# 这里有一点难想到特判末尾为0的情况
# 将数字进行逆序
reverse_num = 0
# 当原始数字小于或等于反转后的数字时,说明已经处理了一半
# 偶位数==,奇位数<
while x > reverse_num:
reverse_num = reverse_num * 10 + x % 10
x //= 10
return x == reverse_num or x == reverse_num // 10
完
感谢你看到这里!一起加油吧!