05 替换空格
解题思路：
字符串是不可变类型，本题中需要替换字符串中的某个字符，可以使用replace方法直接替换;以下是遍历字符串的方式进行求解的，逐个判断字符串中的字符是否为空，若为空，将新字符串添加相应字符串;否则添加原来字符。该方法的时间复杂度为o(n)
代码：
class Solution:
def replaceSpace(self, s: str) -> str:
# return s.replace(' ', '%20')
tmp = ''
for i in range(len(s)):
tmp += '%20' if s[i] == ' ' else s[i]
return tmp
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder(); // 可变的字符串对象，没有线程安全
for(Character c : s.toCharArray()){ // for写法，字符串转字符列表
if(c == ' '){res.append("%20");} // 双引号
else{res.append(c);}
}
return res.toString();
}
}
在Java和python3中，string都是不可变类型，需要增加新变量来得到最后的结果。而C++是可变类型，通过s.resize()可以改变字符串长度，按照空格数改变字符串长度，然后从后往前寻找空格，往相应地方添加题目中要求的字符。
class Solution {
public:
string replaceSpace(string s) {
// 首先先确定空格的数量，然后更改字符串的长度，用两个指针从后往前遍历，如果遇到空格，从后往前将20%写上
int len = s.size();
int count = 0;
for(char c : s){
if(c == ' '){ // C++中单字符用单引号
count++;
}
}
s.resize(len + count * 2);
for(int i=len-1,j=s.size()-1;i
if(s[i] == ' '){
s[j] = '0';
s[j-1] = '2';
s[j-2] = '%';
j -= 2;
}else{
s[j] = s[i];
}
}
return s;
}
};
06 从尾到头打印链表
我的思路就是逐个读取链表节点的value得到一个list，然后逆序输出list即可，时间复杂度和空间复杂度都是o(n)
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
result = []
# 正序读取O(n)
while head is not None: # 可以简写为：while head:
result.append(head.val)
head = head.next
# list逆序输出,下标操作
return [result[len(result)-i-1] for i in range(len(result))]
# python中list逆序可以直接通过切片实现
# return result[::-1]
解题方法：
递归回溯法：
若head不是空，那么逐个遍历链表，直到head为空时，再依次回溯回去。在python的代码中，我认为self.reversePrint()本身就是一个递归的机制，表示求某条链表的逆序。
return self.reversePrint(head.next) + [head.val] if head else []
辅助栈法：
由于本题是单链表，需要逆序输出值，考虑到栈先进后出的原则，考虑用栈来解决此题。以上我的思路就是这种方法，在python中，使用list就足够。在Java中，需要使用LinkedList stack = new LinkedList()定义一个栈，然后stack.removeLast()出栈存储值。
09 用两个栈实现队列
首先，明确队列和栈的工作方式。队列是“先进先出”，栈是“先进后出”。本题需要完成两个功能，分别是添加和删除，即往队尾添加新元素，删除队首的元素。如果用一个栈来完成队列的操作，添加元素时，直接添加即可;删除元素时，弹出最后一个值(栈底元素)就需要逐个弹出所有元素。那么可以用一个栈完成添加操作，另一个栈逆序存储列表顺序，完成删除操作。在python中，可以直接用list作为栈。
class CQueue:
def __init__(self):
# 初始化队列，即两个空栈
self.A, self.B = [], []
def appendTail(self, value: int) -> None:
# 添加队尾元素
self.A.append(value)
def deleteHead(self) -> int:
# 删除队首元素，并弹出该值
if self.B: return self.B.pop()
# 队列为空
if not self.A: return -1
# 将A逆序存储到B中
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
此处注意一个点：判断列表是否为空时，直接if list，若True表示不空，Flase表示空。is not None表示对象不存在。
20 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。
暴力破解，逻辑判断，if-else堆砌：(没有得到最终答案，仍然考虑不全面)主要考虑小数点左右，e左右两侧的合格与否，判断两侧字符串是否为整数，存在给定字符中字符顺序导致的各种问题。
class Solution:
def __init__(self):
self.mark = None
def isNum(self, s):
try:
int(s) # 直接转为float就可以判断是否为数值型字符串了
return True
except ValueError:
return False
def split(self, s, c):
pos = s.find(c)
return s[:pos], s[pos + 1:]
def isNumber(self, s: str) -> bool:
sym = ['+', '-', '.', 'e', 'E']
num = [repr(i) for i in range(10)]
s = s.strip(' ')
if self.isNum(s): return True # 若本身就是整数
if s == '': return False
# 保证字符在合法范围
for c in s:
# print(c)
if c not in sym + num:
return False
for c in s:
# 寻找小数点的位置,如果有一侧为整数暂时标记成True(方便1.,.2这种的)
if c == '.':
if s.count(c) <= 1:
left, right = self.split(s, c)
if right != '' and right[0] in ['+', '-']:
return False # 小数点右侧不能有符号
if (self.isNum(left) and right == '') or (self.isNum(right) and left == ''):
return True # 1. .2
elif self.isNum(left) and self.isNum(right):
return True # 1.2
else: return False
# 寻找e的位置,再判断是否有小数点,然后判断完成直接return
if c in ['e', 'E']:
left, right = self.split(s, c)
if (self.isNum(left) or (self.isNum(self.split(left, '.')[0]) or self.isNum(self.split(left, '.')[1]))) and self.isNum(right): # 左侧是整数/小数，右侧是整数
self.mark = True
# print('e', self.mark)
else: self.mark = False
return self.mark
else: self.mark = False
return self.mark
haha = Solution()
test = ['1.+2', '.-4', '9.-', '+++', '. 1', 'ee', ' ', '..', '12E', '1a3.12', '1.2.3', '+-1', '.', 'e', '1.0e', '.0e',
'1e1.2', '1.2e3.4', # 都是False
'1.0', ' .2', '1. ', '+5.4e3', '1.1e2', '0.e2', '123', '+12', '-12', '-1E-16', '5e2', '+.8'] # 都是True
for i in test:
print(i, haha.isNumber(i))
官方解题方法：：看着有一个好高级的名字，其实还是考虑各种情况!
本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。空格[ ]、数字[0-9]、正负号[+, -] 、小数点[.]、幂符号[e, E]。
状态定义:
按照字符串从左到右的顺序，定义以下 9 种状态。
开始的空格：字符串左右两侧的空格，内部空格按照其他字符处理，直接判为False
幂符号前的正负号：幂符号左右都可以有正负号;幂符号后不能是小数;前后都不能为空
小数点前的数字：小数点前后只能一处为空，另一处需要数字，小数点后不可有符号，小数点前可以正负号
小数点、小数点后的数字
当小数点前为空格时，小数点、小数点后的数字
幂符号
幂符号后的正负号
幂符号后的数字
结尾的空格
结束状态：
合法的结束状态有 2, 3, 7, 8
补课
24.翻转列表，输出新列表的头节点
方法一：迭代双指针
遍历单链表，修改next指针(时间复杂度为O(N)，空间复杂度为O(1))
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None # 标记当前节点，前一节点
while cur: # 若当前节点存在，执行循环体
tmp = cur.next # 暂存下一节点
cur.next = pre # 修改当前节点的方向为前一节点
pre = cur # 修改当前按节点为前一节点，为下一次循环做准备
cur = tmp # 将下一节点作为下一次的当前节点
return pre
方法二：递归回溯法
考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。(时间复杂度、空间复杂度均为O(N))。递归就是将一部分重复的操作提取出来，函数内部调用自身的方式进行简单的循环，设置递归出口以及返回值即可。以下操作，就是逐步遍历整条单链表，直到找到最后一个节点，然后用res标记反链的头节点(在找到最后一个节点，发现cur为None的时候，res获得了返回值pre，此时的pre为最后一个节点，之后res一直没有改变)，然后依次改变前面几对节点的连接方向。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
def reverse(cur, pre): # 交换两个节点的方向
if not cur: return pre # 递归出口
res = reverse(cur.next, cur) # 递归
cur.next = pre # 执行操作
return res
return reverse(head, None)
30 包含 min 函数的栈
包含 min 函数的栈：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
在python中，list就可以当作是一个栈，并且list本身就包含pop,push,min方法。如果自己实现这个程序，寻找最小值可能最容易想到的就是遍历比较，这样需要消耗的时间复杂度为O(N)。那么，题目的难点就在于min的复杂度压缩。我们可以设置一个最小值辅助栈来实现，在压栈出栈的过程中，就按照大小顺序将元素压入另一个栈中。解析：易出错的点在于压栈的时候，需要将小于等于当前最小值的元素都压入B栈，否则一旦pop出去，就会出错
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.A, self.B = [],[]
def push(self, x: int) -> None:
self.A.append(x) # x压栈
if not self.B or x <= self.B[-1]: # 若x小于B中的最小值，那么压入B;否则不压
self.B.append(x)
def pop(self) -> None:
if self.A.pop() == self.B[-1]:
self.B.pop()
def top(self) -> int:
return self.A[-1]
def min(self) -> int:
return self.B[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
35. 复杂链表的复制
在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。
复制分为两类，分别是浅复制和深复制。浅复制为复制头节点;深复制为复制所有节点和连接关系，修改复制链表时原链表不受影响，二者完全独立。在python中可使用的方法：copy.deepcopy(head)。解析1;解析2
将含有多个指针的链表看作有向图来处理，通过DFS和BFS两种方式递归解决。
35.1 DFS:通过递归拷贝所有next节点和random节点，用字典存储
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
# return copy.deepcopy(head) import cop
def dfs(head):
if not head: return None
if head in visited:
return visited[head]
newNode = Node(head.val, None, None) # 定义一个新节点
visited[head] = newNode
newNode.next = dfs(head.next)
newNode.random = dfs(head.random)
return newNode
visited = {}
return dfs(head)
执行过程：先不看newNode.random=dfs(head.random)这一句
递归：dfs(7) -> 7 -> dfs(13) -> 13 -> dfs(11) -> 11 -> dfs(10) -> 10 -> dfs(1) -> 1 -> dfs(None)【递归的过程创造了7 13 11 10 1五个独立的节点，然后创建了5对原链表节点和新节点的映射】
回溯：dfs(None)得到返回值None，因此newNode(1).next = None -> 执行return newNode，因此newNode(10).next = 1 -> 依次进行，得到了7->13->11->10->1->None
最后分析random的递归回溯过程，此处newNode.random的值是通过if head in visited:return visited[head]获得返回值的，在next遍历的过程中，在字典中存储了所有的节点对{7:7, 13:13, 11:11, 10:10, 1: 1}，即得到dfs(1)=1,dfs(10)=10,…
35.2 哈希表方式
深度拷贝单链表：顺着next遍历这条链表，用当前节点的值创建新节点，建立“源节点”和“新节点”之间的映射关系，然后按照源节点的连接方式对新节点进行连接即可。(标记新节点的前驱节点pre的next为新节点，然后当前节点后移，前驱节点更新为新节点。)
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:return
# 形成{原:新}映射,dict[原节点] = 新节点
cur = head # 对链表处理时，一定要将head存起来
visited = {}
while cur:
visited[cur] = Node(cur.val)
cur = cur.next
# 新节点的连边直接等于原节点的边,dict.get(key)的方式等同于dict[key]，有捕捉异常的作用
cur = head
while cur:
visited[cur].next = visited.get(cur.next) # 新节点.next = 映射关系(原节点.next)
visited[cur].random = visited.get(cur.random)
cur = cur.next
return visited[head]
35.3 拼接+拆分
逐个生成新节点，并修改原节点的next，使得新节点逐个跟随在原节点之后，之间用next连接。
然后按照原节点的random方式对新节点进行random连接。
最后将新节点构成的链表和原节点的拆开。
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
cur = head
# 1. 复制各节点，并构建拼接链表
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
# 2. 构建各新节点的 random 指向
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. 拆分两链表
cur = res = head.next
pre = head
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
pre.next = None # 单独处理原链表尾节点
return res # 返回新链表头节点
58 II. 左旋转字符串
给定一个字符串和一个整数，然后该整数将字符串分割成两部分，然后左右两部分交换位置拼接，该过程切片就可以实现。
return s[n:]+s[:n]
如果不用切片该怎么做呢?还是用list，直接遍历两次字符串，先将后半部分填入list，然后再将前半部分填入，最后join在一起。
res = []
for i in range(n, len(s)):
res.append(s[i])
for i in range(n):
res.append(s[i])
return ''.join(res)
# 用余数简化代码 大连做人流哪里好 http://www.dl-fkw.com/
for i in range(n, n+len(s)): # 如abcde,n=2,i的范围在2,3,4,5,6,对5取余结果:2,3,4,0,1
res.append(s[i % len(s)])
总结：要求不让借用list和join方法如何处理：直接将list换成字符串类型的，将list.append换成加号即可不用join。本题涉及到的知识点就是Java和python中的字符串为不可变对象，要对字符串进行操作，必须重新定义一个新字符串或者list。
用切片方式最快，无冗余操作，效率最高。
列表(Python) 和 StringBuilder(Java) 都是可变对象，每轮遍历拼接字符时，只是向列表尾部添加一个新的字符元素。最终拼接转化为字符串时，系统 仅申请一次内存 。
在 Python 和 Java 中，字符串是 “不可变对象” 。因此，每轮遍历拼接字符时，都需要新建一个字符串;因此，系统 需申请 NN 次内存 ，数据量较大时效率低下。
C++中字符串是可变类型，实现方式是将左字符串逆序，右字符串逆序，然后整个逆序，以下分别是调用库函数和自己实现reverse操作：
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverseString(s, 0, n - 1);
reverseString(s, n, s.size() - 1);
reverseString(s, 0, s.size() - 1);
return s;
}
private:
void reverseString(string& s, int i, int j) {
while(i < j) swap(s[i++], s[j--]);
}
};
59 I. 滑动窗口的最大值
简单题目一定会有所限制，像本题第一反应如下，用list切片作为窗口，可以得到n-k+1个窗口，每个窗口中寻找max，需要O(k)的时间复杂度。总体时间复杂度为O(n-k+1)k：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
def max(lst): # 求list的max
max_num = lst[0]
for i in range(len(lst)):
max_num = lst[i] if lst[i] > max_num else max_num
return max_num
# list,遍历,切片,max
res = []
if len(nums) == 0:return res
for i in range(len(nums)-k+1)：
res.append(max(nums[i:i+k]))
return res
因此重点就是如何降低时间复杂度!借鉴30题 包含min函数的栈，用o(1)的方式得到min。一般窗口对应的数据结构为双端队列，本题用单端队列即可。Python 通过zip(range(), range())可实现滑动窗口的左右边界i, j 同时遍历。
复杂度分析：图解查看此处
时间复杂度O(n)：其中n为数组 nums长度;线性遍历nums占用 O(n) ;每个元素最多仅入队和出队一次，因此单调队列 deque 占用 O(2n)。
空间复杂度O(k)： 双端队列 deque 中最多同时存储 k个元素(即窗口大小)。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
deque = collections.deque()
res, n = [], len(nums)
for i, j in zip(range(1 - k, n + 1 - k), range(n)):
# 删除 deque 中对应的 nums[i-1]
if i > 0 and deque[0] == nums[i - 1]:
deque.popleft()
# 保持 deque 递减
while deque and deque[-1] < nums[j]:
deque.pop()
deque.append(nums[j])
# 记录窗口最大值
if i >= 0:
res.append(deque[0])
return res
此处用到了python中的collections库，学习点这里
59 II. 队列的最大值
**题目要求：**请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。
67. 把字符串转换成整数
**题目要求：**将字符串中的数字转换成整数输出。
丢弃无用的开头空格字符
当第一个非空格字符为正负号时，寻找紧挨着的连续数字，得到最后的带符号整数;若首个非空格字符是数字时，那就得到连续的整数(其后包含一些其他字符的干扰项，就无视啦)
任何不能转换成整数的条件下，返回0
如果超出整数范围，那么输出+/- int_max
20 59 67 三道题理解收尾;其余题目回顾复习