ARTS - Week 11

ARTS - Week 11

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

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

Algorithm

LeetCode Problems 141 - Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Difficulty: Easy

Example:

Linked List Cycle

Solution

第一种解法:使用 set 结构

使用 set 结构保存已遍历过的节点信息,当遍历到的节点已存在于 set 中时,代表是循环链表

# Python

class Solution(object):
    def hasCycle(self, head):
        seen_nodes = set()
        node = head
        while node:
            if node in seen_nodes:
                return True
            seen_nodes.add(node)
            node = node.next

        return False
# Ruby
def has_cycle?(head)
  seen_nodes = Set.new

  while !head.nil?
    if seen_nodes.include?(head)
      return true
    else
      seen_nodes << head
    end
    head = head.next
  end

  return false
end

复杂度

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

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 100.00 % of python3 submissions.
Your memory usage beats 10.64 % of python submissions.

第二种解法:使用快慢两个指针

每次遍历时,快指针前进2格,慢指针前进1格。当快指针和慢指针相遇时,为循环链表,否则为非循环链表

# Python

class Solution(object):
    def hasCycle(self, head):
        slower, faster = head, head

        while slower and faster and faster.next:
            slower, faster = slower.next, faster.next.next
            if slower == faster:
                return True

        return False
# Ruby
def has_cycle?(head)
  slower, faster = head, head

  while !slower.nil? && !faster.nil? && !faster.next.nil?
    slower = slower.next
    faster = faster.next.next

    return true if slower == faster
  end

  return false
end

复杂度

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

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 100.00 % of python3 submissions.
Your memory usage beats 45.46 % of python3 submissions.


Review

AN INTEGER FORMULA FOR FIBONACCI NUMBERS

本文讨论斐波那契数列的各种方法和逐步优化的思路。其中共包括以下几种方式:

  • 递归法:使用递归法代码简洁,也很形象的定义了斐波那契数列。但是时间复杂度为O(2n);
  • 正推法:维护一个新的数组,使用一个 for 循环求解。时间复杂度为O(N);
  • 通项公式:通过通项公式,本质上转换为an。再次通过减治法求得an,这个过程的时间复杂度为O(logn);
  • 矩阵法:通过二维矩阵转换为求an,时间复杂度为O(logn)。

# ARTS 

评论

Your browser is out-of-date!

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

×