左神算法-初级4

• 矩阵
• • 1、转圈打印矩阵
  • 2、旋转正方形矩阵
  • 3、“之” 字形打印矩阵
• 链表
• • 1、判断一个单链表是否是回文结构
  • 2、链表与荷兰国旗问题
  • 3、复制含有随机指针节点的链表
  • 4、两个单链表相交问题

矩阵

1、转圈打印矩阵

【要求】 额外空间复杂度为O(1)

转圈打印的过程就是不断顺时针打印外围元素的过程，
只要给你一个左上角的点（如(0,0)）和右下角的点（如(3,3)），
你就能够打印出1 2 3 4 8 12 16 15 14 13 9 5；同样，给你(1,1)和(2,2)，你就能打印出6 7 11 10。
这个根据两点打印正方形上元素的过程可以抽取出来，整个问题也就迎刃而解了。

def print_matrix(arr):
    if not arr:
        return []
    
    def print_circle(top_row,top_column,down_row,down_column):
        if top_row == down_row:
            for i in range(top_column, down_column + 1):
                print(arr[top_row][i], end=" ")
        elif top_column == down_column:
            for i in range(top_row, down_row + 1):
                print(arr[top_column][i], end=" ")
        else:
            for i in range(top_column, down_column):
                # 第一行打印  从第一列到最后一列
                print(arr[top_row][i], end=" ")
            for i in range(top_row, down_row):
                print(arr[i][down_column], end=" ")
            for i in range(down_column, top_column, -1):
                print(arr[down_row][i], end=" ")
            for i in range(down_row, top_row, -1):
                print(arr[i][top_column], end=" ")   
    
    m = len(arr) - 1
    n = len(arr[0]) - 1
    top_row = 0
    top_column = 0
    down_row = m
    down_column = n
    while down_row >= top_row and down_column >= top_column:
        print_circle(top_row,top_column,down_row,down_column)
        top_row += 1
        top_column += 1
        down_row -= 1
        down_column -= 1
        
arr = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]
print_matrix(arr)

2、旋转正方形矩阵

【题目】 给定一个整型正方形矩阵matrix， 请把该矩阵调整成顺时针旋转90度的样子。
【要求】 额外空间复杂度为O(1)。

首先选取矩阵四个角上的点1,3,9,7，按顺时针的方向1到3的位置（1->3）、3->9、9->7、7->1，
这样对于旋转后的矩阵而言，这四个点已经调整好了。接下来只需调整2,6,8,4的位置，调整方法是一样的。
只需对矩阵第一行的前n-1个点采用同样的方法进行调整、对矩阵第二行的前前n-3个点……，
那么调整n阶矩阵就容易了。

def roation_square(arr):
    if not arr:
        return []
    m = len(arr) - 1
    n = len(arr[0]) - 1
    top_row = 0
    top_column = 0
    down_row = m
    down_column = n
    while down_row > top_row and down_column > top_column:
        for i in range(top_column,down_column):
            arr[i][down_column], arr[down_row][down_column - i],\
            arr[down_row - i][top_column],arr[top_row][i] = \
            arr[top_row][i],arr[i][down_column], \
            arr[down_row][down_column - i],arr[down_row - i][top_column]
        top_row += 1
        top_column += 1
        down_row -= 1
        down_column -= 1
    return arr
        
arr = [
    [1,2,3,4],
    [5,6,7,8],
    [9,10,11,12],
    [13,14,15,16]]

print(roation_square(arr))

3、“之” 字形打印矩阵

【题目】 给定一个矩阵matrix， 按照“之” 字形的方式打印这
个矩阵， 例如：
1 2 3 4
5 6 7 8
9 10 11 12

“之” 字形打印的结果为： 1， 2， 5， 9， 6， 3， 4， 7， 10， 11，8， 12
【要求】 额外空间复杂度为O(1)。

def print_z_matrix(arr):
    a_row = 0
    a_column = 0
    b_row = 0
    b_column = 0
    end_row = len(arr) - 1
    end_column = len(arr[0]) - 1
    
    def print_level(a_row, a_column, b_row, b_column, flag):
        if flag == 0:
            j = b_column
            for i in range(b_row, a_row-1, -1):
                print(arr[i][j], end = '')
                j += 1
        else:
            j = a_column
            for i in range(a_row, b_row+1):
                print(arr[i][j], end = '')
                j -= 1
        
    while a_row <= end_row:
        flag = 0
        print_level(a_row, a_column, b_row, b_column, flag)
        if a_column == end_column:
            a_row += 1
        else:
            a_column += 1
        if b_row == end_row:
            b_column += 1
        else:
            b_row += 1
        flag = not flag
        
arr = [
    [1, 2, 3, 4],
    [5, 6, 7, 8], 
    [9, 10, 11, 12]]

print_z_matrix(arr)

链表

1、判断一个单链表是否是回文结构

额外空间复杂度O(1)解法
常规思路，很容易想到准备一个。这样栈结构，把链表数据依次存入。
然后再同时遍历这两个链表，判断两个链表的当前节点是否相等（equal）。
这种解法实现很简单，时间复杂度为 O(n)，额外空间复杂度为 O(n)。

使用快慢指针找到中间节点，把后半部分变成逆序链表

def get_bool(head):
    # 用栈进行倒序，空间复杂度O（n）
    if not head:
        return True
    cur = head
    stack = []
    while cur:
        stack.append(cur)
        cur = cur.next
    cur = head
    while cur:
        if cur == stack.pop():
            cur = cur.next
        else:
            return False
    return True

2、链表与荷兰国旗问题

将单向链表按某值划分成左边小、 中间相等、 右边大的形式
给定一个单向链表的头节点head， 节点的值类型是整型， 再给定一个
整 数pivot。 实现一个调整链表的函数， 将链表调整为左部分都是值小于 pivot
的节点， 中间部分都是值等于pivot的节点， 右部分都是值大于 pivot的节点。
除这个要求外， 对调整后的节点顺序没有更多的要求。

分别存入三个链表，small，equal，large中，三个链表分别标注头尾两个指针。

def partitionList(head, pivot):
    if not head:
        return False
    small_head = small_end = None
    mid_head = mid_end = None
    big_head = big_end = None
    p = head
    while p:
        if p.val < pivot:
            if not small_head:
                small_head = small_end =  p
            else:
                small_end.next = p
                small_end = p
        elif p.val == pivot:
            if not mid_head:
                mid_head = mid_end =  p
            else:
                mid_end.next = p
                mid_end = p
        else:
            if not big_head:
                big_head = big_end =  p
            else:
                big_end.next = p
                big_end = p
        p = p.next
    
    if small_head != None and mid_head != None and big_head != None:
        head = small_head
        small_end.next = mid_head
        mid_head.next = big_head
        big_end.next = None
    elif small_head != None and mid_head != None and big_head == None:
        head = small_head
        small_end.next = mid_head
        mid_head.next = None
    elif small_head != None and mid_head == None and big_head == None:
        head = small_head
        small_end.next = None
    elif small_head != None and mid_head == None and big_head != None:
        head = small_head
        small_end.next = big_head
        big_end.next = None
    
    elif small_head == None and mid_head != None and big_head != None:
        head = mid_head
        mid_end.next = big_head
        big_end.next = None
    elif small_head == None and mid_head != None and big_head == None:
        head = mid_head
        mid_head.next = None
    
    elif small_head == None and mid_head == None and big_head != None:
        head = big_head
        big_end.next = None
    return head

3、复制含有随机指针节点的链表

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
#         cur = pHead
#         dic = {}
#         while cur:
#             clone = RandomListNode(cur.label)
#             dic[cur] = clone
#             cur = cur.next
#         for old in dic.keys():
#             if old.next in dic:
#                 dic[old].next = dic[old.next]
#             if old.random in dic:
#                 dic[old].random = dic[old.random]
#         return dic[pHead]
        cur = pHead
        while cur:
            clone = RandomListNode(cur.label)
            clone.next = cur.next
            cur.next = clone
            cur = clone.next
        cur = pHead
        while cur:
            clone = cur.next
            if cur.random:
                clone.random = cur.random.next
            cur = clone.next
        cur = pHead
        head = pHead.next
        while cur and cur.next:
            clone = cur.next
            cur.next = clone.next
            cur = clone
        return head

4、两个单链表相交问题

两个单链表相交问题：三种情况如下：
1、两个无环单链表第一个交点
2、一个无环，一个有环单链表，不会相交
3、两个有环单链表第一个交点

解题思路：
首先判断两个链表是否有环；
如果都无环：两个无环单链表相交问题
如果一个有，一个无：必定不相交，直接返回 None
如果都有环：两个有环单链表相交问题

# 查看是否有环
#使用哈希表visited，遍历链表，如果 node in visited,则有环，且node为如环结点
def hascycle(head):
    if not head:
        return False
    seen = set()
    cur = head
    while cur:
        if cur in seen:
            return True
        seen.add(cur)
        cur = cur.next
    return False
# 快指针和慢指针，快指针一次两步，慢指针一次一步，当相遇时，证明有环。此时将快指针重置到头节点，
# 快指针步数变为一步，当再次相遇时，为入环结点
def hascycle2(head):
    if not head:
        return False
    p = head
    slow = p
    fast = p
    while fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            p1 = head
            while slow != p1:
                slow = slow.next
                p1 = p1.next
            return slow
    return None

# 查看是否相交：
def Intersect(head1, head2):
    loop1 = hascycle2(head1)
    loop2 = hascycle2(head2)
    
    def noloop(head1, head2):
        p1 = head1
        p2 = head2
        while p1 != p2:
            p1 = p1.next if p1 else head2
            p2 = p2.next if p2 else head1
        return p1
    def bothloop(head1, head2, loop1, loop2):
        p1 = head1
        p2 = head2
        # 入环结点相同，相交点不在环上
        # 先找到较长的一支，然后减去两支之差，此时长度相同，一起移动
        if loop1 == loop2:
            n = 0
            while p1.next != loop1:
                p1 = p1.next
                n += 1
            while p2.next != loop1:
                p2 = p2.next
                n -= 1
            if n>0:
                p1 = head1
                p2 = head2
            else:
                p1 = head2
                p2 = head1
            n = abs(n)
            while n != 0:
                p1 = p1.next
                n -= 1
            while p1 != p2:
                p1 = p1.next
                p2 = p2.next
            return p1
            
        else:
        # 入环结点不同，相交点在环上
        # 在链表1的环上转一圈,如果没有找到链表2的入环结点，说明不想交
            cur1 = loop1.next
            while cur1 != loop1:
                if cur1 == loop2:
                    return 1oop1  # 返回loop1或loop2均可,整个环就是两链表的相交部分
                cur1 = cur1.next
            return None
        
    
    if not loop1 and not loop2:
        return noloop(head1, head2)
    if loop1 and loop2:
        return bothloop(head1, head2)
    return None

本文地址：https://blog.csdn.net/weixin_43915860/article/details/110875567