Leaky Cauldron

环形链表

Posted on 2020-03-08 Edited on 2022-07-20

题目

给定一个链表, 判断链表中是否有环, 若有则返回链表尾指向的结点.

解法一

遍历时使用 HashSet 保存所有节点, 若遍历到重复节点则返回该节点

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class CycleList {
    public static ListNode hasCycle(ListNode head) {
        HashSet<ListNode> nodeSet = new HashSet<>();

        while (head != null) {
            if (nodeSet.contains(head))
                return head;
            nodeSet.add(head);
            head = head.next;
        }

        return null;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
class CycleList:
    def hasCycle(self, head):     
        node_set = set()
        while head:
            if head in node_set:
                return head
            node_set.add(head)
            head = head.next
        
        return None

解法二

使用快慢指针, 该解法空间复杂度为 O(1) , 慢指针每次移动一个位置, 快指针每次移动两个位置, 该方法利用了两个定律:

若链表中有环, 则两指针必相遇
两指针相遇后, 快指针放回头结点, 从此快慢指针都每次移动一个位置, 两指针必在第一个入环节点处相遇

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class CycleList {
	public static ListNode hasCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return null;

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        while (slow != fast) {
            if (fast.next == null || fast.next.next ==null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        fast = head;

        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class CycleList:
    def hasCycle(self, head):
        if head and head.next and head.next.next:
            slow = head.next
            fast = head.next.next
            
            while slow != fast:
                if fast.next and fast.next.next:
                    slow = slow.next
                    fast = fast.next.next
                else:
                    return None
            
            fast = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            
            return fast
        else:
            return None

例题 LeetCode # 141

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1，则在该链表中没有环。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

要求：

空间复杂度为 O(1)

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class CycleList {
	public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return false;

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        while (slow != fast) {
            if (fast.next == null || fast.next.next ==null)
                return false;
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class CycleList:
	def hasCycle(self, head):
        if head and head.next and head.next.next:
            slow = head.next
            fast = head.next.next
            
            while slow != fast:
                if fast.next and fast.next.next:
                    slow = slow.next
                    fast = fast.next.next
                else:
                    return False
                    
            return True
        else:
            return False

复制带随机指针的链表

Posted on 2020-03-07 Edited on 2022-07-20

题目 LeetCode # 138

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val ：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例 1：

1 2	输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

1 2	输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例 3：

1 2	输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

示例 4：

1
2
3

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

题解

方法一: 使用 `HashMap`

通过使用 HashMap 来建立原结点与复制后结点之间的对应关系, 再遍历原链表建立新结点 random 指针的指向关系

Java

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyList {
    public static Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node tmp1 = head;
        while (tmp1 != null) {
            map.put(tmp1, new Node(tmp1.val));
            tmp1 = tmp1.next;
        }

        Node tmp2 = head;
        while (tmp2 != null) {
            map.get(tmp2).next = map.get(tmp2.next);
            map.get(tmp2).random = map.get(tmp2.random);
            tmp2 = tmp2.next;
        }

        return map.get(head);
    }
}

Python

class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

class CopyList:
    def copy_random_list(self, head):
        list_map = {}
        tmp1 = head
        while tmp1:
            list_map[tmp1] = Node(tmp1.val)
            tmp1 = tmp1.next
        
        tmp2 = head
        while tmp2:
            list_map.get(tmp2).next = list_map.get(tmp2.next)
            list_map.get(tmp2).random = list_map.get(tmp2.random)
            tmp2 = tmp2.next
        
        return list_map.get(head)

方法二: 复制结点

复制原链表结点 ( 如 1->2->3 复制为 1->1->2->2->3->3 ), 再复制 random 指针的指向, 最后将新链表分离.

Java

public class Code_13_CopyList {
    public static Node copyRandomList(Node head) {
        if (head == null)
            return null;

        Node tmp = head;
        Node newNode = null;
		
        // 复制结点
        while (tmp != null) {
            newNode = new Node(tmp.val);
            newNode.next = tmp.next;
            tmp.next = newNode;
            tmp = newNode.next;
        }

        tmp = head;
        // 复制 random 指针
        while (tmp != null) {
            newNode = tmp.next;
            newNode.random = tmp.random != null ? tmp.random.next : null;
            tmp = newNode.next;
        }

        tmp = head;
        Node next = null;
        Node result = head.next;
        // 分离新链表, 复原原链表
        while (tmp != null) {
            next = tmp.next.next;
            newNode = tmp.next;
            tmp.next = next;
            newNode.next = next != null ? next.next : null;
            tmp = next;
        }

        return result;
    }
}

Python

class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

class CopyList:
    def copy_random_list(self, head):
        if head is None:
            return None
        
        tmp = head
        
        while tmp:
            new_node = Node(tmp.val)
            new_node.next = tmp.next
            tmp.next = new_node
            tmp = new_node.next
            
        tmp = head
        while tmp:
            new_node = tmp.next
            new_node.random = tmp.random.next if tmp.random else None
            tmp = new_node.next
        
        tmp = head
        result = head.next
        while tmp:
            next = tmp.next.next
            new_node = tmp.next
            tmp.next = next
            new_node.next = next.next if next else None
            tmp = next
        
        return result

分隔链表

Posted on 2020-03-02 Edited on 2022-07-20

题目

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入:

1	head = 1->4->3->2->5->2, x = 3

输出:

1	1->2->2->4->3->5

要求

每部分中结点从左到右顺序与原链表的先后次序一致

题解

可创建三个指针分别保存三个部分的结点, 新结点追加即可

class ListNode {
    int val;
    ListNode next;

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

public class PartitionList {
    public static ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode middle = new ListNode(0);
        ListNode right = new ListNode(0);

        ListNode node1 = left;
        ListNode node2 = middle;
        ListNode node3 = right;

        while (head != null) {
            if (head.val < x) {
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else if (head.val == x) {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            } else {
                node3.next = head;
                head = head.next;
                node3 = node3.next;
                node3.next = null;
            }
        }

        node1.next = middle.next;
        node2.next = right.next;

        return left.next;
    }
}

例题: LeetCode # 86

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入:

1	head = 1->4->3->2->5->2, x = 3

输出:

1	1->2->2->4->3->5

Java

class ListNode {
    int val;
    ListNode next;

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

public class PartitionList {
    public static ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);

        ListNode node1 = left;
        ListNode node2 = right;

        while (head != null) {
            if (head.val < x) {
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }

        node1.next = right.next;

        return left.next;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class PartitionList:
    def partition(self, head, x):
        left = ListNode(0)
        right = ListNode(0)
        
        node1 = left
        node2 = right
        
        while head:
            if head.val < x:
                node1.next = head
                head = head.next
                node1 = node1.next
                node1.next = None
            else:
                node2.next = head
                head = head.next
                node2 = node2.next
                node2.next = None
            
        node1.next = right.next
        return left.next

判断一个链表是否为回文结构

Posted on 2020-03-01 Edited on 2022-07-20

若不考虑空间复杂度, 可将所有元素存入栈中, 边出栈边比较即可, 此时空间复杂度为 O(N) ; 也可先利用快慢指针找到中间指针 , 再将中间指针后的部分存入栈中, 出栈时与链表前半部分比较, 此时空间占用为 N/2 , 空间复杂度仍为 O(N) . 若要实现空间复杂度 O(1) , 可考虑先利用快慢指针找到中间结点, 后将中间结点后的结点的指针方向反向, 即可实现由链表尾向中间结点的遍历, 之后还原链表结构即可. 链表逆序过程中需注意边界, 前半部分最后一个元素和逆序后的后半部分的最后一个元素的 next 均需置空, 否则遍历时很容易死循环.

Java

class ListNode {
    int val;
    ListNode next;

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

public class IsPalindrome {
    public static ListNode middleNode(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode fastPointer = head;
        ListNode slowPointer = head;

        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }

        return slowPointer;
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null)
            return true; // LeetCode 测试用例中输入为[]时要求返回true, 很沙雕

        ListNode middleNode = middleNode(head);
        ListNode tailNode = reversePointer(middleNode);

        ListNode leftPointer = head;
        ListNode rightPointer = tailNode;

        while (leftPointer != null && rightPointer != null) {
            if (leftPointer.val != rightPointer.val) {
                reversePointer(rightPointer);
                return false;
            }
            leftPointer = leftPointer.next;
            rightPointer = rightPointer.next;
        }
        reversePointer(tailNode);

        return true;
    }

    public static ListNode reversePointer(ListNode startNode) {
        ListNode slow = startNode;
        ListNode fast = slow.next;
        slow.next = null;
        ListNode tmp = null;
        while (fast != null) {
            tmp = fast.next;
            fast.next = slow;
            slow = fast;
            fast = tmp;
        }

        startNode.next = null;

        return slow;
    }
}

Python

class IsPalindrome:
    def middle_node(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_pointer(self, start_node):
        slow = start_node
        fast = start_node.next
        slow.next = None

        while fast:
            tmp = fast.next
            fast.next = slow
            slow = fast
            fast = tmp

        start_node.next = None

        return slow

    def is_palindrome(self, head):
        if head is None:
            return True

        middle_node = self.middle_node(head)
        tail_node = self.reverse_pointer(middle_node)

        left_pointer = head
        right_pointer = tail_node

        while left_pointer and right_pointer:
            if left_pointer.val != right_pointer.val:
                self.reverse_pointer(right_pointer)
                return False

            left_pointer = left_pointer.next
            right_pointer = right_pointer.next

        self.reverse_pointer(tail_node)
        return True

链表的中间结点

Posted on 2020-03-01 Edited on 2022-07-20

题目 LeetCode # 876

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

1
2
3

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

题解

使用快慢指针, 快指针步长为 2, 慢指针步长为 1, 当快指针走到末尾时, 慢指针恰好走到中点. 循环的终止条件应为快指针的下个或下下个结点为空.

Java

class ListNode {
    int val;
    ListNode next;

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

public class MiddleNode {
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode fastPointer = head;
        ListNode slowPointer = head;
		
		/*
        若要获取偶数长度链表中间结点中的前一个则改为:
        while (fastPointer.next != null && fastPointer.next.next != null)
         */
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }

        return slowPointer;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow

搜索二维矩阵

Posted on 2020-02-29 Edited on 2022-07-20

题目

给定一个 M * N 的矩阵, 矩阵中每一行从左到右依次递增, 每一列从上到下依次递增, 判断矩阵中是否含有整数K.

矩阵示例

1
2
3

0, 1, 2, 3, 4,
2, 3, 4, 5, 6,
6, 7, 8, 9, 10

要求

时间复杂度为 O(M + N) , 空间复杂度为 O(1)

题解

可先选取左下角或右上角处的元素进行比较, 每次移动时, 均只有两种可能的移动方向. 每次查找最多横向比较 N 次, 纵向比较 M 次, 故时间复杂度为 O(M + N)

    /**
     * 本例从右上角处元素开始比较
     * @param matrix 输入矩阵
     * @param target 目标数值
     * @return 是否含有该数值
     */
public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int M = 0;
        if (matrix.length == 0)
            return false;

        int N = matrix[0].length - 1;

        int cuR = M;
        int cuC = N;

        while (cuR < matrix.length && cuC >= 0) {
            if (matrix[cuR][cuC] > target)
                cuC--;
            else if (matrix[cuR][cuC] < target)
                cuR++;
            else {
                return true;
            }
        }

        return false;
    }
}

例题: LeetCode # 74

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例:

输入:

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

1	target = 3

输出: true

Java

class SearchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int M = 0;
        if (matrix.length == 0)
            return false;

        int N = matrix[0].length - 1;

        int cuR = M;
        int cuC = N;

        while (cuR < matrix.length && cuC >= 0) {
            if (matrix[cuR][cuC] > target)
                cuC--;
            else if (matrix[cuR][cuC] < target)
                cuR++;
            else {
                return true;
            }
        }

        return false;
    }
}

Python

class SearchMatrix:
        """
        本例从右上角元素开始比较
        :param matrix: 输入矩阵
        :param target: 目标数值
        :return: 是否含有该数值
        """
    def search_matrix(self, matrix, target):
        M = 0
        if len(matrix) == 0:
            return False
        
        N = len(matrix[0]) - 1
        
        cuR = M
        cuC = N
        
        while cuR < len(matrix) and cuC >= 0:
            if matrix[cuR][cuC] > target:
                cuC -= 1
            elif matrix[cuR][cuC] < target:
                cuR += 1
            else:
                return True
        
        return False

之字形打印矩阵

Posted on 2020-02-16 Edited on 2022-07-20

题目

给定一个矩阵, 按照之字型的方式打印矩阵, 例如

1
2
3

1  2  3  4
5  6  7  8
9  10 11 12

输出

1	1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12

要求

额外空间复杂度为 O(1)

题解

本题可以考虑设定两个游标 a 和 b , 初始时均指向左上角, 后分别沿上边界和左边界移动, 当运动到边的末尾时分别向下和向右移动, 打印 a 和 b 两点形成的对角线上的点即可.

需注意 a, b 横纵坐标增加的顺序, 否则容易在拐点出现下标越界

图来自程序员客栈

Java

public class PrintMatrixZigZag {
    public static void printMatrixZigZag(int[][] matrix) {
        int row1 = 0;
        int col1 = 0;
        int row2 = 0;
        int col2 = 0;
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;
        boolean fromUp = false;
        while (row1 <= endR) {
            printDiagonal(matrix, row1, col1, row2, col2, fromUp);
            // 需注意 a, b 横纵坐标增加的顺序, 否则容易在拐点出现下标越界
            row1 = col1 == endC ? row1 + 1 : row1;
            col1 = col1 == endC ? col1 : col1 + 1;
            col2 = row2 == endR ? col2 + 1 : col2;
            row2 = row2 == endR ? row2 : row2 + 1;
            fromUp = !fromUp; // 反转
        }
    }

    /**
     * @param fromUp True: 从上向下打印
     */
    public static void printDiagonal(int[][] m, int row1, int col1, int row2, int col2, boolean fromUp) {
        if (fromUp) {
            while (row1 <= row2) {
                System.out.print(m[row1++][col1--] + " ");
            }
        } else {
            while (row1 <= row2) {
                System.out.print(m[row2--][col2++] + " ");
            }
        }
    }

    public static void main(String[] args) {
        int[][] inputMatrix = {
                {1, 2,  3,  4},
                {5, 6,  7,  8},
                {9, 10, 11, 12}
        };

        printMatrixZigZag(inputMatrix);
    }
}

Python

def print_matrix_zigzag(matrix):
    row1 = 0
    col1 = 0
    row2 = 0
    col2 = 0
    end_row = len(matrix) - 1
    end_col = len(matrix[0]) - 1
    from_up = False
    result = []

    while row1 <= end_row:
        result.extend(get_diagonal(matrix, row1, col1, row2, col2, from_up))
        row1 = row1 + 1 if col1 == end_col else row1
        col1 = col1 if col1 == end_col else col1 + 1
        col2 = col2 + 1 if row2 == end_row else col2
        row2 = row2 if row2 == end_row else row2 + 1
        from_up = not from_up

    print(result)


def get_diagonal(m, row1, col1, row2, col2, from_up):
    tmp_result = []
    if from_up:
        for i in range(row1, row2 + 1):
            tmp_result.append(m[i][col1])
            col1 -= 1
    else:
        for i in range(row2, row1 - 1, -1):
            tmp_result.append(m[i][col2])
            col2 += 1

    return tmp_result


if __name__ == '__main__':
    input_matrix = [
        [1, 2,  3,  4],
        [5, 6,  7,  8],
        [9, 10, 11, 12]
    ]

    print_matrix_zigzag(input_matrix)

顺时针打印矩阵

Posted on 2020-02-14 Edited on 2022-07-20

题目: LeetCode # 29

LeetCode # 54 类似

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:

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

输出:

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

示例 2:

输入:

[
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10,11,12]
]

输出:

1	[1,2,3,4,8,12,11,10,9,5,6,7]

方法一：模拟坐标移动

取左上角和右下角两个位置, 分别移动

(r1  , c1) (r1, c1+1) ··· (r1  , c2)
   ···                    (r1+1, c2)
(r2-1, c1)                    ···
(r2  , c1) ··· (r2, c2-1) (r2  , c2)

Java

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int row1 = 0, col1 = 0;
        int row2 = matrix.length - 1, col2 = matrix[0].length - 1;

        while (row1 <= row2 && col1 <= col2)
            result.addAll(getEdge(matrix, row1++, col1++, row2--, col2--));

        return result;
    }

    public List<Integer> getEdge(int[][] m, int row1, int col1, int row2, int col2) {
        List<Integer> tmpResult = new ArrayList<>();

        if (row1 == row2) {
            for (int i = col1; i <= col2; i++)
                tmpResult.add(m[row1][i]);
            return tmpResult;
        }

        if (col1 == col2) {
            for (int i = row1; i <= row2; i++)
                tmpResult.add(m[i][col1]);
            return tmpResult;
        }

        int curR = row1;
        int curC = col1;
        while (curC != col2) tmpResult.add(m[row1][curC++]);
        while (curR != row2) tmpResult.add(m[curR++][col2]);
        while (curC != col1) tmpResult.add(m[row2][curC--]);
        while (curR != row1) tmpResult.add(m[curR--][col1]);

        return tmpResult;
    }
}

Python

class Solution:
    def spiralOrder(self, matrix: list) -> list:
        result = []
        if not matrix or len(matrix) == 0: return result
        row1, col1 = 0, 0
        row2, col2 = len(matrix) - 1, len(matrix[0]) - 1

        def get_edge(matrix: list) -> list:
            if row1 == row2:
                for i in range(col1, col2 + 1):
                    result.append(matrix[row1][i])
                return

            if col1 == col2:
                for i in range(row1, row2 + 1):
                    result.append(matrix[i][col1])
                return

            for i in range(col1, col2): result.append(matrix[row1][i])
            for i in range(row1, row2): result.append(matrix[i][col2])
            for i in range(col2, col1, -1): result.append(matrix[row2][i])
            for i in range(row2, row1, -1): result.append(matrix[i][col1])

        while (row1 <= row2 and col1 <= col2):
            get_edge(matrix)
            row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 - 1, col2 - 1

        return result

Go

func spiralOrder(matrix [][]int) []int {
    var result []int
    if matrix == nil || len(matrix) == 0 {
        return result
    }
    row1, col1 := 0, 0
    row2, col2 := len(matrix) - 1, len(matrix[0]) - 1

    for row1 <= row2 && col1 <= col2 {
        result = append(result, getEdge(matrix, row1, col1, row2, col2)...)
        row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 - 1, col2 - 1
    }

    return result
}

func getEdge(m [][]int, row1, col1, row2, col2 int) []int {
    var tmpResult []int
    if row1 == row2 {
        for i := col1; i <= col2; i++ {
            tmpResult = append(tmpResult, m[row1][i])
        }
        return tmpResult
    }
    if col1 == col2 {
        for i := row1; i <= row2; i++ {
            tmpResult = append(tmpResult, m[i][col1])
        }
        return tmpResult
    }

    for i := col1; i < col2; i++ {
        tmpResult = append(tmpResult, m[row1][i])
    }
    for i := row1; i < row2; i++ {
        tmpResult = append(tmpResult, m[i][col2])
    }
    for i := col2; i > col1; i-- {
        tmpResult = append(tmpResult, m[row2][i])
    }
    for i := row2; i > row1; i-- {
        tmpResult = append(tmpResult, m[i][col1])
    }

    return tmpResult
}

方法二：移动边界法

使用四个变量分别记录四个方向上的边界，每遍历完一条边则边界向中心移动一个单位。

Java

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int l = 0, r = matrix[0].length - 1;
        int t = 0, b = matrix.length - 1;

        while (l <= r && t <= b) {
            for (int i = l; i <= r; i++) result.add(matrix[t][i]);
            t++;
            for (int i = t; i <= b; i++) result.add(matrix[i][r]);
            r--;
            for (int i = r; i >= l && t <= b; i--) result.add(matrix[b][i]);
            b--;
            for (int i = b; i >= t && l <= r; i--) result.add(matrix[i][l]);
            l++;
        }

        return result;
    }
}

Python

class Solution:
    def spiralOrder(self, matrix: list) -> list:
        result = []
        if not matrix or len(matrix) == 0: return result
        l, r, t, b = 0, len(matrix[0]) - 1, 0, len(matrix) - 1

        while l <= r and t <= b:
            for i in range(l, r + 1): result.append(matrix[t][i])
            t += 1
            for i in range(t, b + 1): result.append(matrix[i][r])
            r -= 1
            if (l <= r and t <= b):
                for i in range(r, l - 1, -1): result.append(matrix[b][i])
                b -= 1
                for i in range(b, t - 1, -1): result.append(matrix[i][l])
                l += 1

        return result

利用 zip 函数：

class Solution:
    def spiralOrder(self, matrix: list) -> list:
        res = []
        while matrix:
            res.extend(matrix[0])
            matrix[:] = list(zip(*matrix[1:]))[::-1]
        
        return res

Go

func spiralOrder(matrix [][]int) []int {
    var result []int
    if matrix == nil || len(matrix) == 0 { return result }

    l, r, t, b := 0, len(matrix[0]) - 1, 0, len(matrix) - 1

    for l <= r && t <= b {
        for i := l; i <= r; i++ { result = append(result, matrix[t][i]) }
        t++
        for i := t; i <= b; i++ { result = append(result, matrix[i][r]) }
        r--
        for i := r; i >= l && t <= b; i-- { result = append(result, matrix[b][i]) }
        b--
        for i := b; i >= t && l <= r; i-- { result = append(result, matrix[i][l]) }
        l++
    }

    return result
}

用栈实现队列

Posted on 2020-02-12 Edited on 2022-07-20

人类迷惑行为 x 2

创建两个栈 push 和 pop , 入队数据只进入 push , 出队只从 pop 出. 通过将 push 栈中的数据倒入 pop 栈中实现队列功能, 倒数据的过程中需满足两个条件:

从push 栈倒入 pop 栈之前, pop 栈必须为空
push 栈中的数据一次性倒完

import java.util.Stack;

public class StackQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public StackQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    public void push(int newEle) {
        stackTransfer(popStack, pushStack);
        pushStack.push(newEle);
    }

    public int poll() {
        stackTransfer(pushStack, popStack);
        if (popStack.isEmpty())
            throw new RuntimeException("Queue is empty");
        return popStack.pop();
    }

    public int peek() {
        stackTransfer(pushStack, popStack);
        if (popStack.isEmpty())
            throw new RuntimeException("Queue is empty");
        return popStack.peek();
    }

    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }


    public void stackTransfer(Stack stack1, Stack stack2) {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }
}

例题: LeetCode #232

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

Java

class MyQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    /** Initialize your data structure here. */
    public MyQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stackTransfer(popStack, pushStack);
        pushStack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        stackTransfer(pushStack, popStack);
        if (popStack.isEmpty())
            throw new RuntimeException("Queue is empty");
        return popStack.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        stackTransfer(pushStack, popStack);
        if (popStack.isEmpty())
            throw new RuntimeException("Queue is empty");
        return popStack.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }

    /** Put elements from stack1 into stack2. */
    public void stackTransfer(Stack stack1, Stack stack2) {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }
}

Python

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.push_stack = []
        self.pop_stack = []

    def push(self, x):
        """
        Push element x to the back of queue.
        """
        self.stack_transfer(self.pop_stack, self.push_stack)
        self.push_stack.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        """
        self.stack_transfer(self.push_stack, self.pop_stack)
        if len(self.pop_stack) == 0:
            return None
        return self.pop_stack.pop()

    def peek(self):
        """
        Get the front element.
        """
        self.stack_transfer(self.push_stack, self.pop_stack)
        if len(self.pop_stack) == 0:
            return None
        return self.pop_stack[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        """
        return len(self.push_stack) == 0 and len(self.pop_stack) == 0

    def stack_transfer(self, stack1, stack2):
        """
        Put elements from stack1 into stack2.
        """
        if len(stack2) == 0:
            while len(stack1) != 0:
                stack2.append(stack1.pop())

用队列实现栈

Posted on 2020-02-11 Edited on 2022-07-20

人类迷惑行为 x 1

queue 只保存队列的最后一个元素, 每次 top 或 pop 操作均需将 queue 中元素除队列最后一个元素外的所有元素倒入 help 中, queue 中最后一个元素再出队列, 以此模拟出栈操作.

import java.util.LinkedList;
import java.util.Queue;

public class QueueStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    public QueueStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    public void push(int newEle) {
        queue.add(newEle);
    }

    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        swap();
        return result;
    }

    public int peek() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        help.add(result);
        swap();
        return result;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    private void swap() {
        Queue tmp = queue;
        queue = help;
        help = tmp;
    }
}

例题: LeetCode #225

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

注意:

你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

Java

class MyStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        queue.add(x);
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        swap();
        return result;
    }

    /**
     * Get the top element.
     */
    public int top() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        help.add(result);
        swap();
        return result;
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue.isEmpty();
    }

    private void swap() {
        Queue tmp = queue;
        queue = help;
        help = tmp;
    }
}

Python

class MyStack():
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        self.help_queue = []

    def push(self, x):
        """
        Push element x onto stack.
        """
        self.queue.insert(0, x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        """
        if len(self.queue) == 0:
            return None

        while len(self.queue) != 1:
            self.help_queue.insert(0, self.queue.pop())

        result = self.queue.pop()
        self.queue, self.help_queue = self.help_queue, self.queue
        return result

    def top(self):
        """
        Get the top element.
        """
        if len(self.queue) == 0:
            return None

        while len(self.queue) != 1:
            self.help_queue.insert(0, self.queue.pop())

        result = self.queue.pop()
        self.help_queue.insert(0, result)
        self.queue, self.help_queue = self.help_queue, self.queue
        return result

    def empty(self):
        """
        Returns whether the stack is empty.
        """
        return len(self.queue) == 0

题目

解法一

Java

Python

解法二

Java

Python

例题 LeetCode # 141

要求：

Java

Python

题目 LeetCode # 138

题解

方法一: 使用 HashMap

Java

Python

方法二: 复制结点

Java

Python

题目

要求

题解

例题: LeetCode # 86

Java

Python

题目 LeetCode # 234

要求

题解

Java

Python

题目 LeetCode # 876

题解

Java

Python

题目

要求

题解

例题: LeetCode # 74

Java

Python

题目

要求

题解

Java

Python

题目: LeetCode # 29

方法一：模拟坐标移动

Java

Python

Go

方法二：移动边界法

Java

Python

Go

例题: LeetCode #232

Java

Python

例题: LeetCode #225

Java

Python

方法一: 使用 `HashMap`