lc953.验证外星语词典
题目链接
emmm直接把列表里的单词每个都按顺序翻译了一遍再检查是否是已经按照英语的排序正确了。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。但是由于我们这样将每个字符都翻译了一遍其实没有必要，更快的实现如2所示，依次比较相邻的两个单词即可，比较都过程是依次比较第一个不同的字母的index是否满足顺序关系，这种方法的一个特殊情况就是当单词不等长的时候要先判断一下。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def isAlienSorted1(self, words: List[str], order: str) -> bool:
eng = [chr(ord("a")+x) for x in...
lc560.和为K的子数组
题目链接
这个题，一开始是觉得应该用滑动窗口做，或者动态规划做，可是思路感觉不是特别清晰。看了答案之后才懂的，如1所示是未优化过的，这个算法的时间复杂度是O（N），空间复杂度是O（N）。这个思路简单地说就是用前缀和，在遍历数组的过程中，将前缀和一一记下，并且判断某个时刻所对应的“k-前缀和”的值是否在字典中以及为多少，将该数字加到答案上。啊话说不知道为什么，用现成的defaultdict反而速度快一点。
class Solution:
def subarraySum1(self, nums: List[int], k: int) -> int:
preSum, ans = 0, 0
preSumFreq = collections.de...
lc098.验证二叉搜索树
题目链接
先是自己写了一下，emmm写的是考察临接的左右子节点是否满足条件，并没有保证整棵子树。要保证正确的话在递归的时候要传递相应的上下界才行。递归的话时间复杂度是O（N），空间复杂度是O（N）。除了递归之外还有一种做法就是利用二叉搜索树的中序遍历能产生一个严格递增的数组的性质，如2所示。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class ...
lc049.字母异位词分组
题目链接
一开始我还以为要考虑两个完全一样的词要不要排除呢看来不需要那么更简单了，介绍两种思路，一种是将单词里的字母排序，另外一种是用26个数字编码单词。前一个个算法的时间复杂度是O（NKlogK），K是字符串的最大长度。空间复杂度是O（NK）。后一个算法的时间和空间复杂度都是O（NK）。
class Solution:
def groupAnagrams1(self, strs: List[str]) -> List[List[str]]:
res = collections.defaultdict(list)
for s in strs:
ranked = "".join(sorted(s))
...
mq034.移除无效的括号
题目链接
啊思路就是记录下无效括号的位置然后再原字符串中除去，但是为什么我怎么慢哦，原来是因为别人在重新生成字符串时是用列表切片方式的所以很快。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
class Solution:
def minRemoveToMakeValid1(self, s: str) -> str:
redundant = list()
stack = list()
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
elif s[i] == ")":
...
mq033.前K个高频单词
题目链接
比较显然的就是用defaultdict或者直接用Count数一下排个序然后把相应的数据输出即可，这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。然后第K大问题总是会有堆，鉴于很久没复习了我先复制粘贴在这里。
from collections import Counter
class Solution:
def topKFrequent1(self, words: List[str], k: int) -> List[str]:
cnt = Counter(words)
res = sorted(cnt.items(), key=lambda x: (-x[1], x[0]))
return [x...
mq032.会议室II
题目链接
做过了，纠结了一下写出来了，但是速度不是很快。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。额想看一下别人的，结果发现时间复杂度和我这个一样的呀？？
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
tmp = []
for elem in intervals:
tmp.append((elem[0], 1))
tmp.append((elem[1], -1))
ranked = sorted(tmp, key=lambda x: x)
...
mq031.有效的括号
题目链接
快速地写了一下，没什么难度。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
class Solution:
def isValid(self, s: str) -> bool:
d = {"(": ")", "[": "]", "{": "}"}
stack = []
for c in s:
if c in "([{":
stack.append(c)
else:
if not stack:
return False
tm...
mq030.反转链表
题目链接
啊要命了，很快就写出了用迭代实现的方法，但是卡在了用递归反转，然后就跑去玩了很久，赶快跑过来把别人的代码先抄一下否则今天就废了。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList1(self, head: ListNode) -> ListNode:
prev = None
while head...
260 post articles, 26 pages.