题目:按照1.2.3.4.8.12.16.15.14.13.9.5.6.7.11.10打印矩阵
答:先换外圈,再换里圈
答:
要求时间复杂度
O
(
M
+
N
)
O(M+N)
O(M+N),MN分别代表数组行列长度,额外空间复杂度
O
(
1
)
O(1)
O(1)
答:从右上出发,如果cur>target,则往左走;如果cur<target,则往下走
类似外排
class ListNode(object): 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 cur.next = pre # 修改 next 引用指向 pre = cur # pre 暂存 cur cur = tmp # cur 访问下一节点 return pre。
第一种方法空间复杂度
O
(
N
)
O(N)
O(N):所有节点都放到栈里去,弹出的顺序就是逆序,和原链表进行比对
第二种方法空间复杂度
O
(
1
)
O(1)
O(1):快指针走2步,慢指针走1步,慢指针走到了中点位置,把中间后半部分给反序,从左右两个顶点分别开始比对。
方法一:生成一个数组结构,数组装的是节点类型,根据荷兰问题重排
进阶问题:左中右三部分的内部做顺序要求,90451,target=3,调整为01945,同时要求时间复杂度
O
(
N
)
O(N)
O(N),额外空间复杂度
O
(
1
)
O(1)
O(1)
答:
方法一:哈希表(字典)
class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if head==None: return head nodemap = dict() cur = head while cur!=None: nodemap[cur] = Node(cur.val) cur = cur.next cur = head while cur!=None: nodemap[cur].next = nodemap.get(cur.next) nodemap[cur].random = nodemap.get(cur.random) cur = cur.next return nodemap[head]
方法二:
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 # 返回新链表头节点
要求时间复杂度 O ( N + M ) O(N+M) O(N+M),额外空间复杂度 O ( 1 ) O(1) O(1)
要求:返回第一个入环节点
方法一:用hashset,第一个重复的节点就是第一个入环节点
方法二:用一个快指针和一个慢指针,如果快指针指向空,则无环;如果快指针和慢指针相遇了,快指针从头开始变成走1步的,再和慢指针相遇的时候就是第一个入环节点
方法一:用hashset,链表1全放进去,查链表2
方法二:先遍历链表1的长度和最后一个节点end1,再遍历链表2的长度和最后一个节点end2,如果end1!=end2,则不可能相交;如果相交的话,找到长度差值len,长的链表先走len步,然后一起走查询相交情况
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ n = 0 tmp_headA = headA tmp_headB = headB while tmp_headA!=None: tmp_headA = tmp_headA.next n += 1 while tmp_headB!=None: tmp_headB = tmp_headB.next n -= 1 if tmp_headA!=tmp_headB: return while n>0: headA = headA.next n -= 1 while n<0: headB = headB.next n += 1 while headA!=None: if headA == headB: return headA headA = headA.next headB = headB.next return
方法三:
情况A,loop1一直next没遇到loop2,直到转回loop1
情况C,loop1一直next遇到了loop2,返回loop1或者loop2