lc937.重新排列日志文件
题目链接
这没啥好说的，就按部就班就行，但是一部分一部分写出来肯定会有点丑，所以看了一下标准答案，把sorted的特性利用得很好了可以说。原来还能这么用啊。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。
class Solution(object):
def reorderLogFiles(self, logs):
def f(log):
id_, rest = log.split(" ", 1)
return (0, rest, id_) if rest[0].isalpha() else (1,)
return sorted(logs, key = f)
lc819.最常见的单词
题目链接
嗯自己写了一下，比较朴实（见1），应该有split函数可以直接按所有包含的标点分的，不过可能正在re里？然后用replace直接替换不想要的标点也会更快（见2）。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
from collections import defaultdict
class Solution:
def mostCommonWord1(self, paragraph: str, banned: List[str]) -> str:
cnt = defaultdict(int)
processed = ""
for char in paragraph:
if c...
lc580.验证回文字符串II
题目链接
这个很显然就是左右双指针啊，但是我一开始还想了一下碰到不同字符的时候该删除哪个，毕竟有可能没把该删的删了反而把另一边的删了，然后一看别人的，哦直接把两遍都各自删一下试试看取个或就行了啊。这个算法的时间复杂度是O（N），空间复杂度是O（N），不用s[::-1]的方式而是逐个遍历的话时间复杂度是O（1）。
class Solution:
def validPalindrome(self, s: str) -> bool:
def isPalindrome(string):
return string == string[::-1]
left, right = 0, len(s) - 1
...
lc415.字符串相加
题目链接
啊就按部就班地写嘛如1，不过写出来有点慢啊，时间和空间消耗都在后半部分。可能是有什么部分不够优美吧。于是复制了别人的代码如下，思路是完全一样的就细节不太一样别人写得更加简练，于是我也试着用了类似的算carry的方法确实有提升，我还有一部分比较慢的原因是求res的时候用了[-1]可能会慢。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def addStrings1(self, num1: str, num2: str) -> str:
def str2num(c):
return ord(c)-ord("0")
if len(num1) < len(nu...
lc002.两数相加
题目链接
先如1所示自己试着写了一下，但是为什么我的时间效率只能超过百分之70的人啊，复制了更快的答案在2中。这个算法的时间复杂度是O(max(N, M))，空间复杂度是O(max(M, N))。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers1(self, l1: ListNode, l2: ListNode) -> ListNode:
...
mq021.整数转换英文表示
题目链接
这个题好像没啥好多说的，很多边界条件。1是我写的，2是我复制的官方题解，2稍微快一点应该是因为没做int到str的转化，我反正做了省得要用1000取模和余数之类的。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def numberToWords1(self, num: int) -> str:
if num == 0:
return "Zero"
snum = str(num)
length = len(snum)
while length % 3 != 0:
snum = "0" + s...
mq020.最后一块石头的重量II
题目链接
啊啊啊看到题就知道应该是用动态规划，但是具体怎么做好像没什么思路。然后点开题解，就看到其实可以转换成”将石头分成两堆，不断缩小两堆石头重量的差值，最小差值即为最小剩余重量“，机智啊，这就转换成01背包问题了啊。 哦不过我又忘了01背包咋做了，虽然参考之前的“分割等和子集”写出来了但是好像不知道怎么把得到的结果转化成答案…哦发现错误了，原来是因为我的最大重量是上取整的，改成下取整就对了。这个算法的时间复杂度是O（N），空间复杂度是O（NM）。然后实现2是优化了空间之后的，空间复杂度给减少到了O（N）。
class Solution:
def lastStoneWeightII1(self, stones: List[int]) -> int:
...
mq019.除自身以外数组的乘积
题目链接
嗯感觉这题和一个剑指里的题目很相似，都是说不能使用除法。哦看了一眼，其实是完全一样的两个题目。这个算法的时间复杂度是O（N），空间复杂度是O（N）。啊还有一种方式是分别计算上下三角而不是一开始把一层的不同两边对齐。我们首先先算下三角below，算出来之后按逆序将nums里的数字依次相乘来算出每个位置的上三角above并且乘以对应位置下上角的数字得到结果。这样可以在维持时间复杂度的情况下将空间复杂度降到O（1）（因为数组是返回的数组所以不计入空间复杂度的计算）。
class Solution:
def productExceptSelf1(self, nums: List[int]) -> List[int]:
left_product, ri...
mq018.区间合并
题目链接
啊这个题之前做过的，首先按照每个区间的第一个数字排序再开始依次排序，如果后一个区间的左端点大于前一个区间的右端点那么久直接将区间加入答案不做任何改变。当然第一个区间也是直接放到答案里。如果发现并列的两个区间有重复的部分就将前一个区间的右端点设置为后一个区间的右端点，此时我们不需要去管左端点因为已经排序过了，必定符合题意。这个算法的时间复杂度是O（NlogN），空间复杂度是O（logN），分别是排序所需的时间复杂度和空间复杂度。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: ...
mq017.螺旋矩阵
题目链接
啊这个题就是典型的模拟嘛，就是要处理好各种边界吧，所以我花了很多时间在试，最后终于写对了，但是空间复杂度居然比较高？不知道为什么，试试不要写成类的方法而是都写在一个函数里。这个算法的时间复杂度O（NM），空间复杂度是O（1）。
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
def right(x, y, time):
for i in range(time, col-time):
res.a...
260 post articles, 26 pages.