按照灵神的建议，基础快刷的内容是这里面的几十道题：编程基础0到1。历经十天也是终于刷完了。
本篇就来总结一下这里面值得探讨或学习的题目。
第一题：1768. 交替合并字符串
这题虽然简单，但我第一次做的时候就是没搞清楚循环的逻辑，导致最终连正确结果都没做出来。实际上，他两个字符串只需满足有一个里面不为空，就可以继续遍历。因此首先是选while循环，其次判断循环的条件是if 第一个字符串不为空 or 第二个字符串不为空， 在这个if里面 再去判断谁不为空。对于当时没做出来这题的我来说，这个判断方式属于是查漏补缺了。完整代码如下：
class Solution: # Python3
def mergeAlternately(self, word1: str, word2: str) -> str:
ans = []
i, m, n = 0, len(word1), len(word2)
while i < m or i < n:
if i < m:
ans.append(word1[i])
if i < n:
ans.append(word2[i])
i += 1
return "".join(ans)
时空复杂度都是O(m+n)的
第二题：389. 找不同
这题印象极其深刻，因为是第一次用位运算秒杀题目。因为题目是把一个字符串打乱顺序之后再额外加一个字母，所以利用异或就可以把相同的字母消除掉，无论是什么顺序。同时也学会了ord()是把字符串转换为ascii码，然后chr()是把ascii值转换回字符串。
class Solution: # Python3
def findTheDifference(self, s: str, t: str) -> str:
k, ans = s + t, 0
for ch in k:
ans ^= ord(ch)
return chr(ans)
时空复杂度都是O(n)的，n是两个字符串长度之和。
第三题：28. 找出字符串中第一个匹配项的下标
这题我还是选择先用最好想的方法做出来，KMP算法以后再学吧哈哈。
那还是比较好想的了，就是遍历长串，遇到和目标串第一个字母相同的就开始遍历后面的部分是否相同，如果都相同就是找到了，如果有不相同的就break掉，然后继续下一个字母的遍历。完整代码如下：
class Solution: # Python3
def strStr(self, haystack: str, needle: str) -> int:
# haystack 里 有 needle
if(len(haystack) < len(needle)):
return -1
for i in range(len(haystack)):
if haystack[i] == needle[0]:
k = i
for j in range(len(needle)):
if k == len(haystack) or haystack[k] != needle[j]:
break
k += 1
else:
return i
return -1
时间复杂度：O(m * n)。 因为遍历长串是m，然后对于m遍历的每个结果都可能会把目标串遍历一遍，也就是n。所以是m * n。
空间复杂度：O(1)
第四题：242. 有效的字母异位词
用一个数组来存每个字母的出现次数，然后遍历另一个数组的时候把统计的次数剪掉，最后看数组里的次数是不是都是0。全部代码如下：
class Solution: # Python3
def isAnagram(self, s: str, t: str) -> bool:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord('a')] += 1
for c in t:
cnt[ord(c) - ord('a')] -= 1
return all(c == 0 for c in cnt)
时间复杂度：O(n)
空间复杂度：O(1)
第五题：283. 移动零
双指针：non_0指针表示的是非零元素所放的位置，current是遍历每个元素，然后如果元素非零，就把元素放在non_0的位置，这样遍历完所有元素之后就会把非零元素按照原本的先后次序放在数组里了，然后后面的都是0了。完整代码如下：
class Solution: # Python3
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
non_0, current = 0, 0
for current in range(len(nums)):
if nums[current] != 0:
nums[current], nums[non_0] = nums[non_0], nums[current]
non_0 += 1
时间复杂度：O(n)。
空间复杂度：O(1)。
第六题：66. 加一
这题主要是判断尾巴后面的数是否是9，因为如果是9就得进位，如果不是9就直接加一就好。
class Solution: # Python3
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
else:
digits[i] = 0
return [1] + digits
时空复杂度均为：O(n)。前者是把List遍历一遍，后者是最坏情况下要创建一个长度为n+1的列表。
第七题：1822. 数组元素积的符号
这题我一开始想的就是算出结果再判断正负，但是实际上只需用0和1就好，每次乘一个负数时就把1变成-1，这样就可以不用算乘积就可以直接算符号。完整代码如下：
class Solution: # Python3
def arraySign(self, nums: List[int]) -> int:
ans = 1
for num in nums:
if num == 0:
return 0
if num < 0:
ans = -ans
return ans
时间复杂度：O(n)
空间复杂度：O(1)
第八题：896. 单调数列
这题也是想了很久的方法也没找到合适的范围来限制所有情况，于是看解答了：用两个bool类型变量来判断是否是升或者降序列，如果两者还有True就说明是单调序列，如果两个都是False就说明不是单调序列。完整代码如下：
class Solution: # Python3
def isMonotonic(self, nums: List[int]) -> bool:
if len(nums) == 1:
return True
is_increasing = True
is_decreasing = True
for i in range(1, len(nums)):
if nums[i] < nums[i-1]:
is_increasing = False
if nums[i] > nums[i-1]:
is_decreasing = False
return is_increasing or is_decreasing
时间复杂度：O(n)
空间复杂度：O(1)
第九题：58. 最后一个单词的长度
从后往前，先把后面的空格遍历完，然后再开始计数非空格的地方，直到下一个空格。
class Solution: # Python3
def lengthOfLastWord(self, s: str) -> int:
n = len(s)
count = 0
i = n - 1
while i >= 0 and s[i] == ' ':
i -= 1
while i >= 0 and s[i] != ' ':
count += 1
i -= 1
return count
时间复杂度：O(n)
空间复杂度：O(1)
第十题：709. 转换成小写字母
这题 一行就结束，但是包含的是很多句话的意思。 先看代码再解释：
class Solution: # Python3
def toLowerCase(self, s: str) -> str:
return "".join(chr(asc | 32) if 65 <= (asc := ord(ch)) <= 90 else ch for ch in s)
首先是对s中的字符取ascii码并赋值给asc， （这里利用的是 ：= 海象运算符）， 然后判断这个ascii码是否在大写字母范围以内，如果是在范围以内，则 把ascii值 或 上32 就变成了小写字母的ascii码，然后用chr()变成字符串，再join到字符串里。
换句话重新说一下就是，遍历字符串s，如果是小写字母就直接加入到结果集，如果是大写字母就转换为小写然后加入结果集。大写字母怎么变成小写字母呢？那就是先获取ascii码，然后或32得到对应小写字母的ascii，再用chr()变成小写字母。
时间复杂度：O(n)。毕竟都遍历了一遍嘛
空间复杂度：O(n)。最后生成的是一个长为n的字符串
第十一题：1275. 找出井字棋的获胜者
这题一开始想的比较复杂，要判断各种情况，感觉应该会有更简单的方式。但是后来看到一种很妙的方法，是得判断各种情况，但是思路非常清晰：
首先用row、col、diag、anti_diag变量来记录行、列、斜线的占领情况，以便后面方便判断是否有人赢的棋局。
随后每下一步棋 就是根据二维数组的数据来 把结果填入到行、列、斜线中，然后判断行、列、斜线是否达到了3。同时看是哪个玩家正在下棋。
如果有到了3的，就说明当前的人赢了，因为我们是在当前玩家下完一步后里面统计并判断。
如果一直都没有人赢，就看下完步骤时，棋局是否填满。
这题我觉得很妙的地方有亮点：1. 它用player的数值在1和-1之间切换来实现玩家的转变。2. 他把胜利条件定为行、列、斜线的和为3，这是巧妙运用了第一点，因为只要在一个行、列、斜线上既有玩家A的棋，又有玩家B的棋，则在程序里就会表现为绝对值不可能到3.
class Solution: # Python3
def tictactoe(self, moves: List[List[int]]) -> str:
# count for wins
row = [0] * 3
col = [0] * 3
diag = 0
anti_diag = 0
# player A = 1, player B = -1
player = 1
for move in moves:
r, c = move
row[r] += player
col[c] += player
if r == c:
diag += player
if r + c == 2:
anti_diag += player
# check for wins
if (abs(row[r]) == 3 or
abs(col[c]) == 3 or
abs(diag) == 3 or
abs(anti_diag) == 3):
return "A" if player == 1 else "B"
# switch player
player *= -1
if len(moves) == 9:
return "Draw"
else:
return "Pending"
时间复杂度：O(n)
空间复杂度：O(1)。指运用了有限的额外变量
第十二题：1041. 困于环中的机器人
这题主要学习的有两点：1. 定义方向数组，这样就方便在判断指令后快速给不同方向赋值。同时也可以利用%4来改变方向。2. 数学结论：只有机器人既没回到原点，又方向没变，才会是不在循环内，否则一定在循环内。就不证明了。完整代码如下：
class Solution: # Python3
def isRobotBounded(self, instructions: str) -> bool:
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]
cur_direction = 0
x, y = 0, 0
for move in instructions:
if move == "G":
dx, dy = direction[cur_direction]
x += dx
y += dy
elif move == "L":
cur_direction = (cur_direction - 1) % 4
elif move == "R":
cur_direction = (cur_direction + 1) % 4
return (x, y) == (0, 0) or cur_direction != 0
时间复杂度：O(n)
空间复杂度：O(1)。 还是有限个数的变量。所以O(1)
第十三题：54. 螺旋矩阵
这题就是按照题意去做就好了，关键就在于如何去控制边界条件。我才用的是最好理解的办法：拿四个变量分别控制四个方向的边界。剩下的就是注意遍历的细节了，例如row和col分别代表什么，在某一方向的遍历里他们的数值是放在行还是列里？完整代码如下：
class Solution: # Python3
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
top, bottom = 0, m
left, right = 0, n
result = []
while top < bottom and left < right:
for col in range(left, right):
result.append(matrix[top][col])
top += 1
for row in range(top, bottom):
result.append(matrix[row][right - 1])
right -= 1
if top < bottom:
for col in range(right - 1, left - 1, - 1):
result.append(matrix[bottom - 1][col])
bottom -= 1
if left < right:
for row in range(bottom - 1, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
时空复杂度均为O(m * n)，前者因为二维数组被遍历一遍；后者因为结果集合存放的个数为m * n。
第十四题：73. 矩阵置零
这题有点意思，我一开始没做出来。后来看题解恍然大悟。
首先我们看看第一行第一列里是否有0，并且用两个布尔变量来表示。然后接下来遍历内部数据，如果找到一个0，就把它的行和列分别在 第一行、第一列 对应的位置表示为0。这样哪些行哪些列需要置为0就十分清晰了。最后根据之前存的两个布尔值来判断是否需要将第一行、第一列也置为0。 完整代码如下：
class Solution: # Python3
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
if not matrix or not matrix[0]:
return
m, n = len(matrix), len(matrix[0])
isFirstRowZero = False
isFirstColZero = False
# check first row
for i in range(n):
if matrix[0][i] == 0:
isFirstRowZero = True
break
# check first col
for j in range(m):
if matrix[j][0] == 0:
isFirstColZero = True
break
# use the first row and col to record 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# set rows to 0
for i in range(1, m):
if matrix[i][0] == 0:
for j in range(1, n):
matrix[i][j] = 0
# set cols to 0
for i in range(1, n):
if matrix[0][i] == 0:
for j in range(1, m):
matrix[j][i] = 0
if isFirstRowZero:
for i in range(n):
matrix[0][i] = 0
if isFirstColZero:
for j in range(m):
matrix[j][0] = 0
时间复杂度：O(m * n)。遍历二维数组
空间复杂度：O(1)。
第十五题：976. 三角形的最大周长
这题巧妙的点就在于在排好序后，从后往前遍历时，满足条件的第一个就一定是最大的值。
class Solution: # Python3
def largestPerimeter(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
for i in range(n - 1, 1, -1):
if nums[i-2] + nums[i-1] > nums[i]:
return nums[i-2] + nums[i-1] + nums[i]
return 0
时间复杂度：O(n * log n)。 因为排序
空间复杂度：O(1)
第十六题：1232. 缀点成线
这题的收获在于，用向量的方式是做乘法毕竟结果，可以避免除法带来的 精度上的问题 以及 处理除数为0的麻烦。
class Solution: # Python3
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
# 方向向量
x1 = coordinates[1][0] - coordinates[0][0]
y1 = coordinates[1][1] - coordinates[0][1]
for coordinate in coordinates:
x2, y2 = coordinate
x3 = x2 - coordinates[0][0]
y3 = y2 - coordinates[0][1]
if(x1 * y3 != x3 * y1):
return False
return True
时空复杂度： O(n)的，O(1)
第十七题：50. Pow(x, n)
本题主要学到的是灵神发布的 快速幂， 我第一次是按常规解法但是如果乘积次数太多且位数太多就会超时，因此快速幂十分有必要。
以下就是快速幂的核心代码：
while n: # 从低到高位 逐个枚举n的比特位
if n & 1:
ans *= x
x *= x
n >>= 1
解释就是 n & 1是看n二进制的最后一位是否为1，是的话就 ans *=，不是的话就不乘。然后判断一位之后都要移一位，且x要做一次幂运算。这样就是利用快速幂的原理了。
完整代码如下：
class Solution: # Python3
def myPow(self, x: float, n: int) -> float:
if x == 0:
return 0.0
if n < 0:
n = -n
x = 1/x
ans = 1
while n: # 从低到高位 逐个枚举n的比特位
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
时间复杂度：O(log n)。因为每次右移一位，就是相对于n除以2，看n能被2除几次就是 log n。
空间复杂度：O(1)
第十八题：206. 反转链表
经典中的经典，考中之考！
搞清楚每个指针每次在指什么东西就好了，流程并不难：
pre是指向前一个节点的， cur是指向当前节点，nxt是临时节点用来临时保存cur.next的值。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution: # Python3
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
时空复杂度：O(n)。O(1)。
第十九题：2. 两数相加
本题学到了1. 递归的用法：把一个问题划分为相同的但是范围更小的问题就适合用递归。2. 当L1和L2不确定谁长时，可以写成 如果L2更长就把它交换到L1，这样可以使代码简洁一点，因为后面可以避免一些不必要的判断。3. 剩下的就是两个的值加上进位carry等于总和了，然后总和s取模就是留在当前位置的数，总和s // 10 就是进位。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution: # Python3
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
if l1 is None and l2 is None:
return ListNode(carry) if carry != 0 else None
if l1 is None:
l1, l2 = l2, l1
s = carry + l1.val + (l2.val if l2 else 0)
l1.val = s % 10
l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, s // 10)
return l1
时空复杂度均为O(n)。前者是长度更长的列表；后者是递归需要O(n)的栈空间。
希望对学习有所帮助！接下来应该是专题篇章了，即每次都是同一类型的题。
