ARTS - Week 12

ARTS - Week 12

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 142 - Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null

Difficulty: Medium

linked list ii

Solution

使用快慢两个指针

解决过程分为两个部分

1.判断链表是否有环,方法同ARTS - Week 11
2.找出环开始的节点

下图中各项标记意义如下:

  • E - 环开始的节点
  • H - 链表 head 到 E 的距离
  • X - slow 和 fast 指针汇合的节点
  • D - E 到 X 的距离
  • L - 环的长度

cycle

slow 指针每次前进一格,fast 指针每次前进两格。当 slow 和 fast 指针汇合时,slow 前进的距离为 H + D,此时,fast 前进的距离为2H + 2D

2H + 2D = H + D + nL(fast 已经绕了 n 圈) -> H = nL - D

此时,从起点 head 新开一个 slow2 指针,每次前进一格,当 slow 和 slow2 汇合时,必为 E 节点。

# Python

class Solution(object):
    def detectCycle(self, head):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow

        return None

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 100.00 % of python3 submissions.
Memory Usage: 16.9 MB
Your memory usage beats 96.19 % of python submissions.

LeetCode Problems 25 - Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

Difficulty: Hard

reverse nodes

Solution

第一种解法

将链表每次以 k + 1 个节点循环反转。
1>2>3>4>5>6>7(k=3) -> 3>2>1>4>5>6>7 -> 3>2>1>6>5>4>7

# Python

class Solution(object):
    def reverseKGroup(self, head, k):
        mark = connect = ListNode(0)
        mark.next = l = r = head

        while True:
            count = 0

            while r and count < k:
                r = r.next
                count += 1

            if count == k:
                prev, cur = r, l
                for _ in range(k):
                    cur.next, cur, prev = prev, cur.next, cur
                connect.next, connect, l = prev, l, r
            else:
                return mark.next

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 36 ms.
Your runtime beats 99.53 % of python3 submissions.
Memory Usage: 12.4 MB
Your memory usage beats 79.43 % of python submissions.

第二种解法:递归
# Python

class Solution(object):
    def reverseKGroup(self, head, k):
        cur, count = head, 0

        while cur and count < k:
            cur = cur.next
            count += 1

        if count == k:
            cur = self.reverseKGroup(cur, k)

            for _ in range(k):
                head.next, cur, head = cur, head, head.next

            head = cur
        return head

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 36 ms.
Your runtime beats 99.53 % of python3 submissions.
Memory Usage: 12.6 MB
Your memory usage beats 29.79 % of python submissions.


Review

Nested Queries with SQLAlchemy ORM - by Miguel Grinberg

我们想按照一定排序规则排列订单记录。
先以订单时间倒序排列,接着按照用户分组订单时间倒序进行排列。如下图:

table

解决方法分为以下几步:

  • 对 Order 表按照用户 id 进行分组(group),再以订单时间倒序排列,生成 subquery
  • Order 表 join 上面生成的 subquery,制定排序规则

SQL 语句如下:

SELECT * FROM orders JOIN (
  SELECT customer_id, max(order_date) AS last_order_date FROM order GROUP BY customer_id
) AS last_orders
ON orders.customer_id = last_orders.customer_id
ORDER BY last_order_date DESC, orders.order_date DESC

对应的 SQLAlchemy 代码如下:

last_orders = db.session.query(
    Order.customer_id, db.func.max(Order.order_date).label('last_order_date')
).group_by(Order.customer_id).subquery()
query = Order.query.join(
    last_orders, Order.customer_id == last_orders.c.customer_id
).order_by(last_orders.c.last_order_date.desc(), Order.order_date.desc())

# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×