Leetcode【227、468、848、1081】
Leetcode【227、468、848、1081】
问题描述：【Stack】227. Basic Calculator II
解题思路：
这道题是实现一个基本计算器，即给一个只包括 +、-、*、/、数字和空格的字符串，计算结果。
这道题很容易想到用栈来记录结果。根据“先乘除，后加减”的原则，没有遇到乘除法之前，数字和 +、- 都入栈。遇到乘除号，在栈中找第一个因子，并在字符串中往后找第二个因子，将两者相乘除的结果压入栈中。最后，栈中就只剩下加减法了。然后对栈从头遍历，从左到右计算加减法即可得到最终答案。
这道题代码虽然比较长，但写起来不难，注意字符串和数字之间的转化即可。
Python3 实现：
class Solution:
def calculate(self, s: str) -> int:
stack = []
i = 0
while i < len(s):
if s[i] != ' ':
stack.append(s[i])
# 先做乘除法，并将结果压入栈
if s[i] == '*' or s[i] == '/':
num1, num2, op = 0, 0, stack.pop()
# 从栈中计算第一个乘法或除法因子
cnt = 0
while stack and stack[-1].isdigit():
num1 += int(stack.pop()) * (10 ** cnt)
cnt += 1
# 计算第二个乘法或除法因子，往后遍历
j = i + 1
while j < len(s):
if s[j] != ' ':
if s[j].isdigit():
num2 = num2 * 10 + int(s[j])
else:
break
j += 1
# 将结果压入栈中
if op == '*':
stack.append(str(num1 * num2))
else:
stack.append(str(num1 // num2))
i = j
continue
i += 1
# 栈中只有加减法
i, ans, op = 0, 0, ''
while i < len(stack):
if stack[i] == '+' or stack[i] == '-':
op = stack[i]
else:
if op == '':
ans = ans * 10 + int(stack[i])
else:
# 从栈中得到第二个加数或减数
j, num2 = i, 0
while j < len(stack):
if stack[j].isdigit():
num2 = num2 * 10 + int(stack[j])
else:
break
j += 1
# 结果累加或累减
if op == '+':
ans += num2
else:
ans -= num2
i = j
continue
i += 1
return ans # 最终的结果问题描述：【String】468. Validate IP Address
解题思路：
这道题给一个字符串，判断其是否是有效的 IPv4 地址或者是 IPv6 地址。
这题只要认真读题，没有任何难度。可以根据字符串中是否含有 "." 或者 ":" 来分为可疑 IPv4 和可疑 IPv6，然后写两个函数分别判断即可。对于每个函数，遇到非法的情况就返回 "Neither"，那么剩下的就是合法的 IPv4 和 IPv6 地址了。
Python3 实现：
class Solution:
def validIPAddress(self, IP: str) -> str:
def validIPV4(IP):
groups = IP.split(".")
if len(groups) != 4:
return "Neither"
for group in groups:
if len(group) > 1 and group[0] == '0': # 不能包含前导0
return "Neither"
if group.isdigit() == False: # 空串和负数也包括在这种情况
return "Neither"
if int(group) > 255:
return "Neither"
return "IPv4"
def validIPV6(IP):
groups = IP.split(":")
if len(groups) != 8:
return "Neither"
for group in groups:
if len(group) == 0:
return "Neither" # 防止::情况出现
if len(group) > 4:
return "Neither"
for g in group: # 含有其他字符
if g not in "0123456789abcdefABCDEF":
return "Neither"
return "IPv6"
if IP.find('.') != -1:
return validIPV4(IP)
elif IP.find(':') != -1:
return validIPV6(IP)
else:
return "Neither"问题描述：【String】848. Shifting Letters
解题思路：
这道题是给一个字符串 S 和数组 shifts，将 S 中前 i+1 个字母移位 shifts[i] 次，返回移位后的字符串。
观察所给的例子，shifts = [3,5,9]，"abc" -> "rpl"，其中 "a" 移动了 3+5+9 次，"b" 移动了 5+9 次，"c" 移动了 9 次。
因此，我们只需要重新构造 shifts，将其每一项 shift[i] 变成 shifts[i] 与后面项的累加值之和。然后，对于 S 中的每个字符，移动 shifts[i] 就是答案。时间复杂度为 O(n)，空间复杂度为 O(1)。
注意：循环移动，写代码时要对总移动数进行 %26 操作，防止字符越界。
Python3 实现：
class Solution:
def shiftingLetters(self, S: str, shifts: List[int]) -> str:
for i in range(len(shifts)-2, -1, -1):
shifts[i] += shifts[i+1]
ans = ""
for s, shift in zip(S, shifts):
ans += chr(ord('a') + (ord(s) - ord('a') + shift) % 26)
return ans问题描述：【Stack】1081. Smallest Subsequence of Distinct Characters
解题思路：
这道题是返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
此题可以使用栈来保存结果。如果字符单调递增，就依次入栈；否则就要看已经在栈中的字符将来还有没有可能再次出现，如果还会出现，就把栈中字符依次删去。
以 text = cdadabcc 为例，算法过程如下：
这是一种贪心的思想，栈中总是维持最小的字典序，局部最优则全局最优。时间复杂度为 O(n)，空间复杂度为 O(26) （最多保存26个小写字母）。
Python3 实现：
class Solution:
def smallestSubsequence(self, text: str) -> str:
dic = dict() # 记录每个字符最后的位置
for i in range(len(text)):
dic[text[i]] = i
stack = []
for i in range(len(text)):
if text[i] in stack: # 已经在栈中出现过，跳过
continue
# 对于栈中每个大于text[i]的字符，如果之后还会出现，就弹出
while stack and stack[-1] > text[i] and dic[stack[-1]] > i:
stack.pop()
stack.append(text[i]) # 判断完成后，将当前字符入栈
return "".join(stack)