好题 | 笔记整理!

链表+ 树(层次遍历) | bfs +dfs | 心得

面试题 04.03. 特定深度节点链表

bfs | 借助队列处理

常规处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        q=[tree]
        ans=[]
        while q:
            sz=len(q)
            pre=x=ListNode()
            for i in range(sz):
                node=q[0]
                del q[0]
                x.next=ListNode(node.val)
                x=x.next
                if node.left:q.append(node.left)
                if node.right:q.append(node.right)
            x.next=None
            ans.append(pre.next)
        return ans

dfs | 先left | 先right

受树层次遍历启发!

先left处理 | 插入节点是在末位

并不是很常见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 先left处理时候 插入节点是在链表末位插入
class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        ans=[]
        def dfs(root,level):
            if not root:return 
            cur=ListNode(root.val)
            if len(ans)==level:
                ans.append(ListNode(root.val))
            else:
                pre=ans[level]  
                # 末位处理|找到链表结尾部分
                while pre.next:pre=pre.next
                pre.next=cur
                pre=pre.next
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        dfs(tree,0)
        return ans

可以存储末位部分 略有优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        ans=[]
        def dfs(root,level):
            if not root:return 
            cur=ListNode(root.val)
            if len(ans)==level:
                ans.append([cur,cur])
            else:
                ans[level][-1].next=cur
                ans[level][-1]=ans[level][-1].next
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        dfs(tree,0)
        return [k for k,_ in ans]

先right处理 | 直接尾插法即可

2326. 螺旋矩阵 IV

比较容易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        ans=[]
        def dfs(root,level):
            if not root:return 
            cur=ListNode(root.val)
            if len(ans)==level:
                ans.append(cur)
            else:
                cur.next=ans[level]
                ans[level]=cur
            dfs(root.right,level+1)
            dfs(root.left,level+1)
        dfs(tree,0)
        return ans

螺旋数组 | 笔记心得

暴力破解 | 只能暴力找规律

过于漫长!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        ls=[[-1 for _ in range(n)] for _ in range(m)]
        l,r=0,n-1
        t,d=0,m-1
        while head:
            # 向左移动
            i,j=t,l
            while j<=r and head:
                ls[i][j]=head.val
                head=head.next
                j+=1
            t+=1
            i,j=t,r
            # 向下走
            while i<=d and head:
                ls[i][j]=head.val
                head=head.next
                i+=1
            r-=1
            i,j=d,r
            while j>=l and head:
                ls[i][j]=head.val
                head=head.next
                j-=1
            d-=1
            i,j=d,l
            while i>=t and head:
                ls[i][j]=head.val
                head=head.next
                i-=1
            l+=1
        return ls

逻辑优化一下 | 试试看

借鉴大佬 | 确实6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        ans=[[-1]*n for _ in range(m)]
        # 模拟右下左上
        d=[[0,1],[1,0],[0,-1],[-1,0]]
        idx=0
        cur=[0,0]
        while head:
            l,r=cur
            ans[l][r]=head.val
            i,j=d[idx]
            if not 0<=l+i<m or not 0<=r+j<n or  ans[l+i][r+j]!=-1:
                idx=(idx+1)%4
                i,j=d[idx]
            cur=[l+i,r+j]
            head=head.next
        return ans
快来参与讨论吧