21天养成编程习惯：Leetcode刷题第十九天

青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。

青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。

本期训练营根据孩子们对知识的掌握情况分成两个打卡群（Leetcode简单打卡群、Leetcode中等打卡群）， 每个打卡群针对不同需求的孩子，这就使得本次活动更具有针对性，对孩子学习编程帮助更大。

活动的时间 从9月1日至9月21日，每天一道编程题。

参与的小朋友可以 ，让他邀请你到本次相应的打卡群并把本次的打卡题目发给你。

微信号：ProgrammingAssistant

Day19： 160_相交链表

难度：简单

/

难度：简单

/

难度：简单

/

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

展开全文

题目数据 保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序 不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

skipB - 在 listB 中 （从头节点开始）跳到交叉节点的节点数

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

skipB - 在 listB 中 （从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案。

示例 1：

输入：intersectVal = 8, listA = [ 4, 1, 8, 4, 5], listB = [ 5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8（注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [ 4, 1, 8, 4, 5]，链表 B 为 [ 5, 0, 1, 8, 4, 5]。

在 A 中，相交节点前有 2个节点；在 B 中，相交节点前有 3个节点。

示例 2：

输入：intersectVal = 2, listA = [ 0, 9, 1, 2, 4], listB = [ 3, 2, 4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2（注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [ 0, 9, 1, 2, 4]，链表 B 为 [ 3, 2, 4]。

在 A 中，相交节点前有 3个节点；在 B 中，相交节点前有 1个节点。

示例 3：

输入：intersectVal = 0, listA = [ 2, 6, 4], listB = [ 1, 5], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [ 2, 6, 4]，链表 B 为 [ 1, 5]。

由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

这两个链表不相交，因此返回 null 。

注意：

listA 中节点数目为 m

listB 中节点数目为 n

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点， intersectVal 为 0

如果 listA 和 listB 有交点， intersectVal == listA[skipA] == listB[skipB]

listA 中节点数目为 m

listB 中节点数目为 n

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点， intersectVal 为 0

如果 listA 和 listB 有交点， intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

实现

思路：通过集合的方法。

C# 语言

* Definition for singly-linked list.

* public class ListNode {

* public int val;

* public ListNode next;

* public ListNode(int x) { val = x; }

publicclassSolution

publicListNode GetIntersectionNode(ListNode headA, ListNode headB)

HashSet<ListNode> hash = newHashSet<ListNode>;

ListNode temp = headA;

while(temp != null)

hash.Add(temp);

temp = temp.next;

temp = headB;

while(temp != null)

if(hash.Contains(temp))

returntemp;

temp = temp.next;

returnnull;

Python 语言

# Definition for singly-linked list.

# class ListNode(object):

# def __init__(self, x):

# self.val = x

# self.next = None

classSolution(object):

defgetIntersectionNode(self, headA, headB):

:type head1, head1: ListNode

:rtype: ListNode

h = set

temp = headA

whiletemp isnotNone:

h.add(temp)

temp = temp.next

temp = headB

whiletemp isnotNone:

iftemp inh:

returntemp

temp = temp.next

returnNone

Day19：59_螺旋矩阵II

难度：中等

/

难度：中等

/

难度：中等

/

示例1：

输入：n = 3

输出：[[ 1, 2, 3],[ 8, 9, 4],[ 7, 6, 5]]

示例 2：

输入：n = 1

输出：[[ 1]]

提示：

1 <= n <= 20

1 <= n <= 20

C# 语言

publicclassSolution

publicint[][] GenerateMatrix( intn)

int[][] matrix = newint[n][];

for( inti = 0; i < n; i++)

matrix[i] = newint[n];

intstart = 0; //起始位置

intend1 = n - 1; //最左边位置

intend2 = n - 1; //最下边位置

intcount = 1;

while(start < end1 && start < end2)

LeftToRight(start, end1, start, matrix, ref count);

TopToBottom(start + 1, end2, end1, matrix, ref count);

RightToLeft(end1 - 1, start, end2, matrix, ref count);

BottomToTop(end2 - 1, start + 1, start, matrix, ref count);

start++;

end1 = n - 1- start;

end2 = n - 1- start;

if(n% 2== 1)

matrix[start][start] = count;

returnmatrix;

privatevoidLeftToRight( intstart, intend, introwIndex, int[][] matrix, ref intfrom)

for( inti = start; i <= end; i++)

matrix[rowIndex][i] = from;

from++;

privatevoidTopToBottom( intstart, intend, intcolIndex, int[][] matrix, ref intfrom)

for( inti = start; i <= end; i++)

matrix[i][colIndex] = from;

from++;

privatevoidRightToLeft( intstart, intend, introwIndex, int[][] matrix, ref intfrom)

for( inti = start; i >= end; i--)

matrix[rowIndex][i] = from;

from++;

privatevoidBottomToTop( intstart, intend, intcolIndex, int[][] matrix, ref intfrom)

for( inti = start; i >= end; i--)

matrix[i][colIndex] = from;

from++;

Python 语言

classSolution(object):

defgenerateMatrix(self, n):

:type n: int

:rtype: List[List[int]]

self.count = 1

self.matrix = [[ 0fori inrange(n)] fori inrange(n)]

start, end1, end2 = 0, n - 1, n - 1

whilestart < end1 andstart < end2:

self.LeftToRight(start, end1, start)

self.TopToBottom(start + 1, end2, end1)

self.RightToLeft(end1 - 1, start, end2)

self.BottomToTop(end2 - 1, start + 1, start)

start += 1

end1 = n - 1- start

end2 = n - 1- start

ifn % 2== 1:

self.matrix[start][start] = self.count

returnself.matrix

defLeftToRight(self, start, end, rowIndex):

fori inrange(start, end + 1):

self.matrix[rowIndex][i] = self.count

self.count += 1

defTopToBottom(self, start, end, colIndex):

fori inrange(start, end + 1):

self.matrix[i][colIndex] = self.count

self.count += 1

defRightToLeft(self, start, end, rowIndex):

fori inrange(start, end - 1, -1):

self.matrix[rowIndex][i] = self.count

self.count += 1

defBottomToTop(self, start, end, colIndex):

fori inrange(start, end - 1, -1):

self.matrix[i][colIndex] = self.count

self.count += 1

青少年编程升级打怪计划

把电子学会的青少年编程能力等级测评作为游戏的关卡，带着小朋友们升级打怪。

每周日晚20:00，利用腾讯会议进行直播分享，之后安排一个测试（与等级测评的题目数量一致）考察小朋友们对知识的掌握情况。

为了，让各个阶段的小朋友都能参与到学习中，我们每个月都会组织Scratch、Python、C++的青少年编程学习活动 ，为小朋友们三助力，即学习编程助力、实践知识助力、 结识伙伴助力。

一键三连，一起学习⬇️