ARTS - Week 3

ARTS - Week 3

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

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

Algorithm

LeetCode Problems 15 - 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Difficulty: Medium

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
 [-1, 0, 1],
 [-1, -1, 2]
] 

Solution

第一种解法:暴力循环(三层嵌套循环)

解法跟 two_sum 中的暴力循环解法类似,这里就不列出代码了。

复杂度

  • Time complexity: O(N3);
  • Space complexity: O(1);
第二种解法:使用 Set 结构

使用两层嵌套循环,用 Set 结构去储存最后一个值。

# Python

class Solution:
    def threeSum(self, nums):
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))

        return list(res)
# Ruby

require 'set'

def three_sum(nums)
  return [] if nums.length < 3
  nums.sort!
  res = []

  for i in (0...(nums.length - 2))
    next if i >= 1 && nums[i] == nums[i - 1]

    set = Set.new
    for j in ((i + 1)...nums.length)
      if !set.include?(nums[j])
        set << (0 - (nums[i] + nums[j]))
      else
        res.push([nums[i], (0 - (nums[i] + nums[j])), nums[j]])
      end
    end
  end

  return res.uniq
end

复杂度

  • Time complexity: O(N2);
  • Space complexity: O(n);

运行结果

Python:
Runtime: 928 ms.
Your runtime beats 78.14 % of python3 submissions.

Ruby:
Runtime: 1644 ms.
Your runtime beats 5.42 % of ruby submissions..

第三种解法:数组双向收缩

数组排序后,循环一层,比当前循环元素大的所有元素进行收缩循环。

# Python

class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0: l += 1
                elif s > 0: r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1

        return res
# Ruby

def three_sum(nums)
  return [] if nums.length < 3
  nums.sort!
  res = []

  for i in (0...(nums.length - 2))
    next if i >= 1 && nums[i] == nums[i - 1]

    l , k = i + 1, nums.length - 1
    while l < k
      sums = nums[i] + nums[l] + nums[k]

      if sums < 0
        l += 1
      elsif sums > 0
        k -= 1
      else
        res.push([nums[i], nums[l], nums[k]])
        l += 1 while l < k && nums[l] == nums[l + 1]
        k -= 1 while l < k && nums[k] == nums[k - 1]
        l += 1
        k -= 1
      end
    end
  end

  return res.uniq
end

复杂度

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

运行结果

Python:
Runtime: 880 ms.
Your runtime beats 83.99 % of python3 submissions.

Ruby:
Runtime: 444 ms.
Your runtime beats 77.11 % of ruby submissions.

LeetCode Problems 98 - Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Difficulty: Medium
Example 1:

Input:
   2
  / \
 1   3
Output: true

Example 2:

   5
  / \
 1   4
    / \
   3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value is 5 but its right child's value is 4.

Solution

将二叉树中序排列,并与所有节点去重排序后进行比较。

# Python

class Solution:
    def isValidBST(self, root):
        inOrder = self.inorder(root)
        return inOrder == list(sorted(set(inOrder)))

    def inorder(self, root):
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)
# Ruby

def is_valid_bst(root)
  in_order = sort_in_order(root)
  return in_order == in_order.uniq.sort
end

def sort_in_order(root)
  return [] if root.nil?

  sort_in_order(root.left) + [root.val] + sort_in_order(root.right)
end

复杂度

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

运行结果

Python:
Runtime: 60 ms.
Your runtime beats 52.13 % of python3 submissions.

Ruby:
Runtime: 68 ms.
Your runtime beats 35.59 % of ruby submissions.

# ARTS 

评论

Your browser is out-of-date!

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

×